public class FindCycleDFS extends DFS { // find a cycle from a start vertex
  protected List cycle; // sequence of edges of the cycle
  protected boolean done;
  protected Vertex cycleStart;
  public Object execute(Graph g, Vertex start, Object info) {
    init(g);
    cycle = new NodeList();
    done = false;
    dfsTraversal(start);
    // remove the vertices and edges from start to cycleStart
    if (!cycle.isEmpty() && start != cycleStart) {
      Iterator pos = cycle.positions();
      while (pos.hasNext()) {
	Position p = (Position) pos.next();
	cycle.remove(p);                     // remove vertex from cycle
	p = (Position) pos.next();
	Edge e = (Edge) p.element();         // remove edge from cycle
	cycle.remove(p);
	Vertex[] endv = g.endVertices(e);
	if ((endv[0] == cycleStart) || (endv[1] == cycleStart )) break;
      }
    }
    return cycle.elements(); // iterator of the vertices and edges of the cycle 
  }
  protected void startVisit(Vertex v) { cycle.insertLast(v); /* add v to cycle */ }
  protected void finishVisit(Vertex v) {
    cycle.remove(cycle.last());	// remove v from cycle
    if (!cycle.isEmpty()) cycle.remove(cycle.last()); // remove edge into v from cycle
  }
  protected void traverseDiscovery(Edge e, Vertex from) { cycle.insertLast(e); }
  protected void traverseBack(Edge e, Vertex from) {
    cycle.insertLast(e);		// back edge e creates a cycle
    cycleStart = G.opposite(from, e);
    cycle.insertLast(cycleStart);	// first vertex completes the cycle
    done = true;
  }
  protected boolean isDone() {  return done; } 
}