CODEWITHSUNDEEP
prologgraph-theorytransitive-closure
LogicProgrammer
LogicProgrammer

Reputation: 77

All simple paths from a vertex to all other reachable nodes

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?

Upvotes: 2

Views: 567

Answers (2)

CapelliC
CapelliC

Reputation: 60034

'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...

Upvotes: 1

repeat
repeat

Reputation: 18726

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 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.

Upvotes: 3

Related Questions