StronglyConnectedComponentFinder { public DisjointSet<?, Vertex<V>> find(Graph<E, V> graph) { final Graph<E, V> coloredGraph = first.visit(graph, new GraphVertexVisitorAdapter<E, V>() { }); final Graph<E, V> transposed = coloredGraph.transpose(); final Graph<E, V> coloredTransposed = second.visit(transposed, new GraphVertexVisitorAdapter<E, V>() { }); final PathCompressingRankedForestDisjointSet<Vertex<V>> set = new PathCompressingRankedForestDisjointSet<>(); for (Vertex<V> vertex : coloredTransposed.getVertices()) { final RankedTreeElement<Vertex<V>> element = set.create(vertex); final Vertex<V> root = findRoot(vertex); if (root.getIndex() == vertex.getIndex()) { continue; } RankedTreeElement<Vertex<V>> rootElement = null; for (RankedTreeElement<Vertex<V>> treeElement : set.sets()) { final Set<Vertex<V>> elements = set.elements(treeElement); if (elements.contains(root)) { rootElement = treeElement; break; } } if (rootElement == null) { rootElement = set.create(root); } set.union(rootElement, element); } return set; }  DisjointSet<?, Vertex<V>> find(Graph<E, V> graph);  }
@Test public void testUndirected() throws Exception { final StronglyConnectedComponentFinder<EdgeDetails, VertexDetails> finder = new StronglyConnectedComponentFinder<>(); final Graph<EdgeDetails, VertexDetails> graph = GraphSamples.undirected(); final DisjointSet<Element<Vertex<VertexDetails>>, Vertex<VertexDetails>> set = (DisjointSet<Element<Vertex<VertexDetails>>, Vertex<VertexDetails>>) finder.find(graph); assertThat(set, is(notNullValue())); assertThat(set.sets(), hasSize(1)); final Element<Vertex<VertexDetails>> root = set.sets().iterator().next(); final Set<Vertex<VertexDetails>> elements = set.elements(root); final Set<Integer> indices = new HashSet<>(); for (Vertex<VertexDetails> element : elements) { indices.add(element.getIndex()); } assertThat(indices, containsInAnyOrder(0, 1, 2, 3, 4, 5)); }
@Test public void testDirected() throws Exception { final StronglyConnectedComponentFinder<EdgeDetails, VertexDetails> finder = new StronglyConnectedComponentFinder<>(); final Graph<EdgeDetails, VertexDetails> graph = GraphSamples.directed(); final DisjointSet<Element<Vertex<VertexDetails>>, Vertex<VertexDetails>> set = (DisjointSet<Element<Vertex<VertexDetails>>, Vertex<VertexDetails>>) finder.find(graph); assertThat(set, is(notNullValue())); final Set<Element<Vertex<VertexDetails>>> sets = set.sets(); assertThat(sets, hasSize(2)); for (Element<Vertex<VertexDetails>> element : sets) { final Set<Vertex<VertexDetails>> elements = set.elements(element); final Set<Integer> indices = new HashSet<>(); for (Vertex<VertexDetails> vertex : elements) { indices.add(vertex.getIndex()); } if (indices.contains(0)) { assertThat(indices, containsInAnyOrder(0, 1, 2, 3)); } else { assertThat(indices, containsInAnyOrder(4, 5)); } } }