The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, vertices at depth
$d$ are only ever connected to other vertices at depths
$d \pm 1$ (and in particular not depth $d$).
When I represent these graphs, I order the vertices at each depth, and record the edges by a series of matrices, essentially the list of adjacency matrices from each depth to the next. (That is, the full adjacency matrix is symmetric and block tridiagonal, with zero diagonal blocks. I just write down the superdiagonal blocks.)
Now, if I reorder the vertices at some depth (this just permutes the rows of one matrix and the columns of the next), obviously I have the same underlying graph. I'd like an algorithm that picks a particular ordering at each depth, for each such graph, producing a 'canonical form', with the following properties:
- the algorithm is idempotent; applying it a second time does nothing,
- the algorithm is stable, in the sense that if you just look at the first $d$ depths of a graph, and see that that graph is already 'in canonical form', then when you produce a canonical form for the whole graph those first $d$ depths aren't changed, and
- as many isomorphic graphs as possible are identified!
It may not be possible to satisfy 3. completely; for example the identity operation satisfies 1. and 2., but does a very bad job at 3. It's not essential for my application that every isomorphic pair of graphs are identified. (I'd be using this algorithm to speed up a combinatorial search of certain types of graphs, where I know that I'm unnecessarily producing many isomorphic copies of the same graph, but the details of the search require that I use this representation.)
Does anyone know of such an algorithm? Can anyone suggest something good?