Find all possible paths w/o loops in Graph in Prolog

Question

I got an homework assignment for my logic course, but more or less don't have any clue how to solve it... With a query like

  ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
  r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],Path).

Prolog should return all possible paths in the given graph. The terms r(X,List) define the graph, meaning that the nodes in List can be reached from node X. In this case, the output would be:

Path = [a,b,c] ;
Path = [a,b,e,d] ;
Path = [a,b,e,f,g] ;
Path = [a,d,e,b,c] ;
Path = [a,d,e,f,g] ;
false.

Although I get the hang of the numerous solutions here on SE and on the web in general to similar problems, I'm somehow too dumb to figure out how to work with the definition of the graph in this assignment.

I figure that find(Start,...) should be called recursively with all members of the list in r(Start,List), but as a total newbie to Prolog(we just did the standard family tree stuff...) I don't know how to do that.

Any help would be really appreciated. I'm aware of the fact that I don't have much to start with, but I already spent half a night trying to figure something out and up to now I don't have a clue.

/Edit:

For starters, I think I'll need some kind of base case to abort the recursion. I think it should be either

find([],_,_).

because I guess that the last recursive call wouldn't have anything to start with, or

find(_,[],_).

assuming that the list of the terms defining adjacent nodes should be empty when the program finished processing it.

Now the actual call. Probably something like

find(Start,[r(Start,[Adjacent|Restadj])|Rest],Path):-
           find(???).

My problems here are the following:

-How do I make the program use the members of the list in the r(...) term as the next Start?

-How do I check if a node has already been "visited"/ How can I remove a node from a specific list in r

-How do I put the found nodes into the Path list? Simply append? Or execute the recursive call with something like [Path|Start]?

As you see, it's not much. Some suggestive questions would be nice, since Prolog seems quite interesting and therefore fun to learn...

---

After spending some time with the neat PDT-Eclipse trace tool, I think I understood what the program is doing. What I dont't get at this point is why the last node always gets lost. After backtracking fails, for example because r(c,[b]) is the next found term and memberchk(b,[b]) fails because of the negation(that's what I thing + does) and no other term with r(c,X) can be found, it starts over with looking for other possibilities to go from node b, which has adjacent nodes left in r(b,[...]). But why does the program forget to put node c into the Path list? Is there a possibility to do some kind of if-then-else in case

 member(r(Node, Adjacent), Graph),
member(AdjNode, Adjacent),
\+ memberchk(AdjNode, Seen),

fails, to still append the last node to Path?

Answer 1

I suspect what's tripping you up here is that instead of getting the data out of the database, you're having to find it from within an explicit data structure. A first crack at this might look like this:

find(_, _, []).
find(Node, Graph, [Node|Path]) :-
    member(r(Node,Adjacent), Graph),
    member(AdjNode, Adjacent),
    find(AdjNode, Graph, Path).

See how I'm using member/2 to find data from within the graph. This solution isn't correct though, because it loops. An improvement might be this:

find(Node, Graph, Path) :- find(Node, Graph, Path, []).

find(_, _, [], _).
find(Node, Graph, [Node|Path], Seen) :-
    member(r(Node, Adjacent), Graph),
    member(AdjNode, Adjacent),
    \+ memberchk(AdjNode, Seen),
    find(AdjNode, Graph, Path, [Node|Seen]).

This one is basically the same as the above version except it has a "seen" list to track where it has already been. This still doesn't produce the output you want, but I think it will be enough to get you on the right track.

Edit in response to your edit,

For starters, I think I'll need some kind of base case to abort the recursion.

Yes. I chose your first case because I don't think you can safely "consume" the graph during traversal. I suppose you could use select/3 in lieu of member/2 and pass the graph-without-this-node onward. That might be an interesting thing to try (suggestion!).

• How do I make the program use the members of the list in the r(...) term as the next Start?

As demonstrated, use member/2 to retrieve things from the graph. It's funny, because you used the exact word for the predicate you need. :)

• How do I check if a node has already been "visited"/ How can I remove a node from a specific list in r

As demonstrated in my second set of code, you have another parameter for your auxiliary predicate, and use memberchk/3 or member/3.

• How do I put the found nodes into the Path list? Simply append? Or execute the recursive call with something like [Path|Start]?

I went with the recursive call. append/3 would be more expensive.

Edit: Using findall/3 per Will's comment, we can find all the paths at once:

all_paths(From, Graph, Paths) :- findall(Path, find(From, Graph, Path), Paths).

You can invoke this like so:

?- all_paths(a, [r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
                 r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], AllPaths).

I haven't tested that but it should work.

Answer 2

building on the excellently clear code by Daniel Lyons, a breadth first search:

all_paths(Node, Graph, Paths) :- 
   bfs(Graph, [[Node]-[]], R, []),      % or dfs(...)
   maplist( fst, Paths, R).

fst(A, A-_).        % utility
pair(B, A, A-B).    %  helpers
add(LS,H,[H|LS]).   %   

bfs(_G, [], Z, Z).                % queue is empty
bfs(Graph, [H|Q], [H|R], Z) :- 
    H = Path-Seen, Path = [Node|_],
    findall( Next, member(r(Node, Next), Graph), NS),
    flatten_diff( NS, Seen, WS),  % working set of nodes
    maplist( add(Path), WS, PS),  % new paths
    maplist( pair([Node|Seen]), PS, QH),  % new addition to the queue
    %% append( QH, Q, Q2),        % DFS
    append(    Q, QH, Q2),        % BFS
    bfs(Graph, Q2, R, Z).

(not tested). flatten_diff(A,B,C) should flatten list of lists A, while removing the elements of it that appear also in list B, producing the list C as the result.

---

As PeterPanter has noticed, Daniel Lyons's code needs a little tweaking, to not exclude the very last node in its resulting paths.

find(Node, Graph, [Node|Path]) :- find(Node, Graph, Path, []).

find(_, _, [], _).
find(Node, Graph, [AdjNode|Path], Seen) :-
    member(r(Node, Adjacent), Graph),
    member(AdjNode, Adjacent),
    \+ memberchk(AdjNode, Seen),
    find(AdjNode, Graph, Path, [Node|Seen]).

There are no empty paths produced now, and it works as expected:

11 ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),    r(d,[a,g]), 
              r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], Path).
Path = [a] ;
Path = [a, b] ;
Path = [a, b, c] ;
Path = [a, b, e] ;
Path = [a, b, e, d] ;
Path = [a, b, e, d, g] ;
Path = [a, b, e, d, g, f] ;
Path = [a, b, e, f] ;
Path = [a, b, e, f, g] ;
Path = [a, d] ;
Path = [a, d, g] ;
Path = [a, d, g, f] ;
Path = [a, d, g, f, e] ;
Path = [a, d, g, f, e, b] ;
Path = [a, d, g, f, e, b, c] ;
false.