Changeset 11212 for branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs

Timestamp:

07/22/14 01:54:47 (10 years ago)

Author:

bburlacu

Message:

#2215: Realized that "Height" in the paper might actually refer to the subtree depth (and not it's level in the tree). Changed code according to this interpretation as it makes more sense and seems to produce the correct results.

File:

• branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs (modified) (2 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs

@@ -128 +128 @@
           for (int i = vertices.Count - 1; i >= 0; --i) {
             var w = vertices[i];
-            // removed requirement for heights to be equal since a compacted dag should not care about heights
-            // this ensures correct behavior when isomorphic subtrees are placed at different depths. 
-            // furthermore, if the nodes have the same labels and the same subtrees then that should be sufficient,
-            // since in the bottom-up approach we are guaranteed that no differences would occur on the lower levels
-            if (v.SubtreeCount != w.OutDegree || label != w.Label)
+            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || label != w.Label)
               continue;
 
@@ -192 +188 @@
 
     private static int Height(IVertex v) {
-      return Height((ISymbolicExpressionTreeNode)v.Content);
+      return ((ISymbolicExpressionTreeNode)v.Content).GetDepth();
     }
 
     private static int Height(ISymbolicExpressionTreeNode n) {
-      var p = n;
-      while (p.Parent != null)
-        p = p.Parent;
-      return p.GetBranchLevel(n);
+      return n.GetDepth();
     }