Prolog - Predicate To Detect Connected Nodes In a Directed Graph

Question

I was looking at this question, in which we make a predicate in Prolog which finds a path between two nodes ("metro stations") in a directed graph. The original code suggested is the following

path(Start, Dest, [[Start,Dest]]) :- connected(Start, Dest).
path(Start, Dest, [[Start, Waypoint]|Path]) :- dif(Dest, Waypoint), 
    connected(Start, Waypoint), path(Waypoint, Dest, Path).

However, in order to deal with loops, and eliminate lists which contain them, I tried along the recursion store the stations in which I stopped already, and to check that I don't repeat any of them. This is the code I came up with (note that I don't make a list of lists, rather a list of the stations themselves)

alldifferent(_,[]).
alldifferent(X,[L|Ls]) :- dif(X,L), alldifferent(X,Ls).

pathaux(Start, Dest, [Start,Dest],Q) :- connected(Start, Dest), alldifferent(Start,Q).
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :- dif(Dest, Waypoint),
    connected(Start, Waypoint), 
    pathaux(Waypoint, Dest, Path, [Start|Q]), alldifferent(Start,Q).

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

However, when I add a rule which creates a loop

connected(ataba,naguib).
connected(naguib,sadat).
connected(sadat,opera).
connected(opera,dokki).
connected(opera,ataba). //Note this one

I get an infinite recursion! how come? and how can one fix this?

@false The solution given in there also does not terminate and recurses forever. — Theorem
I'm very new to Prolog so I just used the one the OP (you) said path(n,Xs, a,X). — Theorem
You need to add your own relation. That is path(connected, Path, X0, X) which terminates that is it produces all possible paths and then terminates by failing — false

false false · Accepted Answer · 2019-06-20T19:41:59

how come?

First, consider the reason for non-termination of your original program:


path(Start, Dest, [[Start,Dest]]) :- false, connected(Start, Dest).
path(Start, Dest, [[Start, Waypoint]|Path]) :-
   dif(Dest, Waypoint), 
   connected(Start, Waypoint),
   path(Waypoint, Dest, Path), false.

This fragment alone is responsible for non-termination. And if this does not terminate, so does your original program.

Now, to your other program. BTW, your definition of alldifferent/2 is commonly written as maplist(dif(X), Xs).


pathaux(Start, Dest, [Start,Dest],Q) :- false, connected(Start, Dest), alldifferent(Start,Q).
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :-
   dif(Dest, Waypoint),
   connected(Start, Waypoint), 
   pathaux(Waypoint, Dest, Path, [Start|Q]), false,
   alldifferent(Start,Q).

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

Do you spot a difference? The list is a bit different, and there is an auxiliary argument, but within the fragment, nobody uses this argument. So it is roughly the same. Thus:

This new definition is just as bad (or worse) than your original program!

The most generic solution is here. See failure-slice for more on this technique to localize the actual reason for non-termination.

Prolog - Predicate To Detect Connected Nodes In a Directed Graph

1 Answers