[9963] | 1 |
|
---|
| 2 | using System;
|
---|
| 3 | using System.Collections.Generic;
|
---|
| 4 | using System.Drawing;
|
---|
| 5 | using System.Linq;
|
---|
| 6 |
|
---|
| 7 | namespace 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 | }
|
---|