Changeset 11225

Timestamp:

07/24/14 23:44:39 (10 years ago)

Author:

bburlacu

Message:

#2215: Fixed a couple of bugs in the BottomUpSimilarityCalculator:

• the child sequences of matching nodes were not sorted in the same way (one was using StringComparison.Ordinal, the other the default)
• when creating the mapping it is necessary to walk the nodes of the first tree in decreasing height order (not level-order as the author claims)

Location:

branches/HeuristicLab.BottomUpTreeDistance

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs (modified) (5 diffs)
• HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs (modified) (1 diff)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

@@ -77 +77 @@
       var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
 
-      foreach (var v in IterateBreadthOrdered(n1)) {
-        if (forwardMap.ContainsKey(v)) continue;
+      // visit nodes in order of decreasing height to ensure correct mapping
+      foreach (var v in n1.IterateNodesPrefix().OrderByDescending(x => compactedGraph[x].Weight)) {
+        if (forwardMap.ContainsKey(v))
+          continue;
         var kv = compactedGraph[v];
         ISymbolicExpressionTreeNode w = null;
-        foreach (var t in IterateBreadthOrdered(n2)) {
-          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv) continue;
+        foreach (var t in n2.IterateNodesPrefix()) {
+          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
+            continue;
           w = t;
           break;
@@ -96 +99 @@
           var s = eV.Current;
           var t = eW.Current;
-          if (reverseMap.ContainsKey(t))
-            throw new Exception("Mapping already present");
+
+          if (reverseMap.ContainsKey(t)) {
+            throw new Exception("A mapping to this node already exists.");
+          }
+
           forwardMap[s] = t;
           reverseMap[t] = s;
@@ -124 +130 @@
         if (n.SubtreeCount == 0) {
           var label = n.ToString();
-          var z = new Vertex { Content = n, Label = label };
-          labelsToVertices[z.Label] = z;
-          vertices.Add(z);
+          if (!labelsToVertices.ContainsKey(label)) {
+            var z = new Vertex { Content = n, Label = label };
+            labelsToVertices[z.Label] = z;
+            vertices.Add(z);
+          }
+          nodesToVertices[n] = labelsToVertices[label];
           queue.Enqueue(n);
         } else {
@@ -135 +144 @@
       while (queue.Any()) {
         var v = queue.Dequeue();
-        string label;
-        if (v.SubtreeCount == 0) {
-          label = v.ToString();
-          nodesToVertices[v] = labelsToVertices[label]; // 18
-        } else {
-          label = v.Symbol.Name;
+
+        if (v.SubtreeCount > 0) {
+          var label = v.Symbol.Name;
           bool found = false;
           var height = v.GetDepth();
@@ -152 +158 @@
             var w = vertices[i];
             var n = (ISymbolicExpressionTreeNode)w.Content;
-            if (n.SubtreeCount == 0) continue; // v is a function node so w will have to be a function node as well
-            if (height != (int)w.Weight || v.SubtreeCount != n.SubtreeCount || label != w.Label)
+            if (v.SubtreeCount != n.SubtreeCount || label != w.Label || height != (int)w.Weight)
               continue;
 
             // sort V and W when the symbol is commutative because we are dealing with unordered trees
-            var wSubtrees = sort ? w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label)
-                                 : w.OutArcs.Select(x => x.Target);
+            var wSubtrees = n.Subtrees.Select(x => nodesToVertices[x]).ToList();
+            if (sort) wSubtrees.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
 
             if (vSubtrees.SequenceEqual(wSubtrees)) {

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpSimilarityCalculatorTest.cs

@@ -46 +46 @@
       TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ -4.3072 (variable 2.4691 X7)) (exp 2.1033)))", 6);
       TestMatchedNodes("(+ (exp 2.1033) (/ -4.3072 (variable 2.4691 X7)))", "(/ 1 (+ (/ (variable 2.4691 X7) -4.3072) (exp 2.1033)))", 4);
+
+      var expr1 = "(* (- 1.2175e+1 (+ (/ (exp -1.4134e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (log 1.3011e+1))";
+      var expr2 = "(* (- 1.2175e+1 (+ (/ (/ (+ (variable 3.0140 X9) (variable 1.3430 X8)) -1.0864e+1) (exp 9.2013)) (exp (log (exp (/ (exp (- (* -4.2461 (variable 2.2634 X5)) (- -9.6267e-1 3.3243))) (- (/ (/ (variable 1.0883 X1) (variable 6.9620e-1 X2)) (log 1.3011e+1)) (variable -4.3098e-1 X7)))))))) (exp (variable 4.0899e-1 X7)))";
+
+      TestMatchedNodes(expr1, expr2, 23);
+
     }