Graph equality 3: toString

Last post about rooted, directed graphs, I swear.

It may be useful to find a canonical string representation for a given graph. In Java terms, how would one write the toString() method that would make all equivalent graphs look equal?

Here's the code:

String toString(graph g) {
   return toString(root(g), [])
}
String toString(node n, linkedlist path) {
   // check to see if I'm in the path already
   for each index i of path:
      if equiv(n, path[i])
         return "\" + (length(path)-i)   // return the Debruijn index

   result = label(n) + "("
   addLast(path, n)
   for each index i of children(n):
      if i>0: result += ","
      result += toString(children(n)[i], path)
   removeLast(path)
   result += ")"

   return result
}

If you had a structure like theta(0,+(1,theta(0,+(1,\2)))) then it would print out as theta(0,+(1,\2)), as would theta(0,+(1,theta(0,+(1,\4)))) and every other variant.

Note that this relies on the equiv test from the first post, but also once you have written toString it can serve as an equivalence test itself since it canonicalizes the graphs.