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

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

#2076: Updated the way the layout is used in the SymbolicExpressionTreeChart; updated simplifier view accordingly.

File size: 11.6 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<T> GetContentNodes() {
68      return nodeMap.Keys;
69    }
70
71    public IEnumerable<VisualTreeNode<T>> GetVisualNodes() {
72      return nodeMap.Values.Select(x => new VisualTreeNode<T>(x.Content) {
73        Width = (int)Math.Round(x.Width),
74        Height = (int)Math.Round(x.Height),
75        X = (int)Math.Round(x.X),
76        Y = (int)Math.Round(x.Y)
77      });
78    }
79
80    public IEnumerable<LayoutNode<T>> GetLayoutNodes() {
81      return nodeMap.Values;
82    }
83
84    public void AddNode(T content) {
85      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
86      var node = new LayoutNode<T> { Content = content };
87      nodeMap.Add(content, node);
88    }
89
90    public void AddNode(LayoutNode<T> node) {
91      var content = node.Content;
92      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
93      nodeMap.Add(content, node);
94    }
95
96    public void AddNodes(IEnumerable<LayoutNode<T>> nodes) {
97      foreach (var node in nodes)
98        nodeMap.Add(node.Content, node);
99    }
100
101    public LayoutNode<T> GetNode(T content) {
102      LayoutNode<T> layoutNode;
103      nodeMap.TryGetValue(content, out layoutNode);
104      return layoutNode;
105    }
106
107    public void ResetCoordinates() {
108      foreach (var node in nodeMap.Values) {
109        node.ResetCoordinates();
110      }
111    }
112
113    public Dictionary<T, PointF> GetCoordinates() {
114      return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
115    }
116
117    /// <summary>
118    /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
119    /// </summary>
120    private void NormalizeCoordinates() {
121      var nodes = nodeMap.Values.ToList();
122      float xmin = 0, ymin = 0;
123      foreach (var node in nodes) {
124        if (xmin > node.X) xmin = node.X;
125        if (ymin > node.Y) ymin = node.Y;
126      }
127      foreach (var node in nodes) {
128        node.X -= xmin;
129        node.Y -= ymin;
130      }
131    }
132
133    public void Center(float width, float height) {
134      // center layout on screen
135      var bounds = Bounds();
136      float dx = 0, dy = 0;
137      if (width > bounds.Width) { dx = (width - bounds.Width) / 2f; }
138      if (height > bounds.Height) { dy = (height - bounds.Height) / 2f; }
139      foreach (var node in nodeMap.Values) { node.Translate(dx, dy); }
140    }
141
142    public void FitToBounds(float width, float height) {
143      var bounds = Bounds();
144      var myWidth = bounds.Width;
145      var myHeight = bounds.Height;
146
147      if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds
148
149      var layers = nodeMap.Values.GroupBy(node => node.Level, node => node).ToList();
150
151      if (myWidth > width) {
152        // need to scale horizontally
153        float x = width / myWidth;
154        foreach (var node in layers.SelectMany(g => g)) {
155          node.X *= x;
156          node.Width *= x;
157        }
158        float spacing = minHorizontalSpacing * x;
159        foreach (var layer in layers) {
160          var nodes = layer.ToList();
161          float minWidth = float.MaxValue;
162          for (int i = 0; i < nodes.Count - 1; ++i) { minWidth = Math.Min(minWidth, nodes[i + 1].X - nodes[i].X); }
163          float w = Math.Min(NodeWidth, minWidth - spacing);
164          foreach (var node in nodes) {
165            node.X += (node.Width - w) / 2f;
166            node.Width = w;
167            //this is a simple solution to ensure that the leftmost and rightmost nodes are not drawn partially offscreen due to scaling and offset
168            //this should work well enough 99.9% of the time with no noticeable visual difference
169            if (node.X < 0) {
170              node.Width += node.X;
171              node.X = 0;
172            } else if (node.X + node.Width > width) {
173              node.Width = width - node.X;
174            }
175          }
176        }
177      }
178      if (myHeight > height) {
179        // need to scale vertically
180        float x = height / myHeight;
181        foreach (var node in layers.SelectMany(g => g)) {
182          node.Y *= x;
183          node.Height *= x;
184        }
185      }
186    }
187
188    public void Clear() {
189      layoutRoot = null;
190      nodeMap.Clear();
191    }
192
193    public void Reset() {
194      foreach (var layoutNode in nodeMap.Values) {
195        // reset layout-related parameters
196        layoutNode.Reset();
197        // reset the width and height since they might have been affected by scaling
198        layoutNode.Width = NodeWidth;
199        layoutNode.Height = NodeHeight;
200      }
201    }
202
203    public void CalculateLayout() {
204      if (layoutRoot == null) throw new Exception("Layout layoutRoot cannot be null.");
205      Reset(); // reset node parameters like Mod, Shift etc. and set coordinates to 0
206      FirstWalk(layoutRoot);
207      SecondWalk(layoutRoot, -layoutRoot.Prelim);
208      NormalizeCoordinates();
209    }
210
211    public void CalculateLayout(float width, float height) {
212      CalculateLayout();
213      FitToBounds(width, height);
214      Center(width, height);
215    }
216
217    /// <summary>
218    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
219    /// </summary>
220    /// <returns></returns>
221    public RectangleF Bounds() {
222      float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
223      var list = nodeMap.Values.ToList();
224      foreach (LayoutNode<T> node in list) {
225        float x = node.X, y = node.Y;
226        if (xmin > x) xmin = x;
227        if (xmax < x) xmax = x;
228        if (ymin > y) ymin = y;
229        if (ymax < y) ymax = y;
230      }
231      return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
232    }
233
234    #region methods specific to the reingold-tilford layout algorithm
235    private void FirstWalk(LayoutNode<T> v) {
236      LayoutNode<T> w;
237      if (v.IsLeaf) {
238        w = v.LeftSibling;
239        if (w != null) {
240          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
241        }
242      } else {
243        var defaultAncestor = v.Children[0]; // leftmost child
244
245        foreach (var child in v.Children) {
246          FirstWalk(child);
247          Apportion(child, ref defaultAncestor);
248        }
249        ExecuteShifts(v);
250        var leftmost = v.Children.First();
251        var rightmost = v.Children.Last();
252        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
253        w = v.LeftSibling;
254        if (w != null) {
255          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
256          v.Mod = v.Prelim - midPoint;
257        } else {
258          v.Prelim = midPoint;
259        }
260      }
261    }
262
263    private void SecondWalk(LayoutNode<T> v, float m) {
264      v.X = v.Prelim + m;
265      v.Y = v.Level * (minVerticalSpacing + NodeHeight);
266      if (v.IsLeaf) return;
267      foreach (var child in v.Children) {
268        SecondWalk(child, m + v.Mod);
269      }
270    }
271
272    private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {
273      var w = v.LeftSibling;
274      if (w == null) return;
275      LayoutNode<T> vip = v;
276      LayoutNode<T> vop = v;
277      LayoutNode<T> vim = w;
278      LayoutNode<T> vom = vip.LeftmostSibling;
279
280      float sip = vip.Mod;
281      float sop = vop.Mod;
282      float sim = vim.Mod;
283      float som = vom.Mod;
284
285      while (vim.NextRight != null && vip.NextLeft != null) {
286        vim = vim.NextRight;
287        vip = vip.NextLeft;
288        vom = vom.NextLeft;
289        vop = vop.NextRight;
290        vop.Ancestor = v;
291        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
292        if (shift > 0) {
293          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
294          MoveSubtree(ancestor, v, shift);
295          sip += shift;
296          sop += shift;
297        }
298        sim += vim.Mod;
299        sip += vip.Mod;
300        som += vom.Mod;
301        sop += vop.Mod;
302      }
303      if (vim.NextRight != null && vop.NextRight == null) {
304        vop.Thread = vim.NextRight;
305        vop.Mod += (sim - sop);
306      }
307      if (vip.NextLeft != null && vom.NextLeft == null) {
308        vom.Thread = vip.NextLeft;
309        vom.Mod += (sip - som);
310        defaultAncestor = v;
311      }
312    }
313
314    private void MoveSubtree(LayoutNode<T> wm, LayoutNode<T> wp, float shift) {
315      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)
316      if (subtrees == 0) throw new Exception("MoveSubtree failed: check if object is really a tree (no cycles)");
317      wp.Change -= shift / subtrees;
318      wp.Shift += shift;
319      wm.Change += shift / subtrees;
320      wp.Prelim += shift;
321      wp.Mod += shift;
322    }
323
324    private void ExecuteShifts(LayoutNode<T> v) {
325      if (v.IsLeaf) return;
326      float shift = 0;
327      float change = 0;
328      for (int i = v.Children.Count - 1; i >= 0; --i) {
329        var w = v.Children[i];
330        w.Prelim += shift;
331        w.Mod += shift;
332        change += w.Change;
333        shift += (w.Shift + change);
334      }
335    }
336
337    private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {
338      var ancestor = u.Ancestor;
339      if (ancestor == null) return null;
340      return ancestor.Parent == v.Parent ? ancestor : null;
341    }
342    #endregion
343  }
344}
Note: See TracBrowser for help on using the repository browser.