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?
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.