/** This class specializes DFS to find a path between the start vertex
  * and a given target vertex.  */
public class FindPathDFS extends DFS {
  protected Sequence path;
  protected boolean done;
  protected Vertex target;
  /** @param info target vertex of the path 
    * @return Iterator of the vertices in a path from the start vertex
    * to the target vertex, or an empty iterator if no such path
    * exists in the graph */
  public Object execute(InspectableGraph g, Vertex start, Object info) {
    super.execute(g, start, info);
    path = new NodeSequence();
    done = false;
    target = (Vertex) info; // target vertex is stored in info parameter
    dfsTraversal(start);
    return new VertexIteratorAdapter(path.elements());
  }
  protected void startVisit(Vertex v) {
    path.insertLast(v); 
    if (v == target)
      done = true;
  }
  protected void finishVisit(Vertex v) {
    if (!done)
      path.remove(path.last());
  }
  protected boolean isDone() {
    return done;
  }
}