The bottom-up tree tree mapping sometimes maps too many nodes
|Reported by:||bburlacu||Owned by:||mkommend|
Sometimes a subtree from the first subtree is mapped to an isomorphic subtree from the second subtree, but then another larger mapping is found which overlaps on the previous mapping (leaving nodes that are mapped twice).
The necessary thing to avoid this bug is to walk the nodes of the first subtree in the order of decreasing depth (so that the largest isomorphic subtree is found first). From the paper: "every largest unmapped subtree of T1 isomorphic to a subtree of T2 will be found during a level-order traversal of T1", where level order does not mean breadth traversal but "order of decreasing depth (how many levels does a subtree have)".
Change History (5)
comment:3 Changed 2 years ago by bburlacu
- Owner changed from bburlacu to mkommend
- Status changed from accepted to reviewing