how can i find all path of node that are connected between : a to g by using rules on Prolog ?
The graph
my simple code:
cites(a,c).
cites(a,c).
cites(b,d).
cites(b,e).
cites(c,f).
cites(e,g).
cites(f,g).
cites(g,d).
cites(h,g).
connected(A,B):-cites(A ,B).
connected(A,B):-cites(A ,C),connected(C ,B).
The first thing you need is a way to generate or test routes. I would do that like this. It will successively find all possible routes via backtracking:
cities(a,b).
cities(a,c).
cities(b,d).
cities(b,e).
cities(c,f).
cities(e,g).
cities(f,g).
cities(g,d).
cities(h,g).
% ------------------------------------------
%
% route( Origin, Destination, Route)
%
% Does Route connect Origin and Destination?
%
%-------------------------------------------
route( A , B , R ) :- % find route R between A and B by...
route( A , B , [A] , P ) , % - invoke the helper, seeding the list of visited nodes with the origin
reverse(R,P) % - and reversing the path to get the route.
. % Easy!
% -----------------------------------------------------------
%
% route( Origin, Destination, Visited, Path )
%
% Finds the path from Origin to Destination, using Visited to
% detect cycles in the graph, building out the final route
% in reverse order.
% -----------------------------------------------------------
route( A , B , Vs , [B|Vs] ) :- % We can get from A to B if...
cities(A,B) , % - A is directly connected to B, and
not_yet_visited(B,Vs) % - we've not yet visited B
. % otherwise...
route( A , B , Vs , Rs ) :- % we can get from A to B if...
cities(A,C) , % - A is connected to some city C, and
not_yet_visited(C,Vs) , % - we've not yet visited C, and
route(C,B,[C|Vs],Rs) % - C is [recursively] connected to B
. % Easy!
%----------------------------------------------------------
%
% not_yet_visited( Node, Visited )
%
% succeeds if Node is not found in Visited; false otherwise
%
%----------------------------------------------------------
not_yet_visited( X , Xs ) :- \+ memberchk(X,Xs) .
Once you have that, then it's a simple matter of using findall/3
, bagof/3
or setof/3
to collect all solutions in a list of lists. Something like:
all_routes( A , B , Rs ) :- findall( route(A,B,R), route(A,B,R), Rs ) .