/** This class specializes DFS to find a path between the start vertex
  * and a given target vertex.  */
public class FindPathDFS extends DFS {
  protected List path;
  protected boolean done;
  protected Vertex target;
  /** @param info target vertex of the path 
    * @return {@link Iterator} of the vertices and edges 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(Graph g, Vertex start, Object info) {
    init(g);
    path = new NodeList();
    done = false;
    target = (Vertex) info; // target vertex is stored in info parameter
    dfsTraversal(start);
    return path.elements();
  }
  protected void startVisit(Vertex v) {
    path.insertLast(v); // add vertex v to path
    if (v == target)
      done = true;
  }
  protected void finishVisit(Vertex v) {
    path.remove(path.last());	// remove v from path
    if(!path.isEmpty())		// if v is not the start vertex
      path.remove(path.last());	// remove discovery edge into v from path
  }
  protected void traverseDiscovery(Edge e, Vertex from) {
    path.insertLast(e); // add edge e to the path
  } 
  protected boolean isDone() { return done; }
}