Changeset 11209 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

Timestamp:

07/18/14 16:40:21 (10 years ago)

Author:

bburlacu

Message:

#1772: Improved performance of the BottomUpDistanceCalculator

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs (modified) (7 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

@@ -51 +51 @@
     }
 
+    private static IArc AddArc(IVertex source, IVertex target) {
+      var arc = new Arc(source, target);
+      source.AddForwardArc(arc);
+      target.AddReverseArc(arc);
+      return arc;
+    }
+
     /// <summary>
     /// Creates a compact representation of the two trees as a directed acyclic graph
@@ -58 +65 @@
     /// <returns>The compacted DAG representing the two trees</returns>
     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 L = new Dictionary<string, IVertex>();
       var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
+      var G = new List<IVertex>();
 
       var nodes = F.Nodes.ToList();
@@ -71 +78 @@
         var z = new Vertex { Content = l, Label = label };
         L[z.Label] = z;
-        G.AddVertex(z);
+        G.Add(z);
       }
 
@@ -86 +93 @@
       while (Q.Any()) {
         var v = Q.Dequeue();
+        var label = Label(v);
         if (v.SubtreeCount == 0) {
-          K[v] = L[Label(v)]; // 18
+          K[v] = L[label]; // 18
         } else {
           bool found = false;
           // for all nodes w in G in reverse order
-          var vertices = G.Vertices.Reverse();
-          foreach (var w in vertices) {
-            if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
+          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;
 
@@ -107 +115 @@
 
           if (!found) {
-            var w = new Vertex { Content = v, Label = Label(v) };
-            G.AddVertex(w);
+            var w = new Vertex { Content = v, Label = label };
+            G.Add(w);
             K[v] = w;
 
             foreach (var u in v.Subtrees) {
-              G.AddArc(w, K[u]);
+              AddArc(w, K[u]);
             } // 40: end for
           } // 41: end if
@@ -131 +139 @@
       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 plist2 = t2.IterateNodesPrefix().ToList();
-      foreach (var n in t1.IterateNodesBreadth()) {
-        ISymbolicExpressionTreeNode v = n;
-        if (!M.ContainsKey(v)) {
-          var w = plist2.Last();
-          var pw = plist2.IndexOf(w); // preorder index of node w
-          foreach (var u in plist2.Where(x => K[x] == K[v])) {
-            if (!M_.ContainsKey(u)) {
-              w = u;
-              // commented out test below since we are dealing with unordered trees
-              //              if (plist2.IndexOf(u) < pw) {
-              //                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 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;
         }
       }
@@ -218 +216 @@
 
           return nodes.OrderByDescending(x => x.Height).Select(x => x.Node);
-
-          //
-          //          var p1 = r1.Parent;
-          //          var p2 = r2.Parent;
-          //
-          //          var virtualRootSymbol = new StartSymbol();
-          //          var virtualRootNode = virtualRootSymbol.CreateTreeNode();
-          //
-          //          virtualRootNode.AddSubtree(r1);
-          //          virtualRootNode.AddSubtree(r2);
-          //
-          //          var nodes = virtualRootNode.IterateNodesPostfix().ToList();
-          //
-          //          virtualRootNode.RemoveSubtree(0);
-          //          virtualRootNode.RemoveSubtree(0);
-          //
-          //          r1.Parent = p1;
-          //          r2.Parent = p2;
-          //
-          //          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
         }
       }