@Test public void testSolveDigraph() { int N = 200; Random r = new Random(); for (int i = 5; i < N; i += r.nextInt(15)) { Digraph digraph = DigraphGenerator.simple(i, r.nextInt(i * (i - 1))); TransitiveClosure tc = new TransitiveClosure(digraph); int test = ReachableVertex.solveDigraph(GraphConverter.convert(digraph)); if (test == -1) { Assert.assertTrue(checkNoThatPoint(tc, i)); } else { Assert.assertTrue(checkThatPoint(tc, test, i)); } } }
public static int solveDigraph(Set<Integer>[] digraph) { int n = digraph.length; Set<Integer>[] rev = reverse(digraph); LinkedList<Integer> postOrder = new LinkedList<>(); boolean[] seen = new boolean[digraph.length]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(i, rev, postOrder, seen); } Set<Integer>[] outdegree = new Set[n]; for (int i = 0; i < n; i++) outdegree[i] = new HashSet<>(); int[] seen2 = new int[digraph.length]; Arrays.fill(seen2, -1); for (int i : postOrder) { if (seen2[i] != -1) continue; dfs2(i, i, digraph, outdegree, seen2); } Set<Integer> used = new HashSet<>(); for (int i : seen2) used.add(i); return solveDAG(outdegree, used); }
ReachableVertex { public static int solveDigraph(Set<Integer>[] digraph) { int n = digraph.length; Set<Integer>[] rev = reverse(digraph); LinkedList<Integer> postOrder = new LinkedList<>(); boolean[] seen = new boolean[digraph.length]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(i, rev, postOrder, seen); } Set<Integer>[] outdegree = new Set[n]; for (int i = 0; i < n; i++) outdegree[i] = new HashSet<>(); int[] seen2 = new int[digraph.length]; Arrays.fill(seen2, -1); for (int i : postOrder) { if (seen2[i] != -1) continue; dfs2(i, i, digraph, outdegree, seen2); } Set<Integer> used = new HashSet<>(); for (int i : seen2) used.add(i); return solveDAG(outdegree, used); } }
ReachableVertex { public static int solveDigraph(Set<Integer>[] digraph) { int n = digraph.length; Set<Integer>[] rev = reverse(digraph); LinkedList<Integer> postOrder = new LinkedList<>(); boolean[] seen = new boolean[digraph.length]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(i, rev, postOrder, seen); } Set<Integer>[] outdegree = new Set[n]; for (int i = 0; i < n; i++) outdegree[i] = new HashSet<>(); int[] seen2 = new int[digraph.length]; Arrays.fill(seen2, -1); for (int i : postOrder) { if (seen2[i] != -1) continue; dfs2(i, i, digraph, outdegree, seen2); } Set<Integer> used = new HashSet<>(); for (int i : seen2) used.add(i); return solveDAG(outdegree, used); }  }
ReachableVertex { public static int solveDigraph(Set<Integer>[] digraph) { int n = digraph.length; Set<Integer>[] rev = reverse(digraph); LinkedList<Integer> postOrder = new LinkedList<>(); boolean[] seen = new boolean[digraph.length]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(i, rev, postOrder, seen); } Set<Integer>[] outdegree = new Set[n]; for (int i = 0; i < n; i++) outdegree[i] = new HashSet<>(); int[] seen2 = new int[digraph.length]; Arrays.fill(seen2, -1); for (int i : postOrder) { if (seen2[i] != -1) continue; dfs2(i, i, digraph, outdegree, seen2); } Set<Integer> used = new HashSet<>(); for (int i : seen2) used.add(i); return solveDAG(outdegree, used); }  static int solveDAG(Set<Integer>[] dag); static int solveDigraph(Set<Integer>[] digraph); }
ReachableVertex { public static int solveDigraph(Set<Integer>[] digraph) { int n = digraph.length; Set<Integer>[] rev = reverse(digraph); LinkedList<Integer> postOrder = new LinkedList<>(); boolean[] seen = new boolean[digraph.length]; for (int i = 0; i < n; i++) { if (seen[i]) continue; dfs(i, rev, postOrder, seen); } Set<Integer>[] outdegree = new Set[n]; for (int i = 0; i < n; i++) outdegree[i] = new HashSet<>(); int[] seen2 = new int[digraph.length]; Arrays.fill(seen2, -1); for (int i : postOrder) { if (seen2[i] != -1) continue; dfs2(i, i, digraph, outdegree, seen2); } Set<Integer> used = new HashSet<>(); for (int i : seen2) used.add(i); return solveDAG(outdegree, used); }  static int solveDAG(Set<Integer>[] dag); static int solveDigraph(Set<Integer>[] digraph);  }