Find duplicate subgraphs in directed graph?

Question

Is there a good way to search for duplicate subgraphs in an immutable directed graph, where edges and nodes may be labeled?

I was thinking I could try to name the nodes according to their position in the graph, but that isn't trivial when you have loops.

Comparing the two subgraphs arising from two different nodes should be as easy as walking the graph from each, comparing the node and edge labels as we go. This would be O(n^2 * n*e) for walking the graph from all pairs of starting nodes. I bet there's a faster way, since for each step in the walk, we're solving the same problem on from the point of view of another node, so dynamic programming springs to mind.

Maybe O(n^2) is doable, but is there an even faster way, like linear time or n log n? How fast could the algorithm possibly be?

EDIT:

Why?
I'm looking to deduplicate a directed graph. You can think of it as a more general case of finding overlapping subtrees in a tree and removing them by turning the tree into the corresponding deduplicated directed acyclic graph. This would of course save storage space.

What's a duplicate subgraph?
If there are two nodes A and B such that the set of all nodes and edges which are transitively reachable from A, including labels, match the corresponding set for node B, and the label on A and B are equal, then A and B are equal. We can then move all incoming edges for A to instead point to B, and then remove any unreachable nodes from the graph.

Answer 1

With those rules in effect, all nodes in a cycle reduce to one node.

Which implies you are looking for an algorithm to produce a tree from the graph.

---

Look for all terminal nodes. Group by label and reduce them down to a single node. These are your irreducible sub-trees.

Find the roots of each terminal and irreducible sub-tree (can be done one sub-tree at a time). Exclude if the node is already an irreducible sub-tree, or if one of its out edges points does not point to an irreducible sub-tree. Group it with every other node pointing to the same irreducible set of sub-trees, including the label information into the grouping. Replace each group with a single node. That node is the root of a new irreducible sub-tree. (The groups can be reduced after investigating the incoming nodes of a given irreducible sub-tree).

Repeat the above for each irreducible sub-tree that was discovered till all have been investigated.

Now go through the list again and grab each node that is not listed as a root of an irreducible tree. These nodes are part of at least one cycle. If there were none stop now, we are done.

Pick a node from the unreduced and walk till a cycle is detected. This can be done by keeping a stack, and set structure. The set will tell you if the node has been visited before, the stack will allow you to close the cycle.

Once a cycle is detected pop each node off the stack till you pop off the already visited node. Reduce all of these popped nodes down to a single node. If this reduced node has an out edge to unreduced node, keep walking to find the next cycle. Otherwise pop off the next node.

Keep poping nodes off till one of them has an unexplored unreduced node (look for unreduced nodes that aren't in the explored set). Push that nodes onto the stack, and into the set and keep looking for cycles as above.

If the stack empties while walking back, select an unexplored and unreduced node. Keep the set as is, it isn't possible to have a cycle with any of these nodes (otherwise this node would have been discovered when walking from them).

Once all nodes have been explored for cycles, loop back to top and keep reducing the trees.

---

You could place the cycle reduction first, but it probably isn't a good strategy.

• Graphs produced by this process are trees
• Trees have no cycles
• There is a good chance that this code will continually encounter trees.