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