Skip to content

Instantly share code, notes, and snippets.

@avanpo
Created October 11, 2017 20:24
Show Gist options
  • Save avanpo/5b180c648e6173ca3e4a5cf846e93ac7 to your computer and use it in GitHub Desktop.
Save avanpo/5b180c648e6173ca3e4a5cf846e93ac7 to your computer and use it in GitHub Desktop.
Comparing java implementations of a modified DFS to Kahn's algorithm.
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment