Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/28/14 11:56:15 (11 years ago)
Author:
bburlacu
Message:

#2076: Got rid of layout adapters. Extracted the previous drawing code and made it into another layout engine called the BoxesLayoutEngine (because it divides the areas necessary for each subtree into boxes and recursively applies the layout). Simplified usage of layout engine so that most of the things are handled internally, and the user just has to provide some lambdas telling the engine how to navigate the original tree. Added context option in the SymbolicExpressionTreeChart to choose which layout engine to use for tree drawing. Moved the SymbolicExpressionTreeLatexFormatter to the HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views assembly because it depends on the layout engine.

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines
Files:
2 added
1 deleted
2 edited
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/LayoutNode.cs

    r10471 r10520  
    2424using System.Linq;
    2525
    26 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    27   public class LayoutNode<T> where T : class {
     26namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
     27  public class LayoutNode<T> : object where T : class {
     28    public float Width { get; set; }
     29    public float Height { get; set; }
     30
    2831    public LayoutNode<T> NextLeft {
    2932      get {
    … …  
    7578      }
    7679    }
     80    /// <summary>
     81    /// Translate the position of the layout node according to the given offsets
     82    /// </summary>
     83    /// <param name="dx"></param>
     84    /// <param name="dy"></param>
     85    public void Translate(float dx, float dy) {
     86      X += dx;
     87      Y += dy;
     88    }
     89
     90    public void ResetCoordinates() {
     91      X = 0;
     92      Y = 0;
     93    }
     94
     95    /// <summary>
     96    /// Reset layout-related parameters
     97    /// </summary>
     98    public void Reset() {
     99      Ancestor = this;
     100      Thread = null;
     101      Change = 0;
     102      Shift = 0;
     103      Prelim = 0;
     104      Mod = 0;
     105      ResetCoordinates();
     106    }
    77107  }
    78108}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs

    r10471 r10520  
    55using System.Linq;
    66
    7 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    8   public class ReingoldTilfordLayoutEngine<T> where T : class {
     7namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
     8  public class ReingoldTilfordLayoutEngine<T> : ILayoutEngine<T> where T : class {
    99    private readonly Dictionary<T, LayoutNode<T>> nodeMap; // provides a reverse mapping T => LayoutNode
     10    public int NodeWidth { get; set; }
     11    public int NodeHeight { get; set; }
     12    private int minHorizontalSpacing = 5;
     13    public int HorizontalSpacing {
     14      get { return minHorizontalSpacing; }
     15      set { minHorizontalSpacing = value; }
     16    }
     17
     18    private int minVerticalSpacing = 5;
     19    public int VerticalSpacing {
     20      get { return minVerticalSpacing; }
     21      set { minVerticalSpacing = value; }
     22    }
     23
     24    public Func<T, IEnumerable<T>> GetChildren { get; set; }
     25    public Func<T, int> GetLength { get; set; }
     26    public Func<T, int> GetDepth { get; set; }
     27    private LayoutNode<T> layoutRoot;
    1028
    1129    public ReingoldTilfordLayoutEngine() {
    … …  
    1331    }
    1432
    15     public Dictionary<T, LayoutNode<T>> NodeMap { get { return nodeMap; } }
     33    public ReingoldTilfordLayoutEngine(T root, Func<T, IEnumerable<T>> childrenFunc)
     34      : this() {
     35      Initialize(root, childrenFunc);
     36    }
     37
     38    public void Initialize(T root, Func<T, IEnumerable<T>> getChildren, Func<T, int> getLength = null, Func<T, int> getDepth = null) {
     39      GetChildren = getChildren;
     40      Clear();
     41      var node = new LayoutNode<T> { Content = root, Width = NodeWidth, Height = NodeHeight };
     42      node.Ancestor = node;
     43      layoutRoot = node;
     44      Expand(node);
     45    }
     46
     47    private void Expand(LayoutNode<T> lRoot) {
     48      nodeMap.Add(lRoot.Content, lRoot);
     49      var children = GetChildren(lRoot.Content).ToList();
     50      if (!children.Any()) return;
     51      lRoot.Children = new List<LayoutNode<T>>(children.Count);
     52      for (int i = 0; i < children.Count; ++i) {
     53        var node = new LayoutNode<T> {
     54          Content = children[i],
     55          Number = i,
     56          Parent = lRoot,
     57          Level = lRoot.Level + 1,
     58          Width = NodeWidth,
     59          Height = NodeHeight
     60        };
     61        node.Ancestor = node;
     62        lRoot.Children.Add(node);
     63        Expand(node);
     64      }
     65    }
     66
     67    public IEnumerable<VisualTreeNode<T>> GetVisualNodes() {
     68      return nodeMap.Values.Select(x => new VisualTreeNode<T>(x.Content) {
     69        Width = (int)Math.Round(x.Width),
     70        Height = (int)Math.Round(x.Height),
     71        X = (int)Math.Round(x.X),
     72        Y = (int)Math.Round(x.Y)
     73      });
     74    }
    1675
    1776    public void AddNode(T content) {
    18       if (nodeMap.ContainsKey(content)) {
    19         throw new ArgumentException("Content already present in the dictionary.");
    20       }
     77      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
    2178      var node = new LayoutNode<T> { Content = content };
    2279      nodeMap.Add(content, node);
    … …  
    2582    public void AddNode(LayoutNode<T> node) {
    2683      var content = node.Content;
    27       if (nodeMap.ContainsKey(content)) {
    28         throw new ArgumentException("Content already present in the dictionary.");
    29       }
     84      if (nodeMap.ContainsKey(content)) { throw new ArgumentException("Content already present in the dictionary."); }
    3085      nodeMap.Add(content, node);
    3186    }
    … …  
    4297    }
    4398
    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 
    6499    public void ResetCoordinates() {
    65100      foreach (var node in nodeMap.Values) {
    66         node.X = 0;
    67         node.Y = 0;
    68       }
     101        node.ResetCoordinates();
     102      }
     103    }
     104
     105    public Dictionary<T, PointF> GetCoordinates() {
     106      return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
    69107    }
    70108
    71109    /// <summary>
    72     /// Transform LayoutNode coordinates so that all coordinates are positive and start from 0.
     110    /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
    73111    /// </summary>
    74112    private void NormalizeCoordinates() {
    75       var list = nodeMap.Values.ToList();
     113      var nodes = nodeMap.Values.ToList();
    76114      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       }
     115      foreach (var node in nodes) {
     116        if (xmin > node.X) xmin = node.X;
     117        if (ymin > node.Y) ymin = node.Y;
     118      }
     119      foreach (var node in nodes) {
     120        node.X -= xmin;
     121        node.Y -= ymin;
     122      }
     123    }
     124
     125    public void Center(float width, float height) {
     126      // center layout on screen
     127      var bounds = Bounds();
     128      float dx = 0, dy = 0;
     129      if (width > bounds.Width) { dx = (width - bounds.Width) / 2f; }
     130      if (height > bounds.Height) { dy = (height - bounds.Height) / 2f; }
     131      foreach (var node in nodeMap.Values) { node.Translate(dx, dy); }
     132    }
     133
     134    public void FitToBounds(float width, float height) {
     135      var bounds = Bounds();
     136      var myWidth = bounds.Width;
     137      var myHeight = bounds.Height;
     138
     139      if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds
     140
     141      var layers = nodeMap.Values.GroupBy(node => node.Level, node => node).ToList();
     142
     143      if (myWidth > width) {
     144        // need to scale horizontally
     145        float x = width / myWidth;
     146        foreach (var node in layers.SelectMany(g => g)) {
     147          node.X *= x;
     148          node.Width *= x;
     149        }
     150        float spacing = minHorizontalSpacing * x;
     151        foreach (var layer in layers) {
     152          var nodes = layer.ToList();
     153          float minWidth = float.MaxValue;
     154          for (int i = 0; i < nodes.Count - 1; ++i) { minWidth = Math.Min(minWidth, nodes[i + 1].X - nodes[i].X); }
     155          float w = Math.Min(NodeWidth, minWidth - spacing);
     156          foreach (var node in nodes) {
     157            node.X += (node.Width - w) / 2f;
     158            node.Width = w;
     159            //this is a simple solution to ensure that the leftmost and rightmost nodes are not drawn partially offscreen due to scaling and offset
     160            //this should work well enough 99.9% of the time with no noticeable visual difference
     161            if (node.X < 0) {
     162              node.Width += node.X;
     163              node.X = 0;
     164            } else if (node.X + node.Width > width) {
     165              node.Width = width - node.X;
     166            }
     167          }
     168        }
     169      }
     170      if (myHeight > height) {
     171        // need to scale vertically
     172        float x = height / myHeight;
     173        foreach (var node in layers.SelectMany(g => g)) {
     174          node.Y *= x;
     175          node.Height *= x;
     176        }
     177      }
     178    }
     179
     180    public void Clear() {
     181      layoutRoot = null;
     182      nodeMap.Clear();
    85183    }
    86184
    87185    public void Reset() {
    88       root = null;
    89       nodeMap.Clear();
    90     }
    91 
    92     public void ResetParameters() {
    93186      foreach (var layoutNode in nodeMap.Values) {
    94187        // 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;
     188        layoutNode.Reset();
    101189      }
    102190    }
    103191
    104192    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);
     193      if (layoutRoot == null) throw new Exception("Layout layoutRoot cannot be null.");
     194      Reset(); // reset node parameters like Mod, Shift etc. and set coordinates to 0
     195      FirstWalk(layoutRoot);
     196      SecondWalk(layoutRoot, -layoutRoot.Prelim);
    111197      NormalizeCoordinates();
    112198    }
    113199
    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));
     200    public void CalculateLayout(float width, float height) {
     201      CalculateLayout();
     202      FitToBounds(width, height);
     203      Center(width, height);
    120204    }
    121205
    … …  
    125209    /// <returns></returns>
    126210    public RectangleF Bounds() {
    127       float xmin, xmax, ymin, ymax; xmin = xmax = ymin = ymax = 0;
     211      float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
    128212      var list = nodeMap.Values.ToList();
    129       for (int i = 0; i < list.Count; ++i) {
    130         float x = list[i].X, y = list[i].Y;
     213      foreach (LayoutNode<T> node in list) {
     214        float x = node.X, y = node.Y;
    131215        if (xmin > x) xmin = x;
    132216        if (xmax < x) xmax = x;
    … …  
    134218        if (ymax < y) ymax = y;
    135219      }
    136       return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing, ymax + minVerticalSpacing);
    137     }
    138 
     220      return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
     221    }
     222
     223    #region methods specific to the reingold-tilford layout algorithm
    139224    private void FirstWalk(LayoutNode<T> v) {
    140225      LayoutNode<T> w;
    … …  
    142227        w = v.LeftSibling;
    143228        if (w != null) {
    144           v.Prelim = w.Prelim + minHorizontalSpacing;
     229          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
    145230        }
    146231      } else {
    … …  
    157242        w = v.LeftSibling;
    158243        if (w != null) {
    159           v.Prelim = w.Prelim + minHorizontalSpacing;
     244          v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
    160245          v.Mod = v.Prelim - midPoint;
    161246        } else {
    … …  
    167252    private void SecondWalk(LayoutNode<T> v, float m) {
    168253      v.X = v.Prelim + m;
    169       v.Y = v.Level * minVerticalSpacing;
     254      v.Y = v.Level * (minVerticalSpacing + NodeHeight);
    170255      if (v.IsLeaf) return;
    171256      foreach (var child in v.Children) {
    … …  
    193278        vop = vop.NextRight;
    194279        vop.Ancestor = v;
    195         float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing;
     280        float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
    196281        if (shift > 0) {
    197282          var ancestor = Ancestor(vim, v) ?? defaultAncestor;
    … …  
    244329      return ancestor.Parent == v.Parent ? ancestor : null;
    245330    }
     331    #endregion
    246332  }
    247333}
Note: See TracChangeset for help on using the changeset viewer.