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] ]

Converting Disconnected Graphs to a Collection of Connected Graphs

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