Opened 3 years ago

Closed 3 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 3 years ago by bburlacu

  • Status changed from new to accepted

comment:2 Changed 3 years ago by bburlacu

r11978:

  • Order nodes in the first tree by decreasing depth when doing the mapping (after the two trees have already been compacted into a directed acyclic graph and the isomorphic subtrees have already been identified).
  • Update unit test with the test case that helped identify this bug
  • Minor changes: rename Label method to GetLabel and make it static, update year in license header

comment:3 Changed 3 years ago by bburlacu

  • Owner changed from bburlacu to mkommend
  • Status changed from accepted to reviewing

comment:4 Changed 3 years ago by mkommend

  • Status changed from reviewing to readytorelease

comment:5 Changed 3 years ago by jkarder

  • Resolution set to done
  • Status changed from readytorelease to closed

r11986: merged r11978 into stable

Note: See TracTickets for help on using tickets.