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 theres 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!

Answer 1

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.