Converting Disconnected Graphs to a Collection of Connected Graphs (revised)

In the original post: Converting Disconnected Graphs to a Collection of Connected Graphs I achieved my goal of converting a disconnected graph into a collection of connected graphs. After some discussion on the JUNG support list I was pointed in the direction of WeakComponentClusterer. Compare this method to the original to see:

* the implementation is now just a few lines of code
* this can be used as a template to provide Collections of other graph types beside just DirectedGraph without having to rewrite the implementation.

Some negatives of this approach over the former:
* it should not perform as well since it first performs some computation to create the vertex set and then performs computation to convert the set into a Collection of graphs. Consequently the set of vertex sets is discarded between the two operations.
* perhaps not a negative but at least notable is the fact that it uses reflection to create a copy of the input graph.

package jung;

import java.util.Collection;
import java.util.Set;

import com.google.common.base.Function;

import edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer;
import edu.uci.ics.jung.algorithms.filters.FilterUtils;
import edu.uci.ics.jung.graph.DirectedGraph;

public class DisconnectedDirectedGraphToWeaklyConnectedDirectedGraphCollection<V, E>
  implements
  Function<DirectedGraph<V, E>, Collection<DirectedGraph<V, E>>> {
 public Collection<DirectedGraph<V, E>> apply(DirectedGraph<V, E> from) {
  WeakComponentClusterer<V, E> wcc = new WeakComponentClusterer<V, E>();
  Set<Set<V>> vertexSets = wcc.transform(from);
  
  return FilterUtils.createAllInducedSubgraphs(vertexSets, from);
 } // 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] ]