directed graphs with a given root node - match another directed graph for equality

Question

There is a directed graph having a single designated node called root from which all other nodes are reachable. Each terminal node (no outgoing edges) takes an string value. Intermediate nodes have one or more outgoing edges but no value associated with them. Edges connecting a node to its neighbor have a string label. The labels for edges emanating from a single node are unique. There could be possible cycles in the graph!

What is the best graph algorithm for checking if two such directed (possibly having cycles) graphs (as described above) are equal?

Answer 1

The graph isomorphism problem is one of the more intriguing problems in TCS. There is an entire page dedicated to it on the wiki.

In your particular case you have two rooted directed graph with a source and a sink.

You could start two BFS in parallel, and check for isomorphism level by level; i.e. levelize the graph and check whether the subset of nodes at each level are isomorphic across the two graphs.

Note that since you have a Directed, Rooted graph you should still be able to levelize it for the purpose of finding isomorphism. Do not enque nodes already visited during the BFS; i.e. levelize using the shortest path to the node from the root when determining the level to group in.

Within a set the comparison should be relatively easy. You have many properties to distinguish nodes at the same level (degree, labels) and should be able to create suitable signatures to sort them. Since you are looking for perfect isomorphism, you should get an exact match.