How to convert a directed graph to its most minimal form?

Question

I'm dealing with rooted, directed, potentially cyclic graphs. Each vertex in the graph has a label, which might or might not be unique. Edges do not have labels. The graph has a designated root vertex from which every vertex is reachable. The order of the edges outgoing from a vertex is relevant.

For my purposes, a vertex is equal to another vertex if they share the same label, and if their outgoing edges are also considered equal (and are in the same order). Two edges are equal if they have the same direction and if the vertices at their corresponding ends are equal.

Because of the equality rules above, a graph can contain multiple "sections" that are effectively equal. For example, in the graph below, there are two isomorphic sections containing vertices with labels {1, 2, 3, 4}. The root of the graph is vertex 0.

_{(source: graphonline.ru)}

I need to be able to identify sections that are identical, and then remove all duplication, without changing the "meaning" of the graph (with regard to the equality rules above). Using the above example as input, I need to produce this:

_{(source: graphonline.ru)}

Is there a known way of doing this within polynomial time?

Answer 1

The solution that ended up working was to essentially run the recursive equality check against every pair of vertices with the same label.

1. Let S = all pairs of vertices with the same label
2. For each s in S:
   1. Compare the two vertices a and b in s by recursively comparing their children
   2. If they compare as equal, take all edges in the graph pointing to b, and point them to a instead