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

Timestamp:

07/24/14 23:44:39 (8 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)

File:

• branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs (modified) (5 diffs)

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)) {