Changeset 16304 for branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

11/19/18 14:34:25 (5 years ago)

Author:

lkammere

Message:

#2915: Merge changes in the trunk to current HEAD into the branch.

Location:

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic

Files:

• . (modified) (1 prop)
• 3.4/Analyzers/SymbolicDataAnalysisBuildingBlockAnalyzer.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisBuildingBlockAnalyzer.cs)
• 3.4/Converters/DerivativeCalculator.cs (modified) (9 diffs)
• 3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs)
• 3.4/Hashing/HashExtensions.cs (modified) (9 diffs)
• 3.4/Hashing/HashUtil.cs (modified) (8 diffs)
• 3.4/Hashing/SymbolicExpressionTreeHash.cs (modified) (6 diffs)
• 3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (4 diffs)
• 3.4/Interpreter/BatchInstruction.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchInstruction.cs)
• 3.4/Interpreter/BatchOperations.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchOperations.cs)
• 3.4/Interpreter/SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs)
• 3.4/Interpreter/SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs)
• 3.4/Plugin.cs.frame (modified) (1 diff)
• 3.4/SymbolicDataAnalysisModel.cs (modified) (3 diffs)
• 3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs (modified) (7 diffs)
• 3.4/packages.config (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/packages.config)

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -27 +28 @@
   public static class DerivativeCalculator {
     public static ISymbolicExpressionTree Derive(ISymbolicExpressionTree tree, string variableName) {
+      if (tree.Root.SubtreeCount != 1)
+        throw new NotImplementedException("Derive is not implemented for symbolic expressions with automatically defined functions (ADF)");
+      if (tree.Root.GetSubtree(0).SubtreeCount != 1)
+        throw new NotImplementedException("Derive is not implemented for multi-variate symbolic expressions");
       var mainBranch = tree.Root.GetSubtree(0).GetSubtree(0);
       var root = new ProgramRootSymbol().CreateTreeNode();
       root.AddSubtree(new StartSymbol().CreateTreeNode());
       var dTree = TreeSimplifier.GetSimplifiedTree(Derive(mainBranch, variableName));
-      // var dTree = Derive(mainBranch, variableName);
+      //var dTree = Derive(mainBranch, variableName);
       root.GetSubtree(0).AddSubtree(dTree);
       return new SymbolicExpressionTree(root);
     }
 
-    private static Constant constantSy = new Constant();
-    private static Addition addSy = new Addition();
-    private static Subtraction subSy = new Subtraction();
-    private static Multiplication mulSy = new Multiplication();
-    private static Division divSy = new Division();
+    private static readonly Constant constantSy = new Constant();
+    private static readonly Addition addSy = new Addition();
+    private static readonly Subtraction subSy = new Subtraction();
+    private static readonly Multiplication mulSy = new Multiplication();
+    private static readonly Division divSy = new Division();
+    private static readonly Cosine cosSy = new Cosine();
+    private static readonly Square sqrSy = new Square();
 
     public static ISymbolicExpressionTreeNode Derive(ISymbolicExpressionTreeNode branch, string variableName) {
@@ -85 +92 @@
           }
           return fgPrime;
-        } else throw new ArgumentException();
+        } else
+          // multiplication with only one argument has no effect -> derive the argument
+          return Derive(branch.GetSubtree(0), variableName);
       }
       if (branch.Symbol is Division) {
@@ -95 +104 @@
           sqrNode.AddSubtree(g);
           return Div(gPrime, sqrNode);
-        } else if (branch.SubtreeCount == 2) {
+        } else {
+          // for two subtrees:
+          // (f/g)' = (f'g - fg')/g²
+
+          // if there are more than 2 subtrees
+          // div(x,y,z) is interpretered as (x/y)/z
+          // which is the same as x / (y*z)
+
+          // --> make a product of all but the first subtree and differentiate as for the 2-argument case above
           var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
-          var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone();
+          var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));
           var fprime = Derive(f, variableName);
           var gprime = Derive(g, variableName);
-          var sqrNode = new Square().CreateTreeNode();
-          sqrNode.AddSubtree((ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone());
-          return Div(Subtract(Product(fprime, g), Product(f, gprime)), sqrNode);
-        } else throw new NotSupportedException();
+          var gSqr = Square(g);
+          return Div(Subtract(Product(fprime, g), Product(f, gprime)), gSqr);
+        }
       }
       if (branch.Symbol is Logarithm) {
@@ -113 +129 @@
         return Product(f, Derive(branch.GetSubtree(0), variableName));
       }
-      if(branch.Symbol is Square) {
+      if (branch.Symbol is Square) {
         var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
         return Product(Product(CreateConstant(2.0), f), Derive(f, variableName));
-      }     
-      if(branch.Symbol is SquareRoot) {
+      }
+      if (branch.Symbol is SquareRoot) {
         var f = (ISymbolicExpressionTreeNode)branch.Clone();
         var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
@@ -133 +149 @@
         sin.AddSubtree(u);
         return Product(CreateConstant(-1.0), Product(sin, Derive(u, variableName)));
+      }
+      if (branch.Symbol is Tangent) {
+        // tan(x)' = 1 / cos²(x)
+        var fxp = Derive(branch.GetSubtree(0), variableName);
+        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
+        return Div(fxp, Square(Cosine(u)));
       }
       throw new NotSupportedException(string.Format("Symbol {0} is not supported.", branch.Symbol));
@@ -144 +166 @@
       return product;
     }
+    private static ISymbolicExpressionTreeNode Product(IEnumerable<ISymbolicExpressionTreeNode> fs) {
+      var product = mulSy.CreateTreeNode();
+      foreach (var f in fs) product.AddSubtree(f);
+      return product;
+    }
     private static ISymbolicExpressionTreeNode Div(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
       var div = divSy.CreateTreeNode();
@@ -163 +190 @@
       return sum;
     }
-                          
+    private static ISymbolicExpressionTreeNode Cosine(ISymbolicExpressionTreeNode f) {
+      var cos = cosSy.CreateTreeNode();
+      cos.AddSubtree(f);
+      return cos;
+    }
+    private static ISymbolicExpressionTreeNode Square(ISymbolicExpressionTreeNode f) {
+      var sqr = sqrSy.CreateTreeNode();
+      sqr.AddSubtree(f);
+      return sqr;
+    }
+
     private static ISymbolicExpressionTreeNode CreateConstant(double v) {
       var constNode = (ConstantTreeNode)constantSy.CreateTreeNode();
@@ -186 +223 @@
           !(n.Symbol is Sine) &&
           !(n.Symbol is Cosine) &&
+          !(n.Symbol is Tangent) &&
           !(n.Symbol is StartSymbol)
         select n).Any();

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -32 +32 @@
 
       public bool Enabled;
-      public int HashValue;           // the initial (fixed) hash value for this individual node/data
-      public int CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
+      public ulong HashValue;           // the initial (fixed) hash value for this individual node/data
+      public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
 
       public Action<HashNode<T>[], int> Simplify;
       public IComparer<T> Comparer;
 
-      public bool IsChild => Arity == 0;
+      public bool IsLeaf => Arity == 0;
 
       public HashNode(IComparer<T> comparer) {
@@ -67 +67 @@
 
       public override int GetHashCode() {
-        return CalculatedHashValue;
+        return (int)CalculatedHashValue;
       }
 
@@ -79 +79 @@
     }
 
-    public static int ComputeHash<T>(this HashNode<T>[] nodes, int i) where T : class {
+    public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {
       var node = nodes[i];
-      var hashes = new int[node.Arity + 1];
-      int idx = 0;
-      foreach (int c in nodes.IterateChildren(i)) {
-        hashes[idx++] = nodes[c].CalculatedHashValue;
-      }
-      hashes[idx] = node.HashValue;
-      return HashUtil.JSHash(hashes);
-    }
-
-    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes) where T : class {
-      var reduced = nodes.Reduce();
-      reduced.Sort();
+      const int size = sizeof(ulong);
+      var hashes = new ulong[node.Arity + 1];
+      var bytes = new byte[(node.Arity + 1) * size];
+
+      for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) {
+        hashes[k] = nodes[j].CalculatedHashValue;
+      }
+      hashes[node.Arity] = node.HashValue;
+      Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);
+      return hashFunction(bytes);
+    }
+
+    // set the enabled state for the whole subtree rooted at this node 
+    public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {
+      nodes[i].Enabled = enabled;
+      for (int j = i - nodes[i].Size; j < i; ++j)
+        nodes[j].Enabled = enabled;
+    }
+
+    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
+      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
 
       for (int i = 0; i < reduced.Length; ++i) {
         var node = reduced[i];
-        if (node.IsChild) {
+        if (node.IsLeaf) {
           continue;
         }
@@ -117 +126 @@
         }
       }
-      simplified.UpdateNodeSizes();
-      simplified.Sort();
-      return simplified;
-    }
-
-    public static void Sort<T>(this HashNode<T>[] nodes) where T : class {
+      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
+    }
+
+    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
+      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
+
       for (int i = 0; i < nodes.Length; ++i) {
         var node = nodes[i];
 
-        if (node.IsChild) {
+        if (node.IsLeaf) {
           continue;
         }
@@ -138 +147 @@
           } else { // i have some non-terminal children
             var sorted = new HashNode<T>[size];
-            var indices = nodes.IterateChildren(i);
-            Array.Sort(indices, (a, b) => nodes[a].CompareTo(nodes[b]));
+            var indices = new int[node.Arity];
+            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
+              indices[k] = j;
+            }
+            Array.Sort(indices, sort);
 
             int idx = 0;
             foreach (var j in indices) {
               var child = nodes[j];
-              if (!child.IsChild) { // must copy complete subtree
+              if (!child.IsLeaf) { // must copy complete subtree
                 Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
                 idx += child.Size;
@@ -153 +165 @@
           }
         }
-        node.CalculatedHashValue = nodes.ComputeHash(i);
-      }
+        node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);
+      }
+      return nodes;
     }
 
     /// <summary>
-    /// Get a function node's child indices from left to right
+    /// Get a function node's child indicest
     /// </summary>
-    /// <typeparam name="T"></typeparam>
-    /// <param name="nodes"></param>
-    /// <param name="i"></param>
+    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
+    /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
+    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
     /// <returns>An array containing child indices</returns>
     public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
@@ -170 +183 @@
       var idx = i - 1;
       for (int j = 0; j < arity; ++j) {
-        while (!nodes[idx].Enabled) { --idx; } // skip nodes possibly disabled by simplification
         children[j] = idx;
         idx -= 1 + nodes[idx].Size;
@@ -177 +189 @@
     }
 
-    public static void UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
+    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
       for (int i = 0; i < nodes.Length; ++i) {
         var node = nodes[i];
-        if (node.IsChild) {
+        if (node.IsLeaf) {
           node.Size = 0;
           continue;
         }
         node.Size = node.Arity;
-        foreach (int j in nodes.IterateChildren(i)) {
+
+        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
           node.Size += nodes[j].Size;
         }
       }
-    }
-
-    /// <summary>
-    /// Reduce nodes of the same type according to arithmetic rules
-    /// </summary>
-    /// <typeparam name="T"></typeparam>
-    /// <param name="g">The given grammar (controls symbol arities)</param>
-    /// <param name="nodes">The node array</param>
-    /// <param name="i">Parent index</param>
-    /// <param name="j">Child index</param>
-    private static void Reduce<T>(this HashNode<T>[] nodes, int i, int j) where T : class {
-      var p = nodes[i]; // parent node
-      var c = nodes[j]; // child node
-
-      if (c.IsChild)
-        return;
-
-      foreach (int k in nodes.IterateChildren(j)) {
-        if (nodes[k].IsChild) continue;
-        nodes.Reduce(j, k);
-      }
-
-      // handle commutative symbols (add, mul) 
-      if (p.IsCommutative && p.HashValue == c.HashValue) {
-        c.Enabled = false;
-        p.Arity += c.Arity - 1;
-      }
-    }
-
-    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
-      nodes.UpdateNodeSizes();
-      int i = nodes.Length - 1;
-      foreach (int c in nodes.IterateChildren(i)) {
-        if (nodes[c].IsChild) continue;
-        nodes.Reduce(i, c);
-      }
+      return nodes;
+    }
+
+    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
       int count = 0;
-      foreach (var node in nodes) {
-        if (!node.Enabled) { ++count; }
+      for (int i = 0; i < nodes.Length; ++i) {
+        var node = nodes[i];
+        if (node.IsLeaf || !node.IsCommutative) {
+          continue;
+        }
+
+        var arity = node.Arity;
+        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
+          if (node.HashValue == nodes[j].HashValue) {
+            nodes[j].Enabled = false;
+            node.Arity += nodes[j].Arity - 1;
+            ++count;
+          }
+        }
       }
       if (count == 0)
@@ -233 +226 @@
 
       var reduced = new HashNode<T>[nodes.Length - count];
-      i = 0;
+      var idx = 0;
       foreach (var node in nodes) {
-        if (node.Enabled) { reduced[i++] = node; }
-      }
-      reduced.UpdateNodeSizes();
-      return reduced;
+        if (node.Enabled) { reduced[idx++] = node; }
+      }
+      return reduced.UpdateNodeSizes();
     }
   }

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs

@@ -20 +20 @@
 #endregion
 
+
 using System;
 using System.Security.Cryptography;
@@ -28 +29 @@
 
     // A simple hash function from Robert Sedgwicks Algorithms in C book.I've added some simple optimizations to the algorithm in order to speed up its hashing process. 
-    public static int RSHash(int[] input) {
+    public static ulong RSHash(byte[] input) {
       const int b = 378551;
-      int a = 63689;
-      int hash = 0;
+      ulong a = 63689;
+      ulong hash = 0;
 
       foreach (var v in input) {
@@ -41 +42 @@
 
     // A bitwise hash function written by Justin Sobel
-    public static int JSHash(int[] input) {
-      int hash = 1315423911;
+    public static ulong JSHash(byte[] input) {
+      ulong hash = 1315423911;
       for (int i = 0; i < input.Length; ++i)
         hash ^= (hash << 5) + input[i] + (hash >> 2);
@@ -49 +50 @@
 
     // This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language". It is a simple hash function using a strange set of possible seeds which all constitute a pattern of 31....31...31 etc, it seems to be very similar to the DJB hash function. 
-    public static int BKDRHash(int[] input) {
-      const int seed = 131;
-      int hash = 0;
+    public static ulong BKDRHash(byte[] input) {
+      ulong seed = 131;
+      ulong hash = 0;
       foreach (var v in input) {
         hash = (hash * seed) + v;
@@ -59 +60 @@
 
     // This is the algorithm of choice which is used in the open source SDBM project. The hash function seems to have a good over-all distribution for many different data sets. It seems to work well in situations where there is a high variance in the MSBs of the elements in a data set. 
-    public static int SDBMHash(int[] input) {
-      int hash = 0;
+    public static ulong SDBMHash(byte[] input) {
+      ulong hash = 0;
       foreach (var v in input) {
         hash = v + (hash << 6) + (hash << 16) - hash;
@@ -68 +69 @@
 
     // An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published. 
-    public static int DJBHash(int[] input) {
-      int hash = 5381;
+    public static ulong DJBHash(byte[] input) {
+      ulong hash = 5381;
       foreach (var v in input) {
         hash = (hash << 5) + hash + v;
@@ -77 +78 @@
 
     // An algorithm proposed by Donald E.Knuth in The Art Of Computer Programming Volume 3, under the topic of sorting and search chapter 6.4. 
-    public static int DEKHash(int[] input) {
-      int hash = input.Length;
+    public static ulong DEKHash(byte[] input) {
+      ulong hash = (ulong)input.Length;
       foreach (var v in input) {
         hash = (hash << 5) ^ (hash >> 27) ^ v;
@@ -85 +86 @@
     }
 
-    public static int CryptoHash(HashAlgorithm ha, int[] input) {
-      return BitConverter.ToInt32(ha.ComputeHash(input.ToByteArray()), 0);
-    }
-
-    public static byte[] ToByteArray(this int[] input) {
-      const int size = sizeof(int);
-      var bytes = new byte[input.Length * sizeof(int)];
-      for (int i = 0; i < input.Length; ++i) {
-        Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
-      }
-      return bytes;
+    public static ulong CryptoHash(HashAlgorithm ha, byte[] input) {
+      return BitConverter.ToUInt64(ha.ComputeHash(input), 0);
     }
   }

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

@@ -1 @@
-using System.Collections.Generic;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2018 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.Linq;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -18 +39 @@
     private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
 
-    public static int ComputeHash(this ISymbolicExpressionTree tree) {
+    public static ulong ComputeHash(this ISymbolicExpressionTree tree) {
       return ComputeHash(tree.Root.GetSubtree(0).GetSubtree(0));
     }
 
-    public static Dictionary<ISymbolicExpressionTreeNode, int> ComputeNodeHashes(this ISymbolicExpressionTree tree) {
-      var root = tree.Root.GetSubtree(0).GetSubtree(0);
-      var nodes = root.MakeNodes();
-      nodes.UpdateNodeSizes();
-
-      for (int i = 0; i < nodes.Length; ++i) {
-        if (nodes[i].IsChild)
-          continue;
-        nodes[i].CalculatedHashValue = nodes.ComputeHash(i);
-      }
-      return nodes.ToDictionary(x => x.Data, x => x.CalculatedHashValue);
-    }
-
-    public static int ComputeHash(this ISymbolicExpressionTreeNode treeNode) {
-      var hashNodes = treeNode.MakeNodes();
-      var simplified = hashNodes.Simplify();
-      return ComputeHash(simplified);
-    }
-
-    public static int ComputeHash(this HashNode<ISymbolicExpressionTreeNode>[] nodes) {
-      int hash = 1315423911;
-      foreach (var node in nodes)
-        hash ^= (hash << 5) + node.CalculatedHashValue + (hash >> 2);
-      return hash;
-    }
-
-    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node) {
+    public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false) {
+      return ComputeSimilarity(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0), simplify);
+    }
+
+    public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false) {
+      HashNode<ISymbolicExpressionTreeNode>[] lhs;
+      HashNode<ISymbolicExpressionTreeNode>[] rhs;
+
+      ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
+
+      if (simplify) {
+        lhs = t1.MakeNodes().Simplify(hashFunction);
+        rhs = t2.MakeNodes().Simplify(hashFunction);
+      } else {
+        lhs = t1.MakeNodes().Sort(hashFunction); // sort calculates hash values
+        rhs = t2.MakeNodes().Sort(hashFunction);
+      }
+
+      var lh = lhs.Select(x => x.CalculatedHashValue).ToArray();
+      var rh = rhs.Select(x => x.CalculatedHashValue).ToArray();
+
+      Array.Sort(lh);
+      Array.Sort(rh);
+
+      return ComputeSimilarity(lh, rh);
+    }
+
+    // this will only work if lh and rh are sorted 
+    private static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
+      double count = 0;
+      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
+        var h1 = lh[i];
+        var h2 = rh[j];
+        if (h1 == h2) {
+          ++count;
+          ++i;
+          ++j;
+        } else if (h1 < h2) {
+          ++i;
+        } else if (h1 > h2) {
+          ++j;
+        }
+      }
+
+      return 2d * count / (lh.Length + rh.Length);
+    }
+
+    public static double ComputeAverageSimilarity(ISymbolicExpressionTree[] trees, bool simplify = false, bool strict = false) {
+      var total = (double)trees.Length * (trees.Length - 1) / 2;
+      double avg = 0;
+      var hashes = new ulong[trees.Length][];
+      // build hash arrays
+      for (int i = 0; i < trees.Length; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      // compute similarity matrix
+      for (int i = 0; i < trees.Length - 1; ++i) {
+        for (int j = i + 1; j < trees.Length; ++j) {
+          avg += ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return avg / total;
+    }
+
+    public static double[,] ComputeSimilarityMatrix(ISymbolicExpressionTree[] trees, bool simplify = false, bool strict = false) {
+      var sim = new double[trees.Length, trees.Length];
+      var hashes = new ulong[trees.Length][];
+      // build hash arrays
+      for (int i = 0; i < trees.Length; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      // compute similarity matrix
+      for (int i = 0; i < trees.Length - 1; ++i) {
+        for (int j = i + 1; j < trees.Length; ++j) {
+          sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return sim;
+    }
+
+    public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool strict = false) {
+      ulong hashFunction(byte[] input) => HashUtil.JSHash(input);
+      var hashNodes = treeNode.MakeNodes(strict);
+      var simplified = hashNodes.Simplify(hashFunction);
+      return simplified.Last().CalculatedHashValue;
+    }
+
+    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node, bool strict = false) {
       var symbol = node.Symbol;
       var name = symbol.Name;
-      if (symbol is Variable) {
-        var variableTreeNode = (VariableTreeNode)node;
-        name = variableTreeNode.VariableName;
-      }
-      var hash = name.GetHashCode();
+      if (node is ConstantTreeNode constantNode) {
+        name = strict ? constantNode.Value.ToString() : symbol.Name;
+      } else if (node is VariableTreeNode variableNode) {
+        name = strict ? variableNode.Weight.ToString() + variableNode.VariableName : variableNode.VariableName;
+      }
+      var hash = (ulong)name.GetHashCode();
       var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
         Data = node,
@@ -79 +166 @@
     }
 
-    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node) {
-      return node.IterateNodesPostfix().Select(ToHashNode).ToArray();
+    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
+      return MakeNodes(tree.Root.GetSubtree(0).GetSubtree(0), strict);
+    }
+
+    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node, bool strict = false) {
+      return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
     }
 
@@ -98 +189 @@
         var node = nodes[i];
 
-        if (node.IsChild) {
+        if (node.IsLeaf) {
           if (node.Data is VariableTreeNode variable) {
             var variableTreeNode = (VariableTreeNode)treeNodes[i];
             variableTreeNode.VariableName = variable.VariableName;
-            variableTreeNode.Weight = 1;
+            variableTreeNode.Weight = variable.Weight;
           } else if (node.Data is ConstantTreeNode @const) {
             var constantTreeNode = (ConstantTreeNode)treeNodes[i];
@@ -129 +220 @@
     // (in other words simplification should be applied in a bottom-up fashion) 
     public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
+      ulong hashFunction(byte[] bytes) => HashUtil.JSHash(bytes);
       var root = tree.Root.GetSubtree(0).GetSubtree(0);
       var nodes = root.MakeNodes();
-      var simplified = nodes.Simplify();
+      var simplified = nodes.Simplify(hashFunction);
       return simplified.ToTree();
     }
@@ -174 +266 @@
             var d = children[k];
             if (nodes[d].Data.Symbol is Constant) {
-              ((ConstantTreeNode)child.Data).Value *= ((ConstantTreeNode)nodes[d].Data).Value;
               nodes[d].Enabled = false;
               node.Arity--;

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -107 +107 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1, Version=0.0.0.1, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core">
@@ -123 +128 @@
   <ItemGroup>
     <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
+    <Compile Include="Analyzers\SymbolicDataAnalysisBuildingBlockAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
@@ -141 +147 @@
     <Compile Include="Converters\DerivativeCalculator.cs" />
     <Compile Include="Converters\TreeToAutoDiffTermConverter.cs" />
+    <Compile Include="Crossovers\SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs" />
     <Compile Include="Formatters\InfixExpressionFormatter.cs" />
     <Compile Include="Formatters\TSQLExpressionFormatter.cs" />
@@ -154 +161 @@
     <Compile Include="Interfaces\IVariableTreeNode.cs" />
     <Compile Include="Interfaces\IVariableSymbol.cs" />
+    <Compile Include="Interpreter\BatchInstruction.cs" />
+    <Compile Include="Interpreter\BatchOperations.cs" />
     <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
+    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
+    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionTreeSimplificationOperator.cs" />
     <Compile Include="SymbolicDataAnalysisModelComplexityCalculator.cs" />

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Plugin.cs.frame

@@ -37 +37 @@
   [PluginDependency("HeuristicLab.Data", "3.3")]
   [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
+  [PluginDependency("HeuristicLab.NativeInterpreter", "0.1")]
   [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisModel.cs

@@ -34 +34 @@
   /// </summary>
   [StorableClass]
-  public abstract class SymbolicDataAnalysisModel : NamedItem, ISymbolicDataAnalysisModel {
+  public abstract class SymbolicDataAnalysisModel : DataAnalysisModel, ISymbolicDataAnalysisModel {
     public static new Image StaticItemImage {
       get { return HeuristicLab.Common.Resources.VSImageLibrary.Function; }
@@ -59 +59 @@
     }
 
-    public IEnumerable<string> VariablesUsedForPrediction {
+    public override IEnumerable<string> VariablesUsedForPrediction {
       get {
         var variables =
@@ -118 +118 @@
       ConstantTreeNode alphaTreeNode = null;
       ConstantTreeNode betaTreeNode = null;
-      // check if model has been scaled previously by analyzing the structure of the tree
+      // check if model has a structure that can be re-used for scaling
       var startNode = SymbolicExpressionTree.Root.GetSubtree(0);
-      if (startNode.GetSubtree(0).Symbol is Addition) {
-        var addNode = startNode.GetSubtree(0);
-        if (addNode.SubtreeCount == 2 && addNode.GetSubtree(0).Symbol is Multiplication && addNode.GetSubtree(1).Symbol is Constant) {
-          alphaTreeNode = addNode.GetSubtree(1) as ConstantTreeNode;
-          var mulNode = addNode.GetSubtree(0);
-          if (mulNode.SubtreeCount == 2 && mulNode.GetSubtree(1).Symbol is Constant) {
-            betaTreeNode = mulNode.GetSubtree(1) as ConstantTreeNode;
-          }
+      var addNode = startNode.GetSubtree(0);
+      if (addNode.Symbol is Addition && addNode.SubtreeCount == 2) {
+        alphaTreeNode = (ConstantTreeNode)addNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
+        var mulNode = addNode.Subtrees.FirstOrDefault(n => n.Symbol is Multiplication);
+        if (mulNode != null) {
+          betaTreeNode = (ConstantTreeNode)mulNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
         }
       }

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
 using System.Globalization;
 using System.Linq;
@@ -31 +30 @@
 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]
@@ -40 +41 @@
     protected override bool IsCommutative { get { return true; } }
 
+    public bool MatchConstantValues { get; set; }
+    public bool MatchVariableWeights { get; set; }
+
     [StorableConstructor]
     protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
@@ -53 +57 @@
     }
 
+    #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 +111 @@
     }
 
+    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 = 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 +162 @@
       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 +222 @@
 
     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; }
     }
   }