Changeset 11021


Ignore:
Timestamp:
06/16/14 15:37:23 (5 years ago)
Author:
bburlacu
Message:

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

Location:
branches/HeuristicLab.EvolutionTracking
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/DirectedGraph/DirectedGraph.cs

    r10936 r11021  
    2424using System.Drawing;
    2525using System.Linq;
     26using System.Text;
    2627using HeuristicLab.Common;
    2728using HeuristicLab.Core;
     
    178179      get { return Common.Resources.VSImageLibrary.Graph; }
    179180    }
     181
     182    public string ExportDot() {
     183      var sb = new StringBuilder();
     184      sb.Append("digraph g {");
     185      foreach (var v in Vertices) {
     186        sb.Append("\"" + v.Id + "\" [label=\"" + v.Label + "\"];" + Environment.NewLine);
     187      }
     188
     189      foreach (var v in Vertices) {
     190        foreach (var c in v.OutArcs.Select(x => x.Target)) {
     191          sb.Append("\"" + v.Id + "\" -> \"" + c.Id + "\"" + Environment.NewLine);
     192        }
     193      }
     194      sb.Append("}");
     195      return sb.ToString();
     196    }
    180197  }
    181198}
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeDistance/BottomUpDistanceCalculator.cs

    r11016 r11021  
    3636      var K = new Dictionary<ISymbolicExpressionTreeNode, IVertex>();
    3737      var F = new DisjointUnion(t1, t2);
     38      var L = new Dictionary<string, IVertex>();
    3839      var Children = new Dictionary<ISymbolicExpressionTreeNode, int>();
    39       var L = new Dictionary<string, IVertex>();
    40       foreach (var l in F.Nodes.Where(x => x.SubtreeCount == 0)) {
    41         var z = new Vertex { Content = l, Label = Label(l) };
    42         //        z.Weight = Height(l); // might be necessary (although not specified in the paper)
    43         //        if (!L.ContainsKey(z.Label))
    44         L[z.Label] = z; // will overwrite key values, possible bug
     40
     41      var nodes = F.Nodes.ToList();
     42
     43      foreach (var l in nodes.Where(x => x.SubtreeCount == 0)) {
     44        var label = Label(l);
     45        var z = new Vertex { Content = l, Label = label };
     46        L[z.Label] = z;
    4547        G.AddVertex(z);
    4648      }
     49
    4750      var Q = new Queue<ISymbolicExpressionTreeNode>();
    48       foreach (var v in F.Nodes) {
     51      foreach (var v in nodes) {
    4952        Children[v] = v.SubtreeCount;
    5053        if (v.SubtreeCount == 0) {
     
    5255        }
    5356      }
     57
    5458      while (Q.Any()) {
    5559        var v = Q.Dequeue();
     
    6064
    6165          foreach (var w in G.Vertices.Reverse()) {
    62             if (Height(v) != Height(w) || v.SubtreeCount != w.OutDegree || Label(v) != w.Label)
    63               break;
    64 
    65             // sort the lists before comparison, as required when dealing with unordered trees
     66            if (Height(v) != Height(w))
     67              break;
     68            if (v.SubtreeCount != w.OutDegree)
     69              break;
     70            if (Label(v) != w.Label)
     71              break;
     72
    6673            var V = v.Subtrees.Select(s => K[s]).OrderBy(x => x.Label);
    6774            var W = w.OutArcs.Select(x => x.Target).OrderBy(x => x.Label);
     
    8491        } // 42: end if
    8592
    86         if (!F.IsRoot(v)) {
    87           Children[v.Parent] = Children[v.Parent] - 1;
    88           if (Children[v.Parent] == 0) {
    89             Q.Enqueue(v.Parent);
    90           } // 47: end if
    91         } // 48: end if
     93        if (v.Parent == null) continue;
     94        var p = v.Parent;
     95        Children[p]--;
     96        if (Children[p] == 0)
     97          Q.Enqueue(p);
    9298      };
     99
     100      using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "graph.dot"))) {
     101        var str = G.ExportDot();
     102        file.WriteLine(str);
     103      }
     104
    93105      return K;
    94106    }
     
    97109      var M = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
    98110      var M_ = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
    99       //var plist1 = t1.IterateNodesPrefix().ToList();
    100111      var plist2 = t2.IterateNodesPrefix().ToList();
    101       foreach (var v in t1.IterateNodesBreadth()) {
     112      foreach (var n in t1.IterateNodesBreadth()) {
     113        ISymbolicExpressionTreeNode v = n;
    102114        if (!M.ContainsKey(v)) {
    103115          var w = plist2.Last();
     116          var pw = plist2.IndexOf(w); // preorder index of node w
    104117          foreach (var u in plist2.Where(x => K[x] == K[v])) {
    105118            if (!M_.ContainsKey(u)) {
    106               if (plist2.IndexOf(u) < plist2.IndexOf(w)) {
    107                 w = u;
    108               }
     119              w = u;
     120              //              if (plist2.IndexOf(u) < pw) {
     121              //                w = u;
     122              //              }
    109123            }
    110124          }
     
    119133              M_[t] = s;
    120134            }
    121             //            var e1 = v.IterateNodesPrefix().GetEnumerator();
    122             //            var e2 = w.IterateNodesPrefix().GetEnumerator();
    123             //            while (e1.MoveNext() && e2.MoveNext()) {
    124             //              M[e1.Current] = e2.Current;
    125             //              M_[e2.Current] = e1.Current;
    126             //            }
    127135          }
    128136        }
     
    141149
    142150      if (distance / (t1.Length + t2.Length) > 0.5 && M.Count > 0) {
    143         using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.txt"))) {
     151        using (var file = new StreamWriter(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "map.tex"))) {
    144152          var str = FormatMapping(t1, t2, M);
    145153          file.WriteLine(str);
     
    171179
    172180      public IEnumerable<ISymbolicExpressionTreeNode> Nodes {
    173         get {
    174           var nodes1 = Item1.Root.IterateNodesBreadth().Reverse();
    175           var nodes2 = Item2.Root.IterateNodesBreadth().Reverse();
    176 
    177           return nodes1.Concat(nodes2);
    178 
    179           //          var nodes =
    180           //            nodes1.Select(n => new { Node = n, Height = Item1.Root.GetBranchLevel(n) })
    181           //              .Concat(nodes2.Select(n => new { Node = n, Height = Item2.Root.GetBranchLevel(n) }))
    182           //              .OrderByDescending(x => x.Height)
    183           //              .Select(x => x.Node);
    184           //
    185           //          return nodes;
    186           //          //          var list = new List<ISymbolicExpressionTreeNode> { Item1.Root, Item2.Root };
    187           //          //          int i = 0;
    188           //          //          while (i != list.Count) {
    189           //          //            var node = list[i];
    190           //          //            if (node.SubtreeCount > 0) {
    191           //          //              list.AddRange(node.Subtrees);
    192           //          //            }
    193           //          //            ++i;
    194           //          //          }
    195           //          //          list.Reverse(); // return nodes in order of decreasing height
    196           //          //          return list;
    197         }
    198       }
    199 
    200       public bool IsRoot(ISymbolicExpressionTreeNode n) {
    201         return (n == Item1.Root || n == Item2.Root);
     181        get { return Item1.Root.IterateNodesPostfix().Concat(Item2.Root.IterateNodesPostfix()); }
    202182      }
    203183    }
     
    219199        var id2 = m2[p.Value];
    220200
    221         sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});", id1, id2));
     201        sb.Append(string.Format(CultureInfo.InvariantCulture, "\\path[draw,->] ({0}) edge[bend left,dashed] ({1});" + Environment.NewLine, id1, id2));
    222202      }
    223203
Note: See TracChangeset for help on using the changeset viewer.