prologtransitive-closure

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


how can i find all path of node that are connected between : a to g by using rules on Prolog ?

The graph

1

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

Solution

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