@Test public void testDoTarjan() throws Exception { Map<NodeType, Node<NodeType>> nodes = new HashMap<>(); for (NodeType t : NodeType.values()) { nodes.put(t, new Node<>(t)); } connectFromTo(nodes, NodeType.A, NodeType.B); connectFromTo(nodes, NodeType.B, NodeType.C); connectFromTo(nodes, NodeType.C, NodeType.D); connectFromTo(nodes, NodeType.C, NodeType.E); connectFromTo(nodes, NodeType.E, NodeType.F); connectFromTo(nodes, NodeType.D, NodeType.F); List<ImmutableList<Node<NodeType>>> result = Graph.doTarjan(nodes.values()); System.out.println("no cycles"); Joiner joiner = Joiner.on("\n"); System.out.println(joiner.join(result)); assertEquals(nodes.size(), result.size()); validateTopoSort(ImmutableList.of(NodeType.A, NodeType.B, NodeType.C, NodeType.E, NodeType.D, NodeType.F), result); connectFromTo(nodes, NodeType.F, NodeType.C); result = Graph.doTarjan(nodes.values()); System.out.println("cycles"); System.out.println(joiner.join(result)); assertFalse(nodes.size() == result.size()); }
public static <E extends Comparable<E>> List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0) { List<Node<E>> allNodes = new ArrayList<>(allNodes0); Collections.sort(allNodes); resetIndexes(allNodes); int index = 0; Deque<Node<E>> s = new LinkedList<>(); List<ImmutableList<Node<E>>> components = new LinkedList<>(); for (Node<E> v : allNodes) { index = strongConnect(index, s, v, components); } return components; }
Graph { public static <E extends Comparable<E>> List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0) { List<Node<E>> allNodes = new ArrayList<>(allNodes0); Collections.sort(allNodes); resetIndexes(allNodes); int index = 0; Deque<Node<E>> s = new LinkedList<>(); List<ImmutableList<Node<E>>> components = new LinkedList<>(); for (Node<E> v : allNodes) { index = strongConnect(index, s, v, components); } return components; } }
Graph { public static <E extends Comparable<E>> List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0) { List<Node<E>> allNodes = new ArrayList<>(allNodes0); Collections.sort(allNodes); resetIndexes(allNodes); int index = 0; Deque<Node<E>> s = new LinkedList<>(); List<ImmutableList<Node<E>>> components = new LinkedList<>(); for (Node<E> v : allNodes) { index = strongConnect(index, s, v, components); } return components; }  }
Graph { public static <E extends Comparable<E>> List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0) { List<Node<E>> allNodes = new ArrayList<>(allNodes0); Collections.sort(allNodes); resetIndexes(allNodes); int index = 0; Deque<Node<E>> s = new LinkedList<>(); List<ImmutableList<Node<E>>> components = new LinkedList<>(); for (Node<E> v : allNodes) { index = strongConnect(index, s, v, components); } return components; }  static List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0); }
Graph { public static <E extends Comparable<E>> List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0) { List<Node<E>> allNodes = new ArrayList<>(allNodes0); Collections.sort(allNodes); resetIndexes(allNodes); int index = 0; Deque<Node<E>> s = new LinkedList<>(); List<ImmutableList<Node<E>>> components = new LinkedList<>(); for (Node<E> v : allNodes) { index = strongConnect(index, s, v, components); } return components; }  static List<ImmutableList<Node<E>>> doTarjan(Collection<Node<E>> allNodes0);  }