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

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

#2076: Thanks for the feedback:

  • I removed the ILayoutNode Interfaces
  • Fixed the error that was causing it to crash in the textual representation
  • The ancestor is a node on the path between the root and the current node (from the paper), but in the algorithm it's assigned differently
  • Parent is the immediate parent

I also increased the node label text size a bit and did some cosmetic improvements.

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