/**
 * 
 */
package com.codemelon.graph.util.search;

import java.util.Iterator;
import java.util.Set;

import com.codemelon.graph.DiGraph;
import com.codemelon.graph.common.Color;
import com.codemelon.graph.util.core.VertexResetter;
import com.codemelon.graph.vertex.Vertex;
/**
 * @author Marshall Farrier
 * @version Nov 26, 2012
 * cf. CLRS, pp. 604ff.
 */
public class DepthFirstSearch {
	private DiGraph graph;
	private int t;	// time in CLRS
	
	public DepthFirstSearch(DiGraph graph) {
		this.graph = graph;
		t = 0;
	}
	
	public void search() {
		new VertexResetter(graph).dfsReset();
		t = 0;
		Iterator<Vertex> it = graph.vertexIterator();
		Vertex u;
		while (it.hasNext()) {
			u = it.next();
			if (u.color == Color.WHITE) {
				visit(u);
			}
		}
	}
	private void visit(Vertex u) {
		t++;
		u.discoveryTime = t;
		u.color = Color.GRAY;
		Set<Vertex> adjacentVertices = u.getAdjacencies();
		for (Vertex v : adjacentVertices) {
			if (v.color == Color.WHITE) {
				v.parent = u;
				visit(v);
			}		
		}
		u.color = Color.BLACK;
		t++;
		u.finishTime = t;
	}
}

@@ -70,24 +70,53 @@
 l.Iterator;%0A
+import java.util.LinkedList;%0A
 import java.
@@ -1094,10 +1094,717 @@
 = t;%0A%09%7D%0A
+%09/**%0A%09 * CLRS, p. 613%0A%09 * @return%0A%09 */%0A%09public LinkedList%3CVertex%3E topologicalSort() %7B%0A%09%09LinkedList%3CVertex%3E result = new LinkedList%3CVertex%3E();%0A%09%09new VertexResetter(graph).dfsReset();%0A%09%09Iterator%3CVertex%3E it = graph.vertexIterator();%0A%09%09Vertex u;%0A%09%09while (it.hasNext()) %7B%0A%09%09%09u = it.next();%0A%09%09%09if (u.color == Color.WHITE) %7B%0A%09%09%09%09topologicalSortVisit(u, result);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return result;%0A%09%7D%0A%09%0A%09private void topologicalSortVisit(Vertex u, LinkedList%3CVertex%3E result) %7B%0A%09%09u.color = Color.GRAY;%0A%09%09Set%3CVertex%3E adjacentVertices = u.getAdjacencies();%0A%09%09for (Vertex v : adjacentVertices) %7B%0A%09%09%09if (v.color == Color.WHITE) %7B%0A%09%09%09%09topologicalSortVisit(v, result);%0A%09%09%09%7D%09%09%0A%09%09%7D%0A%09%09u.color = Color.BLACK;%0A%09%09result.addFirst(u);%09%0A%09%7D%0A
 %7D%0A

Add topological sort to DepthFirstSearch