Changeset 11021

Timestamp:

06/16/14 15:37:23 (10 years ago)

Author:

bburlacu

Message:

#1772: Added ExportDot method to DirectedGraph. Worked on the BottomUpDistanceCalculator.

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking/3.4/DirectedGraph/DirectedGraph.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs (modified) (9 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/DirectedGraph.cs

@@ -24 +24 @@
 using System.Drawing;
 using System.Linq;
+using System.Text;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -178 +179 @@
       get { return Common.Resources.VSImageLibrary.Graph; }
     }
+
+    public string ExportDot() {
+      var sb = new StringBuilder();
+      sb.Append("digraph g {");
+      foreach (var v in Vertices) {
+        sb.Append("\"" + v.Id + "\" [label=\"" + v.Label + "\"];" + Environment.NewLine);
+      }
+
+      foreach (var v in Vertices) {
+        foreach (var c in v.OutArcs.Select(x => x.Target)) {
+          sb.Append("\"" + v.Id + "\" -> \"" + c.Id + "\"" + Environment.NewLine);
+        }
+      }
+      sb.Append("}");
+      return sb.ToString();
+    }
   }
 }

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

@@ -36 +36 @@
       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 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 (although not specified in the paper)
-        //        if (!L.ContainsKey(z.Label))
-        L[z.Label] = z; // will overwrite key values, possible bug
+
+      var nodes = F.Nodes.ToList();
+
+      foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) {
+        var label = Label(l);
+        var z = new Vertex { Content = l, Label = label };
+        L[z.Label] = z;
         G.AddVertex(z);
       }
+
       var Q = new Queue<ISymbolicExpressionTreeNode>();
-      foreach (var v in F.Nodes) {
+      foreach (var v in nodes) {
         Children[v] = v.SubtreeCount;
         if (v.SubtreeCount == 0) {
@@ -52 +55 @@
         }
       }
+
       while (Q.Any()) {
         var v = Q.Dequeue();
@@ -60 +64 @@
 
           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
+            if (Height(v) != Height(w))
+              break;
+            if (v.SubtreeCount != w.OutDegree)
+              break;
+            if (Label(v) != w.Label)
+              break;
+
             var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
             var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
@@ -84 +91 @@
         } // 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
+        if (v.Parent == null) continue;
+        var p = v.Parent;
+        Children[p]--;
+        if (Children[p] == 0)
+          Q.Enqueue(p);
       };
+
+      using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "graph.dot"))) {
+        var str = G.ExportDot();
+        file.WriteLine(str);
+      }
+
       return K;
     }
@@ -97 +109 @@
       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()) {
+      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)) {
-              if (plist2.IndexOf(u) < plist2.IndexOf(w)) {
-                w = u;
-              }
+              w = u;
+              //              if (plist2.IndexOf(u) < pw) {
+              //                w = u;
+              //              }
             }
           }
@@ -119 +133 @@
               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;
-            //            }
           }
         }
@@ -141 +149 @@
 
       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"))) {
+        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.tex"))) {
           var str = FormatMapping(t1, t2, M);
           file.WriteLine(str);
@@ -171 +179 @@
 
       public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
-        get {
-          var nodes1 = Item1.Root.IterateNodesBreadth().Reverse();
-          var nodes2 = Item2.Root.IterateNodesBreadth().Reverse();
-
-          return nodes1.Concat(nodes2);
-
-          //          var nodes =
-          //            nodes1.Select(n => new { Node = n, Height = Item1.Root.GetBranchLevel(n) })
-          //              .Concat(nodes2.Select(n => new { Node = n, Height = Item2.Root.GetBranchLevel(n) }))
-          //              .OrderByDescending(x => x.Height)
-          //              .Select(x => x.Node);
-          //
-          //          return nodes;
-          //          //          var list = new List<ISymbolicExpressionTreeNode> { Item1.Root, Item2.Root };
-          //          //          int i = 0;
-          //          //          while (i != list.Count) {
-          //          //            var node = list[i];
-          //          //            if (node.SubtreeCount > 0) {
-          //          //              list.AddRange(node.Subtrees);
-          //          //            }
-          //          //            ++i;
-          //          //          }
-          //          //          list.Reverse(); // return nodes in order of decreasing height
-          //          //          return list;
-        }
-      }
-
-      public bool IsRoot(ISymbolicExpressionTreeNode n) {
-        return (n == Item1.Root || n == Item2.Root);
+        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
       }
     }
@@ -219 +199 @@
         var id2 = m2[p.Value];
 
-        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});", id1, id2));
+        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
       }