source: branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs @ 9970

Last change on this file since 9970 was 9970, checked in by bburlacu, 6 years ago

#2076: Refactored layout engine to be more generic. Svn-copied folders from trunk and readded layout files.

File size: 7.2 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using System.Drawing;
5using System.Linq;
6
7namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
8  public class ReingoldTilfordLayoutEngine<T> where T : class {
9    private readonly Dictionary<T, ILayoutNode<T>> nodes; // provides a reverse mapping T => ILayoutNode
10
11    public ReingoldTilfordLayoutEngine() {
12      nodes = new Dictionary<T, ILayoutNode<T>>();
13    }
14
15    public Dictionary<T, ILayoutNode<T>> Nodes { get { return nodes; } }
16
17    public void AddNode(T content, ILayoutNode<T> node) {
18      if (nodes.ContainsKey(content)) {
19        throw new ArgumentException("Content already present in the dictionary.");
20      }
21      nodes.Add(content, node);
22    }
23
24    public ILayoutNode<T> GetNode(T content) {
25      ILayoutNode<T> ILayoutNode;
26      nodes.TryGetValue(content, out ILayoutNode);
27      return ILayoutNode;
28    }
29
30    private float minHorizontalSpacing = 5;
31    public float MinHorizontalSpacing {
32      get { return minHorizontalSpacing; }
33      set { minHorizontalSpacing = value; }
34    }
35
36    private float minVerticalSpacing = 5;
37    public float MinVerticalSpacing {
38      get { return minVerticalSpacing; }
39      set { minVerticalSpacing = value; }
40    }
41
42    private ILayoutNode<T> root;
43    public ILayoutNode<T> Root {
44      get { return root; }
45      set {
46        root = value;
47      }
48    }
49
50    public void ResetCoordinates() {
51      foreach (var node in nodes.Values) {
52        node.X = 0;
53        node.Y = 0;
54      }
55    }
56
57    /// <summary>
58    /// Transform ILayoutNode coordinates so that all coordinates are positive and start from 0.
59    /// </summary>
60    private void NormalizeCoordinates() {
61      var list = nodes.Values.ToList();
62      float xmin = 0, ymin = 0;
63      for (int i = 0; i != list.Count; ++i) {
64        if (xmin > list[i].X) xmin = list[i].X;
65        if (ymin > list[i].Y) ymin = list[i].Y;
66      }
67      for (int i = 0; i != list.Count; ++i) {
68        list[i].X -= xmin;
69        list[i].Y -= ymin;
70      }
71    }
72
73    public void Reset() {
74      root = null;
75      nodes.Clear();
76    }
77
78    public void ResetParameters() {
79      foreach (var layoutNode in nodes.Values) {
80        // reset layout-related parameters
81        layoutNode.Ancestor = layoutNode;
82        layoutNode.Thread = null;
83        layoutNode.Change = 0;
84        layoutNode.Shift = 0;
85        layoutNode.Prelim = 0;
86        layoutNode.Mod = 0;
87      }
88    }
89
90    public void CalculateLayout() {
91      if (root == null)
92        throw new Exception("Root cannot be null.");
93      ResetCoordinates(); // reset node X,Y coordinates
94      ResetParameters(); // reset node parameters like Mod, Shift etc.
95      FirstWalk(root);
96      SecondWalk(root, -root.Prelim);
97      NormalizeCoordinates();
98    }
99
100    /// <summary>
101    /// Returns a map of coordinates for each ILayoutNode in the symbolic expression tree.
102    /// </summary>
103    /// <returns></returns>
104    public Dictionary<T, PointF> GetNodeCoordinates() {
105      return nodes.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
106    }
107
108    /// <summary>
109    /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
110    /// </summary>
111    /// <returns></returns>
112    public RectangleF Bounds() {
113      float xmin, xmax, ymin, ymax; xmin = xmax = ymin = ymax = 0;
114      var list = nodes.Values.ToList();
115      for (int i = 0; i != list.Count; ++i) {
116        float x = list[i].X, y = list[i].Y;
117        if (xmin > x) xmin = x;
118        if (xmax < x) xmax = x;
119        if (ymin > y) ymin = y;
120        if (ymax < y) ymax = y;
121      }
122      return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing, ymax + minVerticalSpacing);
123    }
124
125    private void FirstWalk(ILayoutNode<T> v) {
126      ILayoutNode<T> w;
127      if (v.IsLeaf) {
128        w = v.LeftSibling;
129        if (w != null) {
130          v.Prelim = w.Prelim + minHorizontalSpacing;
131        }
132      } else {
133        var defaultAncestor = v.Children[0]; // leftmost child
134
135        foreach (var child in v.Children) {
136          FirstWalk(child);
137          Apportion(child, ref defaultAncestor);
138        }
139        ExecuteShifts(v);
140        var leftmost = v.Children.First();
141        var rightmost = v.Children.Last();
142        float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
143        w = v.LeftSibling;
144        if (w != null) {
145          v.Prelim = w.Prelim + minHorizontalSpacing;
146          v.Mod = v.Prelim - midPoint;
147        } else {
148          v.Prelim = midPoint;
149        }
150      }
151    }
152
153    private void SecondWalk(ILayoutNode<T> v, float m) {
154      v.X = v.Prelim + m;
155      v.Y = v.Level * minVerticalSpacing;
156      if (v.IsLeaf) return;
157      foreach (var child in v.Children) {
158        SecondWalk(child, m + v.Mod);
159      }
160    }
161
162    private void Apportion(ILayoutNode<T> v, ref ILayoutNode<T> defaultAncestor) {
163      var w = v.LeftSibling;
164      if (w == null) return;
165      ILayoutNode<T> vip = v;
166      ILayoutNode<T> vop = v;
167      ILayoutNode<T> vim = w;
168      ILayoutNode<T> vom = vip.LeftmostSibling;
169
170      float sip = vip.Mod;
171      float sop = vop.Mod;
172      float sim = vim.Mod;
173      float som = vom.Mod;
174
175      while (vim.NextRight != null && vip.NextLeft != null) {
176        vim = vim.NextRight;
177        vip = vip.NextLeft;
178        vom = vom.NextLeft;
179        vop = vop.NextRight;
180        vop.Ancestor = v;
181        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing;
182        if (shift > 0) {
183          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
184          MoveSubtree(ancestor, v, shift);
185          sip += shift;
186          sop += shift;
187        }
188        sim += vim.Mod;
189        sip += vip.Mod;
190        som += vom.Mod;
191        sop += vop.Mod;
192      }
193      if (vim.NextRight != null && vop.NextRight == null) {
194        vop.Thread = vim.NextRight;
195        vop.Mod += (sim - sop);
196      }
197      if (vip.NextLeft != null && vom.NextLeft == null) {
198        vom.Thread = vip.NextLeft;
199        vom.Mod += (sip - som);
200        defaultAncestor = v;
201      }
202    }
203
204    private void MoveSubtree(ILayoutNode<T> wm, ILayoutNode<T> wp, float shift) {
205      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
206      if (subtrees == 0) throw new Exception();
207      wp.Change -= shift / subtrees;
208      wp.Shift += shift;
209      wm.Change += shift / subtrees;
210      wp.Prelim += shift;
211      wp.Mod += shift;
212    }
213
214    private void ExecuteShifts(ILayoutNode<T> v) {
215      if (v.IsLeaf) return;
216      float shift = 0;
217      float change = 0;
218      for (int i = v.Children.Count - 1; i >= 0; --i) {
219        var w = v.Children[i];
220        w.Prelim += shift;
221        w.Mod += shift;
222        change += w.Change;
223        shift += (w.Shift + change);
224      }
225    }
226
227    private ILayoutNode<T> Ancestor(ILayoutNode<T> u, ILayoutNode<T> v) {
228      var ancestor = u.Ancestor;
229      if (ancestor == null) return null;
230      return ancestor.Parent == v.Parent ? ancestor : null;
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.