@Test public void testTarjanStrongComponentsCycle() { Structure<Vertex, Edge> structure = new DirectedGraph(); Vertex u = structure.addVertex("u"); Vertex v = structure.addVertex("v"); Vertex w = structure.addVertex("w"); structure.addEdge(v, w); structure.addEdge(w, u); structure.addEdge(u, v); HashMap<Vertex, Integer> componentOfVertex = new HashMap<>(); HashSet<HashSet<Vertex>> verticesInComponent = new HashSet<>(); StronglyConnectedComponents.tarjanStrongComponents(structure, componentOfVertex, verticesInComponent, new HashSet<>()); assertSame("Number of components", verticesInComponent.size(), 1); assertThat("First component", verticesInComponent.toArray()[0], equalsVertexSet(structure.getVertices())); }
public static void tarjanStrongComponents(Structure s, HashMap<Vertex, Integer> componentOfVertex, HashSet<HashSet<Vertex>> verticesInComponent, HashSet<Vertex> removedVertices) { int numScc = 0; int index = 0; Stack<Vertex> tarStack = new Stack<>(); HashSet<Vertex> onStack = new HashSet<>(); HashMap<Vertex, Integer> dfs = new HashMap<>(); HashMap<Vertex, Integer> lowlink = new HashMap<>(); HashMap<Vertex, Vertex> parent = new HashMap<>(); HashMap<Vertex, ArrayList<Vertex>> children = new HashMap<>(); HashMap<Vertex, Integer> childIterationPos = new HashMap<>(); Collection<Vertex> vertices = s.getVertices(); for (Vertex v : vertices) { if (removedVertices.contains(v)) continue; if (dfs.containsKey(v)) continue; dfs.put(v, index); lowlink.put(v, index); index++; ArrayList<Vertex> vChildren = new ArrayList<>(); for (Edge e : v.getIncidentEdges()) if (e.getSource() == v) if (!removedVertices.contains(e.getTarget())) vChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) vChildren.add(e.getSource()); children.put(v, vChildren); childIterationPos.put(v, 0); tarStack.push(v); parent.put(v, null); onStack.add(v); Vertex current = v; while (current != null) { Integer currentChildIdx = childIterationPos.get(current); if (currentChildIdx < children.get(current).size()) { Vertex child = children.get(current).get(currentChildIdx); childIterationPos.put(current, currentChildIdx + 1); if (!dfs.containsKey(child)) { parent.put(child, current); ArrayList<Vertex> grandChildren = new ArrayList<>(); for (Edge e : child.getIncidentEdges()) if (e.getSource() == child) if (!removedVertices.contains(e.getTarget())) grandChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) grandChildren.add(e.getSource()); children.put(child, grandChildren); childIterationPos.put(child, 0); dfs.put(child, index); lowlink.put(child, index); index++; tarStack.push(child); onStack.add(child); current = child; } else if (onStack.contains(child)) { lowlink.put(current, Math.min(lowlink.get(current), dfs.get(child))); } } else { if (lowlink.get(current).equals(dfs.get(current))) { Vertex top = null; HashSet<Vertex> scc = new HashSet<>(); while (top != current) { top = tarStack.pop(); onStack.remove(top); scc.add(top); componentOfVertex.put(top, numScc); } verticesInComponent.add(scc); numScc++; } Vertex newLast = parent.get(current); if (newLast != null) lowlink.put(newLast, Math.min(lowlink.get(newLast), lowlink.get(current))); current = newLast; } } } }
StronglyConnectedComponents extends Algorithm { public static void tarjanStrongComponents(Structure s, HashMap<Vertex, Integer> componentOfVertex, HashSet<HashSet<Vertex>> verticesInComponent, HashSet<Vertex> removedVertices) { int numScc = 0; int index = 0; Stack<Vertex> tarStack = new Stack<>(); HashSet<Vertex> onStack = new HashSet<>(); HashMap<Vertex, Integer> dfs = new HashMap<>(); HashMap<Vertex, Integer> lowlink = new HashMap<>(); HashMap<Vertex, Vertex> parent = new HashMap<>(); HashMap<Vertex, ArrayList<Vertex>> children = new HashMap<>(); HashMap<Vertex, Integer> childIterationPos = new HashMap<>(); Collection<Vertex> vertices = s.getVertices(); for (Vertex v : vertices) { if (removedVertices.contains(v)) continue; if (dfs.containsKey(v)) continue; dfs.put(v, index); lowlink.put(v, index); index++; ArrayList<Vertex> vChildren = new ArrayList<>(); for (Edge e : v.getIncidentEdges()) if (e.getSource() == v) if (!removedVertices.contains(e.getTarget())) vChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) vChildren.add(e.getSource()); children.put(v, vChildren); childIterationPos.put(v, 0); tarStack.push(v); parent.put(v, null); onStack.add(v); Vertex current = v; while (current != null) { Integer currentChildIdx = childIterationPos.get(current); if (currentChildIdx < children.get(current).size()) { Vertex child = children.get(current).get(currentChildIdx); childIterationPos.put(current, currentChildIdx + 1); if (!dfs.containsKey(child)) { parent.put(child, current); ArrayList<Vertex> grandChildren = new ArrayList<>(); for (Edge e : child.getIncidentEdges()) if (e.getSource() == child) if (!removedVertices.contains(e.getTarget())) grandChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) grandChildren.add(e.getSource()); children.put(child, grandChildren); childIterationPos.put(child, 0); dfs.put(child, index); lowlink.put(child, index); index++; tarStack.push(child); onStack.add(child); current = child; } else if (onStack.contains(child)) { lowlink.put(current, Math.min(lowlink.get(current), dfs.get(child))); } } else { if (lowlink.get(current).equals(dfs.get(current))) { Vertex top = null; HashSet<Vertex> scc = new HashSet<>(); while (top != current) { top = tarStack.pop(); onStack.remove(top); scc.add(top); componentOfVertex.put(top, numScc); } verticesInComponent.add(scc); numScc++; } Vertex newLast = parent.get(current); if (newLast != null) lowlink.put(newLast, Math.min(lowlink.get(newLast), lowlink.get(current))); current = newLast; } } } } }
StronglyConnectedComponents extends Algorithm { public static void tarjanStrongComponents(Structure s, HashMap<Vertex, Integer> componentOfVertex, HashSet<HashSet<Vertex>> verticesInComponent, HashSet<Vertex> removedVertices) { int numScc = 0; int index = 0; Stack<Vertex> tarStack = new Stack<>(); HashSet<Vertex> onStack = new HashSet<>(); HashMap<Vertex, Integer> dfs = new HashMap<>(); HashMap<Vertex, Integer> lowlink = new HashMap<>(); HashMap<Vertex, Vertex> parent = new HashMap<>(); HashMap<Vertex, ArrayList<Vertex>> children = new HashMap<>(); HashMap<Vertex, Integer> childIterationPos = new HashMap<>(); Collection<Vertex> vertices = s.getVertices(); for (Vertex v : vertices) { if (removedVertices.contains(v)) continue; if (dfs.containsKey(v)) continue; dfs.put(v, index); lowlink.put(v, index); index++; ArrayList<Vertex> vChildren = new ArrayList<>(); for (Edge e : v.getIncidentEdges()) if (e.getSource() == v) if (!removedVertices.contains(e.getTarget())) vChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) vChildren.add(e.getSource()); children.put(v, vChildren); childIterationPos.put(v, 0); tarStack.push(v); parent.put(v, null); onStack.add(v); Vertex current = v; while (current != null) { Integer currentChildIdx = childIterationPos.get(current); if (currentChildIdx < children.get(current).size()) { Vertex child = children.get(current).get(currentChildIdx); childIterationPos.put(current, currentChildIdx + 1); if (!dfs.containsKey(child)) { parent.put(child, current); ArrayList<Vertex> grandChildren = new ArrayList<>(); for (Edge e : child.getIncidentEdges()) if (e.getSource() == child) if (!removedVertices.contains(e.getTarget())) grandChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) grandChildren.add(e.getSource()); children.put(child, grandChildren); childIterationPos.put(child, 0); dfs.put(child, index); lowlink.put(child, index); index++; tarStack.push(child); onStack.add(child); current = child; } else if (onStack.contains(child)) { lowlink.put(current, Math.min(lowlink.get(current), dfs.get(child))); } } else { if (lowlink.get(current).equals(dfs.get(current))) { Vertex top = null; HashSet<Vertex> scc = new HashSet<>(); while (top != current) { top = tarStack.pop(); onStack.remove(top); scc.add(top); componentOfVertex.put(top, numScc); } verticesInComponent.add(scc); numScc++; } Vertex newLast = parent.get(current); if (newLast != null) lowlink.put(newLast, Math.min(lowlink.get(newLast), lowlink.get(current))); current = newLast; } } } }  }
StronglyConnectedComponents extends Algorithm { public static void tarjanStrongComponents(Structure s, HashMap<Vertex, Integer> componentOfVertex, HashSet<HashSet<Vertex>> verticesInComponent, HashSet<Vertex> removedVertices) { int numScc = 0; int index = 0; Stack<Vertex> tarStack = new Stack<>(); HashSet<Vertex> onStack = new HashSet<>(); HashMap<Vertex, Integer> dfs = new HashMap<>(); HashMap<Vertex, Integer> lowlink = new HashMap<>(); HashMap<Vertex, Vertex> parent = new HashMap<>(); HashMap<Vertex, ArrayList<Vertex>> children = new HashMap<>(); HashMap<Vertex, Integer> childIterationPos = new HashMap<>(); Collection<Vertex> vertices = s.getVertices(); for (Vertex v : vertices) { if (removedVertices.contains(v)) continue; if (dfs.containsKey(v)) continue; dfs.put(v, index); lowlink.put(v, index); index++; ArrayList<Vertex> vChildren = new ArrayList<>(); for (Edge e : v.getIncidentEdges()) if (e.getSource() == v) if (!removedVertices.contains(e.getTarget())) vChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) vChildren.add(e.getSource()); children.put(v, vChildren); childIterationPos.put(v, 0); tarStack.push(v); parent.put(v, null); onStack.add(v); Vertex current = v; while (current != null) { Integer currentChildIdx = childIterationPos.get(current); if (currentChildIdx < children.get(current).size()) { Vertex child = children.get(current).get(currentChildIdx); childIterationPos.put(current, currentChildIdx + 1); if (!dfs.containsKey(child)) { parent.put(child, current); ArrayList<Vertex> grandChildren = new ArrayList<>(); for (Edge e : child.getIncidentEdges()) if (e.getSource() == child) if (!removedVertices.contains(e.getTarget())) grandChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) grandChildren.add(e.getSource()); children.put(child, grandChildren); childIterationPos.put(child, 0); dfs.put(child, index); lowlink.put(child, index); index++; tarStack.push(child); onStack.add(child); current = child; } else if (onStack.contains(child)) { lowlink.put(current, Math.min(lowlink.get(current), dfs.get(child))); } } else { if (lowlink.get(current).equals(dfs.get(current))) { Vertex top = null; HashSet<Vertex> scc = new HashSet<>(); while (top != current) { top = tarStack.pop(); onStack.remove(top); scc.add(top); componentOfVertex.put(top, numScc); } verticesInComponent.add(scc); numScc++; } Vertex newLast = parent.get(current); if (newLast != null) lowlink.put(newLast, Math.min(lowlink.get(newLast), lowlink.get(current))); current = newLast; } } } }  static void components(UndirectedGraph s,
                                  HashMap<Vertex, Integer> componentOfVertex,
                                  HashSet<HashSet<Vertex>> verticesInComponent,
                                  HashSet<Vertex> removedVertices); static void tarjanStrongComponents(Structure s,
                                              HashMap<Vertex, Integer> componentOfVertex,
                                              HashSet<HashSet<Vertex>> verticesInComponent,
                                              HashSet<Vertex> removedVertices); @Override AlgorithmParameters getParameters(Structure structure, Highlights highlights); Object run(Structure s, StronglyConnectedComponentsParameters parameters, Set<Object> selection,
                      ProgressHandler onprogress); }
StronglyConnectedComponents extends Algorithm { public static void tarjanStrongComponents(Structure s, HashMap<Vertex, Integer> componentOfVertex, HashSet<HashSet<Vertex>> verticesInComponent, HashSet<Vertex> removedVertices) { int numScc = 0; int index = 0; Stack<Vertex> tarStack = new Stack<>(); HashSet<Vertex> onStack = new HashSet<>(); HashMap<Vertex, Integer> dfs = new HashMap<>(); HashMap<Vertex, Integer> lowlink = new HashMap<>(); HashMap<Vertex, Vertex> parent = new HashMap<>(); HashMap<Vertex, ArrayList<Vertex>> children = new HashMap<>(); HashMap<Vertex, Integer> childIterationPos = new HashMap<>(); Collection<Vertex> vertices = s.getVertices(); for (Vertex v : vertices) { if (removedVertices.contains(v)) continue; if (dfs.containsKey(v)) continue; dfs.put(v, index); lowlink.put(v, index); index++; ArrayList<Vertex> vChildren = new ArrayList<>(); for (Edge e : v.getIncidentEdges()) if (e.getSource() == v) if (!removedVertices.contains(e.getTarget())) vChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) vChildren.add(e.getSource()); children.put(v, vChildren); childIterationPos.put(v, 0); tarStack.push(v); parent.put(v, null); onStack.add(v); Vertex current = v; while (current != null) { Integer currentChildIdx = childIterationPos.get(current); if (currentChildIdx < children.get(current).size()) { Vertex child = children.get(current).get(currentChildIdx); childIterationPos.put(current, currentChildIdx + 1); if (!dfs.containsKey(child)) { parent.put(child, current); ArrayList<Vertex> grandChildren = new ArrayList<>(); for (Edge e : child.getIncidentEdges()) if (e.getSource() == child) if (!removedVertices.contains(e.getTarget())) grandChildren.add(e.getTarget()); else if (!e.isDirected) if (!removedVertices.contains(e.getSource())) grandChildren.add(e.getSource()); children.put(child, grandChildren); childIterationPos.put(child, 0); dfs.put(child, index); lowlink.put(child, index); index++; tarStack.push(child); onStack.add(child); current = child; } else if (onStack.contains(child)) { lowlink.put(current, Math.min(lowlink.get(current), dfs.get(child))); } } else { if (lowlink.get(current).equals(dfs.get(current))) { Vertex top = null; HashSet<Vertex> scc = new HashSet<>(); while (top != current) { top = tarStack.pop(); onStack.remove(top); scc.add(top); componentOfVertex.put(top, numScc); } verticesInComponent.add(scc); numScc++; } Vertex newLast = parent.get(current); if (newLast != null) lowlink.put(newLast, Math.min(lowlink.get(newLast), lowlink.get(current))); current = newLast; } } } }  static void components(UndirectedGraph s,
                                  HashMap<Vertex, Integer> componentOfVertex,
                                  HashSet<HashSet<Vertex>> verticesInComponent,
                                  HashSet<Vertex> removedVertices); static void tarjanStrongComponents(Structure s,
                                              HashMap<Vertex, Integer> componentOfVertex,
                                              HashSet<HashSet<Vertex>> verticesInComponent,
                                              HashSet<Vertex> removedVertices); @Override AlgorithmParameters getParameters(Structure structure, Highlights highlights); Object run(Structure s, StronglyConnectedComponentsParameters parameters, Set<Object> selection,
                      ProgressHandler onprogress);  }