0

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
  • 10,264
  • 13
  • 101
  • 209
Theorem
  • 105
  • 4
  • 1
    [Here](https://stackoverflow.com/q/30328433/772868) is the fix. – false Jun 20 '19 at 19:28
  • @false The solution given in there also does not terminate and recurses forever. – Theorem Jun 20 '19 at 19:40
  • How did you call it? – false Jun 20 '19 at 19:42
  • I'm very new to Prolog so I just used the one the OP (you) said path(n,Xs, a,X). – Theorem Jun 20 '19 at 19:51
  • 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 Jun 20 '19 at 20:00
  • Nevermind, I don't think I have enough knowledge yet to understand and apparently use this generic implementation. Too many components I haven't studied yet.. – Theorem Jun 20 '19 at 20:27
  • ??? Just copy-paste it – false Jun 20 '19 at 20:44
  • Possible duplicate of [Define graph in Prolog: edge and path, finding if there is a path between two vertices](https://stackoverflow.com/questions/21161624/define-graph-in-prolog-edge-and-path-finding-if-there-is-a-path-between-two-ve) – Nicholas Carey Jun 24 '19 at 21:30

1 Answers1

2

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 for more on this technique to localize the actual reason for non-termination.

false
  • 10,264
  • 13
  • 101
  • 209
  • First of all, thank you for your answer. I don't really understand the code samples. Why are the predicates re-ordered and why are there falses? – Theorem Jun 20 '19 at 19:54
  • What was re-ordered? I only inserted these **false** goals. – false Jun 20 '19 at 19:58
  • I misread the code, oops! I fail to see how this code is somewhat equivalent to mine. It always terminates after the recursive call to pathaux? – Theorem Jun 20 '19 at 20:06
  • All the goals you added are now behind a **false**. No way these goals can improve termination – false Jun 20 '19 at 20:08
  • Well, now, but in my implementation they weren't there. What I don't understand is how come the program acts as if there was a false there. – Theorem Jun 20 '19 at 20:22
  • By adding **false**, the number of inferences (the steps Prolog performs) is reduced (or stays the same). If now this fragment still loops (= has infinitely many inferences) so does your original program. So both programs do not perform exactly the same steps but they are close enough to draw useful conclusions as in this case that they have essentially the same looping behaviour. – false Jun 20 '19 at 23:02