Search code examples
prologtransitive-closure

Prolog, give a path from point x to the goal

This is my code:


% A The first link as a predicate
link(1,2).
link(2,3).
link(3,4).
link(3,6).
link(6,7).
link(6,5).

So what we did with the path predicate is check from a given starting point check if there exists a path from that point to the goal (which is defined at the top). This gives the correct outcome for all possible values.

What I need to do now is, I know there is a valid path from 1 to the goal, my path() predicate told me so, now i need to return a list of nodes that shows the that path to the goal, so with using path(L), path([2,3,6,5]) is true.

Solution

  • If I understand your problem statement, you

    • Have a directed graph (a digraph) defined by link(From,To).
    • Wish to be able to traverse that digraph from some origin node to some destination node and identify the path[s] between the 2 nodes.

    This is a pretty straightforward problem that doesn't require assert/1 or retract/1.

    A common pattern in Prolog programming is the use of helper predicates that carry extra arguments that track the persistent state required to accomplish the task at hand.

    Graph traversal, as an algorithm, is pretty easy (and nicely recursive):

    • You can travel from node A to node B if nodes A and B are directly connected, or
    • You can travel from node A to node B if node A is connected to some other node X such that you can travel from node X to node B.

    The trick here is that you need to track what nodes you've visited (and their order), and you'd want to do that anyway, so that you can detect cycles in the graph. Trying to traverse a cyclic graph like this::

    a → b → c → b

    leads to infinite recursion unless you check to see whether or not you've already visited node b.

    That leads pretty direction to an implementation like this:

    • A traverse/3 predicate, traverse(Origin, Destination,Path), and,
    • A traverse/4 helper predicate, traverse(Origin,Destination,Visited,Path).

    You can fiddle with it at https://swish.swi-prolog.org/p/oZUomEcK.pl

    link(1,2).
link(2,3).
link(3,4).
link(3,6).
link(6,7).
link(6,5).

% ---------------------------------------------------------------------------
%
% traverse( Origin, Destination, ReversePath )
% 
% traverse/3 traverses a directed graph defined by link(From,To).
% The path taken is listed in reverse order:
% [Destination, N3, N2, N1 , Origin]
%
% ---------------------------------------------------------------------------
traverse(A,B,P) :-         % to traverse a graph
  traverse(A,B, [], P)     % - invoke the helper, seeding the visited list with the empty list
  .                        %

% ---------------------------------------------------------------------------
% traverse( Origin, Destination, Visited, ReversePath )
% ---------------------------------------------------------------------------
traverse( A , B , V , [B,A|V] ) :- % Traversal of a graph from A to B,
  link(A,B)                        % - succeeds if there exists an edge between A and B.
  .                                %
traverse( A , B , V , P     ) :-   % otherwise, we can get from A to B if...
  link(A,X) ,                      % - an edge exists between A and some node X
  \+ member(X,V) ,                 % - that we have not yet visited,
  traverse(X,B,[A|V],P)            % - and we can get from X to B (adding A to the list of visited nodes
  .                                %

    Once you have that, invoking traverse/3 with all arguments unbound

    ?- traverse(A,B,P) .

    results in finding all paths in the graph via backtracking.

    If you want to know all the paths in the graph, beginning at a specific origin node, invoke it with the origin argument bound:

    ?- traverse(1,B,P) .

    And if you want to know if two specific nodes are connected, invoke it with both origin and destination bound:

    ?- traverse(1,5,P) .

    Note: because we're building the list of visited nodes by prepending them to the list of visited nodes, the path thus build is in reverse (destination-first) order. If you want the path in proper (origin-first) order, just use reverse/2 in the main predicate:

    traverse(A,B,P) :- traverse(A,B, [], RP ), reverse(RP,P) .