0

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.

7
  • When you speak about subgraph, you think about a connected component, or not necessarily ? I'm not sure a traversal would find all subgraphes. If you imagine a graph with two disconnected triangles, you'd have many, many isomorphic subgraphs: One node, one edge, an edge and a node, two disconnected edges, two connected edges, two connected edges and a node, two connected edges and an edge, a full triangle... intuitively I smell output size could even be NP, so I think you do have some more requirements that aren't explicit
    – Arthur Hv
    Oct 6 '20 at 12:03
  • Good point. I'm happy to just find (one of) the largest ones in that case, so there would only be one match between two isomorphic triangles. I'm aiming for reduplication here, so the larger the better, and the faster the better. Oct 6 '20 at 12:17
  • To expand upon what @ArthurHv points out, take the (unlabelled) graph. A->B->C->D->A. What are the duplicate subgraphs, if any, in that example? I think I understand what you wish to do for a tree but it's not clear in general.
    – JimmyJames
    Oct 6 '20 at 14:28
  • It's a typo. Fixed it. Editing the question to clarify what counts as a duplicate subgraph. Oct 6 '20 at 16:57
  • Is the input graph acyclic or can there be cycles?
    – Jasmijn
    Oct 6 '20 at 17:20
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.