source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs @ 11120

Last change on this file since 11120 was 11120, checked in by gkronber, 5 years ago

#2076,#2159, #2092
multi-ticket merge to stable:

File size: 9.5 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    public int NodeWidth { get; set; }
10    public int NodeHeight { get; set; }
11    private int minHorizontalSpacing = 5;
12    public int HorizontalSpacing {
13      get { return minHorizontalSpacing; }
14      set { minHorizontalSpacing = value; }
15    }
16
17    private int minVerticalSpacing = 5;
18    public int VerticalSpacing {
19      get { return minVerticalSpacing; }
20      set { minVerticalSpacing = value; }
21    }
22
23    private readonly Func<T, IEnumerable<T>> GetChildren;
24
25    public ReingoldTilfordLayoutEngine(Func<T, IEnumerable<T>> GetChildren) {
26      this.GetChildren = GetChildren;
27    }
28
29    public IEnumerable<VisualTreeNode<T>> CalculateLayout(T root) {
30      return CalculateLayout(root, 0, 0);
31    }
32
33    public IEnumerable<VisualTreeNode<T>> CalculateLayout(T root, float width, float height) {
34      Dictionary<T, LayoutNode<T>> layoutNodeMap = new Dictionary<T, LayoutNode<T>>();
35      var layoutRoot = new LayoutNode<T> { Content = root, Width = NodeWidth, Height = NodeHeight, };
36      layoutRoot.Ancestor = layoutRoot;
37      Expand(layoutRoot, layoutNodeMap);
38
39      FirstWalk(layoutRoot);
40      SecondWalk(layoutRoot, -layoutRoot.Prelim);
41      NormalizeCoordinates(layoutNodeMap.Values);
42      if (height != 0 && width != 0) {
43        FitToBounds(width, height, layoutNodeMap.Values);
44        Center(width, height, layoutNodeMap.Values);
45      }
46
47      return layoutNodeMap.Values.Select(x => new VisualTreeNode<T>(x.Content) {
48        Width = (int)Math.Round(x.Width),
49        Height = (int)Math.Round(x.Height),
50        X = (int)Math.Round(x.X),
51        Y = (int)Math.Round(x.Y)
52      });
53    }
54
55    private void Expand(LayoutNode<T> lRoot, Dictionary<T, LayoutNode<T>> map) {
56      map.Add(lRoot.Content, lRoot);
57      var children = GetChildren(lRoot.Content).ToList();
58      if (!children.Any()) return;
59      lRoot.Children = new List<LayoutNode<T>>(children.Count);
60      for (int i = 0; i < children.Count; ++i) {
61        var node = new LayoutNode<T> {
62          Content = children[i],
63          Number = i,
64          Parent = lRoot,
65          Level = lRoot.Level + 1,
66          Width = NodeWidth,
67          Height = NodeHeight
68        };
69        node.Ancestor = node;
70        lRoot.Children.Add(node);
71        Expand(node, map);
72      }
73    }
74
75
76    /// <summary>
77    /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
78    /// </summary>
79    private static void NormalizeCoordinates(IEnumerable<LayoutNode<T>> nodes) {
80      float xmin = 0, ymin = 0;
81      foreach (var node in nodes) {
82        if (xmin > node.X) xmin = node.X;
83        if (ymin > node.Y) ymin = node.Y;
84      }
85      foreach (var node in nodes) {
86        node.X -= xmin;
87        node.Y -= ymin;
88      }
89    }
90
91    private void Center(float width, float height, IEnumerable<LayoutNode<T>> nodes) {
92      // center layout on screen
93      var bounds = Bounds(nodes);
94      float dx = 0, dy = 0;
95      if (width > bounds.Width) { dx = (width - bounds.Width) / 2f; }
96      if (height > bounds.Height) { dy = (height - bounds.Height) / 2f; }
97      foreach (var node in nodes) { node.Translate(dx, dy); }
98    }
99
100    private void FitToBounds(float width, float height, IEnumerable<LayoutNode<T>> nodes) {
101      var bounds = Bounds(nodes);
102      var myWidth = bounds.Width;
103      var myHeight = bounds.Height;
104
105      if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds
106
107      var layers = nodes.GroupBy(node => node.Level, node => node).ToList();
108
109      if (myWidth > width) {
110        // need to scale horizontally
111        float x = width / myWidth;
112        foreach (var node in layers.SelectMany(g => g)) {
113          node.X *= x;
114          node.Width *= x;
115        }
116        float spacing = minHorizontalSpacing * x;
117        foreach (var layer in layers) {
118          var nodesLayer = layer.ToList();
119          float minWidth = float.MaxValue;
120          for (int i = 0; i < nodesLayer.Count - 1; ++i) { minWidth = Math.Min(minWidth, nodesLayer[i + 1].X - nodesLayer[i].X); }
121          float w = Math.Min(NodeWidth, minWidth - spacing);
122          foreach (var node in nodesLayer) {
123            node.X += (node.Width - w) / 2f;
124            node.Width = w;
125            //this is a simple solution to ensure that the leftmost and rightmost nodes are not drawn partially offscreen due to scaling and offset
126            //this should work well enough 99.9% of the time with no noticeable visual difference
127            if (node.X < 0) {
128              node.Width += node.X;
129              node.X = 0;
130            } else if (node.X + node.Width > width) {
131              node.Width = width - node.X;
132            }
133          }
134        }
135      }
136      if (myHeight > height) {
137        // need to scale vertically
138        float x = height / myHeight;
139        foreach (var node in layers.SelectMany(g => g)) {
140          node.Y *= x;
141          node.Height *= x;
142        }
143      }
144    }
145
146
147    /// <summary>
148    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
149    /// </summary>
150    /// <returns></returns>
151    private RectangleF Bounds(IEnumerable<LayoutNode<T>> nodes) {
152      float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
153      foreach (LayoutNode<T> node in nodes) {
154        float x = node.X, y = node.Y;
155        if (xmin > x) xmin = x;
156        if (xmax < x) xmax = x;
157        if (ymin > y) ymin = y;
158        if (ymax < y) ymax = y;
159      }
160      return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
161    }
162
163    #region methods specific to the reingold-tilford layout algorithm
164    private void FirstWalk(LayoutNode<T> v) {
165      LayoutNode<T> w;
166      if (v.IsLeaf) {
167        w = v.LeftSibling;
168        if (w != null) {
169          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
170        }
171      } else {
172        var defaultAncestor = v.Children[0]; // leftmost child
173
174        foreach (var child in v.Children) {
175          FirstWalk(child);
176          Apportion(child, ref defaultAncestor);
177        }
178        ExecuteShifts(v);
179        var leftmost = v.Children.First();
180        var rightmost = v.Children.Last();
181        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
182        w = v.LeftSibling;
183        if (w != null) {
184          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
185          v.Mod = v.Prelim - midPoint;
186        } else {
187          v.Prelim = midPoint;
188        }
189      }
190    }
191
192    private void SecondWalk(LayoutNode<T> v, float m) {
193      v.X = v.Prelim + m;
194      v.Y = v.Level * (minVerticalSpacing + NodeHeight);
195      if (v.IsLeaf) return;
196      foreach (var child in v.Children) {
197        SecondWalk(child, m + v.Mod);
198      }
199    }
200
201    private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {
202      var w = v.LeftSibling;
203      if (w == null) return;
204      LayoutNode<T> vip = v;
205      LayoutNode<T> vop = v;
206      LayoutNode<T> vim = w;
207      LayoutNode<T> vom = vip.LeftmostSibling;
208
209      float sip = vip.Mod;
210      float sop = vop.Mod;
211      float sim = vim.Mod;
212      float som = vom.Mod;
213
214      while (vim.NextRight != null && vip.NextLeft != null) {
215        vim = vim.NextRight;
216        vip = vip.NextLeft;
217        vom = vom.NextLeft;
218        vop = vop.NextRight;
219        vop.Ancestor = v;
220        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
221        if (shift > 0) {
222          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
223          MoveSubtree(ancestor, v, shift);
224          sip += shift;
225          sop += shift;
226        }
227        sim += vim.Mod;
228        sip += vip.Mod;
229        som += vom.Mod;
230        sop += vop.Mod;
231      }
232      if (vim.NextRight != null && vop.NextRight == null) {
233        vop.Thread = vim.NextRight;
234        vop.Mod += (sim - sop);
235      }
236      if (vip.NextLeft != null && vom.NextLeft == null) {
237        vom.Thread = vip.NextLeft;
238        vom.Mod += (sip - som);
239        defaultAncestor = v;
240      }
241    }
242
243    private void MoveSubtree(LayoutNode<T> wm, LayoutNode<T> wp, float shift) {
244      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)
245      if (subtrees == 0) throw new Exception("MoveSubtree failed: check if object is really a tree (no cycles)");
246      wp.Change -= shift / subtrees;
247      wp.Shift += shift;
248      wm.Change += shift / subtrees;
249      wp.Prelim += shift;
250      wp.Mod += shift;
251    }
252
253    private void ExecuteShifts(LayoutNode<T> v) {
254      if (v.IsLeaf) return;
255      float shift = 0;
256      float change = 0;
257      for (int i = v.Children.Count - 1; i >= 0; --i) {
258        var w = v.Children[i];
259        w.Prelim += shift;
260        w.Mod += shift;
261        change += w.Change;
262        shift += (w.Shift + change);
263      }
264    }
265
266    private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {
267      var ancestor = u.Ancestor;
268      if (ancestor == null) return null;
269      return ancestor.Parent == v.Parent ? ancestor : null;
270    }
271    #endregion
272  }
273}
Note: See TracBrowser for help on using the repository browser.