## 2.15 Graph structures and paths

As an example, consider the following connected graph:

Fig. 2.15

The edges can be represented in Prolog as facts:

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).

To represent the fact that the edges are bi-directional we could either
add eight more 'edge' clauses (edge(2,1),etc.) or we could try a rule like:

(*) edge(X,Y) :- edge(Y,X).

This is not a good idea, however. To see why it is not a good idea,
try the following goal.

?- edge(5,1).

Notice that the rule (*) will be tried over and over in an infinite
loop, so the goal will not terminate. Try it! A better way to handle this
is to use a rule such as the following.

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

Note the use of disjunction ';' in this rule. This rule could have been
written as two rules:

connected(X,Y) :- edge(X,Y).
connected(X,Y) :- edge(Y,X).

We wish to develop a Prolog definition which generates paths between
any two nodes of the graph. More specifically, we require the following
(kind of) behavior for the predicate 'paths'.

?- path(1,5,P).
P = [1,2,5] ;
P = [1,2,3,5] ;
P = [1,2,3,4,5] ;
P = [1,4,5] ;
P = [1,4,3,5] ;
P = [1,4,3,2,5] ;
P = [1,3,5] ;
P = [1,3,4,5] ;
P = [1,3,2,5] ;
no

The paths are represented by the list of nodes through which one must
travel to get from node 1 to node 5. Here is a definition for paths:

path(A,B,Path) :-
travel(A,B,[A],Q),
reverse(Q,Path).
travel(A,B,P,[B|P]) :-
connected(A,B).
travel(A,B,Visited,Path) :-
connected(A,C),
C \== B,
\+member(C,Visited),
travel(C,B,[C|Visited],Path).

A declarative reading for the first clause amounts to "A path from
A to B is obtained if A and B are connected". A declarative reading
for the second clause amounts to "A path from A to B is obtained provided
that A is connected to a node C different from B that is not on the previously
visited part of the path, and one continues finding a path from C to B".
Avoiding repeated nodes ensures that the program will not cycle endlessly.

*Exercise 2.15* Suppose that edges have lengths. How does one calculate
shortest paths between points in Prolog? Hint: One can use
the `setof` goal, discussed in §2.12 and §4.15 ...

shortest(A,B,Path,Length) :-
setof([P,L],path(A,B,P,L),Set),
Set = [_|_], % fail if no path
minimal(Set,[Path,Length]).

Try the exercise (with hint) first before looking at this simplified
solution
.

Prolog Code for this section.

Prolog Tutorial Contents