JGraphT:EqualsAndHashCode

From Eigenpedia

There are many articles available on the web (e.g. http://www.ibm.com/developerworks/java/library/j-jtp05273.html) explaining the need to keep equals and hashCode methods consistent for each class.

This is especially important for any Vertex and Edge objects used with JGraphT since the default graph implementations rely on HashSet/HashMap for efficiently storing and accessing graph structures.

If you make a mistake with these methods, the observed behavior will typically be very confusing. In many cases, bugs have been logged against JGraphT in situations where investigation eventually determined that the cause of the problem was actually in the user-defined Vertex/Edge classes.

For example, suppose your Vertex class overrides equals, but forgets to override hashCode. You have vertices v1, v2, v3, v4, v5, where v3.equals(v5), and you add them all to a graph, with edges v1->v2->v3->v4->v5. If hashCode had been defined correctly, then the attempt to add v5 would have discarded it, since an equal vertex (v3) was already present in the graph.

However, the hash codes for v3 and v5 are different (since they are different objects, and the default hashCode implementation is based on object identity). Suppose these hash codes do not collide when folded down into the array used by the HashMap inside of the graph. As a result, when you add v5 to the graph, HashMap won't even compare it against v3, since it only calls equals in case of a collision. Now you have a corrupt graph, since it contains two vertex objects which are equals; this violates the contract of the graph.

Under these circumstances, you may not notice anything wrong at first. However, if you use the CycleDetector class on this graph, you'll be in for a surprise, since it relies on ArrayList.indexOf, and this doesn't do any hashing, so it will see that v3 and v5 are equals, and detect a cycle (whereas you are thinking v3 and v5 are different vertices).

Tracking these problems down can be time-consuming, so JGraphT supplies a class ParanoidGraph to help you. You can use it to wrap one of your own graphs; by calling the addVertex/addEdge methods on ParanoidGraph (rather than on your graph directly), you get automatic verification as part of each object addition; an IllegalArgumentException will be thrown if a bad object is detected. Note that this checking is very expensive, so only use it during debugging or sanity checking.

Example from a unit test:

 public void testParanoidGraph()
 {
     BrokenVertex v1 = new BrokenVertex(1);
     BrokenVertex v2 = new BrokenVertex(2);
     BrokenVertex v3 = new BrokenVertex(1);

     SimpleGraph<BrokenVertex, DefaultEdge> g =
         new SimpleGraph<BrokenVertex, DefaultEdge>(DefaultEdge.class);
      ParanoidGraph<BrokenVertex, DefaultEdge> pg =
         new ParanoidGraph<BrokenVertex, DefaultEdge>(g);
     pg.addVertex(v1);
     pg.addVertex(v2);
     try {
         pg.addVertex(v3);
         // should not get here
         assertFalse();
     } catch (IllegalArgumentException ex) {
         // expected, swallow
     }
 }

 private class BrokenVertex
 {
     private int x;

     BrokenVertex(int x)
     {
         this.x = x;
     }

     public boolean equals(Object other)
     {
         if (!(other instanceof BrokenVertex)) {
             return false;
         }
         return x == ((BrokenVertex) other).x;
     }
 }