Changeset 17687 for branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching

Timestamp:

07/19/20 19:07:40 (4 years ago)

Author:

fbaching

Message:

#1837: merged changes from trunk

• apply changes from Attic release to all SlidingWindow specific code files (replace StorableClass with StorableType)

Location:

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic

Files:

• . (modified) (1 prop)
• 3.4/TreeMatching (moved) (moved from branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching)
• 3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs) (8 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeEqualityComparer.cs (modified) (2 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeMatching.cs (modified) (4 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeMaxCommonSequenceCalculator.cs (deleted)
• 3.4/TreeMatching/SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator.cs) (3 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeNodeComparer.cs (modified) (2 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs) (2 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeNodeSimilarityComparer.cs (deleted)
• 3.4/TreeMatching/SymbolicExpressionTreePhenotypicSimilarityCalculator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreePhenotypicSimilarityCalculator.cs) (3 diffs)

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
 using System.Globalization;
 using System.Linq;
@@ -29 +28 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Optimization.Operators;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HEAL.Attic;
+
+using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  [StorableClass]
+  [StorableType("63ACB7A4-137F-468F-BE42-A4CA6B62C63B")]
   [Item("SymbolicExpressionTreeBottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
   public class SymbolicExpressionTreeBottomUpSimilarityCalculator : SolutionSimilarityCalculator {
@@ -40 +41 @@
     protected override bool IsCommutative { get { return true; } }
 
+    public bool MatchConstantValues { get; set; }
+    public bool MatchVariableWeights { get; set; }
+
     [StorableConstructor]
-    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
-      : base(deserializing) {
+    protected SymbolicExpressionTreeBottomUpSimilarityCalculator(StorableConstructorFlag _) : base(_) {
     }
 
@@ -53 +56 @@
     }
 
+    #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 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 map = ComputeBottomUpMapping(t1.Root, t2.Root);
-      return 2.0 * map.Count / (t1.Length + t2.Length);
+      }
+      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
     }
 
@@ -78 +110 @@
     }
 
+    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2));
+    }
+
     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 = n1.IterateNodesPrefix().OrderByDescending(x => x.GetDepth()).ToList();
-      var nodes2 = n2.IterateNodesPrefix().ToList();
-      for (int i = 0; i < nodes1.Count; ++i) {
-        var v = nodes1[i];
-        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];
-        ISymbolicExpressionTreeNode w = null;
-        for (int j = 0; j < nodes2.Count; ++j) {
-          var t = nodes2[j];
-          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
+        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;
-          w = t;
+
+          // 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;
         }
-        if (w == null) continue;
-
-        // 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).ToList();
-        var ww = IterateBreadthOrdered(w, comparer).ToList();
-        int len = Math.Min(vv.Count, ww.Count);
-        for (int j = 0; j < len; ++j) {
-          var s = vv[j];
-          var t = ww[j];
-          Debug.Assert(!reverseMap.ContainsKey(t));
-
-          forwardMap[s] = t;
-          reverseMap[t] = s;
-        }
-      }
-
-      return forwardMap;
+      }
+
+      return forward;
     }
 
@@ -132 +161 @@
       var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
       var labelMap = new Dictionary<string, GraphNode>(); // L
-      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
 
       var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
-      var list = new List<GraphNode>();
-      var queue = new Queue<ISymbolicExpressionTreeNode>();
-
-      foreach (var n in nodes) {
-        if (n.SubtreeCount == 0) {
-          var label = GetLabel(n);
+      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);
+
+        if (node.SubtreeCount == 0) {
           if (!labelMap.ContainsKey(label)) {
-            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
-            labelMap[z.Label] = z;
-          }
-          nodeMap[n] = labelMap[label];
-          queue.Enqueue(n);
+            labelMap[label] = new GraphNode(node, label);
+          }
+          nodeMap[node] = labelMap[label];
         } else {
-          childrenCount[n] = n.SubtreeCount;
-        }
-      }
-      while (queue.Any()) {
-        var n = queue.Dequeue();
-        if (n.SubtreeCount > 0) {
+          var v = new GraphNode(node, label);
           bool found = false;
-          var label = n.Symbol.Name;
-          var depth = n.GetDepth();
-
-          bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
-          var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
-          if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
-
-          for (int i = list.Count - 1; i >= 0; --i) {
-            var w = list[i];
-            if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
+          var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
+
+          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;
-
-            // sort V and W when the symbol is commutative because we are dealing with unordered trees
-            var m = w.SymbolicExpressionTreeNode;
-            var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
-            if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
-
-            found = nSubtrees.SequenceEqual(mSubtrees);
+            }
+
+            var ww = Subtrees(w, commutative);
+            found = vv.SequenceEqual(ww);
+
             if (found) {
-              nodeMap[n] = w;
+              nodeMap[node] = w;
               break;
             }
           }
-
           if (!found) {
-            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
-            list.Add(w);
-            nodeMap[n] = w;
+            nodeMap[node] = v;
+            graph.Add(v);
           }
         }
-
-        if (n == n1 || n == n2)
-          continue;
-
-        var p = n.Parent;
-        if (p == null)
-          continue;
-
-        childrenCount[p]--;
-
-        if (childrenCount[p] == 0)
-          queue.Enqueue(p);
-      }
-
+      }
       return nodeMap;
     }
 
-    private IEnumerable<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;
-    }
-
-    private static string GetLabel(ISymbolicExpressionTreeNode node) {
+    private string GetLabel(ISymbolicExpressionTreeNode node) {
       if (node.SubtreeCount > 0)
         return node.Symbol.Name;
 
-      var constant = node as ConstantTreeNode;
-      if (constant != null)
-        return constant.Value.ToString(CultureInfo.InvariantCulture);
-
-      var variable = node as VariableTreeNode;
-      if (variable != null)
-        return variable.Weight + variable.VariableName;
+      if (node is ConstantTreeNode constant)
+        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
+
+      if (node is VariableTreeNode variable)
+        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
 
       return node.ToString();
@@ -232 +221 @@
 
     private class GraphNode {
-      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
-      public string Label;
-      public int Depth;
+      private GraphNode() { }
+
+      public GraphNode(ISymbolicExpressionTreeNode node, string label) {
+        SymbolicExpressionTreeNode = node;
+        Label = label;
+        Hash = GetHashCode();
+        Depth = node.GetDepth();
+        Length = node.GetLength();
+      }
+
+      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; }
     }
   }

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeEqualityComparer.cs

@@ -2 +2 @@
 using System.Collections.Generic;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HEAL.Attic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  [StorableType("535830d4-551e-4b53-97e3-9605bd7e785f")]
   public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
-    public SymbolicExpressionTreeNodeSimilarityComparer SimilarityComparer { get; set; }
+    [Storable]
+    public SymbolicExpressionTreeNodeEqualityComparer SimilarityComparer { get; set; }
+
+
+    [StorableConstructor]
+    protected SymbolicExpressionTreeEqualityComparer(StorableConstructorFlag _) { }
+    public SymbolicExpressionTreeEqualityComparer() { }
 
     public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
       if (SimilarityComparer == null) throw new Exception("SimilarityComparer needs to be initialized first.");
-      return a.Length == b.Length &&
-             SymbolicExpressionTreeMatching.Match(a.Root, b.Root, SimilarityComparer) == Math.Min(a.Length, b.Length);
+      return a.Length == b.Length && SymbolicExpressionTreeMatching.Match(a.Root, b.Root, SimilarityComparer) == Math.Min(a.Length, b.Length);
     }
 
@@ -16 +23 @@
       return (tree.Length << 8) % 12345;
     }
+
   }
 }

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMatching.cs

@@ -1 @@
-using System;
+#region License Information
+
+/* HeuristicLab
+ * Copyright (C) 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;
@@ -7 +30 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public static class SymbolicExpressionTreeMatching {
-    public static bool ContainsSubtree(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+    public static bool ContainsSubtree(this ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeEqualityComparer comparer) {
       return FindMatches(root, subtree, comparer).Any();
     }
-    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeEqualityComparer comparer) {
       return FindMatches(tree.Root, subtree, comparer);
     }
 
-    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeEqualityComparer comp) {
       var fragmentLength = subtree.GetLength();
       // below, we use ">=" for Match(n, subtree, comp) >= fragmentLength because in case of relaxed conditions, 
@@ -29 +52 @@
     /// </summary>
     /// <returns>Number of pairs that were matched</returns>
-    public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
+    public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, ISymbolicExpressionTreeNodeSimilarityComparer comp) {
       if (!comp.Equals(a, b)) return 0;
       int m = a.SubtreeCount;
@@ -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];
+    }
   }
 }

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -25 +25 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Optimization.Operators;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HEAL.Attic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  [StorableClass]
+  [StorableType("2634824A-D8E6-4047-9146-79EDF50BEED8")]
   [Item("SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator", "A similarity calculator based on the size of the maximum common subtree between two trees")]
   public class SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator : SolutionSimilarityCalculator {
@@ -46 +46 @@
 
     [StorableConstructor]
-    protected SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator(bool deserializing) : base(deserializing) { }
+    protected SymbolicExpressionTreeMaxCommonSubtreeSimilarityCalculator(StorableConstructorFlag _) : base(_) { }
 
     public override IDeepCloneable Clone(Cloner cloner) {

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeComparer.cs

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 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 HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HEAL.Attic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  [StorableType("eabf848e-d10c-499e-8c48-c771232ede0e")]
   // this comparer considers that a < b if the type of a is "greater" than the type of b, for example:
   // - A function node is "greater" than a terminal node
@@ -8 +31 @@
   // - used for bringing subtrees to a "canonical" form when the operation allows reordering of arguments
   public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
-    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (!(a is SymbolicExpressionTreeTerminalNode)) {
-        return b is SymbolicExpressionTreeTerminalNode
-          ? -1
-          : string.Compare(a.Symbol.Name, b.Symbol.Name, StringComparison.Ordinal);
-      }
-      if (!(b is SymbolicExpressionTreeTerminalNode)) return 1;
-      // at this point we know a and b are terminal nodes
+    public static int CompareNodes(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      var ta = a as SymbolicExpressionTreeTerminalNode;
+      var tb = b as SymbolicExpressionTreeTerminalNode;
+
+      if (ta == null)
+        return tb == null ? String.CompareOrdinal(a.Symbol.Name, b.Symbol.Name) : -1;
+
+      if (tb == null)
+        return 1;
+
+      // at this point we know a and b are both terminals
       var va = a as VariableTreeNode;
-      if (va != null) {
-        if (b is ConstantTreeNode) return -1;
-        var vb = (VariableTreeNode)b;
-        return (va.VariableName.Equals(vb.VariableName)
-          ? va.Weight.CompareTo(vb.Weight)
-          : string.Compare(va.VariableName, vb.VariableName, StringComparison.Ordinal));
-      }
-      // at this point we know for sure that a is a constant tree node
-      if (b is VariableTreeNode) return 1;
-      var ca = (ConstantTreeNode)a;
-      var cb = (ConstantTreeNode)b;
-      return ca.Value.CompareTo(cb.Value);
+      var vb = b as VariableTreeNode;
+
+      if (va != null)
+        return vb == null ? -1 : CompareVariables(va, vb);
+
+      if (vb != null)
+        return 1;
+
+      // at this point we know a and b are not variables
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+
+      if (ca != null && cb != null)
+        return ca.Value.CompareTo(cb.Value);
+
+      // for other unknown terminal types, compare strings
+      return string.CompareOrdinal(a.ToString(), b.ToString());
+    }
+
+    private static int CompareVariables(VariableTreeNode a, VariableTreeNode b) {
+      int result = string.CompareOrdinal(a.VariableName, b.VariableName);
+      return result == 0 ? a.Weight.CompareTo(b.Weight) : result;
+    }
+
+    public int Compare(ISymbolicExpressionTreeNode x, ISymbolicExpressionTreeNode y) {
+      return CompareNodes(x, y);
     }
   }
+
 }

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeNodeEqualityComparer.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HEAL.Attic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [Item("SymbolicExpressionTreeNodeEqualityComparer", "An operator that checks node equality based on different similarity measures.")]
-  [StorableClass]
+  [StorableType("F5BC06AA-3F08-4692-93E8-E44CE8205A46")]
   public class SymbolicExpressionTreeNodeEqualityComparer : Item, ISymbolicExpressionTreeNodeSimilarityComparer {
     [StorableConstructor]
-    protected SymbolicExpressionTreeNodeEqualityComparer(bool deserializing) : base(deserializing) { }
+    protected SymbolicExpressionTreeNodeEqualityComparer(StorableConstructorFlag _) : base(_) { }
     protected SymbolicExpressionTreeNodeEqualityComparer(SymbolicExpressionTreeNodeEqualityComparer original, Cloner cloner)
       : base(original, cloner) {

branches/1837_Sliding Window GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreePhenotypicSimilarityCalculator.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -26 +26 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Optimization.Operators;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HEAL.Attic;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [Item("SymbolicExpressionTreePhenotypicSimilarityCalculator", "An operator that calculates the similarity betweeon two trees based on the correlation of their outputs.")]
-  [StorableClass]
+  [StorableType("163CE915-506E-472B-B77F-156ECC9D9C05")]
   public class SymbolicExpressionTreePhenotypicSimilarityCalculator : SolutionSimilarityCalculator {
     [Storable]
@@ -40 +40 @@
 
     [StorableConstructor]
-    protected SymbolicExpressionTreePhenotypicSimilarityCalculator(bool deserializing) : base(deserializing) { }
+    protected SymbolicExpressionTreePhenotypicSimilarityCalculator(StorableConstructorFlag _) : base(_) { }
 
     public SymbolicExpressionTreePhenotypicSimilarityCalculator(SymbolicExpressionTreePhenotypicSimilarityCalculator original, Cloner cloner)