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

Pound for Pound Challenge

I just joined the Biggest Loser - Pound for Pound Challenge. I pledged to lose 8 pounds by event end ( I think it's in June ). Anyway, hope this helps me and some family in the community.

Pound for Pound Challenge Home

The Last Carnegie Ride?

Kyle and I went riding at Carnegie (near Livermore,CA) this morning for what may be the last time... I certainly hope not, but they plan to close it, I think, next week, for what might be a permanent closure.

They had most of Corral Hollow Creek closed off (this is the area close to the rode and near the entrance to the park). But, otherwise with the fog keeping the ground a touch wet the traction was great, and the temperature was about 50 degrees. So, the conditions were near perfect. I sure hope they don't close this park for good: So many families have had great times there.

I've always felt that the dirt biking community is a small community, full of hard working folks who can barely speak up for themselves and are often picked on by larger communities like environmentalists. Don't get me wrong I'm more green than many but environmentalists have so many bigger fish to fry. Unfortunately, they have trouble battlign the big boys like gas companies and automobile makers. So, it's just easy to get a few wins against the little guy.

For more info see:
http://www.sharetrails.org/releases/media/?story=671

Vote to keep it open here:
http://carnegieforever.org/

Why engineers and motorcycles don't mix

Wait, I'm an engineer (software engineer :-) and I ride motorcycles... maybe the title of this blog entry should be "sometimes engineers and motorcycles don't mix". That would have applied to me a few times I can think of...

Triplet class

I wrote a Triplet class, it seems general purpose enough to share, so here it is:

package harsch.sandbox;

import org.apache.commons.lang.builder.CompareToBuilder;
import org.apache.commons.lang.builder.HashCodeBuilder;

/**
 * 
 * @author Tim Harsch
 * 
 * @param <L>
 * @param <M>
 * @param <R>
 */
public class Triplet<L, M, R> implements Comparable<Object> {
 private final L left;
 private final M mid;
 private final R right;

 public R getRight() {
  return right;
 } // end getter

 public M getMid() {
  return mid;
 } // end getter

 public L getLeft() {
  return left;
 } // end getter

 public Triplet(final L left, final M mid, final R right) {
  this.left = left;
  this.mid = mid;
  this.right = right;
 } // end constructor

 public static <A, B, C> Triplet<A, B, C> create(A left, B mid, C right) {
  return new Triplet<A, B, C>(left, mid, right);
 } // end factory method

 @Override
 public final boolean equals(Object o) {
  if (!(o instanceof Triplet<?, ?, ?>))
   return false;

  final Triplet<?, ?, ?> other = (Triplet<?, ?, ?>) o;
  return equal(getLeft(), other.getLeft())
    && equal(getMid(), other.getMid())
    && equal(getRight(), other.getRight());
 } // end method

 public static final boolean equal(Object o1, Object o2) {
  if (o1 == null) {
   return o2 == null;
  }
  return o1.equals(o2);
 } // end method

 @Override
 public int hashCode() {
  return new HashCodeBuilder(17, 13).append(this.left).append(this.mid)
    .append(this.right).toHashCode();
 } // end method

 @Override
 public int compareTo(Object o) {
  Triplet<?, ?, ?> other = (Triplet<?, ?, ?>) o;
  return new CompareToBuilder().append(this.left, other.left).append(
    this.mid, other.mid).append(this.right, other.right)
    .toComparison();
 } // end method

 @Override
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append('<');
  if (left == null) {
   sb.append("null");
  } else {
   sb.append(left.toString());
  } // end if
  sb.append(',');
  if (mid == null) {
   sb.append("null");
  } else {
   sb.append(mid.toString());
  } // end if
  sb.append(',');
  if (right == null) {
   sb.append("null");
  } else {
   sb.append(right.toString());
  } // end if
  sb.append('>');
  return sb.toString();
 } // end method
} // end class

UPromise

I use a service called UPromise, which I think any parent planning for a college education should use. You can simply sign up and then register a credit card that you use with them. From that point forward, any purchases that you make with any of their affiliated sites will get you a percentage kick back, which goes into your Account and can be transfered to a 529 college account. The nice part is it costs you nothing and you would be making the purchase anyway, so why not get the extra points. Oh, and it doesn't matter if your credit card already earns you miles, points or cash back. You get the college savings anyway!

Java Maps Inline Initialization

I found a blog sometime back at
http://nileshbansal.blogspot.com/2009/04/initializing-java-maps-inline.html

It shows how to inline initialize a Java map, like so:
Map map = new HashMap<String, String>() {{
put("Harry", "Potter");
put("Ron", "Weasley");
put("Hermione", "Granger");
}};

I find myself forgetting the exact syntax if I haven't used in awhile so I thought I would blog it :-)

An alternate way is using Google collections:
Map<String, String> map = ImmutableMap.of( "x", "y" );