Graph Traversals: Generic Implementation

Recently I had to go back and dive deep into the fundamental elements involved in graph traversal algorithms; specifically, I wanted to get refreshingly clear in my head the essence of these and related techniques. I found that the approach taken in the book I always recommend was right on target to allow me to reach my objective. The approach Prof. Skiena proposes is captured somewhat in the implementation we describe in this and the next two posts in this series.

Base Classes

All graph traversals share a certain "philosophy", in the sense that they are trying to achieve a goal (traverse the graph), and to do so they maintain some state (e.g. discovered, time, ...) and use some appropriate data structure explicitly (queue) or implicitly (stack). The idea is then to abstract those commonalities as much as possible and provide "entry" points to the implementation by means of an API (function/method calls), which enable the tailoring of a generic implementation to the solution specific to a given problem.


Two base classes may be defined, actually one base class and an interface for the entry points API:

• GraphTraversal: Base container for the main state elements and the pointer to the TraversalProcedures class. The Graph class was described in our previous post. The state is captured by arrays, keeping track of when vertices are discovered, and processed, and which vertex is the parent of which vertex. This class also keeps a handle to the given interface implementation of the traversal procedures (proc).
  

  
  package com.medina.toolbox.graphs;
  
  public class GraphTraversal {
  
   public Graph g;
   public TraversalProcedures proc;
   public boolean[] processed;
   public boolean[] discovered;
   public int[] parent;
   
   /* Allow for early termination */
   public boolean finished = false;
   
   public GraphTraversal(Graph g, TraversalProcedures proc) {
    
    this.g = g;
    this.proc = proc;
    this.processed = new boolean[g.getNumVertices()];
    this.discovered = new boolean[g.getNumVertices()];
    this.parent = new int[g.getNumVertices()];
    this.finished = false;
    
    /* Initialize Traversal */
    for (int i = 0; i < g.getNumVertices(); i++) {
     processed[i] = Boolean.FALSE;
     discovered[i] = Boolean.FALSE;
     parent[i] = -1;
    }
      
   } 
  }
  
  

• TraversalProcedures: class hierarchy for entry points API. As we will see in a following post, particular graph implementations can be tailored by adding specific functionality to these API calls.
  

  
  package com.medina.toolbox.graphs;
  
  public interface TraversalProcedures {
   void init(Graph g, GraphTraversal gt);
   boolean processVertexEarly(int v);
   boolean processVertexLate(int v);
   boolean processEdge(int x, int y); 
   void finalize();
  }
  
  

Using this base class and interface let's implement two graph traversal techniques.