Index: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs
===================================================================
--- branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs	(revision 11852)
+++ branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs	(revision 11855)
@@ -47,5 +47,5 @@
       //    the cloning will also clone the vertex data object, therefore reference comparison of node lists will not work
       // 2) replaces the parent of the current individual with the clone, and alters graph connections accordingly
-      //    therefore, vChild will be the vertex of the child, and vClone the vertex of the cloned parent
+      //    so that vChild vertex will represent the child, and vClone will represent the cloned parent
       var result = base.Apply();
       var vChild = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
Index: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs
===================================================================
--- branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs	(revision 11852)
+++ 	(revision )
@@ -1,197 +1,0 @@
-﻿#region License Information
-/* HeuristicLab
- * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
- *
- * This file is part of HeuristicLab.
- *
- * HeuristicLab is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * HeuristicLab is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
- */
-#endregion
-
-using System;
-using System.Collections.Generic;
-using System.IO;
-using System.Linq;
-using HeuristicLab.Core;
-using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
-using HeuristicLab.EvolutionTracking;
-
-namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public static class SymbolicDataAnalysisExpressionTracing {
-    public static FragmentGraph TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex) {
-      var graph = new FragmentGraph();
-      var vertices = Trace(graphNode, subtreeIndex).ToList();
-      graph.AddVertices(vertices);
-      return graph;
-    }
-    /// <summary>
-    /// Traces a subtree in a genealogy of individuals, tracking down it's genetic components
-    /// </summary>
-    /// <param name="graphNode">The point in the genealogy where to start the tracing from</param>
-    /// <param name="subtreeIndex">The traced subtree preorder index in the current tree</param>
-    /// <param name="parentNode">The parent node in the fragment graph if there is any</param>
-    /// <returns></returns>
-    private static IEnumerable<FragmentNode> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> graphNode, int subtreeIndex, FragmentNode parentNode = null) {
-      var node = graphNode; // current node
-      var index = subtreeIndex; // current index
-      var parent = parentNode; // current parent
-
-      IGenealogyGraphNode<ISymbolicExpressionTree> n1 = null;
-      int i1 = -1;
-
-      while (true) {
-        if (node == n1 && index == i1)
-          throw new InvalidOperationException("Infinite loop detected");
-
-        n1 = node;
-        i1 = index;
-
-        if (!node.Parents.Any()) {
-          // no tracing if there are no parents, return a fragment node representing the current trace
-          var fragmentNode = new FragmentNode(node.Data) { SubtreeIndex = index };
-          if (parent != null) {
-            var arc = new GenealogyGraphArc(parent, fragmentNode);
-            parent.AddArc(arc);
-            fragmentNode.AddArc(arc);
-          }
-          yield return fragmentNode;
-          break;
-        }
-        var parents = node.Parents.ToList();
-        var fragment = (IFragment<ISymbolicExpressionTreeNode>)node.InArcs.Last().Data;
-
-        if (fragment == null) {
-          // the fragment can be null for two reasons:
-          // 1) the individual is an elite
-          // 2) the crossover/mutation made no changes to the root parent (or there is a bug in fragment identification)
-          if (index >= parents[0].Data.Length) {
-            throw new InvalidOperationException("Index exceeds tree length.");
-          }
-          node = parents[0];
-          continue;
-        }
-
-        var fragmentLength = fragment.Root.GetLength();
-        var tree = node.Data;
-        var subtree = tree.NodeAt(index);
-        var subtreeLength = subtree.GetLength();
-
-        #region mutation tracing
-        if (parents.Count == 1) {
-          // we are tracing a mutation operation
-          var fragmentNode = new FragmentNode(node.Data) {
-            SubtreeIndex = index,
-            FragmentIndex = fragment.Index1
-          };
-          if (parent != null) {
-            var arc = new Arc(parent, fragmentNode);
-            parent.AddArc(arc);
-            fragmentNode.AddArc(arc);
-          }
-          if (node == parents[0])
-            throw new InvalidOperationException("Node == parents[0]");
-
-          node = parents[0];
-
-          if (index == fragment.Index1) {
-            // index stays the same
-          } else if (fragment.Index1 < index) {
-            if (index < fragment.Index1 + fragmentLength) {
-              // in the case of mutation, the fragment could have been introduced via a node replacement
-              // there is no guarantee the subtree exists above this level, therefore the index is set to the fragment index
-              index = fragment.Index1;
-            } else {
-              // subtree outside of fragment
-              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
-            }
-          } else if (index < fragment.Index1) {
-            if (fragment.Index1 < index + subtreeLength) {
-              // subtree contains fragment
-              index = fragment.Index1;
-            } else {
-              // index stays the same
-            }
-          }
-          yield return fragmentNode;
-          if (node == graphNode && index == subtreeIndex)
-            throw new ArgumentException("Infinite recursion detected");
-          var up = Trace(node, index, fragmentNode).ToList(); // force immediate query execution
-          foreach (var v in up) { yield return v; }
-          break;
-        }
-        #endregion
-
-        #region crossover tracing
-        if (parents.Count == 2) {
-          if (node == parents[0])
-            throw new InvalidOperationException("Node == parents[0]");
-          if (node == parents[1])
-            throw new InvalidOperationException("Node == parents[1]");
-          // we are tracing a crossover operation
-          if (fragment.Index1 == index) {
-            node = parents[1]; // take second parent which contains the fragment
-            index = fragment.Index2;
-            continue;
-          }
-
-          if (fragment.Index1 < index) {
-            if (fragment.Index1 + fragmentLength > index) {
-              node = parents[1]; // fragment contains subtree, take second parent
-              index += fragment.Index2 - fragment.Index1; // the subtree has the same index relative to the fragment
-            } else {
-              // fragment distinct from subtree
-              node = parents[0]; // take first parent which contains the subtree
-              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength; // subtreeIndex must be adjusted according to swapped fragments sizes
-            }
-            continue;
-          }
-
-          if (fragment.Index1 > index) {
-            if (fragment.Index1 < index + subtreeLength) {
-              // subtree contains fragment => branching point in the fragment graph
-              var fragmentNode = new FragmentNode(node.Data) {
-                SubtreeIndex = index,
-                FragmentIndex = fragment.Index1
-              };
-              if (parent != null) {
-                var arc = new GenealogyGraphArc(parent, fragmentNode);
-                parent.AddArc(arc);
-                fragmentNode.AddArc(arc);
-              }
-              yield return fragmentNode;
-
-              if (parents[1].Data.NodeAt(fragment.Index2).GetLength() != fragmentLength) {
-                throw new Exception("Fragment lengths should match!");
-              }
-              // the two paths below ("left" and "right") correspond to the subtree and the fragment, respectively
-              var left = Trace(parents[0], index, fragmentNode); // trace subtree
-              var right = Trace(parents[1], fragment.Index2, fragmentNode); // trace fragment
-              foreach (var v in left.Concat(right)) { yield return v; }
-              break;
-            } else {
-              node = parents[0]; // fragment distinct from subtree: update node, index remains unchanged
-            }
-          }
-        }
-        #endregion
-      }
-    }
-
-    private static string ViewAsText(this ISymbolicExpressionTreeNode root) {
-      var writer = new StringWriter();
-      SymbolicExpressionTreeHierarchicalFormatter.RenderNode(writer, root, string.Empty);
-      return writer.ToString();
-    }
-  }
-}
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 11852)
+++ branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs	(revision 11855)
@@ -36,4 +36,5 @@
     private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
     private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
+    private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
 
     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
@@ -42,4 +43,5 @@
       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
+      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
     }
 
@@ -68,4 +70,5 @@
       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
+      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
       TraceRecursive(node, subtreeIndex);
       return traceGraph;
@@ -100,6 +103,5 @@
         var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
         if (fragment == null) {
-          //          if (parents.Count == 2)
-          //            throw new Exception("There should always be a crossover fragment.");
+          // TODO: think about what the correct behavior should be here (seems good so far)
           // the node is either an elite node or (in rare cases) no fragment was transferred
           g = parents[0];
@@ -109,5 +111,5 @@
         int fi = fragment.Index1;               // fragment index
         int fl = fragment.Root.GetLength();     // fragment length
-        int sl = g.Data.NodeAt(si).GetLength(); // subtree length
+        int sl = NodeAt(g.Data, si).GetLength(); // subtree length
 
         #region trace crossover
@@ -126,5 +128,5 @@
               // fragment distinct from subtree
               g = parents[0];
-              si += g.Data.NodeAt(fi).GetLength() - fl;
+              si += NodeAt(g.Data, fi).GetLength() - fl;
             }
             continue;
@@ -160,5 +162,5 @@
             g = parents[0];
             if (fi < si)
-              si += g.Data.NodeAt(fi).GetLength() - fl;
+              si += NodeAt(g.Data, fi).GetLength() - fl;
             continue;
           }
@@ -188,4 +190,16 @@
       }
       return n;
+    }
+
+    // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
+    // this caching will be even more effective with larger tree sizes
+    private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
+      List<ISymbolicExpressionTreeNode> list;
+      nodeListCache.TryGetValue(tree, out list);
+      if (list == null) {
+        list = tree.IterateNodesPrefix().ToList();
+        nodeListCache[tree] = list;
+      }
+      return list[index];
     }
 
@@ -221,10 +235,4 @@
       return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
     }
-    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
-      return NodeAt(tree.Root, index);
-    }
-    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
-      return root.IterateNodesPrefix().ElementAt(index);
-    }
     #endregion
   }
