Graph equality

Here's a piece of code I figured out for testing when two rooted directed graphs are equivalent.

boolean equiv(Graph g1, Graph g2) {
   seen = empty set        // set of ordered pairs of nodes
   worklist = empty queue  // queue of pairs of nodes
   enqueue(worklist, (root(g1), root(g2)))

   while (worklist not empty) {
      (lhs,rhs) = dequeue(worklist)
      if ((lhs,rhs) is in seen)
         continue
      seen = union(seen, {(lhs,rhs)})

      if label(lhs) != label(rhs)
         return false
      if arity(lhs) != arity(rhs)
         return false
      for i in 1...arity(lhs)
         enqueue(worklist, (child(lhs,i),child(rhs,i)))
   }
   return true
}

This algorithm will check every unique pair that is encountered and return false if any of them are incompatible. If there are no incompatibilities, then the two graphs are equivalent. Notice that this allows the two different graphs to have different numbers of nodes. This comes in handy in two situations that are relevant to my research: PEGs and recursive types.

If you don't know what a PEG is, read this paper: http://cseweb.ucsd.edu/~rtate/publications/eqsat/. The algorithm above will tell you when two PEGs are syntactically equal, even if someone has unrolled the thetas any number of times. For example, it will tell you that the expressions theta(0,+(1,\2)) and theta(0,+(1,theta(0,+(1,\2)))) are equivalent (this syntax uses Debruijn indexes, I hope it's clear).

This also comes in handy when trying to represent recursive types. Say you have a simple linked list as follows:

struct list {
   int data;
   struct list *next;
}

You could represent this type in a compiler as the following rooted directed graph: struct(int, ptr(\2)). Using structural typing can be difficult when you have recursive types. For instance, the above struct should be structurally equivalent to this one:

struct list {
   int data;
   struct list2 {
      int data;
      struct list2* next;
   } *next;
}

...whose graph would look like struct(int,ptr(struct(int,ptr(\2)))). The algorithm described above would mark these two graphs as equivalent, as desired.

Both the time and space complexity are clearly O(N1*N2), but the actual complexity is proportional to the number of equivalent pairs of nodes in the two graphs. For most graphs this will be small, so the complexity can be as low as O(max(N1,N2)).