How to store the list of visited node in a path on a graph in Prolog

Question

I am studying Prolog and I am finding some difficulty interpreting the slide proposed by my professor.

Starting from the classic program that say if exist a path between two node of a graph, this one:

edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).

path(X,Y) :- edge(X,Y).

path(X,Y) :- path(X,Z),
             edge(Z,Y).

He introduce a new version that use the predicate: path(X,Y,Path) that is TRUE if in the graph exist a path between X and Y and if Path is the list of visited nodes

So he give me the following new version of the previous program:

/* BASE CASE: exist an edge between X and Y, so the Path is
              the couple [X,Y]
*/
path(X,Y,[X,Y]) :- edge(X,Y).

path(X,Y,P) :- path(X,Z,P1),
               edge(Z,Y),
               lastelem(P,Y,P1).

The base case is pretty simple: if exist an edge that connect X and Y it is true that exist a path from X to Y and the list of the visited node is [X,Y]

I have some problems with the second rule: if X and Y are not connect by only a single edge, so that there is a path between X and Y, have to exist a path between X and an other node Z (and P1 is the list of the visited node in this path) an an edge that connect Z to the final node Y.

This is pretty simple...the problem is with the last predicate lastelem/3 that it is not provided in the slide (so I don't know exactly what it do):

lastelem(P,Y,P1).

I think that it generate P inserting Y in P1 or something like it...

Do you have some more precise idea about it and a possible implementation of this predicate?

The base case is actually less simple than it could have been: `path(X, X, [X])`. — Fred Foo, May 01 '13 at 16:52

score 3 · Answer 1 · edited May 23 '17 at 12:31

There's no need to re-invent the wheel by writing recursive code yourself.

Simply define a binary relation edge/2 ...

edge(a,b).
edge(b,c).
edge(a,e).
edge(c,d).
edge(d,e).
edge(f,e).

... and use the meta-predicate path/4!

?- path(edge,Path,From,To).
  Path = [To]       , From = To
; Path = [a,b]      , From = a, To = b 
; Path = [a,b,c]    , From = a, To = c
; Path = [a,b,c,d]  , From = a, To = d
; Path = [a,b,c,d,e], From = a, To = e
; Path = [b,c]      , From = b, To = c
; Path = [b,c,d]    , From = b, To = d
; Path = [b,c,d,e]  , From = b, To = e
; Path = [a,e]      , From = a, To = e
; Path = [c,d]      , From = c, To = d
; Path = [c,d,e]    , From = c, To = e
; Path = [d,e]      , From = d, To = e
; Path = [f,e]      , From = f, To = e 
; false.

score 0 · Answer 2 · answered May 01 '13 at 16:56

0

The professor probably wants to append Y to P:

lastelem(Lst0, X, Lst) :-
    append(Lst0, [X], Lst).

[That's a pretty stupid idea, though, since appending to a list takes linear time. A constant-time solution is to prepend the element:

% I wouldn't actually write a predicate for this, but nevertheless:
lastelem(Lst, X, [X|Lst]).

This gives the path in reverse order, but a single reverse/2 solves that.]

answered May 01 '13 at 16:56

Fred Foo

355,277
75
744
836

The first one don't work: if I launch the query I obtain this error message: [debug] ?- path(a,d, Path). ERROR: Out of local stack Exception: (1,597,352) path(a, _G488, _G489) ? – AndreaNobili May 01 '13 at 17:13
same problem with the second version :-( – AndreaNobili May 01 '13 at 17:14
@AndreaNobili: then the search gets stuck in a cycle. Try it on a graph without cycles. – Fred Foo May 01 '13 at 17:22
it seems to me that this graph (rappresented by the edges of my previous example) have not cycles... – AndreaNobili May 01 '13 at 17:31
yes and the problem seems to be in the lastelem predicate and not in the path predicate that work well... – AndreaNobili May 01 '13 at 17:48
@AndreaNobili: now I see. The recursive clause for `path` should call `edge` before going into recursion. – Fred Foo May 01 '13 at 17:50
mmm, I think that I have solved in this way: lastelem(P, Y, P1) :- append(P1, [Y], P). – AndreaNobili May 01 '13 at 17:51
seems to work well infact with te previous graph I have that: [debug] ?- path(a,d,Path). Path = [a, b, c, d] And it is correct: P is the final Path, P1 is the subpath foun and Y is the element to add...so I have to append Y to P1 to obtain P...I think that this is correct – AndreaNobili May 01 '13 at 17:53

score 0 · Answer 3 · answered May 01 '13 at 17:26

I'd probably do something like:

path(X,Y,Path) :-
  path(X,Y,T) ,
  reverse(T,Path)
  .

path( X , Y , [] ) :- % a path exists between X and Y:
  connected(X,Y)      % - if they are directly connected
  .                   %
path( X , Y , P  ) :- % a path exists between X and Y:
  connected(X,T) ,    % - if X is connected to another node (T)
  T \= Y ,            % - and T is not the destination (Y)
  not visited(T,P) ,  % - and T has not yet been visited
  path(T,Y, [X|P])    % - and a path exists between T and Y
  .                   %

connected(X,Y) :- edge(X,Y) . % two nodes are connected if they are
connected(X,Y) :- edge(Y,X) . % if they are adjacent adjacent.

visited(X,[X|Xs]) :- ! .             % a node is visited
visited(X,[_|Xs]) :- visited(X,Xs) . % if it exists in the list of already-visited nodes

I have to use the posted version because, later, he develop it further adding other features — AndreaNobili, May 01 '13 at 17:27

How to store the list of visited node in a path on a graph in Prolog

3 Answers3