Changeset 16279 for trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching

Timestamp:

11/06/18 15:41:13 (6 years ago)

Author:

bburlacu

Message:

#2959: Simplify code, improve performance, fix another potential bug in relation with 3).

File:

• trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs (modified) (3 diffs)

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

@@ -132 +132 @@
         }
 
-        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly
-        // (as in the paper) because the trees are unordered (subtree order might differ). the solution is 
-        // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)
-        // while iterating over the two subtrees
-        var vv = IterateBreadthOrdered(v, comparer);
-        var ww = IterateBreadthOrdered(w, comparer);
-        int len = Math.Min(vv.Count, ww.Count);
-        for (int j = 0; j < len; ++j) {
-          var s = vv[j];
-          var t = ww[j];
+        // at this point we know that v and w are isomorphic (same length and depth) 
+        // however, the mapping cannot be done directly (as in the paper) 
+        // because the trees are unordered (subtree order might differ). 
+        // the solution is to sort once again (this will work because the subtrees are isomorphic!)
+        var vv = v.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash);
+        var ww = w.IterateNodesPrefix().OrderBy(x => compactedGraph[x].Hash);
+
+        foreach (var pair in vv.Zip(ww, Tuple.Create)) {
+          var s = pair.Item1;
+          var t = pair.Item2;
 
           if (reverseMap.ContainsKey(t))
@@ -152 +152 @@
 
       return forwardMap;
-    }
-
-    private List<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
-      var list = new List<ISymbolicExpressionTreeNode> { node };
-      int i = 0;
-      while (i < list.Count) {
-        var n = list[i];
-        if (n.SubtreeCount > 0) {
-          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
-          list.AddRange(subtrees);
-        }
-        i++;
-      }
-      return list;
     }
 
@@ -177 +163 @@
       var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
       var labelMap = new Dictionary<string, GraphNode>(); // L
-      var comparer = new SymbolicExpressionTreeNodeComparer();
 
       var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F