source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs @ 10520

Last change on this file since 10520 was 10520, checked in by bburlacu, 5 years ago

#2076: Got rid of layout adapters. Extracted the previous drawing code and made it into another layout engine called the BoxesLayoutEngine (because it divides the areas necessary for each subtree into boxes and recursively applies the layout). Simplified usage of layout engine so that most of the things are handled internally, and the user just has to provide some lambdas telling the engine how to navigate the original tree. Added context option in the SymbolicExpressionTreeChart to choose which layout engine to use for tree drawing. Moved the SymbolicExpressionTreeLatexFormatter to the HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views assembly because it depends on the layout engine.

File size: 11.2 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using System.Drawing;
5using System.Linq;
6
7namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
8  public class ReingoldTilfordLayoutEngine<T> : ILayoutEngine<T> where T : class {
9    private readonly Dictionary<T, LayoutNode<T>> nodeMap; // provides a reverse mapping T => LayoutNode
10    public int NodeWidth { get; set; }
11    public int NodeHeight { get; set; }
12    private int minHorizontalSpacing = 5;
13    public int HorizontalSpacing {
14      get { return minHorizontalSpacing; }
15      set { minHorizontalSpacing = value; }
16    }
17
18    private int minVerticalSpacing = 5;
19    public int VerticalSpacing {
20      get { return minVerticalSpacing; }
21      set { minVerticalSpacing = value; }
22    }
23
24    public Func<T, IEnumerable<T>> GetChildren { get; set; }
25    public Func<T, int> GetLength { get; set; }
26    public Func<T, int> GetDepth { get; set; }
27    private LayoutNode<T> layoutRoot;
28
29    public ReingoldTilfordLayoutEngine() {
30      nodeMap = new Dictionary<T, LayoutNode<T>>();
31    }
32
33    public ReingoldTilfordLayoutEngine(T root, Func<T, IEnumerable<T>> childrenFunc)
34      : this() {
35      Initialize(root, childrenFunc);
36    }
37
38    public void Initialize(T root, Func<T, IEnumerable<T>> getChildren, Func<T, int> getLength = null, Func<T, int> getDepth = null) {
39      GetChildren = getChildren;
40      Clear();
41      var node = new LayoutNode<T> { Content = root, Width = NodeWidth, Height = NodeHeight };
42      node.Ancestor = node;
43      layoutRoot = node;
44      Expand(node);
45    }
46
47    private void Expand(LayoutNode<T> lRoot) {
48      nodeMap.Add(lRoot.Content, lRoot);
49      var children = GetChildren(lRoot.Content).ToList();
50      if (!children.Any()) return;
51      lRoot.Children = new List<LayoutNode<T>>(children.Count);
52      for (int i = 0; i < children.Count; ++i) {
53        var node = new LayoutNode<T> {
54          Content = children[i],
55          Number = i,
56          Parent = lRoot,
57          Level = lRoot.Level + 1,
58          Width = NodeWidth,
59          Height = NodeHeight
60        };
61        node.Ancestor = node;
62        lRoot.Children.Add(node);
63        Expand(node);
64      }
65    }
66
67    public IEnumerable<VisualTreeNode<T>> GetVisualNodes() {
68      return nodeMap.Values.Select(x => new VisualTreeNode<T>(x.Content) {
69        Width = (int)Math.Round(x.Width),
70        Height = (int)Math.Round(x.Height),
71        X = (int)Math.Round(x.X),
72        Y = (int)Math.Round(x.Y)
73      });
74    }
75
76    public void AddNode(T content) {
77      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
78      var node = new LayoutNode<T> { Content = content };
79      nodeMap.Add(content, node);
80    }
81
82    public void AddNode(LayoutNode<T> node) {
83      var content = node.Content;
84      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
85      nodeMap.Add(content, node);
86    }
87
88    public void AddNodes(IEnumerable<LayoutNode<T>> nodes) {
89      foreach (var node in nodes)
90        nodeMap.Add(node.Content, node);
91    }
92
93    public LayoutNode<T> GetNode(T content) {
94      LayoutNode<T> layoutNode;
95      nodeMap.TryGetValue(content, out layoutNode);
96      return layoutNode;
97    }
98
99    public void ResetCoordinates() {
100      foreach (var node in nodeMap.Values) {
101        node.ResetCoordinates();
102      }
103    }
104
105    public Dictionary<T, PointF> GetCoordinates() {
106      return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
107    }
108
109    /// <summary>
110    /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
111    /// </summary>
112    private void NormalizeCoordinates() {
113      var nodes = nodeMap.Values.ToList();
114      float xmin = 0, ymin = 0;
115      foreach (var node in nodes) {
116        if (xmin > node.X) xmin = node.X;
117        if (ymin > node.Y) ymin = node.Y;
118      }
119      foreach (var node in nodes) {
120        node.X -= xmin;
121        node.Y -= ymin;
122      }
123    }
124
125    public void Center(float width, float height) {
126      // center layout on screen
127      var bounds = Bounds();
128      float dx = 0, dy = 0;
129      if (width > bounds.Width) { dx = (width - bounds.Width) / 2f; }
130      if (height > bounds.Height) { dy = (height - bounds.Height) / 2f; }
131      foreach (var node in nodeMap.Values) { node.Translate(dx, dy); }
132    }
133
134    public void FitToBounds(float width, float height) {
135      var bounds = Bounds();
136      var myWidth = bounds.Width;
137      var myHeight = bounds.Height;
138
139      if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds
140
141      var layers = nodeMap.Values.GroupBy(node => node.Level, node => node).ToList();
142
143      if (myWidth > width) {
144        // need to scale horizontally
145        float x = width / myWidth;
146        foreach (var node in layers.SelectMany(g => g)) {
147          node.X *= x;
148          node.Width *= x;
149        }
150        float spacing = minHorizontalSpacing * x;
151        foreach (var layer in layers) {
152          var nodes = layer.ToList();
153          float minWidth = float.MaxValue;
154          for (int i = 0; i < nodes.Count - 1; ++i) { minWidth = Math.Min(minWidth, nodes[i + 1].X - nodes[i].X); }
155          float w = Math.Min(NodeWidth, minWidth - spacing);
156          foreach (var node in nodes) {
157            node.X += (node.Width - w) / 2f;
158            node.Width = w;
159            //this is a simple solution to ensure that the leftmost and rightmost nodes are not drawn partially offscreen due to scaling and offset
160            //this should work well enough 99.9% of the time with no noticeable visual difference
161            if (node.X < 0) {
162              node.Width += node.X;
163              node.X = 0;
164            } else if (node.X + node.Width > width) {
165              node.Width = width - node.X;
166            }
167          }
168        }
169      }
170      if (myHeight > height) {
171        // need to scale vertically
172        float x = height / myHeight;
173        foreach (var node in layers.SelectMany(g => g)) {
174          node.Y *= x;
175          node.Height *= x;
176        }
177      }
178    }
179
180    public void Clear() {
181      layoutRoot = null;
182      nodeMap.Clear();
183    }
184
185    public void Reset() {
186      foreach (var layoutNode in nodeMap.Values) {
187        // reset layout-related parameters
188        layoutNode.Reset();
189      }
190    }
191
192    public void CalculateLayout() {
193      if (layoutRoot == null) throw new Exception("Layout layoutRoot cannot be null.");
194      Reset(); // reset node parameters like Mod, Shift etc. and set coordinates to 0
195      FirstWalk(layoutRoot);
196      SecondWalk(layoutRoot, -layoutRoot.Prelim);
197      NormalizeCoordinates();
198    }
199
200    public void CalculateLayout(float width, float height) {
201      CalculateLayout();
202      FitToBounds(width, height);
203      Center(width, height);
204    }
205
206    /// <summary>
207    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
208    /// </summary>
209    /// <returns></returns>
210    public RectangleF Bounds() {
211      float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
212      var list = nodeMap.Values.ToList();
213      foreach (LayoutNode<T> node in list) {
214        float x = node.X, y = node.Y;
215        if (xmin > x) xmin = x;
216        if (xmax < x) xmax = x;
217        if (ymin > y) ymin = y;
218        if (ymax < y) ymax = y;
219      }
220      return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
221    }
222
223    #region methods specific to the reingold-tilford layout algorithm
224    private void FirstWalk(LayoutNode<T> v) {
225      LayoutNode<T> w;
226      if (v.IsLeaf) {
227        w = v.LeftSibling;
228        if (w != null) {
229          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
230        }
231      } else {
232        var defaultAncestor = v.Children[0]; // leftmost child
233
234        foreach (var child in v.Children) {
235          FirstWalk(child);
236          Apportion(child, ref defaultAncestor);
237        }
238        ExecuteShifts(v);
239        var leftmost = v.Children.First();
240        var rightmost = v.Children.Last();
241        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
242        w = v.LeftSibling;
243        if (w != null) {
244          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
245          v.Mod = v.Prelim - midPoint;
246        } else {
247          v.Prelim = midPoint;
248        }
249      }
250    }
251
252    private void SecondWalk(LayoutNode<T> v, float m) {
253      v.X = v.Prelim + m;
254      v.Y = v.Level * (minVerticalSpacing + NodeHeight);
255      if (v.IsLeaf) return;
256      foreach (var child in v.Children) {
257        SecondWalk(child, m + v.Mod);
258      }
259    }
260
261    private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {
262      var w = v.LeftSibling;
263      if (w == null) return;
264      LayoutNode<T> vip = v;
265      LayoutNode<T> vop = v;
266      LayoutNode<T> vim = w;
267      LayoutNode<T> vom = vip.LeftmostSibling;
268
269      float sip = vip.Mod;
270      float sop = vop.Mod;
271      float sim = vim.Mod;
272      float som = vom.Mod;
273
274      while (vim.NextRight != null && vip.NextLeft != null) {
275        vim = vim.NextRight;
276        vip = vip.NextLeft;
277        vom = vom.NextLeft;
278        vop = vop.NextRight;
279        vop.Ancestor = v;
280        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
281        if (shift > 0) {
282          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
283          MoveSubtree(ancestor, v, shift);
284          sip += shift;
285          sop += shift;
286        }
287        sim += vim.Mod;
288        sip += vip.Mod;
289        som += vom.Mod;
290        sop += vop.Mod;
291      }
292      if (vim.NextRight != null && vop.NextRight == null) {
293        vop.Thread = vim.NextRight;
294        vop.Mod += (sim - sop);
295      }
296      if (vip.NextLeft != null && vom.NextLeft == null) {
297        vom.Thread = vip.NextLeft;
298        vom.Mod += (sip - som);
299        defaultAncestor = v;
300      }
301    }
302
303    private void MoveSubtree(LayoutNode<T> wm, LayoutNode<T> wp, float shift) {
304      int subtrees = wp.Number - wm.Number; // TODO: Investigate possible bug (if the value ever happens to be zero) - happens when the tree is actually a graph (but that's outside the use case of this algorithm which only works with trees)
305      if (subtrees == 0) throw new Exception("MoveSubtree failed: check if object is really a tree (no cycles)");
306      wp.Change -= shift / subtrees;
307      wp.Shift += shift;
308      wm.Change += shift / subtrees;
309      wp.Prelim += shift;
310      wp.Mod += shift;
311    }
312
313    private void ExecuteShifts(LayoutNode<T> v) {
314      if (v.IsLeaf) return;
315      float shift = 0;
316      float change = 0;
317      for (int i = v.Children.Count - 1; i >= 0; --i) {
318        var w = v.Children[i];
319        w.Prelim += shift;
320        w.Mod += shift;
321        change += w.Change;
322        shift += (w.Shift + change);
323      }
324    }
325
326    private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {
327      var ancestor = u.Ancestor;
328      if (ancestor == null) return null;
329      return ancestor.Parent == v.Parent ? ancestor : null;
330    }
331    #endregion
332  }
333}
Note: See TracBrowser for help on using the repository browser.