1 


2  using System;


3  using System.Collections.Generic;


4  using System.Drawing;


5  using System.Linq;


6 


7  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {


8  public class ReingoldTilfordLayoutEngine<T> : ILayoutEngine<T> where T : class {


9  public int NodeWidth { get; set; }


10  public int NodeHeight { get; set; }


11  private int minHorizontalSpacing = 5;


12  public int HorizontalSpacing {


13  get { return minHorizontalSpacing; }


14  set { minHorizontalSpacing = value; }


15  }


16 


17  private int minVerticalSpacing = 5;


18  public int VerticalSpacing {


19  get { return minVerticalSpacing; }


20  set { minVerticalSpacing = value; }


21  }


22 


23  private readonly Func<T, IEnumerable<T>> GetChildren;


24 


25  public ReingoldTilfordLayoutEngine(Func<T, IEnumerable<T>> GetChildren) {


26  this.GetChildren = GetChildren;


27  }


28 


29  public IEnumerable<VisualTreeNode<T>> CalculateLayout(T root) {


30  return CalculateLayout(root, 0, 0);


31  }


32 


33  public IEnumerable<VisualTreeNode<T>> CalculateLayout(T root, float width, float height) {


34  Dictionary<T, LayoutNode<T>> layoutNodeMap = new Dictionary<T, LayoutNode<T>>();


35  var layoutRoot = new LayoutNode<T> { Content = root, Width = NodeWidth, Height = NodeHeight, };


36  layoutRoot.Ancestor = layoutRoot;


37  Expand(layoutRoot, layoutNodeMap);


38 


39  FirstWalk(layoutRoot);


40  SecondWalk(layoutRoot, layoutRoot.Prelim);


41  NormalizeCoordinates(layoutNodeMap.Values);


42  if (height != 0 && width != 0) {


43  FitToBounds(width, height, layoutNodeMap.Values);


44  Center(width, height, layoutNodeMap.Values);


45  }


46 


47  return layoutNodeMap.Values.Select(x => new VisualTreeNode<T>(x.Content) {


48  Width = (int)Math.Round(x.Width),


49  Height = (int)Math.Round(x.Height),


50  X = (int)Math.Round(x.X),


51  Y = (int)Math.Round(x.Y)


52  });


53  }


54 


55  private void Expand(LayoutNode<T> lRoot, Dictionary<T, LayoutNode<T>> map) {


56  map.Add(lRoot.Content, lRoot);


57  var children = GetChildren(lRoot.Content).ToList();


58  if (!children.Any()) return;


59  lRoot.Children = new List<LayoutNode<T>>(children.Count);


60  for (int i = 0; i < children.Count; ++i) {


61  var node = new LayoutNode<T> {


62  Content = children[i],


63  Number = i,


64  Parent = lRoot,


65  Level = lRoot.Level + 1,


66  Width = NodeWidth,


67  Height = NodeHeight


68  };


69  node.Ancestor = node;


70  lRoot.Children.Add(node);


71  Expand(node, map);


72  }


73  }


74 


75 


76  /// <summary>


77  /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)


78  /// </summary>


79  private static void NormalizeCoordinates(IEnumerable<LayoutNode<T>> nodes) {


80  float xmin = 0, ymin = 0;


81  foreach (var node in nodes) {


82  if (xmin > node.X) xmin = node.X;


83  if (ymin > node.Y) ymin = node.Y;


84  }


85  foreach (var node in nodes) {


86  node.X = xmin;


87  node.Y = ymin;


88  }


89  }


90 


91  private void Center(float width, float height, IEnumerable<LayoutNode<T>> nodes) {


92  // center layout on screen


93  var bounds = Bounds(nodes);


94  float dx = 0, dy = 0;


95  if (width > bounds.Width) { dx = (width  bounds.Width) / 2f; }


96  if (height > bounds.Height) { dy = (height  bounds.Height) / 2f; }


97  foreach (var node in nodes) { node.Translate(dx, dy); }


98  }


99 


100  private void FitToBounds(float width, float height, IEnumerable<LayoutNode<T>> nodes) {


101  var bounds = Bounds(nodes);


102  var myWidth = bounds.Width;


103  var myHeight = bounds.Height;


104 


105  if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds


106 


107  var layers = nodes.GroupBy(node => node.Level, node => node).ToList();


108 


109  if (myWidth > width) {


110  // need to scale horizontally


111  float x = width / myWidth;


112  foreach (var node in layers.SelectMany(g => g)) {


113  node.X *= x;


114  node.Width *= x;


115  }


116  float spacing = minHorizontalSpacing * x;


117  foreach (var layer in layers) {


118  var nodesLayer = layer.ToList();


119  float minWidth = float.MaxValue;


120  for (int i = 0; i < nodesLayer.Count  1; ++i) { minWidth = Math.Min(minWidth, nodesLayer[i + 1].X  nodesLayer[i].X); }


121  float w = Math.Min(NodeWidth, minWidth  spacing);


122  foreach (var node in nodesLayer) {


123  node.X += (node.Width  w) / 2f;


124  node.Width = w;


125  //this is a simple solution to ensure that the leftmost and rightmost nodes are not drawn partially offscreen due to scaling and offset


126  //this should work well enough 99.9% of the time with no noticeable visual difference


127  if (node.X < 0) {


128  node.Width += node.X;


129  node.X = 0;


130  } else if (node.X + node.Width > width) {


131  node.Width = width  node.X;


132  }


133  }


134  }


135  }


136  if (myHeight > height) {


137  // need to scale vertically


138  float x = height / myHeight;


139  foreach (var node in layers.SelectMany(g => g)) {


140  node.Y *= x;


141  node.Height *= x;


142  }


143  }


144  }


145 


146 


147  /// <summary>


148  /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].


149  /// </summary>


150  /// <returns></returns>


151  private RectangleF Bounds(IEnumerable<LayoutNode<T>> nodes) {


152  float xmin = 0, xmax = 0, ymin = 0, ymax = 0;


153  foreach (LayoutNode<T> node in nodes) {


154  float x = node.X, y = node.Y;


155  if (xmin > x) xmin = x;


156  if (xmax < x) xmax = x;


157  if (ymin > y) ymin = y;


158  if (ymax < y) ymax = y;


159  }


160  return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);


161  }


162 


163  #region methods specific to the reingoldtilford layout algorithm


164  private void FirstWalk(LayoutNode<T> v) {


165  LayoutNode<T> w;


166  if (v.IsLeaf) {


167  w = v.LeftSibling;


168  if (w != null) {


169  v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;


170  }


171  } else {


172  var defaultAncestor = v.Children[0]; // leftmost child


173 


174  foreach (var child in v.Children) {


175  FirstWalk(child);


176  Apportion(child, ref defaultAncestor);


177  }


178  ExecuteShifts(v);


179  var leftmost = v.Children.First();


180  var rightmost = v.Children.Last();


181  float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;


182  w = v.LeftSibling;


183  if (w != null) {


184  v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;


185  v.Mod = v.Prelim  midPoint;


186  } else {


187  v.Prelim = midPoint;


188  }


189  }


190  }


191 


192  private void SecondWalk(LayoutNode<T> v, float m) {


193  v.X = v.Prelim + m;


194  v.Y = v.Level * (minVerticalSpacing + NodeHeight);


195  if (v.IsLeaf) return;


196  foreach (var child in v.Children) {


197  SecondWalk(child, m + v.Mod);


198  }


199  }


200 


201  private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {


202  var w = v.LeftSibling;


203  if (w == null) return;


204  LayoutNode<T> vip = v;


205  LayoutNode<T> vop = v;


206  LayoutNode<T> vim = w;


207  LayoutNode<T> vom = vip.LeftmostSibling;


208 


209  float sip = vip.Mod;


210  float sop = vop.Mod;


211  float sim = vim.Mod;


212  float som = vom.Mod;


213 


214  while (vim.NextRight != null && vip.NextLeft != null) {


215  vim = vim.NextRight;


216  vip = vip.NextLeft;


217  vom = vom.NextLeft;


218  vop = vop.NextRight;


219  vop.Ancestor = v;


220  float shift = (vim.Prelim + sim)  (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;


221  if (shift > 0) {


222  var ancestor = Ancestor(vim, v) ?? defaultAncestor;


223  MoveSubtree(ancestor, v, shift);


224  sip += shift;


225  sop += shift;


226  }


227  sim += vim.Mod;


228  sip += vip.Mod;


229  som += vom.Mod;


230  sop += vop.Mod;


231  }


232  if (vim.NextRight != null && vop.NextRight == null) {


233  vop.Thread = vim.NextRight;


234  vop.Mod += (sim  sop);


235  }


236  if (vip.NextLeft != null && vom.NextLeft == null) {


237  vom.Thread = vip.NextLeft;


238  vom.Mod += (sip  som);


239  defaultAncestor = v;


240  }


241  }


242 


243  private void MoveSubtree(LayoutNode<T> wm, LayoutNode<T> wp, float shift) {


244  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)


245  if (subtrees == 0) throw new Exception("MoveSubtree failed: check if object is really a tree (no cycles)");


246  wp.Change = shift / subtrees;


247  wp.Shift += shift;


248  wm.Change += shift / subtrees;


249  wp.Prelim += shift;


250  wp.Mod += shift;


251  }


252 


253  private void ExecuteShifts(LayoutNode<T> v) {


254  if (v.IsLeaf) return;


255  float shift = 0;


256  float change = 0;


257  for (int i = v.Children.Count  1; i >= 0; i) {


258  var w = v.Children[i];


259  w.Prelim += shift;


260  w.Mod += shift;


261  change += w.Change;


262  shift += (w.Shift + change);


263  }


264  }


265 


266  private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {


267  var ancestor = u.Ancestor;


268  if (ancestor == null) return null;


269  return ancestor.Parent == v.Parent ? ancestor : null;


270  }


271  #endregion


272  }


273  }

