5.3 Paths in a Graph

A directed graph is simple if there is no more than one edge with a given start and end vertices. We define a path in such a graph as a sequence of vertices where each next vertex can be reached by an edge from the preceding one. A path is acyclic if no vertex in it is repeated. We want a function which, given a graph G and a vertex V in it, will list all acyclic paths in G starting from V.

The first decision to make, as always, is the representation of the objects. We shall represent a graph in the format

  s.Vertex(e.List-of-next) ...
where e.List-of-next includes all those vertices which can be reached from s.Vertex by an edge (it may be empty). For instance, the graph in Fig. 5.1 is represented as:

  A()B(A C)C(D E)D(C)E(A B D)
 

 
Figure 5.1 A directed graph

The shortest solution of the problem is:

  Paths {
     eP(e1 sV e2)(e3 sV(e.Next)e4) =
          <Paths eP sV (e.Next)(e3 e4)>
          <Paths eP (e2)(e3 sV(e.Next)e4)>;
     eP(e1)(e2) = (eP);
         }
where the initial call should be:

  <Paths (V)(G)>
 

With the graph in Fig. 5.1 and the initial vertex E , our function results in:

  (E A)(E B A)(E B C D)(E B C)(E B)
  (E D C)(E D)(E)()
 

Let us explain how we came to this solution. As often happens, it is not an original problem but its generalization that admits a straightforward recursive definition. In our case we make two generalizations: first, instead of a single starting vertex V, we consider a list of vertices V^list , asking for the set of paths which can start with any vertex from V^list. Second, we allow an arbitrary prefix P of the paths we compute. Thus

  <Paths P(V ^list)(G)> must yield the set of paths which all start with P, then pick any of the vertices in V^list and travel through the graph G.

The idea of the algorithm is to remove from the graph the records for those vertices which have already appeared in the path. In this way we guarantee that there will be no repeated entries in the paths we construct. In the left side of sentence 1 we see a pattern which finds the first vertex sV for which continuation is still possible because there is a record for it in the graph. Then the set we want will consist of two subsets for which we have written two parallel recursive calls of Paths : in the first we add sV to eP , e.Next becomes V^list, and the record for sV is eliminated; in the second, we look for other vertices in V^listwith the unaltered graph G. When there are no possible continuations, we give out the path P.

From the viewpoint of efficiency, however, this algorithm is faulty, because at each recursive step of Pathsone extra copy of the graph (or what remains of the graph) is made. This is corrected in the following program:

  $ENTRY Go { =
           <Prout 'Type in the graph'>
           <Br 'graph='<Input>>
           <Prout 'Initial vertices, please'>
           <Prout <Paths (<Input>)>>; }
  $EXTRN Input;
   
  Paths {
     ePs1eQ(s1 e2) = <Paths ePs1eQ(e2)>;
     eP(s1 e2) = <Paths ePs1 (<Next s1>)>
                 <Paths eP(e2)>;
     eP() = (eP); }
   
  Next {
     sV, <Dg 'graph'>: e1 sV(eN) e2 = eN
         <Br 'graph=' e1 sV(eN) e2>;  }

The graph is taken from the argument of Pathsand kept buried under 'graph' . Each time we want a continuation for a vertex, we use the function Next , which copies only the pertinent part of the graph definition. We therefore have to check at each recursive step of Path that the candidate vertex does not appear in the path (sentence 1).

Exercise 5.2 You might have noticed that with both versions of Pathsthe empty path is one of the elements of the resulting set. Although this is a natural consequence of our recursive definition, it may be deemed undesirable. Modify the program(s) so as to eliminate the empty path.