Graph isomorphism checking using BFS

Question

I have two input graphs, with the same number of nodes and edges and both are rooted and undirected. I need to check whether they are isomorphic with each other or not. If so, I want my algorithm to return the mapping between two graphs. Since both of the graphs are rooted, I am assuming that BFS is going to return faster if they are not isomorphic. Is there any better algorithm or any implementation/article that can help me with this question? Thanks.

Answer 1

A few thoughts:

Having two rooted graphs does simplify the isomorphism challenge, because you have one known vertex mapping. You can use this root to assign a more detailed initial analysis of vertex degrees:

• Assign each vertex with its distance from the root.
• Now the degree for each vertex can be split into three components: in-degree, across-degree and out-degree, representing the count of those edges that go from that vertex to points of lower distance, the same distance and greater distance respectively.
• the list of 4-tuples: (distance, in-degree, across-degree, out-degree) can be sorted and must produce matched lists if the graphs are isomorphic. This also gives an initial partition of the vertices, in the language of the paper @fidbc linked, groups of vertices which can only be mapped within that group.

If any of the 4-tuples turn out to be unique, that is another fixed mapping point and could be used as an alternate root.

Every technique that usually only has degree to work on can work with this sub-divided distance/degree tuple.

You could also sum the outward paths (out-paths) inwards towards the root for a fifth characteristic, each vertex contributing $(1+$out-paths$)$ to each of its inward-linked vertices, if this is likely to be useful. Again the extended tuples must match count for type across the graphs for isomorphism.

Answer 2

There is a very simple algorithm for determining if two trees are isomorphic:

1. Label the leaves with '01'
2. Label the parents of the leaves with '0' + sorted(labels(children)) + '1'
3. Repeat until you reach the root

Then you compare root labels.