Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs	(revision 11015)
@@ -65,4 +65,11 @@
 
     public string Format(ISymbolicExpressionTree symbolicExpressionTree) {
+      string s;
+      Format(symbolicExpressionTree, out s);
+      return s;
+    }
+
+    public Dictionary<ISymbolicExpressionTreeNode, string> Format(ISymbolicExpressionTree symbolicExpressionTree, out string str, int offset = 0) {
+      var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
       var root = symbolicExpressionTree.Root;
       var actualRoot = root.SubtreeCount == 0 ? root.GetSubtree(0) : root;
@@ -78,19 +85,21 @@
                 "\\begin{tikzpicture}" + nl +
                 "\\def\\ws{1}" + nl +
-                "\\def\\hs{0.7}" + nl);
+                "\\def\\hs{0.7}" + nl +
+                "\\def\\offs{" + offset + "}" + nl);
 
-      var nodeIndices = new Dictionary<ISymbolicExpressionTreeNode, int>();
       var nodes = symbolicExpressionTree.IterateNodesBreadth().ToList();
       for (int i = 0; i < nodes.Count; ++i) {
         var node = nodes[i];
-        nodeIndices.Add(node, i);
+        var id = Guid.NewGuid().ToString();
+        nodeIds[node] = id;
         var coord = nodeCoordinates[node];
         var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
-        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1},\\hs*{2}) {{{3}}};", i, ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+        sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1} + {2},\\hs*{3}) {{{4}}};", nodeIds[node], ws * coord.X, offset, -hs * coord.Y, EscapeLatexString(nodeName)));
       }
 
       for (int i = 0; i < nodes.Count; ++i) {
+        var n = nodes[i];
         foreach (var s in nodes[i].Subtrees) {
-          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", i, nodeIndices[s]));
+          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
         }
       }
@@ -98,5 +107,6 @@
       sb.Append("\\end{tikzpicture}" + nl +
                 "\\end{document}" + nl);
-      return sb.ToString();
+      str = sb.ToString();
+      return nodeIds;
     }
 
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Views/3.4/HeuristicLab.EvolutionTracking.Views-3.4.csproj
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Views/3.4/HeuristicLab.EvolutionTracking.Views-3.4.csproj	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Views/3.4/HeuristicLab.EvolutionTracking.Views-3.4.csproj	(revision 11015)
@@ -97,5 +97,7 @@
       <DependentUpon>FrequentFragmentsDialog.cs</DependentUpon>
     </Compile>
-    <Compile Include="GenealogyGraphChart.cs" />
+    <Compile Include="GenealogyGraphChart.cs">
+      <SubType>UserControl</SubType>
+    </Compile>
     <Compile Include="GenealogyGraphChart.Designer.cs">
       <DependentUpon>GenealogyGraphChart.cs</DependentUpon>
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4.csproj
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4.csproj	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic.Views-3.4.csproj	(revision 11015)
@@ -279,5 +279,7 @@
       <DependentUpon>SymboldDataAnalysisGenealogyView.cs</DependentUpon>
     </Compile>
-    <Compile Include="Tracking\SymbolicDataAnalysisExpressionGenealogyGraphChart.cs" />
+    <Compile Include="Tracking\SymbolicDataAnalysisExpressionGenealogyGraphChart.cs">
+      <SubType>UserControl</SubType>
+    </Compile>
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionGenealogyGraphChart.Designer.cs">
       <DependentUpon>SymbolicDataAnalysisExpressionGenealogyGraphChart.cs</DependentUpon>
@@ -289,5 +291,7 @@
       <DependentUpon>SymbolicDataAnalysisExpressionLineageExplorerView.cs</DependentUpon>
     </Compile>
-    <Compile Include="Tracking\SymbolicExpressionChartControl.cs" />
+    <Compile Include="Tracking\SymbolicExpressionChartControl.cs">
+      <SubType>UserControl</SubType>
+    </Compile>
     <Compile Include="Tracking\SymbolicExpressionChartControl.Designer.cs">
       <DependentUpon>SymbolicExpressionChartControl.cs</DependentUpon>
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/FragmentGraphView.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/FragmentGraphView.cs	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/FragmentGraphView.cs	(revision 11015)
@@ -69,5 +69,5 @@
       var chart = symbolicExpressionChartControl.Chart;
       tileDictionary.Clear();
-      foreach (var node in Content.Nodes) {
+      foreach (var node in Content.Vertices) {
         var graphNode = (IGenealogyGraphNode<ISymbolicExpressionTree>)node.Content;
         var tile = new SymbolicExpressionTreeTile(chart);
@@ -79,5 +79,5 @@
         tileDictionary.Add(node, tileNode);
       }
-      foreach (var node in Content.Nodes.Where(n => n.OutArcs.Any())) {
+      foreach (var node in Content.Vertices.Where(n => n.OutArcs.Any())) {
         var layoutNode = tileDictionary[node];
         layoutNode.Children = new List<TileLayoutNode>(node.OutArcs.Select(a => tileDictionary[(FragmentNode)a.Target]));
@@ -87,5 +87,5 @@
     private void Draw() {
       var chart = symbolicExpressionChartControl.Chart;
-      var nodes = Content.Nodes.ToList();
+      var nodes = Content.Vertices.ToList();
       var root = nodes[0];
       var fragmentRoot = tileDictionary[root];
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic.Views/3.4/Tracking/SymboldDataAnalysisGenealogyView.cs	(revision 11015)
@@ -100,5 +100,5 @@
         var subtreeIndex = graphNode.Content.IterateNodesPrefix().ToList().IndexOf(subtree);
         var fragmentGraph = SymbolicDataAnalysisExpressionTracing.TraceSubtree(graphNode, subtreeIndex);
-        if (fragmentGraph.Nodes.Any()) {
+        if (fragmentGraph.Vertices.Any()) {
           MainFormManager.MainForm.ShowContent(fragmentGraph); // display the fragment graph on the screen
         }
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj	(revision 11015)
@@ -306,4 +306,5 @@
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs" />
     <Compile Include="Tracking\SymbolicDataAnalysisExpressionTracing.cs" />
+    <Compile Include="TreeDistance\BottomUpDistanceCalculator.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />
@@ -340,4 +341,8 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views\3.4\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views-3.4.csproj">
+      <Project>{423bd94f-963a-438e-ba45-3bb3d61cd03b}</Project>
+      <Name>HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views-3.4</Name>
+    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.4\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj">
       <Project>{06D4A186-9319-48A0-BADE-A2058D462EEA}</Project>
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs	(revision 11014)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeSimilarityCalculator.cs	(revision 11015)
@@ -103,5 +103,7 @@
 
         if (found) {
-          similarity += MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
+          //          similarity += MaxCommonSubtreeSimilarity(current, tree, SimilarityComparer);
+          var distance = BottomUpDistanceCalculator.CalculateDistance(current, tree) / (current.Length + tree.Length);
+          similarity += 1 - distance;
         }
       }
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs	(revision 11015)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs	(revision 11015)
@@ -0,0 +1,200 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2013 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.Globalization;
+using System.IO;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
+using HeuristicLab.EvolutionTracking;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  public static class BottomUpDistanceCalculator {
+    private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      var G = new DirectedGraph();
+      var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
+      var F = new DisjointUnion(t1, t2);
+      var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
+      var L = new Dictionary<string, IVertex>();
+      foreach (var l in F.Nodes.Where(x => x.SubtreeCount == 0)) {
+        var z = new Vertex { Content = l, Label = Label(l) };
+        z.Weight = Height(l); // might be necessary
+        L[z.Label] = z;
+        G.AddVertex(z);
+      }
+      var Q = new Queue<ISymbolicExpressionTreeNode>();
+      foreach (var v in F.Nodes) {
+        Children[v] = v.SubtreeCount;
+        if (v.SubtreeCount == 0) {
+          Q.Enqueue(v);
+        }
+      }
+      do {
+        var v = Q.Dequeue();
+        if (v.SubtreeCount == 0) {
+          K[v] = L[Label(v)]; // 18
+        } else {
+          bool found = false;
+
+          foreach (var w in G.Vertices.Reverse()) {
+            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
+              break;
+            // sort the lists before comparison, as required when dealing with unordered trees
+            var V = v.Subtrees.OrderBy(Label).Select(s => K[s]);
+            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
+            if (V.SequenceEqual(W)) {
+              K[v] = w;
+              found = true;
+              break;
+            }
+          } // 32: end for
+
+          if (!found) {
+            var w = new Vertex { Content = v, Label = Label(v), Weight = Height(v) };
+            K[v] = w;
+
+            foreach (var u in v.Subtrees) {
+              G.AddArc(w, K[u]);
+            } // 40: end for
+          } // 41: end if
+        } // 42: end if
+
+        if (!F.IsRoot(v)) {
+          Children[v.Parent] = Children[v.Parent] - 1;
+          if (Children[v.Parent] == 0) {
+            Q.Enqueue(v.Parent);
+          } // 47: end if
+        } // 48: end if
+      } while (Q.Count != 0);
+      return K;
+    }
+
+    private static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> Mapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, IVertex> K) {
+      var M = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
+      var M_ = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
+      //var plist1 = t1.IterateNodesPrefix().ToList();
+      var plist2 = t2.IterateNodesPrefix().ToList();
+      foreach (var v in t1.IterateNodesBreadth()) {
+        if (!M.ContainsKey(v)) {
+          var w = plist2.Last();
+          foreach (var u in plist2.Where(x => K[x] == K[v])) {
+            if (!M_.ContainsKey(u)) {
+              if (plist2.IndexOf(u) < plist2.IndexOf(w)) {
+                w = u;
+              }
+            }
+          }
+          if (K[v] == K[w]) {
+            // simultaneous preorder traversal of the two subtrees
+            var nodesV = v.IterateNodesPrefix().ToList();
+            var nodesW = w.IterateNodesPrefix().ToList();
+            for (int i = 0; i < Math.Min(nodesV.Count, nodesW.Count); ++i) {
+              var s = nodesV[i];
+              var t = nodesW[i];
+              M[s] = t;
+              M_[t] = s;
+            }
+            //            var e1 = v.IterateNodesPrefix().GetEnumerator();
+            //            var e2 = w.IterateNodesPrefix().GetEnumerator();
+            //            while (e1.MoveNext() && e2.MoveNext()) {
+            //              M[e1.Current] = e2.Current;
+            //              M_[e2.Current] = e1.Current;
+            //            }
+          }
+        }
+      }
+      return M;
+    }
+
+    public static double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
+      var K = Compact(t1, t2);
+      var M = Mapping(t1, t2, K);
+      int d = t1.Length - M.Count;
+      int s = M.Count(x => !Label(x.Key).Equals(Label(x.Value)));
+      int i = t2.Length - M.Count;
+
+      double distance = s * p + i * q + d * r;
+
+      if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
+        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.txt"))) {
+          var str = FormatMapping(t1, t2, M);
+          file.WriteLine(str);
+        }
+      }
+
+      return distance;
+    }
+
+    private static string Label(ISymbolicExpressionTreeNode n) {
+      return n.ToString();
+    }
+
+    private static int Height(IVertex v) {
+      return (int)Math.Round(v.Weight); // use the vertex weight as height in this particular context
+    }
+
+    private static int Height(ISymbolicExpressionTreeNode n) {
+      var p = n;
+      while (p.Parent != null)
+        p = p.Parent;
+      return p.GetBranchLevel(n);
+    }
+
+    private class DisjointUnion : Tuple<ISymbolicExpressionTree, ISymbolicExpressionTree> {
+      public DisjointUnion(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2)
+        : base(t1, t2) {
+      }
+
+      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
+        get { return Item1.IterateNodesPrefix().Concat(Item2.IterateNodesPrefix()); }
+      }
+
+      public bool IsRoot(ISymbolicExpressionTreeNode n) {
+        return (n == Item1.Root || n == Item2.Root);
+      }
+    }
+
+    // draw the mapping between t1 and t2
+    private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
+      var formatter = new SymbolicExpressionTreeLatexFormatter();
+      var sb = new StringBuilder();
+
+      string s1, s2;
+      var m1 = formatter.Format(t1, out s1);
+      var m2 = formatter.Format(t2, out s2, 20);
+
+      sb.Append(s1);
+      sb.Append(s2);
+
+      foreach (var p in map) {
+        var id1 = m1[p.Key];
+        var id2 = m2[p.Value];
+
+        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});", id1, id2));
+      }
+
+      return sb.ToString();
+    }
+  }
+}
