Index: /trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs
===================================================================
--- /trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs	(revision 16282)
+++ /trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs	(revision 16283)
@@ -30,4 +30,6 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
+using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
+
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableClass]
@@ -55,24 +57,38 @@
     }
 
+    #region static methods
+    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
+      return tree.Root.GetSubtree(0).GetSubtree(0);
+    }
+
+    public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
+      return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict);
+    }
+
+    public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
+      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
+      return CalculateSimilarity(n1, n2, strict);
+    }
+
+    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
+      return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict);
+    }
+
+    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
+      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
+      return calculator.ComputeBottomUpMapping(n1, n2);
+    }
+    #endregion
+
     public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      if (t1 == t2)
-        return 1;
-
-      var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
-      var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
-      var map = ComputeBottomUpMapping(actualRoot1, actualRoot2);
-      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
-    }
-
-    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
+      return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map);
+    }
+
+    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) {
       if (t1 == t2) {
         map = null;
         return 1;
       }
-
-      var actualRoot1 = t1.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
-      var actualRoot2 = t2.Root.GetSubtree(0).GetSubtree(0); // skip root and start symbols
-      map = ComputeBottomUpMapping(actualRoot1, actualRoot2);
-
+      map = ComputeBottomUpMapping(t1, t2);
       return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
     }
@@ -95,61 +111,44 @@
     }
 
+    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      return ComputeBottomUpMapping(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0));
+    }
+
     public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
-      var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
       var compactedGraph = Compact(n1, n2);
 
-      var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
-      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
-
-      // visit nodes in order of decreasing height to ensure correct mapping
-      var nodes1 = (List<ISymbolicExpressionTreeNode>)n1.IterateNodesPrefix();
-      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPrefix();
-
-      foreach (var v in nodes1) {
-        if (forwardMap.ContainsKey(v)) {
+      IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) {
+        var subtrees = node.IterateNodesPrefix();
+        return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees;
+      }
+
+      var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first
+      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix();
+
+      var forward = new NodeMap();
+      var reverse = new NodeMap();
+
+      foreach (ISymbolicExpressionTreeNode v in nodes1) {
+        if (forward.ContainsKey(v))
           continue;
+
+        var kv = compactedGraph[v];
+        var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label);
+
+        foreach (ISymbolicExpressionTreeNode w in nodes2) {
+          if (w.GetLength() != kv.Length || w.GetDepth() != kv.Depth || reverse.ContainsKey(w) || compactedGraph[w] != kv)
+            continue;
+
+          // map one whole subtree to the other
+          foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) {
+            forward[t.Item1] = t.Item2;
+            reverse[t.Item2] = t.Item1;
+          }
+
+          break;
         }
-
-        var kv = compactedGraph[v];
-
-        var w = nodes2.Last();
-        int k = nodes2.Count - 1;
-
-        for (int j = 0; j < nodes2.Count; ++j) {
-          var t = nodes2[j];
-
-          if (reverseMap.ContainsKey(t) || kv != compactedGraph[t])
-            continue;
-
-          if (j < k) {
-            w = t;
-            k = j;
-          }
-        }
-
-        if (kv != compactedGraph[w]) {
-          continue;
-        }
-
-        // 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))
-            continue;
-
-          forwardMap[s] = t;
-          reverseMap[t] = s;
-        }
-      }
-
-      return forwardMap;
+      }
+
+      return forward;
     }
 
@@ -167,4 +166,9 @@
       var graph = new List<GraphNode>();
 
+      IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) {
+        var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
+        return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees;
+      }
+
       foreach (var node in nodes) {
         var label = GetLabel(node);
@@ -172,7 +176,5 @@
         if (node.SubtreeCount == 0) {
           if (!labelMap.ContainsKey(label)) {
-            var g = new GraphNode(node, label);
-            graph.Add(g);
-            labelMap[label] = g;
+            labelMap[label] = new GraphNode(node, label);
           }
           nodeMap[node] = labelMap[label];
@@ -182,15 +184,12 @@
           var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
 
-          IEnumerable<GraphNode> vv, ww;
-
-          for (int i = graph.Count - 1; i >= 0; --i) {
-            var w = graph[i];
-
+          var vv = Subtrees(v, commutative);
+
+          foreach (var w in graph) {
             if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) {
               continue;
             }
 
-            vv = commutative ? v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : v.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
-            ww = commutative ? w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]).OrderBy(x => x.Hash) : w.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
+            var ww = Subtrees(w, commutative);
             found = vv.SequenceEqual(ww);
 
@@ -234,13 +233,8 @@
 
       public int Hash { get; }
-
       public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }
-
       public string Label { get; }
-
       public int Depth { get; }
-
       public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
-
       public int Length { get; }
     }
Index: /trunk/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/SymbolicExpressionTreeBottomUpSimilarityCalculatorTest.cs
===================================================================
--- /trunk/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/SymbolicExpressionTreeBottomUpSimilarityCalculatorTest.cs	(revision 16282)
+++ /trunk/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/SymbolicExpressionTreeBottomUpSimilarityCalculatorTest.cs	(revision 16283)
@@ -7,14 +7,13 @@
   [TestClass]
   public class BottomUpSimilarityCalculatorTest {
-    private readonly SymbolicExpressionTreeBottomUpSimilarityCalculator busCalculator;
-    private readonly SymbolicExpressionImporter importer;
+    private readonly SymbolicExpressionTreeBottomUpSimilarityCalculator similarityCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator() { MatchConstantValues = false, MatchVariableWeights = false };
+    private readonly SymbolicExpressionImporter importer = new SymbolicExpressionImporter();
 
-    private const int N = 150;
+    private const int N = 1000;
     private const int Rows = 1;
     private const int Columns = 10;
 
     public BottomUpSimilarityCalculatorTest() {
-      busCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator();
-      importer = new SymbolicExpressionImporter();
+      var parser = new InfixExpressionParser();
     }
 
@@ -23,39 +22,24 @@
     [TestProperty("Time", "short")]
     public void BottomUpTreeSimilarityCalculatorTestMapping() {
-      TestMatchedNodes("(+ 1 2)", "(+ 2 1)", 5);
-      TestMatchedNodes("(- 2 1)", "(- 1 2)", 2);
-      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (+ (variable 1 X2) 1))", 2);
+      TestMatchedNodes("(+ 1 1)", "(+ 2 2)", 0, strict: true);
+      TestMatchedNodes("(+ 1 1)", "(+ 2 2)", 3, strict: false);
+      TestMatchedNodes("(+ 1 1)", "(+ 1 2)", 1, strict: true);
+      TestMatchedNodes("(+ 2 1)", "(+ 1 2)", 3, strict: true);
 
-      TestMatchedNodes("(* (variable 1 X1) (variable 1 X2))", "(* (+ (variable 1 X1) 1) (variable 1 X2))", 2);
+      TestMatchedNodes("(- 1 1)", "(- 2 2)", 0, strict: true);
+      TestMatchedNodes("(- 1 1)", "(- 2 2)", 3, strict: false);
 
-      TestMatchedNodes("(+ (variable 1 a) (variable 1 b))", "(+ (variable 1 a) (variable 1 a))", 1);
-      TestMatchedNodes("(+ (+ (variable 1 a) (variable 1 b)) (variable 1 b))", "(+ (* (+ (variable 1 a) (variable 1 b)) (variable 1 b)) (+ (+ (variable 1 a) (variable 1 b)) (variable 1 b)))", 5);
-
-      TestMatchedNodes(
-        "(* (+ 2.84 (exp (+ (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))) (/ (variable 2.0539 X5) (variable -9.2452e-1 X6))))) 2.9081)",
-        "(* (- (variable 9.581e-1 X6) (+ (- (variable 5.1491e-1 X5) 1.614e+1) (+ (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)) (log (/ (variable 2.0539 X5) (variable -9.2452e-1 X6)))))) 2.9081)",
-        9);
-
-      TestMatchedNodes("(* (* (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x))) (variable 1.68 x)) (* (* (variable 1.68 x) (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x)))) (variable 2.55 x)))", "(* (variable 2.55 x) (* (variable 1.68 x) (* (variable 1.68 x) (* (variable 1.68 x) (variable 2.55 x)))))", 9);
-
-      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);
-
-      const string 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))";
-      const string 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);
-
+      TestMatchedNodes("(- 2 1)", "(- 1 2)", 2, strict: true);
+      TestMatchedNodes("(- 2 1)", "(- 1 2)", 3, strict: false);
     }
 
-    private void TestMatchedNodes(string expr1, string expr2, int expected) {
+    private void TestMatchedNodes(string expr1, string expr2, int expected, bool strict) {
       var t1 = importer.Import(expr1);
       var t2 = importer.Import(expr2);
 
-      var mapping = busCalculator.ComputeBottomUpMapping(t1.Root, t2.Root);
-      var c = mapping.Count;
+      var map = SymbolicExpressionTreeBottomUpSimilarityCalculator.ComputeBottomUpMapping(t1, t2, strict);
 
-      if (c != expected) {
-        throw new Exception("Match count " + c + " is different than expected value " + expected);
+      if (map.Count != expected) {
+        throw new Exception($"Match count {map.Count} is different than expected value {expected} for expressions:\n{expr1} and {expr2} (strict = {strict})");
       }
     }
@@ -77,5 +61,5 @@
       for (int i = 0; i < trees.Length - 1; ++i) {
         for (int j = i + 1; j < trees.Length; ++j) {
-          s += busCalculator.CalculateSimilarity(trees[i], trees[j]);
+          s += similarityCalculator.CalculateSimilarity(trees[i], trees[j]);
         }
       }
