Find path in graph by backtracking using prolog

Question

I have the following graph:

maniere(v11,h11).
maniere(h11,v12).
maniere(h11,h21).
maniere(v12,v22).
maniere(v22,h13).
maniere(v22,h23).
maniere(h13,v21).
maniere(v22,h23).
maniere(h12,h22).
maniere(h23,v23).
maniere(h33,v23).
maniere(v13,h32).
maniere(v23,h32).

The required output is:

?- traverser(v11, v23).
v11 to h11
h11 to v12 
v12 to v22 
v22 to h13 
h13 to v21 
v22 to h23 
h23 to v23 
true .

I'm having trouble when I don't format the output as requested.

Answer 1

The general rule for traversing a graph is pretty simple:

• The simple/special case:

  We can get from A to B if A and B are directly connected.

• The more general/recursive case:

  We can get from A to B if A is connected to some intermediate node X, and we can then get from X to B.

Correct?

That can be expressed directly in Prolog.

For the sake of argument we will use edge/2 to define our graph, so edge(a,b). is a fact that tell us that we can travel from a to b (but not from b to a — our graph is a directed graph.

traverse(A,B) :- edge(A,B).
traverse(A,B) :- edge(A,X), traverse(X,B).

To get what you need, though, you'll want to track your path through the graph. To do that, you need to use a helper predicate that takes additional arguments to carry state and return results, The other reason for tracking your path through the graph is so that you can detect cycles in the graph — if you wind up back at a node you've already visited, you'll wind up going into an infinite loop (or at least, until the stack overflows). That gets you to this:

traverse(A,B) :-       % we can get from A to B iff...
    traverse(A,B,[A]). % - we invoke the helper, seeding the list of visited nodes with A, the origin node

% ---------------------------------------
% traverse(Origin, Destination, Visited )
% ---------------------------------------
traverse( A , B , _ ) :- % we can get from A to B iff...
    edge(A,B).           % - A and B are directly connected.
traverse( A , B , V ) :- % Otherwise, we can get from A to B iff...
    edge(A,X),           % - An edge exists from A to X, and
    not_visited(X,V),    % - We have not yet visited X, and
    traverse(X,B,[X|V]). % - We can get from X to B

not_visited(N,V) :- % we haven't visited node N... 
    \+ member(N,V). % - if N is not contained in the list of visited nodes (V).

But you need to return the complete path, which is just a matter of adding an additional argument to the helper predicate:

traverse(A,B,P) :-         % we can get from A to B iff...
    traverse(A,B,[A],P). % - we invoke the helper, seeding the list of visited nodes with A, the origin node

% ---------------------------------------
% traverse(Origin, Destination, Visited )
% ---------------------------------------
traverse( A , B , V, [B|V] ) :- % we can get from A to B iff...
    edge(A,B).                  % - A and B are directly connected.
traverse( A , B , V, P     ) :- % Otherwise, we can get from A to B iff...
    edge(A,X),                  % - An edge exists from A to X, and
    not_visited(X,V),           % - We have not yet visited X, and
    traverse(X,B,[X|V],P).      % - We can get from X to B

not_visited(N,V) :- % we haven't visited node N... 
    \+ member(N,V). % - if N is not contained in the list of visited nodes (V).

And then, you need a way to display the path.

You might notice that the path is returned in reverse order. You can use recursion to deal with that:

display_path([]).
display_path([_]).
display_path([To,From|Ns]) :-
  display_path([From|Ns]),
  display_leg(From,To).

display_leg(From,To) :- write(From), write(' --> '), write(To), nl.

But that's a little counter-intuitive. Better to have the helper reverse the list on success:

traverse(A,B,P) :-       % we can get from A to B iff...
    traverse(A,B,[A],P). % - we invoke the helper, seeding the list of visited nodes with A, the origin node

% ---------------------------------------
% traverse(Origin, Destination, Visited )
% ---------------------------------------
traverse( A , B , V, P ) :- % we can get from A to B iff...
    edge(A,B),              % - A and B are directly connected,
    reverse([B|V],P).
traverse( A , B , V, P ) :- % Otherwise, we can get from A to B iff...
    edge(A,X),              % - An edge exists from A to X, and
    not_visited(X,V),       % - We have not yet visited X, and
    traverse(X,B,[X|V],P).  % - We can get from X to B

not_visited(N,V) :- % we haven't visited node N... 
    \+ member(N,V). % - if N is not contained in the list of visited nodes (V).

That makes display_path/1 much more intuitive:

display_path([]).
display_path([_]).
display_path([From,To|Ns]) :-
  display_leg(From,To),
  display_path([To|Ns]).

display_leg(From,To) :-
    write(From),
    write(' --> '),
    write(To),
    nl.

And we can wrap our traverse/3 up with display_path/1:

visit(A,B) :- traverse(A,B,P), display_path(P). 

Wrapping it all up, we get this (you can fiddle with it at https://swish.swi-prolog.org/p/rmEdFAqE.pl):

edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).

visit(A,B) :- traverse(A,B,P), display_path(P). 

traverse(A,B,P) :-       % we can get from A to B iff...
    traverse(A,B,[A],P). % - we invoke the helper, seeding the list of visited nodes with A, the origin node

% ---------------------------------------
% traverse(Origin, Destination, Visited )
% ---------------------------------------
traverse( A , B , V, P ) :- % we can get from A to B iff...
    edge(A,B),              % - A and B are directly connected,
    reverse([B|V],P).
traverse( A , B , V, P ) :- % Otherwise, we can get from A to B iff...
    edge(A,X),              % - An edge exists from A to X, and
    not_visited(X,V),       % - We have not yet visited X, and
    traverse(X,B,[X|V],P).  % - We can get from X to B

not_visited(N,V) :- % we haven't visited node N... 
    \+ member(N,V). % - if N is not contained in the list of visited nodes (V).

display_path([]).
display_path([_]).
display_path([A,B|Ns]) :-
  display_leg(A,B),
  display_path([B|Ns]).

display_leg(From,To) :-
    write(From),
    write(' --> '),
    write(To),
    nl.