how to find all connected path from node to another node using prolog?

Question

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

Answer 1

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

Answer 2

Following short and simple code is adapted from here.

cities(1,2).
cities(2,3).
cities(3,4).
cities(3,5).
cities(2,5).
cities(5,6).
cities(2,6).

connected(X,Y,[cities(X,Y)]) :- cities(X,Y).
connected(X,Y,[cities(X,Z)|P]) :- cities(X,Z),connected(Z,Y,P).

Then one can search for paths:

?- connected(1,6,P).
P = [cities(1, 2), cities(2, 6)] ;
P = [cities(1, 2), cities(2, 3), cities(3, 5), cities(5, 6)] ;
P = [cities(1, 2), cities(2, 5), cities(5, 6)] ;