Traversing a graph (with possible loops) and returning the path in Prolog

Question

I'm given a list of arcs:

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

I've written a set of clauses which will tell me if there's a path from node X to node Y. Loops may occur and I've accounted for that.

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

path(X,Y,P) :-
    arc(X,Y).
path(X,Y,P) :-
    \+ member(X,P),
    arc(X,Z),
    append([X],P,L),
    path(Z,Y,L).

I need to modify this to, on success, return a list of nodes that were traversed. I'm unclear as to how I would do this.

I assume my base case would be something like path2(X,Y,[X,Y]) :- arc(X,Y). but that won't work with my program. Is there something wrong with my solution for the previous part, or am I just missing a small modification? Any help would be appreciated. Thanks!

What are you trying to achieve with "path(X,Y,P) :- arc(X,Y)."? (It's a good idea to make sure that all the variables in the head also exist in the body.) — Kaarel, Oct 10 '10 at 19:51
It's the base case. Once we have an arc from the current node (X) to the final node (Y) then we've found a path. P is the list of nodes we've already visited. I understand what you're saying and agree that P doesn't really have a use in that clause (or does it?) but I just don't see where to go from there. — birderic, Oct 10 '10 at 20:04

score 2 · Accepted Answer · answered Oct 10 '10 at 22:23

Close... but consider:

path(Start, End, Path) :-
    path(Start, End, [], Path).

Calling path/3 with a start and end node will construct the path between them, if it exists, and backtrack to give you alternate routes. No nodes are visited twice. The [] is a node accumulator list so we can check we're not going in circles as the path is built.

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    Mid == End, !,
    append(Acc, [Now, End], Path).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

These predicates do the actual work. The first one is the base-case, where the end node is reached via another call to arc/2; in this case, a path has been built. The second one traverses the (directed) graph, but only to nodes that haven't been visited yet.

All paths can be located at once using findall/3 via:

findall(Path, path(Start,End,Path), Paths).

For bound values of Start and End to node atoms.

score 1 · Answer 2 · edited May 23 '17 at 10:34

Move to a higher level and use transitive-closure¹ as the basic idiom!

%        your binary predicate arc/2 gets used here
%         |
%         v
?- path(arc, Path, From, To).
   From = To       , Path = [To]
;  From = a, To = b, Path = [a,b] 
;  From = a, To = c, Path = [a,b,c]
;  From = a, To = d, Path = [a,b,c,d]
;  From = a, To = e, Path = [a,b,c,d,e]
;  From = a, To = f, Path = [a,b,c,d,e,f]
;  From = b, To = c, Path = [b,c]
;  From = b, To = d, Path = [b,c,d]
;  From = b, To = e, Path = [b,c,d,e]
;  From = b, To = f, Path = [b,c,d,e,f]
;  From = c, To = d, Path = [c,d]
;  From = c, To = b, Path = [c,d,b]
;  From = c, To = e, Path = [c,d,e]
;  From = c, To = f, Path = [c,d,e,f]
;  From = d, To = b, Path = [d,b]
;  From = d, To = c, Path = [d,b,c]
;  From = d, To = e, Path = [d,e]
;  From = d, To = f, Path = [d,e,f]
;  From = e, To = f, Path = [e,f]
;  false.

^{Footnote 1: As implemented by the versatile meta-predicate path/4.}

score 0 · Answer 3 · answered Nov 17 '15 at 19:04

The answer given by sharky doesn't seem to work for me, but the following mod does and feels more straightforward to me. :

path(Now, End, Acc, [Now,End]) :-
    arc(Now, End),
    \+ member(Now, Acc),
    \+ member(End, Acc).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

Do tell me if I'm missing something.

Traversing a graph (with possible loops) and returning the path in Prolog

3 Answers3