/** Specialize DFS to find a cycle in connected component of start vertex. */
public class FindCycleDFS extends DFS {
  protected Sequence cycle; // sequence of edges of the cycle
  protected boolean done;
  protected Vertex cycleStart, target;
  /** @return Iterator of edges of a cycle in the component of start vertex */
  public Object execute(InspectableGraph g, Vertex start, Object info) {
    super.execute(g, start, info);
    cycle = new NodeSequence();
    done = false;
    dfsTraversal(start);
    if (!cycle.isEmpty() && start != cycleStart) {
      PositionIterator pos = cycle.positions();
      while (pos.hasNext()) { // remove the edges from start to cycleStart
	Position p = pos.nextPosition();
	Edge e = (Edge) p.element();
	cycle.remove(p);
	if (g.areIncident(cycleStart, e)) break;
      }
    }
    return new EdgeIteratorAdapter(cycle.elements());
  }
  protected void finishVisit(Vertex v) { 
    if ((!cycle.isEmpty()) && (!done)) cycle.remove(cycle.last());
  }
  protected void traverseDiscovery(Edge e, Vertex from) {
    if (!done) cycle.insertLast(e);
  }
  protected void traverseBack(Edge e, Vertex from) {
    if (!done) {
      cycle.insertLast(e); // back edge e creates a cycle
      cycleStart = G.opposite(from, e);
      done = true;
    }
  }
  protected boolean isDone() {  return done; } 
}