Changeset 11594 for branches/Breadcrumbs/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

Timestamp:

11/27/14 11:23:37 (10 years ago)

Author:

jkarder

Message:

#2116: merged r10041-r11593 from trunk into branch

Location:

branches/Breadcrumbs

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs (modified) (2 diffs)

branches/Breadcrumbs

@@ -8 +8 @@
 FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
+Google.ProtocolBuffers-2.4.1.473.dll
 HeuristicLab 3.3.5.1.ReSharper.user
 HeuristicLab 3.3.6.0.ReSharper.user
 HeuristicLab.4.5.resharper.user
 HeuristicLab.ExtLibs.6.0.ReSharper.user
+HeuristicLab.Scripting.Development
 HeuristicLab.resharper.user
 ProtoGen.exe
@@ -17 +19 @@
 _ReSharper.HeuristicLab
 _ReSharper.HeuristicLab 3.3
+_ReSharper.HeuristicLab 3.3 Tests
 _ReSharper.HeuristicLab.ExtLibs
 bin
 protoc.exe
-_ReSharper.HeuristicLab 3.3 Tests
-Google.ProtocolBuffers-2.4.1.473.dll

@@ -8 +8 @@
 FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
+Google.ProtocolBuffers-2.4.1.473.dll
 HeuristicLab 3.3.5.1.ReSharper.user
 HeuristicLab 3.3.6.0.ReSharper.user
 HeuristicLab.4.5.resharper.user
 HeuristicLab.ExtLibs.6.0.ReSharper.user
+HeuristicLab.Scripting.Development
 HeuristicLab.resharper.user
 ProtoGen.exe
@@ -17 +19 @@
 _ReSharper.HeuristicLab
 _ReSharper.HeuristicLab 3.3
+_ReSharper.HeuristicLab 3.3 Tests
 _ReSharper.HeuristicLab.ExtLibs
 bin
 protoc.exe
-_ReSharper.HeuristicLab 3.3 Tests
-Google.ProtocolBuffers-2.4.1.473.dll

branches/Breadcrumbs/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

@@ -1 @@
-using System;
+#region License Information
+
+/* HeuristicLab
+ * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#endregion
+
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -45 +68 @@
       return matrix[m, n] + 1;
     }
+
+    /// <summary>
+    /// Calculates the difference between two symbolic expression trees.
+    /// </summary>
+    /// <param name="tree">The first symbolic expression tree</param>
+    /// <param name="other">The second symbolic expression tree</param>
+    /// <returns>Returns the root of the subtree (from T1) by which T1 differs from T2, or null if no difference is found.</returns>
+    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTree tree, ISymbolicExpressionTree other) {
+      return Difference(tree.Root, other.Root);
+    }
+
+    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) {
+      var a = node.IterateNodesPrefix().ToList();
+      var b = other.IterateNodesPrefix().ToList();
+      var list = new List<ISymbolicExpressionTreeNode>();
+      for (int i = 0, j = 0; i < a.Count && j < b.Count; ++i, ++j) {
+        var s1 = a[i].ToString();
+        var s2 = b[j].ToString();
+        if (s1 == s2) continue;
+        list.Add(a[i]);
+        // skip subtrees since the parents are already different
+        i += a[i].SubtreeCount;
+        j += b[j].SubtreeCount;
+      }
+      ISymbolicExpressionTreeNode result = list.Count > 0 ? LowestCommonAncestor(node, list) : null;
+      return result;
+    }
+
+    private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
+      if (nodes.Count == 0)
+        throw new ArgumentException("The nodes list should contain at least one element.");
+
+      if (nodes.Count == 1)
+        return nodes[0];
+
+      int minLevel = nodes.Min(x => root.GetBranchLevel(x));
+
+      // bring the nodes in the nodes to the same level (relative to the root)
+      for (int i = 0; i < nodes.Count; ++i) {
+        var node = nodes[i];
+        var level = root.GetBranchLevel(node);
+        for (int j = minLevel; j < level; ++j)
+          node = node.Parent;
+        nodes[i] = node;
+      }
+
+      // while not all the elements in the nodes are equal, go one level up
+      while (nodes.Any(x => x != nodes[0])) {
+        for (int i = 0; i < nodes.Count; ++i)
+          nodes[i] = nodes[i].Parent;
+      }
+
+      return nodes[0];
+    }
   }
 }

@@ -8 +8 @@
 FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
+Google.ProtocolBuffers-2.4.1.473.dll
 HeuristicLab 3.3.5.1.ReSharper.user
 HeuristicLab 3.3.6.0.ReSharper.user
 HeuristicLab.4.5.resharper.user
 HeuristicLab.ExtLibs.6.0.ReSharper.user
+HeuristicLab.Scripting.Development
 HeuristicLab.resharper.user
 ProtoGen.exe
@@ -17 +19 @@
 _ReSharper.HeuristicLab
 _ReSharper.HeuristicLab 3.3
+_ReSharper.HeuristicLab 3.3 Tests
 _ReSharper.HeuristicLab.ExtLibs
 bin
 protoc.exe
-_ReSharper.HeuristicLab 3.3 Tests
-Google.ProtocolBuffers-2.4.1.473.dll