source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/TreeLayout.cs @ 9835

Last change on this file since 9835 was 9835, checked in by bburlacu, 8 years ago

#1772: Merged remaining trunk changes into the EvolutionaryTracking branch.

File size: 9.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26
27namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
28  public class Node {
29    public Node Thread;
30    public Node Ancestor;
31
32    public float Mod; // position modifier
33    public float Prelim;
34    public float Change;
35    public float Shift;
36    public int Number;
37
38    public float X;
39    public float Y;
40
41    public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
42
43    //    public int Number {
44    //      get {
45    //        var parent = SymbolicExpressionTreeNode.Parent;
46    //        if (parent == null) return -1;
47    //        return parent.IndexOfSubtree(SymbolicExpressionTreeNode);
48    //      }
49    //    }
50
51    public bool IsLeaf {
52      get { return SymbolicExpressionTreeNode.SubtreeCount == 0; }
53    }
54  }
55
56  public class TreeLayout {
57    private float distance = 5;
58    public float Distance {
59      get { return distance; }
60      set { distance = value; }
61    }
62
63    private ISymbolicExpressionTree symbolicExpressionTree;
64    public ISymbolicExpressionTree SymbolicExpressionTree {
65      get { return symbolicExpressionTree; }
66      set {
67        symbolicExpressionTree = value;
68        nodes.Clear();
69        var treeNodes = SymbolicExpressionTree.IterateNodesBreadth().ToList();
70        foreach (var treeNode in treeNodes) {
71          var node = new Node { SymbolicExpressionTreeNode = treeNode };
72          node.Ancestor = node;
73          nodes.Add(treeNode, node);
74        }
75        // assign a number to each node, representing its position among its siblings (parent.IndexOfSubtree)
76        foreach (var treeNode in treeNodes.Where(x => x.SubtreeCount > 0)) {
77          for (int i = 0; i != treeNode.SubtreeCount; ++i) {
78            nodes[treeNode.GetSubtree(i)].Number = i;
79          }
80        }
81        var r = nodes[symbolicExpressionTree.Root];
82        FirstWalk(r);
83        SecondWalk(r, -r.Prelim);
84        NormalizeCoordinates();
85      }
86    }
87
88    /// <summary>
89    /// Returns a map of coordinates for each node in the symbolic expression tree.
90    /// </summary>
91    /// <returns></returns>
92    public Dictionary<ISymbolicExpressionTreeNode, PointF> GetNodeCoordinates() {
93      var dict = new Dictionary<ISymbolicExpressionTreeNode, PointF>();
94      if (nodes == null || nodes.Count == 0) return dict;
95      foreach (var node in nodes.Values) {
96        dict.Add(node.SymbolicExpressionTreeNode, new PointF { X = node.X, Y = node.Y });
97      }
98      return dict;
99    }
100
101    /// <summary>
102    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
103    /// </summary>
104    /// <returns></returns>
105    public RectangleF Bounds() {
106      float xmin, xmax, ymin, ymax; xmin = xmax = ymin = ymax = 0;
107      var list = nodes.Values.ToList();
108      for (int i = 0; i != list.Count; ++i) {
109        float x = list[i].X, y = list[i].Y;
110        if (xmin > x) xmin = x;
111        if (xmax < x) xmax = x;
112        if (ymin > y) ymin = y;
113        if (ymax < y) ymax = y;
114      }
115      return new RectangleF(xmin, ymin, xmax + distance, ymax + distance);
116    }
117
118    /// <summary>
119    /// Returns a string containing all the coordinates (useful for debugging).
120    /// </summary>
121    /// <returns></returns>
122    public string DumpCoordinates() {
123      if (nodes == null || nodes.Count == 0) return string.Empty;
124      return nodes.Values.Aggregate("", (current, node) => current + (node.X + " " + node.Y + Environment.NewLine));
125    }
126
127    private readonly Dictionary<ISymbolicExpressionTreeNode, Node> nodes;
128
129    public TreeLayout() {
130      nodes = new Dictionary<ISymbolicExpressionTreeNode, Node>();
131    }
132
133    /// <summary>
134    /// Transform node coordinates so that all coordinates are positive and start from 0.
135    /// </summary>
136    private void NormalizeCoordinates() {
137      var list = nodes.Values.ToList();
138      float xmin = 0, ymin = 0;
139      for (int i = 0; i != list.Count; ++i) {
140        if (xmin > list[i].X) xmin = list[i].X;
141        if (ymin > list[i].Y) ymin = list[i].Y;
142      }
143      for (int i = 0; i != list.Count; ++i) {
144        list[i].X -= xmin;
145        list[i].Y -= ymin;
146      }
147    }
148
149    private void FirstWalk(Node v) {
150      Node w;
151      if (v.IsLeaf) {
152        w = LeftSibling(v);
153        if (w != null) {
154          v.Prelim = w.Prelim + distance;
155        }
156      } else {
157        var symbExprNode = v.SymbolicExpressionTreeNode;
158        var defaultAncestor = nodes[symbExprNode.GetSubtree(0)]; // let defaultAncestor be the leftmost child of v
159        for (int i = 0; i != symbExprNode.SubtreeCount; ++i) {
160          var s = symbExprNode.GetSubtree(i);
161          w = nodes[s];
162          FirstWalk(w);
163          Apportion(w, ref defaultAncestor);
164        }
165        ExecuteShifts(v);
166        int c = symbExprNode.SubtreeCount;
167        var leftmost = nodes[symbExprNode.GetSubtree(0)];
168        var rightmost = nodes[symbExprNode.GetSubtree(c - 1)];
169        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
170        w = LeftSibling(v);
171        if (w != null) {
172          v.Prelim = w.Prelim + distance;
173          v.Mod = v.Prelim - midPoint;
174        } else {
175          v.Prelim = midPoint;
176        }
177      }
178    }
179
180    private void SecondWalk(Node v, float m) {
181      v.X = v.Prelim + m;
182      v.Y = symbolicExpressionTree.Root.GetBranchLevel(v.SymbolicExpressionTreeNode) * distance;
183      var symbExprNode = v.SymbolicExpressionTreeNode;
184      foreach (var s in symbExprNode.Subtrees) {
185        SecondWalk(nodes[s], m + v.Mod);
186      }
187    }
188
189    private void Apportion(Node v, ref Node defaultAncestor) {
190      var w = LeftSibling(v);
191      if (w == null) return;
192      Node vip = v;
193      Node vop = v;
194      Node vim = w;
195      Node vom = LeftmostSibling(vip);
196
197      float sip = vip.Mod;
198      float sop = vop.Mod;
199      float sim = vim.Mod;
200      float som = vom.Mod;
201
202      while (NextRight(vim) != null && NextLeft(vip) != null) {
203        vim = NextRight(vim);
204        vip = NextLeft(vip);
205        vom = NextLeft(vom);
206        vop = NextRight(vop);
207        vop.Ancestor = v;
208        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + distance;
209        if (shift > 0) {
210          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
211          MoveSubtree(ancestor, v, shift);
212          sip += shift;
213          sop += shift;
214        }
215        sim += vim.Mod;
216        sip += vip.Mod;
217        som += vom.Mod;
218        sop += vop.Mod;
219      }
220      if (NextRight(vim) != null && NextRight(vop) == null) {
221        vop.Thread = NextRight(vim);
222        vop.Mod += (sim - sop);
223      }
224      if (NextLeft(vip) != null && NextLeft(vom) == null) {
225        vom.Thread = NextLeft(vip);
226        vom.Mod += (sip - som);
227        defaultAncestor = v;
228      }
229    }
230
231    private void MoveSubtree(Node wm, Node wp, float shift) {
232      int subtrees = wp.Number - wm.Number;
233      wp.Change -= shift / subtrees;
234      wp.Shift += shift;
235      wm.Change += shift / subtrees;
236      wp.Prelim += shift;
237      wp.Mod += shift;
238    }
239
240    private void ExecuteShifts(Node v) {
241      if (v.IsLeaf) return;
242      float shift = 0;
243      float change = 0;
244      for (int i = v.SymbolicExpressionTreeNode.SubtreeCount - 1; i >= 0; --i) {
245        var subtree = v.SymbolicExpressionTreeNode.GetSubtree(i);
246        var w = nodes[subtree];
247        w.Prelim += shift;
248        w.Mod += shift;
249        change += w.Change;
250        shift += (w.Shift + change);
251      }
252    }
253
254    #region Helper functions
255    private Node Ancestor(Node vi, Node v) {
256      var ancestor = vi.Ancestor;
257      return ancestor.SymbolicExpressionTreeNode.Parent == v.SymbolicExpressionTreeNode.Parent ? ancestor : null;
258    }
259
260    private Node NextLeft(Node v) {
261      int c = v.SymbolicExpressionTreeNode.SubtreeCount;
262      return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(0)]; // return leftmost child
263    }
264
265    private Node NextRight(Node v) {
266      int c = v.SymbolicExpressionTreeNode.SubtreeCount;
267      return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(c - 1)]; // return rightmost child
268    }
269
270    private Node LeftSibling(Node n) {
271      var parent = n.SymbolicExpressionTreeNode.Parent;
272      if (parent == null) return null;
273      int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);
274      if (i == 0) return null;
275      return nodes[parent.GetSubtree(i - 1)];
276    }
277
278    private Node LeftmostSibling(Node n) {
279      var parent = n.SymbolicExpressionTreeNode.Parent;
280      if (parent == null) return null;
281      int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);
282      if (i == 0) return null;
283      return nodes[parent.GetSubtree(0)];
284    }
285    #endregion
286  }
287}
Note: See TracBrowser for help on using the repository browser.