I recently discovered JUNG, and I have a use case to treat all weakly connected subgraphs of a directed graph as separate graphs. So given any directed graph, be it just one connected directed graph or several connected, strongly connected or weakly connected directed graphs this code will return to you the disjoint union of all graphs as a collection of connected graphs with edge direction maintained from the original.
The code uses implements Function from google collections, since it could be useful to apply this code to a collection of input graphs. Also I just prefer google collections over jakarta. It however does use Jakarta collections as well since that is what JUNG uses.
package jung;
import java.util.Collection;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import org.apache.commons.collections15.Factory;
import com.google.common.base.Function;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
public class DisconnectedDirectedGraphToWeaklyConnectedDirectedGraphCollection<V, E>
implements
Function<DirectedGraph<V, E>, Collection<DirectedGraph<V, E>>> {
private Set<V> visited;
public Collection<DirectedGraph<V, E>> apply(DirectedGraph<V, E> from) {
List<DirectedGraph<V, E>> subGraphs = Lists.newArrayList();
Stack<V> verticesRemaining = new Stack<V>();
verticesRemaining.addAll(from.getVertices());
Factory<DirectedGraph<V, E>> graphFactory = DirectedSparseGraph
.<V, E> getFactory();
do {
visited = Sets.newHashSet();
DirectedGraph<V, E> newGraph = graphFactory.create();
dfsCopy(verticesRemaining.pop(), from, newGraph);
verticesRemaining.removeAll(visited);
subGraphs.add(newGraph);
} while (!verticesRemaining.isEmpty());
return subGraphs;
} // end method
private void dfsCopy(V v, DirectedGraph<V, E> from, DirectedGraph<V, E> to) {
if (!visited.add(v)) {
return;
} // end if
for (E e : from.getInEdges(v)) {
V neighbor = from.getSource(e);
to.addEdge(e, neighbor, v);
dfsCopy(neighbor, from, to);
} // end for
for (E e : from.getOutEdges(v)) {
V neighbor = from.getDest(e);
to.addEdge(e, v, neighbor);
dfsCopy(neighbor, from, to);
} // end for
} // end method
} // end class
And here is a simple test class:
package jung;
import java.util.Collection;
import junit.framework.Assert;
import org.apache.log4j.Logger;
import org.junit.Test;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
public class TestDisconnectedDirectedGraphToConnectedDirectedGraphCollection {
private final static Logger logger = Logger
.getLogger(TestDisconnectedDirectedGraphToConnectedDirectedGraphCollection.class);
@Test
public void testSubGraphs() {
DirectedGraph<String, String> dg = DirectedSparseGraph
.<String, String> getFactory().create();
// g1: a connected graph
uniqEdge(dg, "A", "B");
uniqEdge(dg, "E", "B");
uniqEdge(dg, "B", "C");
uniqEdge(dg, "B", "D");
// g2: another connected graph
uniqEdge(dg, "F", "G");
uniqEdge(dg, "F", "H");
// g3: a pair of nodes connected by an edge
uniqEdge(dg, "I", "J");
// g4: a loop
uniqEdge(dg, "K", "K");
// g5: a weakly connected graph
uniqEdge(dg, "L", "M");
uniqEdge(dg, "N", "M");
logger.debug(dg);
DisconnectedDirectedGraphToWeaklyConnectedDirectedGraphCollection<String, String> f = new DisconnectedDirectedGraphToWeaklyConnectedDirectedGraphCollection<String, String>();
Collection<DirectedGraph<String, String>> g = f.apply(dg);
logger.debug(g);
Assert.assertEquals("union of disjoint graphs is not the correct size",
5, g.size());
} // end test
private void uniqEdge(Graph<String, String> g, String src, String dest) {
g.addEdge(src + dest, src, dest);
}
} // end test class
And here is the output of the test case:
2010-02-25 14:47:51,058 [TestDirectedGraphToDisjointUnionOfWeaklyConnectedDirectedGraphs.java 43] DEBUG - [Vertices:K
Edges:KK[K,K] , Vertices:I,J
Edges:IJ[I,J] , Vertices:F,G,H
Edges:FG[F,G] FH[F,H] , Vertices:L,M,N
Edges:NM[N,M] LM[L,M] , Vertices:D,E,A,B,C
Edges:AB[A,B] EB[E,B] BC[B,C] BD[B,D] ]
NOTE: See
this follow on post for a revised version
