All simple paths from a vertex to all other reachable nodes

Question

I am completely new to Prolog and was looking into graphs. I found a problem online that asks me to specify a node and then list all simple paths reachable from that node. There is no goal node, just try all possibilities and return all those paths.

I represented the graph as path(X, Y), symbolizing a directed edge from X to Y.

I built this simple knowledge base which is cyclical:

path(a, b).
path(b, c).
path(c, d).
path(d, a).
path(d, e).
path(d, f).
path(f, g).

If I query all_paths(a, P), then P should be(assuming ; is spammed until all options exhausted).

P = [a].
P = [a, b].
P = [a, b, c].
P = [a, b, c, d].
P = [a, b, c, d, e].
P = [a, b, c, d, f].
P = [a, b, c, d, f, g].

I wrote something like that as a starter:

all_paths(Source, P) :- all_paths(Source, P, []).
all_paths(_, [], _).
all_paths(Source, [Source | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Node | Visited]).

Ok, changed it a bit, now I get back:

X = [] ? ;
X = [a] ? ;
X = [a,b] ? ;
X = [a,b,c] ? ;
X = [a,b,c,d] ? ; <- Here it does not pick up e
X = [a,b,c,d] ? ;
X = [a,b,c,d] ? ;
X = [a,b,c,d,f] ? ;

Can someone help in figuring out how to get all paths correctly?

Consider this fix: `all_paths(X, [X|Xs]) :- all_paths(X, Xs, [X]). all_paths(_, [], _). all_paths(Source, [Node | Nodes], Visited) :- path(Source, Node), maplist(dif(Node), Visited), all_paths(Node, Nodes, [Node | Visited]).` — repeat, Oct 16 '15 at 19:03

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

No need to reinvent the wheel!

First, we rename your predicate path/2 to edge/2:

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

Then, we use meta-predicate path/4 in combination with edge/2:

?- 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 = [a,b,c,d,f],   From = a, To = f
; Path = [a,b,c,d,f,g], From = a, To = g
; Path = [b,c],         From = b, To = c
; Path = [b,c,d],       From = b, To = d
; Path = [b,c,d,a],     From = b, To = a
; Path = [b,c,d,e],     From = b, To = e
; Path = [b,c,d,f],     From = b, To = f
; Path = [b,c,d,f,g],   From = b, To = g
; Path = [c,d],         From = c, To = d
; Path = [c,d,a],       From = c, To = a
; Path = [c,d,a,b],     From = c, To = b
; Path = [c,d,e],       From = c, To = e
; Path = [c,d,f],       From = c, To = f
; Path = [c,d,f,g],     From = c, To = g
; Path = [d,a],         From = d, To = a
; Path = [d,a,b],       From = d, To = b
; Path = [d,a,b,c],     From = d, To = c
; Path = [d,e],         From = d, To = e
; Path = [d,f],         From = d, To = f
; Path = [d,f,g],       From = d, To = g
; Path = [f,g],         From = f, To = g
; false.

Edit

If we are only interested in the paths starting at a, we simply write:

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

I might have not made it clear, sorry. I want to use no libraries except member function and also my path must always start from a, i.e. I want all simple paths starting from a to some other nodes. so I don't need paths starting in node b for example. — LogicProgrammer, Oct 16 '15 at 18:46
@Pterodactylus. [tag:transitive-closure] is a very common idiom: use it! — repeat, Oct 16 '15 at 18:52
I appreciate your input but how can I implement this path function myself? I am interested in black box itself and it seems like I am moving towards correct direction but there is something missing in my logic I wrote. — LogicProgrammer, Oct 16 '15 at 18:52
@Pterodactylus. Take a fresh start. Look at the rock-solid implementation of `path/4` (http://stackoverflow.com/q/30328433/4609915). — repeat, Oct 16 '15 at 18:55

CapelliC · Accepted Answer · 2015-10-16T19:18:59.273

'swapping' Node and Source

all_paths(_, [], _).
all_paths(Source, [Node | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Source | Visited]).

yields

?- all_paths(a, P).
P = [] ;
P = [b] ;
P = [b, c] ;
P = [b, c, d] ;
P = [b, c, d, e] ;
P = [b, c, d, f] ;
P = [b, c, d, f, g] ;
false.

it's missing the start node, that I would simply add in the 'driver' predicate:

all_paths(Source, [Source|P]) :- all_paths(Source, P, []).

yields

?- all_paths(a, P).
P = [a] ;
P = [a, b] ;
P = [a, b, c] ;
P = [a, b, c, d] ;
P = [a, b, c, d, e] ;
P = [a, b, c, d, f] ;
P = [a, b, c, d, f, g] ;
false.

a style note: the code is more readable if we follow some rule about IO arguments. Output arguments should go after input ones. Well, this is not always applicable...

That was highly useful. I need to train my eye for such mistakes. You probably saved me hours of inspection. Thanks, upvote and I accept the answer. — LogicProgrammer, Oct 16 '15 at 19:18

All simple paths from a vertex to all other reachable nodes

2 Answers2

Edit