Comparing java implementations of a modified DFS to Kahn's algorithm.

TopologicalSortComparison.java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.Set;

public class TopologicalSortComparison {

	private static final boolean verbose = false;
	private static final int T = 100;
	private static final int I = 100;
	private static final int N = 2000;
	private static final double[] P = { 0.001, 0.003, 0.01, 0.03, 0.1, 0.3 };

	private static Random random = new Random(0);

	private static boolean prob(double p) {
		return random.nextFloat() < p;
	}

	private static class Graph {
		Node[] nodes;

		void reset() {
			for (Node n : nodes) {
				n.reset();
			}
		}

		static Graph generateAcyclic(int n, double p) {
			Graph g = initGraph(n);
			int[] order = randomOrder(n);
			for (int i = 0; i < g.nodes.length; i++) {
				Node u = g.nodes[order[i]];
				List<Node> tmpChildren = new ArrayList<Node>();
				for (int j = i + 1; j < g.nodes.length; j++) {
					Node v = g.nodes[order[j]];
					if (prob(p)) {
						tmpChildren.add(v);
						v.parents.add(u);
						v.parentsBackup.add(u);
					}
				}
				Collections.sort(tmpChildren);
				u.children = new Node[tmpChildren.size()];
				u.children = tmpChildren.toArray(u.children);
			}
			return g;
		}

		static Graph generateSometimes(int n, double p) {
			Graph g = generateAcyclic(n, p);
			for (int i = 0; i < 4; i++) {
				Node n1 = g.nodes[random.nextInt(n)];
				Node n2 = g.nodes[random.nextInt(n)];

				if (n1 != n2) {
					HashSet<Node> n1Children = new HashSet<Node>(Arrays.asList(n1.children));
					n1Children.add(n2);
					n2.parents.add(n1);
					n2.parentsBackup.add(n1);
					n1.children = n1Children.toArray(new Node[n1Children.size()]);
				}
			}
			return g;
		}

		static Graph generateRandom(int n, double p) {
			Graph g = initGraph(n);
			for (Node u : g.nodes) {
				List<Node> tmpChildren = new ArrayList<Node>();
				for (Node v : g.nodes) {
					if (prob(p)) {
						tmpChildren.add(v);
						v.parents.add(u);
						v.parentsBackup.add(u);
					}
				}
				u.children = new Node[tmpChildren.size()];
				u.children = tmpChildren.toArray(u.children);
			}
			return g;
		}

		private static Graph initGraph(int n) {
			Graph g = new Graph();
			g.nodes = new Node[n];
			for (int i = 0; i < n; i++) {
				Node node = new Node();
				node.val = i;
				node.parents = new HashSet<Node>();
				node.parentsBackup = new HashSet<Node>();
				g.nodes[i] = node;
			}
			return g;
		}

		// Uses the Fisher-Yates shuffle to generate
		// a sequence of integers 0 to n - 1 in a 
		// uniformly random order.
		private static int[] randomOrder(int n) {
			int[] order = new int[n];
			for (int i = 0; i < n; i++) {
				order[i] = i;
			}
			for (int i = n - 1; i > 0; i--) {
				int j = random.nextInt(i + 1);
				int tmp = order[i];
				order[i] = order[j];
				order[j] = tmp;
			}
			return order;
		}
	}

	private static class Node implements Comparable<Node> {
		int val;
		Node[] children;

		HashSet<Node> parents;
		HashSet<Node> parentsBackup;

		boolean visited;
		boolean inStack;

		@Override
		public int compareTo(Node other) {
			return this.val - other.val;
		}

		void reset() {
			parents = new HashSet<Node>(parentsBackup);
			visited = false;
			inStack = false;
		}
	}

	private static class Sort {

		List<Node> topologicalSortDFS(Graph g) {
			LinkedList<Node> sortedNodes = new LinkedList<Node>();

			for (Node n : g.nodes) {
				if (!n.visited) {
					boolean acyclic = visit(sortedNodes, n);
					if (!acyclic) return null;
				}
			}
			return sortedNodes;
		}

		private boolean visit(LinkedList<Node> sortedNodes, Node n) {
			if (n.inStack) return false;

			n.inStack = true;
			//System.out.format("Visiting %d.\n", n.val);
			for (Node m : n.children) {
				if (!m.visited) {
					boolean acyclic = visit(sortedNodes, m);
					if (!acyclic) return false;
				}
			}
			//System.out.format("Leaving %d.\n", n.val);
			n.visited = true;
			n.inStack = false;
			sortedNodes.addFirst(n);
			return true;
		}

		List<Node> topologicalSortKahn(Graph g) {
			List<Node> sortedNodes = new LinkedList<Node>();
			Queue<Node> freeNodes = getFreeNodes(g);

			while (freeNodes.size() > 0) {
				Node n = freeNodes.remove();
				//System.out.format("Adding %d.\n", n.val);
				sortedNodes.add(n);
				removeEdges(freeNodes, n);
			}

			if (sortedNodes.size() != g.nodes.length) return null; 

			return sortedNodes;
		}

		private void removeEdges(Queue<Node> freeNodes, Node parent) {
			for (Node child : parent.children) {
				child.parents.remove(parent);
				if (child.parents.isEmpty()) {
					freeNodes.add(child);
				}
			}
		}

		private Queue<Node> getFreeNodes(Graph g) {
			Queue<Node> freeNodes = new LinkedList<Node>();
			for (Node n : g.nodes) {
				if (n.parents.isEmpty()) {
					freeNodes.add(n);
				}
			}
			return freeNodes;
		}
	}

	public static void main(String[] args) {
		Sort s = new Sort();

		for (double p : P) {
			double tDFS = 0;
			double fDFS = 0;
			double tKahn = 0;
			double fKahn = 0;
			int cf = 0;

			for (int t = 0; t < T; t++) {
				Graph g = Graph.generateRandom(N, p);

				long totalTrueDFS = 0;
				long totalFalseDFS = 0;
				long totalTrueKahn = 0;
				long totalFalseKahn = 0;
				Boolean acyclic = null;

				for (int i = 0; i < I; i++) {
					if (prob(0.5)) {
						long start = System.nanoTime();
						List<Node> dfsSort = s.topologicalSortDFS(g);
						boolean dfs = dfsSort != null;
						long mid = System.nanoTime();
						List<Node> kahnSort = s.topologicalSortKahn(g);
						boolean kahn = kahnSort != null;
						long end = System.nanoTime();
						if (dfs != kahn || acyclic != null && !acyclic.equals(dfs)) {
							System.out.println("Output different!");
							return;
						}
						if (acyclic == null) {
							acyclic = dfs;
						}
						if (dfs) {
							totalTrueDFS += mid - start;
							totalTrueKahn += end - mid;
						} else {
							totalFalseDFS += mid - start;
							totalFalseKahn += end - mid;
						}
					} else {
						long start = System.nanoTime();
						List<Node> kahnSort = s.topologicalSortKahn(g);
						boolean kahn = kahnSort != null;
						long mid = System.nanoTime();
						List<Node> dfsSort = s.topologicalSortDFS(g);
						boolean dfs = dfsSort != null;
						long end = System.nanoTime();
						if (dfs != kahn || acyclic != null && !acyclic.equals(dfs)) {
							System.out.println("Output different!");
							return;
						}
						if (acyclic == null) {
							acyclic = dfs;
						}
						if (dfs) {
							totalTrueDFS += end - mid;
							totalTrueKahn += mid - start;
						} else {
							totalFalseDFS += end - mid;
							totalFalseKahn += mid - start;
						}
					}
					g.reset();
				}

				double avgTrueDFS = (double)totalTrueDFS / I;
				double avgFalseDFS = (double)totalFalseDFS / I;
				double avgTrueKahn = (double)totalTrueKahn / I;
				double avgFalseKahn = (double)totalFalseKahn / I;

				tDFS += avgTrueDFS;
				fDFS += avgFalseDFS;
				tKahn += avgTrueKahn;
				fKahn += avgFalseKahn;

				cf += acyclic ? 0 : 1;

				if (verbose) {
					System.out.format("Graph %d:\n", t + 1);
					System.out.format("DFS:  true: %.1f, false: %.1f\n", avgTrueDFS, avgFalseDFS);
					System.out.format("Kahn: true: %.1f, false: %.1f\n", avgTrueKahn, avgFalseKahn);
				}
			}
			tDFS /= T;
			fDFS /= T;
			tKahn /= T;
			fKahn /= T;

			System.out.format("p = %.3f\n", p);
			System.out.format("DFS:  true: %.1f, false: %.1f\n", tDFS, fDFS);
			System.out.format("Kahn: true: %.1f, false: %.1f\n", tKahn, fKahn);
			System.out.format("  %d out of %d cyclic\n", cf, T);
			System.out.format("Ratio: %.10f, %.10f\n", tDFS / tKahn, fDFS / fKahn);
		}
	}
}