Opened 10 years ago
Closed 10 years ago
#2313 closed defect (done)
The bottom-up tree tree mapping sometimes maps too many nodes
Reported by: | bburlacu | Owned by: | mkommend |
---|---|---|---|
Priority: | medium | Milestone: | HeuristicLab 3.3.11 |
Component: | Problems.DataAnalysis.Symbolic | Version: | 3.3.10 |
Keywords: | Cc: |
Description
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:1 Changed 10 years ago by bburlacu
- Status changed from new to accepted
comment:2 Changed 10 years ago by bburlacu
comment:3 Changed 10 years ago by bburlacu
- Owner changed from bburlacu to mkommend
- Status changed from accepted to reviewing
comment:4 Changed 10 years ago by mkommend
- Status changed from reviewing to readytorelease
comment:5 Changed 10 years ago by jkarder
- Resolution set to done
- Status changed from readytorelease to closed
r11978: