Index: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs
===================================================================
--- branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs	(revision 13426)
+++ branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs	(revision 13479)
@@ -35,5 +35,5 @@
   public class TraceCalculator : Item {
     private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
-    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
+    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>> traceCache;
     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
 
@@ -42,4 +42,6 @@
     public bool CacheTraceNodes { get; set; }
 
+    public int TraceCacheHits { get; set; }
+
     public TraceCalculator() {
       ResetState();
@@ -60,5 +62,5 @@
       TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
-      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
+      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>>();
     }
 
@@ -145,13 +147,22 @@
               // subtree contains fragment => branching point in the fragment graph
               var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
-              var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
-              if (!(CacheTraceNodes && traceCache.Contains(t0))) {
+              if (CacheTraceNodes) {
+                var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, si, n, si, fi);
+                var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent1, fragment.Index2, n, si, fi);
+                if (!traceCache.Contains(t0)) {
+                  traceCache.Add(t0);
+                  TraceRecursive(parent0, si, n, si, fi);
+                } else {
+                  TraceCacheHits++;
+                }
+                if (!traceCache.Contains(t1)) {
+                  traceCache.Add(t1);
+                  TraceRecursive(parent1, fragment.Index2, n, si, fi);
+                } else {
+                  TraceCacheHits++;
+                }
+              } else {
                 TraceRecursive(parent0, si, n, si, fi);
-                traceCache.Add(t0);
-              }
-              var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
-              if (!(CacheTraceNodes && traceCache.Contains(t1))) {
                 TraceRecursive(parent1, fragment.Index2, n, si, fi);
-                traceCache.Add(t1);
               }
               break;
@@ -174,5 +185,5 @@
             var n = AddTraceNode(g); // current node becomes "last" as we restart tracing from the parent
             int i = si < fi ? si : fi;
-            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
+            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, int, IGenealogyGraphNode<ISymbolicExpressionTree>, int, int>(parent0, i, n, si, fi);
             if (!(CacheTraceNodes && traceCache.Contains(t))) {
               TraceRecursive(parent0, i, n, si, fi);
