[9970] | 1 |
|
---|
| 2 | using System;
|
---|
| 3 | using System.Collections.Generic;
|
---|
| 4 | using System.Drawing;
|
---|
| 5 | using System.Linq;
|
---|
| 6 |
|
---|
[10520] | 7 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
|
---|
| 8 | public class ReingoldTilfordLayoutEngine<T> : ILayoutEngine<T> where T : class {
|
---|
[10471] | 9 | private readonly Dictionary<T, LayoutNode<T>> nodeMap; // provides a reverse mapping T => LayoutNode
|
---|
[10520] | 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 | }
|
---|
[9970] | 17 |
|
---|
[10520] | 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 |
|
---|
[9970] | 29 | public ReingoldTilfordLayoutEngine() {
|
---|
[10471] | 30 | nodeMap = new Dictionary<T, LayoutNode<T>>();
|
---|
[9970] | 31 | }
|
---|
| 32 |
|
---|
[10520] | 33 | public ReingoldTilfordLayoutEngine(T root, Func<T, IEnumerable<T>> childrenFunc)
|
---|
| 34 | : this() {
|
---|
| 35 | Initialize(root, childrenFunc);
|
---|
| 36 | }
|
---|
[9970] | 37 |
|
---|
[10520] | 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 |
|
---|
[10471] | 76 | public void AddNode(T content) {
|
---|
[10520] | 77 | if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
|
---|
[10471] | 78 | var node = new LayoutNode<T> { Content = content };
|
---|
| 79 | nodeMap.Add(content, node);
|
---|
[9970] | 80 | }
|
---|
| 81 |
|
---|
[10471] | 82 | public void AddNode(LayoutNode<T> node) {
|
---|
| 83 | var content = node.Content;
|
---|
[10520] | 84 | if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
|
---|
[10471] | 85 | nodeMap.Add(content, node);
|
---|
[9970] | 86 | }
|
---|
| 87 |
|
---|
[10471] | 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 |
|
---|
[9970] | 99 | public void ResetCoordinates() {
|
---|
[10471] | 100 | foreach (var node in nodeMap.Values) {
|
---|
[10520] | 101 | node.ResetCoordinates();
|
---|
[9970] | 102 | }
|
---|
| 103 | }
|
---|
| 104 |
|
---|
[10520] | 105 | public Dictionary<T, PointF> GetCoordinates() {
|
---|
| 106 | return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
|
---|
| 107 | }
|
---|
| 108 |
|
---|
[9970] | 109 | /// <summary>
|
---|
[10520] | 110 | /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
|
---|
[9970] | 111 | /// </summary>
|
---|
| 112 | private void NormalizeCoordinates() {
|
---|
[10520] | 113 | var nodes = nodeMap.Values.ToList();
|
---|
[9970] | 114 | float xmin = 0, ymin = 0;
|
---|
[10520] | 115 | foreach (var node in nodes) {
|
---|
| 116 | if (xmin > node.X) xmin = node.X;
|
---|
| 117 | if (ymin > node.Y) ymin = node.Y;
|
---|
[9970] | 118 | }
|
---|
[10520] | 119 | foreach (var node in nodes) {
|
---|
| 120 | node.X -= xmin;
|
---|
| 121 | node.Y -= ymin;
|
---|
[9970] | 122 | }
|
---|
| 123 | }
|
---|
| 124 |
|
---|
[10520] | 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;
|
---|
[10471] | 182 | nodeMap.Clear();
|
---|
[9970] | 183 | }
|
---|
| 184 |
|
---|
[10520] | 185 | public void Reset() {
|
---|
[10471] | 186 | foreach (var layoutNode in nodeMap.Values) {
|
---|
[9970] | 187 | // reset layout-related parameters
|
---|
[10520] | 188 | layoutNode.Reset();
|
---|
[9970] | 189 | }
|
---|
| 190 | }
|
---|
| 191 |
|
---|
| 192 | public void CalculateLayout() {
|
---|
[10520] | 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);
|
---|
[9970] | 197 | NormalizeCoordinates();
|
---|
| 198 | }
|
---|
| 199 |
|
---|
[10520] | 200 | public void CalculateLayout(float width, float height) {
|
---|
| 201 | CalculateLayout();
|
---|
| 202 | FitToBounds(width, height);
|
---|
| 203 | Center(width, height);
|
---|
[9970] | 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() {
|
---|
[10520] | 211 | float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
|
---|
[10471] | 212 | var list = nodeMap.Values.ToList();
|
---|
[10520] | 213 | foreach (LayoutNode<T> node in list) {
|
---|
| 214 | float x = node.X, y = node.Y;
|
---|
[9970] | 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 | }
|
---|
[10520] | 220 | return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
|
---|
[9970] | 221 | }
|
---|
| 222 |
|
---|
[10520] | 223 | #region methods specific to the reingold-tilford layout algorithm
|
---|
[10471] | 224 | private void FirstWalk(LayoutNode<T> v) {
|
---|
| 225 | LayoutNode<T> w;
|
---|
[9970] | 226 | if (v.IsLeaf) {
|
---|
| 227 | w = v.LeftSibling;
|
---|
| 228 | if (w != null) {
|
---|
[10520] | 229 | v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
|
---|
[9970] | 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) {
|
---|
[10520] | 244 | v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
|
---|
[9970] | 245 | v.Mod = v.Prelim - midPoint;
|
---|
| 246 | } else {
|
---|
| 247 | v.Prelim = midPoint;
|
---|
| 248 | }
|
---|
| 249 | }
|
---|
| 250 | }
|
---|
| 251 |
|
---|
[10471] | 252 | private void SecondWalk(LayoutNode<T> v, float m) {
|
---|
[9970] | 253 | v.X = v.Prelim + m;
|
---|
[10520] | 254 | v.Y = v.Level * (minVerticalSpacing + NodeHeight);
|
---|
[9970] | 255 | if (v.IsLeaf) return;
|
---|
| 256 | foreach (var child in v.Children) {
|
---|
| 257 | SecondWalk(child, m + v.Mod);
|
---|
| 258 | }
|
---|
| 259 | }
|
---|
| 260 |
|
---|
[10471] | 261 | private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {
|
---|
[9970] | 262 | var w = v.LeftSibling;
|
---|
| 263 | if (w == null) return;
|
---|
[10471] | 264 | LayoutNode<T> vip = v;
|
---|
| 265 | LayoutNode<T> vop = v;
|
---|
| 266 | LayoutNode<T> vim = w;
|
---|
| 267 | LayoutNode<T> vom = vip.LeftmostSibling;
|
---|
[9970] | 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;
|
---|
[10520] | 280 | float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
|
---|
[9970] | 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 |
|
---|
[10471] | 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)");
|
---|
[9970] | 306 | wp.Change -= shift / subtrees;
|
---|
| 307 | wp.Shift += shift;
|
---|
| 308 | wm.Change += shift / subtrees;
|
---|
| 309 | wp.Prelim += shift;
|
---|
| 310 | wp.Mod += shift;
|
---|
| 311 | }
|
---|
| 312 |
|
---|
[10471] | 313 | private void ExecuteShifts(LayoutNode<T> v) {
|
---|
[9970] | 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 |
|
---|
[10471] | 326 | private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {
|
---|
[9970] | 327 | var ancestor = u.Ancestor;
|
---|
| 328 | if (ancestor == null) return null;
|
---|
| 329 | return ancestor.Parent == v.Parent ? ancestor : null;
|
---|
| 330 | }
|
---|
[10520] | 331 | #endregion
|
---|
[9970] | 332 | }
|
---|
| 333 | }
|
---|