# Strongly connected component finding based on the guava graph library with Kosaraju

I have been writing a small compiler generator for which I need to solve the strongly connected component problem. As the Guava library contains, to my knowledge, no implementation for that problem, I have decided to write my own based on Kosaraju's algorithm.

For this, I have created a GraphUtils class and a GraphTraverser<T> to iterate over the graph.

import com.google.common.collect.ImmutableList;

public class GraphUtils {
private GraphUtils() {
}

/**
* Guarantees: the graph will be directed and forest-like without self loops.
*
* @param graph
* @return the SCC graph. each node contains all the nodes in the CC of the original graph
*/
public static <T> Graph<Set<T>> findStronglyConnectedComponents(Graph<T> graph) {
if (graph.nodes().isEmpty()) {
throw new IllegalArgumentException("Can't find components in an empty graph");
}
final MutableGraph<Set<T>> result = GraphBuilder.directed().allowsSelfLoops(false)
.nodeOrder(ElementOrder.insertion()).build();
// Kosaraju's algorithm

final Map<T, Set<T>> ccStore = new HashMap<>(graph.nodes().size());
// Step 1
final ImmutableList<T> topologicalOrder = GraphUtils.traverse(graph).postOrderTraversal(graph.nodes()).toList()
.reverse();
// Step 2
final Graph<T> transposeGraph = Graphs.transpose(graph);
// Step 3
for (T node : topologicalOrder) {
if (ccStore.keySet().contains(node)) {
continue;
}
final Set<T> connectedComponent = new HashSet<>();
final Set<T> hitExistingNodes = new HashSet<>();

GraphUtils.traverse(transposeGraph)

hitExistingNodes.forEach(n -> {
// We encounterd a connection between connected components
Set<T> existingCC = ccStore.get(n);
result.putEdge(existingCC, connectedComponent);
});
connectedComponent.forEach(n -> {
ccStore.put(n, connectedComponent);
});
}

return result;
}

public static <T> GraphTraverser<T> traverse(Graph<T> graph) {
return new GraphTraverser<>(graph);
}
}


GraphTraverser<T>

import com.google.common.collect.AbstractIterator;

public class GraphTraverser<T> {
private static final class PostOrderNode<T> {
public final T root;
public final Iterator<T> childIterator;

public PostOrderNode(T root, Iterator<T> childIterator) {
this.root = Objects.requireNonNull(root);
this.childIterator = Objects.requireNonNull(childIterator);
}
}

private final class PostOrderIterator extends AbstractIterator<T> {
private final ArrayDeque<PostOrderNode<T>> stack = new ArrayDeque<>();
private final Iterator<T> rootNodes;
private final Set<T> visitedSet;
private final Set<T> ignoredSet;
private final Consumer<T> ignoreNodeEncountered;

public PostOrderIterator(Collection<T> roots, Set<T> ignoredNodes, Consumer<T> ignoreNodeMet) {
this.rootNodes = roots.iterator();
this.visitedSet = new HashSet<>(graph.nodes().size());
this.ignoredSet = ignoredNodes;
this.ignoreNodeEncountered = ignoreNodeMet;
}

@Override
protected T computeNext() {
while (stack.isEmpty() && rootNodes.hasNext()) {
pushNodeIfUnvisited(rootNodes.next());
}
while (!stack.isEmpty()) {
PostOrderNode<T> top = stack.getLast();
if (top.childIterator.hasNext()) {
T child = top.childIterator.next();
pushNodeIfUnvisited(child);
} else {
stack.removeLast();
}
}
return endOfData();
}

private void pushNodeIfUnvisited(T t) {
if (ignoredSet.contains(t)) {
if (ignoreNodeEncountered != null) {
ignoreNodeEncountered.accept(t);
}
return;
}
return;
}
}

private PostOrderNode<T> expand(T t) {
return new PostOrderNode<T>(t, graph.successors(t).iterator());
}
}

private final Graph<T> graph;

public GraphTraverser(Graph<T> graph) {
this.graph = Objects.requireNonNull(graph);
}

public FluentIterable<T> postOrderTraversal() {
return postOrderTraversal(graph.nodes());
}

public FluentIterable<T> postOrderTraversal(Collection<T> rootNodes) {
return postOrderTraversal(rootNodes, Collections.emptySet(), null);
}

/**
* Does post order traversal of the (directed) graph. When a node in ignoredNodes is encountered, ignoreNodeMet is
* called
*
* @param rootNodes
*            the nodes to start traversal at
* @param ignoredNodes
*            nodes that will be ignored, i.e. not recursively traversed
* @param ignoredNodeMet
*            might be null for no callback
* @return
*/
public FluentIterable<T> postOrderTraversal(Collection<T> rootNodes, Set<T> ignoredNodes,
Consumer<T> ignoredNodeMet) {
return new FluentIterable<T>() {
@Override
public Iterator<T> iterator() {
return new PostOrderIterator(rootNodes, ignoredNodes, ignoredNodeMet);
}
};
}
}


Here's an example usage, with current, correct output:

MutableGraph<Integer> originalGraph = GraphBuilder.directed().expectedNodeCount(10).build();
originalGraph.putEdge(1, 0);
originalGraph.putEdge(2, 1);
originalGraph.putEdge(0, 2);
originalGraph.putEdge(0, 3);
originalGraph.putEdge(5, 3);
originalGraph.putEdge(3, 4);

System.out.println(originalGraph);
// isDirected: true, allowsSelfLoops: false, nodes: [1, 0, 2, 3, 5, 4], edges: [<1 -> 0>, <0 -> 2>, <0 -> 3>, <2 -> 1>, <3 -> 4>, <5 -> 3>]
Graph<Set<Integer>> sccGraph = GraphUtils.findStronglyConnectedComponents(originalGraph);
System.out.println(sccGraph);
// isDirected: true, allowsSelfLoops: false, nodes: [[5], [0, 1, 2], [3], [4]], edges: [<[5] -> [3]>, <[0, 1, 2] -> [3]>, <[3] -> [4]>]


I'm mostly interested in the design of GraphTraverser<T> and the efficiency of the algorithm and the returned result. If you find any bugs, please point them out. Any comments on code style and readability are appreciated.