Changeset 11165 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

07/09/14 16:40:29 (10 years ago)

Author:

bburlacu

Message:

#1772: Added fix to improve accuracy of bottom-up tree distance.

File:

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

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

@@ -26 +26 @@
 using System.Linq;
 using System.Text;
+using System.Text.RegularExpressions;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views;
@@ -36 +37 @@
   /// </summary>
   public static class BottomUpDistanceCalculator {
+    /// <summary>
+    /// Creates a compact representation of the two trees as a directed acyclic graph
+    /// </summary>
+    /// <param name="t1">The first tree</param>
+    /// <param name="t2">The second tree</param>
+    /// <returns>The compacted DAG representing the two trees</returns>
     private static Dictionary<ISymbolicExpressionTreeNode, IVertex> Compact(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
       var G = new DirectedGraph();
@@ -79 +86 @@
             if (V.SequenceEqual(W)) {
               K[v] = w;
+              //              // merge vertices
+              //              foreach (var a in K[v].InArcs) {
+              //                a.Target = w;
+              //              }
+              //              G.RemoveVertex(K[v]);
+
               found = true;
               break;
@@ -148 +161 @@
       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)));
@@ -185 +209 @@
 
       public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
-        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
-      }
+        get {
+          var r1 = Item1.Root;
+          var r2 = Item2.Root;
+
+          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);
+
+          for (int i = 0; i < nodes.Count - 1; ++i) { yield return nodes[i]; }
+        }
+      }
+    }
+
+    public static string RemoveFirstLines(string text, int linesCount) {
+      var lines = Regex.Split(text, "\r\n|\r|\n").Skip(linesCount);
+      return string.Join(Environment.NewLine, lines.ToArray());
     }
 
@@ -198 +242 @@
       var m2 = formatter.Format(t2, out s2, 20);
 
+      // skip first 6 lines of s2
+      s2 = RemoveFirstLines(s2, 6);
+
       sb.Append(s1);
       sb.Append(s2);