Changeset 11211 for branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs

Timestamp:

07/22/14 01:40:12 (10 years ago)

Author:

bburlacu

Message:

#2215: Added implementation of the BottomUpTreeDistanceCalculator in branches/HeuristicLab.BottomUpTreeDistance.

Location:

branches/HeuristicLab.BottomUpTreeDistance

Files:

• . (added)
• HeuristicLab.Problems.DataAnalysis.Symbolic (copied) (copied from trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance (copied) (copied from branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs (copied) (copied from branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs) (9 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpTreeDistanceCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
 using System.Globalization;
 using System.Linq;
@@ -30 +31 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
-using HeuristicLab.EvolutionTracking;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -40 +40 @@
   [StorableClass]
   [Item("Bottom-up distance calculator", "An operator that calculates the bottom-up distance between two symbolic expression trees.")]
-  public class BottomUpDistanceCalculator : Item, IDistanceCalculator {
-    public BottomUpDistanceCalculator() { }
-
-    protected BottomUpDistanceCalculator(BottomUpDistanceCalculator original, Cloner cloner)
+  public class BottomUpTreeDistanceCalculator : Item, ISymbolicExpressionTreeDistanceCalculator {
+    public BottomUpTreeDistanceCalculator() { }
+
+    protected BottomUpTreeDistanceCalculator(BottomUpTreeDistanceCalculator original, Cloner cloner)
       : base(original, cloner) {
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new BottomUpDistanceCalculator(this, cloner);
-    }
-
-    private static IArc AddArc(IVertex source, IVertex target) {
-      var arc = new Arc(source, target);
-      source.AddForwardArc(arc);
-      target.AddReverseArc(arc);
-      return arc;
+      return new BottomUpTreeDistanceCalculator(this, cloner);
+    }
+
+    // return a normalized distance measure in the interval (0,1)
+    public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
+    }
+
+    public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      var compactedGraph = Compact(t1, t2);
+
+      var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
+      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
+
+      foreach (var v in t1.IterateNodesBreadth()) {
+        if (forwardMap.ContainsKey(v)) continue;
+        var kv = compactedGraph[v];
+        var w = t2.IterateNodesBreadth().FirstOrDefault(x => !reverseMap.ContainsKey(x) && compactedGraph[x] == kv); // not sure of iteration order here (pre/post order or breadth), this seems to work
+        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 by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees
+        var eV = IterateBreadthOrdered(v).GetEnumerator();
+        var eW = IterateBreadthOrdered(w).GetEnumerator();
+
+        while (eV.MoveNext() && eW.MoveNext()) {
+          var s = eV.Current;
+          var t = eW.Current;
+          forwardMap[s] = t;
+          reverseMap[t] = s;
+        }
+      }
+
+      int c = forwardMap.Count(x => !Label(x.Key).Equals(Label(x.Value)));
+      double distance = c + t1.Length + t2.Length - 2 * forwardMap.Count;
+      return distance;
     }
 
@@ -65 +93 @@
     /// <returns>The compacted DAG representing the two trees</returns>
     private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
-      var F = new DisjointUnion(t1, t2);
-      var L = new Dictionary<string, IVertex>();
-      var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
-      var G = new List<IVertex>();
-
-      var nodes = F.Nodes.ToList();
+      var nodesToVertices = new Dictionary<ISymbolicExpressionTreeNode, IVertex>(); // K
+      var disjointUnion = new DisjointUnion(t1, t2); // F
+      var labelsToVertices = new Dictionary<string, IVertex>(); // L
+      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
+      var vertices = new List<IVertex>(); // G
+
+      var nodes = disjointUnion.Nodes.ToList();
 
       // for all leaf labels l in F
@@ -77 +105 @@
         var label = Label(l);
         var z = new Vertex { Content = l, Label = label };
-        L[z.Label] = z;
-        G.Add(z);
-      }
-
-      var Q = new Queue<ISymbolicExpressionTreeNode>();
-
-      // for all nodes
+        labelsToVertices[z.Label] = z;
+        vertices.Add(z);
+      }
+
+      var treeNodes = new Queue<ISymbolicExpressionTreeNode>();
+
       foreach (var v in nodes) {
-        Children[v] = v.SubtreeCount;
+        childrenCount[v] = v.SubtreeCount;
         if (v.SubtreeCount == 0) {
-          Q.Enqueue(v);
-        }
-      }
-
-      while (Q.Any()) {
-        var v = Q.Dequeue();
+          treeNodes.Enqueue(v);
+        }
+      }
+
+      while (treeNodes.Any()) {
+        var v = treeNodes.Dequeue();
         var label = Label(v);
         if (v.SubtreeCount == 0) {
-          K[v] = L[label]; // 18
+          nodesToVertices[v] = labelsToVertices[label]; // 18
         } else {
           bool found = false;
           // for all nodes w in G in reverse order
-          for (int i = G.Count - 1; i >= 0; --i) {
-            var w = G[i];
-            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || label != w.Label)
-              break;
+          for (int i = vertices.Count - 1; i >= 0; --i) {
+            var w = vertices[i];
+            // removed requirement for heights to be equal since a compacted dag should not care about heights
+            // this ensures correct behavior when isomorphic subtrees are placed at different depths. 
+            // furthermore, if the nodes have the same labels and the same subtrees then that should be sufficient,
+            // since in the bottom-up approach we are guaranteed that no differences would occur on the lower levels
+            if (v.SubtreeCount != w.OutDegree || label != w.Label)
+              continue;
 
             // sort V and W because we are dealing with unordered trees
-            var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
-            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
-            if (V.SequenceEqual(W)) {
-              K[v] = w;
+            var vSubtrees = v.Subtrees.Select(s => nodesToVertices[s]).OrderBy(x => x.Label);
+            var wSubtrees = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
+            if (vSubtrees.SequenceEqual(wSubtrees)) {
+              nodesToVertices[v] = w;
               found = true;
               break;
@@ -116 +147 @@
           if (!found) {
             var w = new Vertex { Content = v, Label = label };
-            G.Add(w);
-            K[v] = w;
+            vertices.Add(w);
+            nodesToVertices[v] = w;
 
             foreach (var u in v.Subtrees) {
-              AddArc(w, K[u]);
+              AddArc(w, nodesToVertices[u]);
             } // 40: end for
           } // 41: end if
@@ -127 +158 @@
         if (v.Parent != null) {
           var p = v.Parent;
-          Children[p]--;
-          if (Children[p] == 0)
-            Q.Enqueue(p);
+          childrenCount[p]--;
+          if (childrenCount[p] == 0)
+            treeNodes.Enqueue(p);
         }
       };
 
-      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 nodes2 = t2.IterateNodesPrefix().Where(x => !M_.ContainsKey(x)).ToList();
-      foreach (var v in t1.IterateNodesBreadth().Where(x => !M.ContainsKey(x))) {
-        var kv = K[v];
-        var w = nodes2.LastOrDefault(x => K[x] == kv);
-        if (w == null) continue;
-
-        // simultaneous preorder traversal of the two subtrees
-        var eV = v.IterateNodesPrefix().GetEnumerator();
-        var eW = w.IterateNodesPrefix().GetEnumerator();
-
-        while (eV.MoveNext() && eW.MoveNext()) {
-          var s = eV.Current;
-          var t = eW.Current;
-          M[s] = t;
-          M_[t] = s;
-        }
-      }
-      return M;
-    }
-
-    // return a normalized distance measure in the interval (0,1)
-    public double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      return BottomUpDistance(t1, t2) / (t1.Length + t2.Length);
-    }
-
-    public static double BottomUpDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, double p = 1, double q = 1, double r = 1) {
-      var K = Compact(t1, t2);
-      var M = Mapping(t1, t2, K);
-
-      var keys = M.Keys.ToList();
-      for (int j = 0; j < keys.Count; ++j) {
-        var key = keys[j];
-        var value = M[key];
-        if (key.Parent != null && value.Parent != null && !M.ContainsKey(key.Parent) && Label(key.Parent).Equals(Label(value.Parent))) {
-          M.Add(key.Parent, value.Parent);
-          keys.Add(key.Parent);
-        }
-      }
-
-      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;
-      return distance;
-    }
+      return nodesToVertices;
+    }
+
+    private static IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
+      var list = new List<ISymbolicExpressionTreeNode> { node };
+      int i = 0;
+      while (i < list.Count) {
+        var n = list[i];
+        if (n.SubtreeCount > 0)
+          list.AddRange(n.Subtrees.OrderBy(Label));
+        i++;
+      }
+      return list;
+    }
+
+    private static IArc AddArc(IVertex source, IVertex target) {
+      var arc = new Arc(source, target);
+      source.AddForwardArc(arc);
+      target.AddReverseArc(arc);
+      return arc;
+    }
+
 
     private static string Label(ISymbolicExpressionTreeNode n) {
@@ -208 +208 @@
 
       public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
-        get {
-          var r1 = Item1.Root;
-          var r2 = Item2.Root;
-
-          var nodes = r1.IterateNodesPostfix().Select(x => new { Node = x, Height = r1.GetBranchLevel(x) })
-            .Concat(r2.IterateNodesPostfix().Select(x => new { Node = x, Height = r2.GetBranchLevel(x) }));
-
-          return nodes.OrderByDescending(x => x.Height).Select(x => x.Node);
-        }
+        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
       }
     }
@@ -227 +219 @@
     // draw the mapping between t1 and t2 as a tikz picture
     private static string FormatMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map) {
-      var formatter = new SymbolicExpressionTreeLatexFormatter();
+      var symbolNameMap = new Dictionary<string, string>
+    {
+      {"ProgramRootSymbol", "Prog"},
+      {"StartSymbol","RPB"},
+      {"Multiplication", "$\\times$"},
+      {"Division", "$\\div$"},
+      {"Addition", "$+$"},
+      {"Subtraction", "$-$"},
+      {"Exponential", "$\\exp$"},
+      {"Logarithm", "$\\log$"}
+    };
+
       var sb = new StringBuilder();
-
-      string s1, s2;
-      var m1 = formatter.Format(t1, out s1);
-      var m2 = formatter.Format(t2, out s2, 20);
-
-      // skip first 6 lines of s2
-      s2 = RemoveFirstLines(s2, 6);
-
-      sb.Append(s1);
-      sb.Append(s2);
+      var nodeIds = new Dictionary<ISymbolicExpressionTreeNode, string>();
+      int offset = 0;
+      var layoutEngine = new ReingoldTilfordLayoutEngine<ISymbolicExpressionTreeNode>(x => x.Subtrees);
+      var nodeCoordinates = layoutEngine.CalculateLayout(t1.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
+
+      double ws = 0.5;
+      double hs = 0.5;
+
+      var nl = Environment.NewLine;
+      sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
+                 "\\usepackage{tikz}" + nl +
+                 "\\begin{document}" + nl +
+                 "\\begin{tikzpicture}" + nl +
+                 "\\def\\ws{1}" + nl +
+                 "\\def\\hs{0.7}" + nl +
+                 "\\def\\offs{" + offset + "}" + nl);
+
+      foreach (var node in t1.IterateNodesBreadth()) {
+        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} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+      }
+
+      foreach (ISymbolicExpressionTreeNode t in t1.IterateNodesBreadth()) {
+        var n = t;
+        foreach (var s in t.Subtrees) {
+          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
+        }
+      }
+
+      nodeCoordinates = layoutEngine.CalculateLayout(t2.Root).ToDictionary(n => n.Content, n => new PointF(n.X, n.Y));
+
+      offset = 20;
+      sb.Append("\\def\\offs{" + offset + "}" + nl);
+      foreach (var node in t2.IterateNodesBreadth()) {
+        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} + \\offs,\\hs*{2}) {{{3}}};", nodeIds[node], ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+      }
+
+      foreach (ISymbolicExpressionTreeNode t in t2.IterateNodesBreadth()) {
+        var n = t;
+        foreach (var s in t.Subtrees) {
+          sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", nodeIds[n], nodeIds[s]));
+        }
+      }
 
       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});" + Environment.NewLine, id1, id2));
-      }
-
+        var id1 = nodeIds[p.Key];
+        var id2 = nodeIds[p.Value];
+
+        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->,color=gray] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
+      }
+      sb.Append("\\end{tikzpicture}" + nl +
+                "\\end{document}" + nl);
       return sb.ToString();
     }
 
+    private static string EscapeLatexString(string s) {
+      return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
+    }
   }
 }