source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs @ 9963

Last change on this file since 9963 was 9963, checked in by bburlacu, 8 years ago

#1772: Merged changes from the trunk and other branches. Added new ExtendedSymbolicExpressionTreeCanvas control for the visual exploration of tree genealogies. Reorganized some files and folders.

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