Graph equality 2: hash codes

In the last post I described an algorithm for detecting when two rooted, directed graphs are equivalent. Now I will describe how to compute a hashcode for such graphs.

This problem is again interesting in the setting of PEGs and recursive types. Computing a hashcode on a recursive structure can be a pain. Doing so in a way that gives all equivalent structures the same hashcode is even trickier. However, it turns out that there is a simple way to do this. The main trick is: give up some accuracy.

You hashcode function doesn't have to be as accurate as your equality function. (Note: in the back of my mind, I'm thinking of the Java way of doing things, where your 'equals' method and your 'hashCode' method should always agree). The only invariant you must maintain is

 A.equals(B)  =>  A.hashCode() == B.hashCode()

So, the solution is to not even compute a hashcode for the entire structure. You can simply compute a hashcode for all nodes that have distance less than N away from the root node. Any rooted directed graph can be thought of as a tree. If it has cycles, then it becomes an infinite tree. We simply take the tree (infinite or not) and chop it at the N-th level down. Then we compute the hashcode for just the remaining tree. For instance, say you have the structure: theta(0,+(1,\2)).
If you set your N-value at 4, you will actually compute the hashcode of the following tree:

        theta
        /   \
       0     +
            / \
           1  theta 
              /   \
             0     +
                  / \
                 1  theta

You essentially completely unfold all recursive structures, but only up to a certain depth. If the two structures are indeed equivalent, then they will produce the same tree. If they are not, then they may or may not produce the same tree. The N value you pick controls how closely your hash function agrees with your equality function.

The time complexity of this algorithm is O(N*B*H) where B is the maximum arity of any node in the graph, and H is the time spent hashing a single node.