Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs	(revision 15714)
@@ -1,31 +1,131 @@
-﻿namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
+﻿using System.Collections;
+using System.Collections.Generic;
+using System.ComponentModel;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
   public class Grammar {
 
     public Symbol StartSymbol;
 
+    #region Symbols
+    public VariableSymbol Var;
+
+    public NonterminalSymbol Expr;
+    public NonterminalSymbol Term;
+    public NonterminalSymbol Factor;
+
+    public TerminalSymbol Addition;
+    public TerminalSymbol Multiplication;
+    #endregion
+
+
     public Grammar(string[] variables) {
       #region Define Symbols
-      VariableSymbol var = new VariableSymbol("var", variables);
+      Var = new VariableSymbol("var", variables);
 
-      NonterminalSymbol expr = new NonterminalSymbol("Expr");
-      NonterminalSymbol term = new NonterminalSymbol("Expr");
-      NonterminalSymbol factor = new NonterminalSymbol("Expr");
+      Expr = new NonterminalSymbol("Expr");
+      Term = new NonterminalSymbol("Term");
+      Factor = new NonterminalSymbol("Factor");
 
-      TerminalSymbol addition = new TerminalSymbol("+");
-      TerminalSymbol multiplication = new TerminalSymbol("*");
+      Addition = new TerminalSymbol("+");
+      Multiplication = new TerminalSymbol("*");
       #endregion
 
 
       #region Production ruless
-      StartSymbol = expr;
+      StartSymbol = Expr;
 
-      expr.AddProduction(term, expr, addition);
-      expr.AddProduction(term);
+      Expr.AddProduction(Term, Expr, Addition);
+      Expr.AddProduction(Term);
 
-      term.AddProduction(factor, term, multiplication);
-      term.AddProduction(factor);
+      Term.AddProduction(Factor, Term, Multiplication);
+      Term.AddProduction(Factor);
 
-      factor.AddProduction(var);
+      Factor.AddProduction(Var);
       #endregion
+    }
+
+    public int CalcHashCode(SymbolString sentence) {
+      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
+      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
+
+      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
+
+      int[] subtreeHashes = GetSubtreeHashes(parseStack.Pop(), parseStack);
+      return AggregateHashes(subtreeHashes);
+    }
+
+    private int[] GetSubtreeHashes(TerminalSymbol currentSymbol, Stack<TerminalSymbol> parseStack) {
+      List<int> childHashes = null;
+
+      if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
+        childHashes = currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToList();
+
+      } else if (ReferenceEquals(currentSymbol, Multiplication)) { // MULTIPLICATION
+        childHashes = new List<int>();
+
+        // First subtree
+        TerminalSymbol firstSubtreeRoot = parseStack.Pop();
+        int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(firstSubtreeRoot, Multiplication)) {
+          childHashes.AddRange(firstSubtreeHashes);
+        } else {
+          childHashes.Add(AggregateHashes(firstSubtreeHashes));
+        }
+
+        // Second subtree
+        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
+        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(secondSubtreeRoot, Multiplication)) {
+          childHashes.AddRange(secondSubtreeHashes);
+        } else {
+          childHashes.Add(AggregateHashes(secondSubtreeHashes));
+        }
+
+        // Sort due to commutativity
+        childHashes.Sort();
+
+
+
+      } else if (ReferenceEquals(currentSymbol, Addition)) { // ADDITION
+        HashSet<int> uniqueChildHashes = new HashSet<int>();
+
+        TerminalSymbol firstSubtreeRoot = parseStack.Pop();
+        int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack);
+
+        // First subtree
+        if (ReferenceEquals(firstSubtreeRoot, Addition)) {
+          uniqueChildHashes.UnionWith(firstSubtreeHashes);
+        } else {
+          uniqueChildHashes.Add(AggregateHashes(firstSubtreeHashes));
+        }
+
+        // Second subtree
+        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
+        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(secondSubtreeRoot, Addition)) {
+          uniqueChildHashes.UnionWith(secondSubtreeHashes);
+        } else {
+          uniqueChildHashes.Add(AggregateHashes(secondSubtreeHashes));
+        }
+
+        childHashes = uniqueChildHashes.ToList();
+        childHashes.Sort();
+      }
+
+      Debug.Assert(childHashes != null, "Sentence not hashable!");
+      return childHashes.ToArray();
+    }
+
+
+    private int AggregateHashes(IEnumerable<int> hashes) {
+      return hashes.Aggregate(0, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }
   }
Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs	(revision 15714)
@@ -1,3 +1,4 @@
-﻿using System.Collections.Generic;
+﻿using System;
+using System.Collections.Generic;
 using System.Collections.ObjectModel;
 using System.Diagnostics;
@@ -41,5 +42,4 @@
       DoubleValue averageTreeLength = new DoubleValue();
       Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength));
-
 
       int maxStringLength = 4;
Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs	(revision 15714)
@@ -1,16 +1,16 @@
-﻿using System;
-using System.Collections.Generic;
+﻿using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
 
   public abstract class Symbol {
-    private readonly string stringRepresentation;
+    public readonly string StringRepresentation;
 
     protected Symbol(string representation) {
-      stringRepresentation = representation;
+      StringRepresentation = representation;
     }
 
     public override string ToString() {
-      return stringRepresentation;
+      return StringRepresentation;
     }
   }
@@ -33,7 +33,14 @@
 
   public class VariableSymbol : NonterminalSymbol { // Convenience class
+    public IEnumerable<TerminalSymbol> VariableTerminalSymbols;
+
     public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) {
+      List<TerminalSymbol> createdSymbols = new List<TerminalSymbol>();
+      VariableTerminalSymbols = createdSymbols;
+
       foreach (string variableName in variableNames) {
-        AddProduction(new TerminalSymbol("[" + variableName + "]"));
+        TerminalSymbol s = new TerminalSymbol(variableName);
+        createdSymbols.Add(s);
+        AddProduction(s);
       }
     }
Index: /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj	(revision 15714)
@@ -98,4 +98,5 @@
     <Compile Include="GrammarEnumeration\Symbol.cs" />
   </ItemGroup>
+  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
Index: /branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs	(revision 15714)
@@ -10,5 +10,5 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
-  [TestClass()]
+  //[TestClass()]
   public class MctsSymbolicRegressionTest {
     private const int Seed = 1234;
Index: /branches/2886_SymRegGrammarEnumeration/Test/Test.csproj
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/Test/Test.csproj	(revision 15713)
+++ /branches/2886_SymRegGrammarEnumeration/Test/Test.csproj	(revision 15714)
@@ -103,5 +103,7 @@
     <Otherwise>
       <ItemGroup>
-        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework" />
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework">
+          <Private>False</Private>
+        </Reference>
       </ItemGroup>
     </Otherwise>
@@ -110,4 +112,5 @@
     <Compile Include="GrammarEnumerationTest.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TreeHashingTest.cs" />
   </ItemGroup>
   <ItemGroup>
Index: /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs
===================================================================
--- /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs	(revision 15714)
+++ /branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs	(revision 15714)
@@ -0,0 +1,84 @@
+﻿using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace Test {
+  [TestClass]
+  public class TreeHashingTest {
+
+    private Grammar grammar;
+    private TerminalSymbol varA;
+    private TerminalSymbol varB;
+    private TerminalSymbol varC;
+
+    [TestInitialize]
+    public void InitTest() {
+      grammar = new Grammar(new[] { "a", "b", "c" });
+
+      varA = grammar.Var.VariableTerminalSymbols.First(s => s.StringRepresentation == "a");
+      varB = grammar.Var.VariableTerminalSymbols.First(s => s.StringRepresentation == "b");
+      varC = grammar.Var.VariableTerminalSymbols.First(s => s.StringRepresentation == "c");
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void SimpleEqualityAddition() {
+      SymbolString s1 = new SymbolString(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
+      SymbolString s2 = new SymbolString(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void SimpleInequalityAddition() {
+      SymbolString s1 = new SymbolString(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
+      SymbolString s2 = new SymbolString(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreNotEqual(hash1, hash2);
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void CommutativityAddition() {
+      SymbolString s1 = new SymbolString(new[] { varA, varB, grammar.Addition });
+      SymbolString s2 = new SymbolString(new[] { varB, varA, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void AssociativityAddition() {
+      SymbolString s1 = new SymbolString(new[] { varA, varB, grammar.Addition, varA, grammar.Addition });
+      SymbolString s2 = new SymbolString(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void RepeatedAddition() {
+      SymbolString s1 = new SymbolString(new[] { varA, varA, grammar.Addition, varA, grammar.Addition });
+      SymbolString s2 = new SymbolString(new[] { varA });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+  }
+}
