/** Generic depth first search traversal of a graph using the template
  * method pattern.  A subclass should override various methods to add
  * functionality to this traversal.  */
public abstract class DFS {
  /** The graph being traversed. */
  protected InspectableGraph G;
  /** The result of the traversal. */
  protected Object visitResult;
  /** Perform a depth first search traversal.
    * @param g Input graph.
    * @param start Start vertex of the traversal.
    * @param info Auxiliary information (to be used by subclasses).
    */
  public Object execute(InspectableGraph g, Vertex start, Object info) {
    G = g;
    for (PositionIterator pos = G.positions(); pos.hasNext(); )
      unVisit(pos.nextPosition());
    return null;
  }
  /**
    * Recursive template method for a generic DFS traversal.
    * @param v Start vertex of the traversal.
    */
  protected Object dfsTraversal(Vertex v) {
    initResult();
    startVisit(v);
    visit(v);
    for (EdgeIterator inEdges = G.incidentEdges(v); inEdges.hasNext(); ) {
      Edge nextEdge = inEdges.nextEdge();
      if (!isVisited(nextEdge)) { // found an unexplored edge, explore it
        visit(nextEdge);
        Vertex w = G.opposite(v, nextEdge);
        if (!isVisited(w)) { // w is unexplored, this is a discovery edge
          traverseDiscovery(nextEdge, v);
          if (!isDone())
            visitResult = dfsTraversal(w);
	}
	else // w is explored, this is a back edge
	  traverseBack(nextEdge, v);
      }
    }
    finishVisit(v);
    return result();
  }