Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/19/14 22:18:49 (11 years ago)
Author:
bburlacu
Message:

#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.

Location:
branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs

    r10468 r10471  
    5353
    5454    public string Format(ISymbolicExpressionTree symbolicExpressionTree) {
     55      layoutEngine.Reset();
    5556      var layoutNodes = layoutAdapter.Convert(symbolicExpressionTree).ToList();
    5657      layoutEngine.Root = layoutNodes[0];
    57       foreach (var ln in layoutNodes)
    58         layoutEngine.AddNode(ln.Content, ln);
     58      layoutEngine.AddNodes(layoutNodes);
    5959      layoutEngine.CalculateLayout();
    6060      var nodeCoordinates = layoutEngine.GetNodeCoordinates();

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r9970 r10471  
    185185    <Compile Include="Formatters\SymbolicExpressionTreeLatexFormatter.cs" />
    186186    <Compile Include="Interfaces\ILayoutAdapter.cs" />
    187     <Compile Include="Interfaces\ILayoutNode.cs" />
    188187    <Compile Include="Interfaces\IReadOnlySymbol.cs" />
    189188    <Compile Include="Interfaces\ISymbolicExpressionGrammar.cs" />

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ILayoutAdapter.cs

    r9970 r10471  
    44namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    55  public interface ILayoutAdapter<T> where T : class {
    6     IEnumerable<ILayoutNode<T>> Convert(T root, Func<T, ILayoutNode<T>> convertFunc);
     6    IEnumerable<LayoutNode<T>> Convert(T root, Func<T, LayoutNode<T>> convertFunc);
    77  }
    88}

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/LayoutEngines/LayoutNode.cs

    r9970 r10471  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
    2425
    25 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.LayoutEngines {
    26   public class LayoutNode<T> : ILayoutNode<T> where T : class {
    27     public ILayoutNode<T> NextLeft {
     26namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
     27  public class LayoutNode<T> where T : class {
     28    public LayoutNode<T> NextLeft {
    2829      get {
    2930        return Children == null ? Thread : Children.First();
    3031      }
    3132    }
    32     public ILayoutNode<T> NextRight {
     33    public LayoutNode<T> NextRight {
    3334      get {
    3435        return Children == null ? Thread : Children.Last();
    3536      }
    3637    }
    37     public ILayoutNode<T> LeftSibling {
     38    public LayoutNode<T> LeftSibling {
    3839      get {
    3940        if (Parent == null) return null;
    … …  
    4142      }
    4243    }
    43     public ILayoutNode<T> LeftmostSibling {
     44    public LayoutNode<T> LeftmostSibling {
    4445      get {
    4546        if (Parent == null) return null;
    … …  
    4849    }
    4950
    50     public ILayoutNode<T> Thread { get; set; }
    51     public ILayoutNode<T> Ancestor { get; set; }
    52     public ILayoutNode<T> Parent { get; set; }
    53     public List<ILayoutNode<T>> Children { get; set; }
     51    public LayoutNode<T> Thread { get; set; }
     52    public LayoutNode<T> Ancestor { get; set; }
     53    public LayoutNode<T> Parent { get; set; }
     54    public List<LayoutNode<T>> Children { get; set; }
    5455    public float Mod { get; set; }
    5556    public float Prelim { get; set; }
    … …  
    6566    }
    6667
    67     public T Content { get; set; }
     68    private T content;
     69    public T Content {
     70      get { return content; }
     71      set {
     72        if (value == null)
     73          throw new ArgumentNullException("LayoutNode: Content cannot be null.");
     74        content = value;
     75      }
     76    }
    6877  }
    6978}

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs

    r9970 r10471  
    77namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    88  public class ReingoldTilfordLayoutEngine<T> where T : class {
    9     private readonly Dictionary<T, ILayoutNode<T>> nodes; // provides a reverse mapping T => ILayoutNode
     9    private readonly Dictionary<T, LayoutNode<T>> nodeMap; // provides a reverse mapping T => LayoutNode
    1010
    1111    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)) {
     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)) {
    1919        throw new ArgumentException("Content already present in the dictionary.");
    2020      }
    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;
     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;
    2842    }
    2943
    … …  
    4054    }
    4155
    42     private ILayoutNode<T> root;
    43     public ILayoutNode<T> Root {
     56    private LayoutNode<T> root;
     57    public LayoutNode<T> Root {
    4458      get { return root; }
    4559      set {
    … …  
    4963
    5064    public void ResetCoordinates() {
    51       foreach (var node in nodes.Values) {
     65      foreach (var node in nodeMap.Values) {
    5266        node.X = 0;
    5367        node.Y = 0;
    … …  
    5670
    5771    /// <summary>
    58     /// Transform ILayoutNode coordinates so that all coordinates are positive and start from 0.
     72    /// Transform LayoutNode coordinates so that all coordinates are positive and start from 0.
    5973    /// </summary>
    6074    private void NormalizeCoordinates() {
    61       var list = nodes.Values.ToList();
     75      var list = nodeMap.Values.ToList();
    6276      float xmin = 0, ymin = 0;
    63       for (int i = 0; i != list.Count; ++i) {
     77      for (int i = 0; i < list.Count; ++i) {
    6478        if (xmin > list[i].X) xmin = list[i].X;
    6579        if (ymin > list[i].Y) ymin = list[i].Y;
    6680      }
    67       for (int i = 0; i != list.Count; ++i) {
     81      for (int i = 0; i < list.Count; ++i) {
    6882        list[i].X -= xmin;
    6983        list[i].Y -= ymin;
    … …  
    7387    public void Reset() {
    7488      root = null;
    75       nodes.Clear();
     89      nodeMap.Clear();
    7690    }
    7791
    7892    public void ResetParameters() {
    79       foreach (var layoutNode in nodes.Values) {
     93      foreach (var layoutNode in nodeMap.Values) {
    8094        // reset layout-related parameters
    8195        layoutNode.Ancestor = layoutNode;
    … …  
    99113
    100114    /// <summary>
    101     /// Returns a map of coordinates for each ILayoutNode in the symbolic expression tree.
     115    /// Returns a map of coordinates for each LayoutNode in the symbolic expression tree.
    102116    /// </summary>
    103117    /// <returns></returns>
    104118    public Dictionary<T, PointF> GetNodeCoordinates() {
    105       return nodes.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
     119      return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
    106120    }
    107121
    … …  
    112126    public RectangleF Bounds() {
    113127      float xmin, xmax, ymin, ymax; xmin = xmax = ymin = ymax = 0;
    114       var list = nodes.Values.ToList();
    115       for (int i = 0; i != list.Count; ++i) {
     128      var list = nodeMap.Values.ToList();
     129      for (int i = 0; i < list.Count; ++i) {
    116130        float x = list[i].X, y = list[i].Y;
    117131        if (xmin > x) xmin = x;
    … …  
    123137    }
    124138
    125     private void FirstWalk(ILayoutNode<T> v) {
    126       ILayoutNode<T> w;
     139    private void FirstWalk(LayoutNode<T> v) {
     140      LayoutNode<T> w;
    127141      if (v.IsLeaf) {
    128142        w = v.LeftSibling;
    … …  
    151165    }
    152166
    153     private void SecondWalk(ILayoutNode<T> v, float m) {
     167    private void SecondWalk(LayoutNode<T> v, float m) {
    154168      v.X = v.Prelim + m;
    155169      v.Y = v.Level * minVerticalSpacing;
    … …  
    160174    }
    161175
    162     private void Apportion(ILayoutNode<T> v, ref ILayoutNode<T> defaultAncestor) {
     176    private void Apportion(LayoutNode<T> v, ref LayoutNode<T> defaultAncestor) {
    163177      var w = v.LeftSibling;
    164178      if (w == null) return;
    165       ILayoutNode<T> vip = v;
    166       ILayoutNode<T> vop = v;
    167       ILayoutNode<T> vim = w;
    168       ILayoutNode<T> vom = vip.LeftmostSibling;
     179      LayoutNode<T> vip = v;
     180      LayoutNode<T> vop = v;
     181      LayoutNode<T> vim = w;
     182      LayoutNode<T> vom = vip.LeftmostSibling;
    169183
    170184      float sip = vip.Mod;
    … …  
    202216    }
    203217
    204     private void MoveSubtree(ILayoutNode<T> wm, ILayoutNode<T> wp, float shift) {
    205       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
    206       if (subtrees == 0) throw new Exception();
     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)");
    207221      wp.Change -= shift / subtrees;
    208222      wp.Shift += shift;
    … …  
    212226    }
    213227
    214     private void ExecuteShifts(ILayoutNode<T> v) {
     228    private void ExecuteShifts(LayoutNode<T> v) {
    215229      if (v.IsLeaf) return;
    216230      float shift = 0;
    … …  
    225239    }
    226240
    227     private ILayoutNode<T> Ancestor(ILayoutNode<T> u, ILayoutNode<T> v) {
     241    private LayoutNode<T> Ancestor(LayoutNode<T> u, LayoutNode<T> v) {
    228242      var ancestor = u.Ancestor;
    229243      if (ancestor == null) return null;

  • branches/HeuristicLab.ReingoldTilfordTreeLayout/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/LayoutEngines/SymbolicExpressionTreeLayoutAdapter.cs

    r9970 r10471  
    2222using System;
    2323using System.Collections.Generic;
    24 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.LayoutEngines;
    2524
    2625namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    2726  // adapter class that provides some conversion methods from symbolic expression trees to layout nodes (preserving the tree structure)
    2827  public class SymbolicExpressionTreeLayoutAdapter : ILayoutAdapter<ISymbolicExpressionTreeNode> {
    29     // default conversion function between ISymbolicExpressionTreeNode and ILayoutNode<ISymbolicExpressionTree>
    30     ILayoutNode<ISymbolicExpressionTreeNode> defaultConvert(ISymbolicExpressionTreeNode node) {
     28    // default conversion function between ISymbolicExpressionTreeNode and LayoutNode<ISymbolicExpressionTree>
     29    LayoutNode<ISymbolicExpressionTreeNode> defaultConvert(ISymbolicExpressionTreeNode node) {
    3130      var layoutNode = new LayoutNode<ISymbolicExpressionTreeNode> { Content = node };
    3231      layoutNode.Ancestor = layoutNode;
    … …  
    3433    }
    3534
    36     public IEnumerable<ILayoutNode<ISymbolicExpressionTreeNode>> Convert(ISymbolicExpressionTree tree, Func<ISymbolicExpressionTreeNode, ILayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
     35    public IEnumerable<LayoutNode<ISymbolicExpressionTreeNode>> Convert(ISymbolicExpressionTree tree, Func<ISymbolicExpressionTreeNode, LayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
    3736      return Convert(tree.Root, convertFunc);
    3837    }
    3938    // translate the symbolic expression tree structure to a layout node tree structure
    4039    // return an enumerable containing all the layout nodes
    41     public IEnumerable<ILayoutNode<ISymbolicExpressionTreeNode>> Convert(ISymbolicExpressionTreeNode root, Func<ISymbolicExpressionTreeNode, ILayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
     40    public IEnumerable<LayoutNode<ISymbolicExpressionTreeNode>> Convert(ISymbolicExpressionTreeNode root, Func<ISymbolicExpressionTreeNode, LayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
    4241      var rootLayoutNode = convertFunc == null ? defaultConvert(root) : convertFunc(root);
    4342      rootLayoutNode.Ancestor = rootLayoutNode;
    4443
    4544      if (root.SubtreeCount > 0) {
    46         rootLayoutNode.Children = new List<ILayoutNode<ISymbolicExpressionTreeNode>>(root.SubtreeCount);
     45        rootLayoutNode.Children = new List<LayoutNode<ISymbolicExpressionTreeNode>>(root.SubtreeCount);
    4746        Expand(rootLayoutNode, convertFunc);
    4847      }
    4948
    50       var list = new List<ILayoutNode<ISymbolicExpressionTreeNode>> { rootLayoutNode };
     49      var list = new List<LayoutNode<ISymbolicExpressionTreeNode>> { rootLayoutNode };
    5150      int i = 0;
    5251      while (i < list.Count) {
    5352        if (list[i].Children != null)
    54           foreach (ILayoutNode<ISymbolicExpressionTreeNode> child in list[i].Children)
    55             list.Add(child);
     53          list.AddRange(list[i].Children);
     54        //          foreach (LayoutNode<ISymbolicExpressionTreeNode> child in list[i].Children)
     55        //            list.Add(child);
    5656        ++i;
    5757      }
    … …  
    5959    }
    6060
    61     private void Expand(ILayoutNode<ISymbolicExpressionTreeNode> layoutNode, Func<ISymbolicExpressionTreeNode, ILayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
     61    private void Expand(LayoutNode<ISymbolicExpressionTreeNode> layoutNode, Func<ISymbolicExpressionTreeNode, LayoutNode<ISymbolicExpressionTreeNode>> convertFunc = null) {
    6262      if (layoutNode.Children == null) return;
    6363      for (int i = 0; i < layoutNode.Content.SubtreeCount; ++i) {
    … …  
    6868        childLayoutNode.Level = layoutNode.Level + 1;
    6969        childLayoutNode.Ancestor = childLayoutNode;
    70         childLayoutNode.Children = subtree.SubtreeCount > 0 ? new List<ILayoutNode<ISymbolicExpressionTreeNode>>(subtree.SubtreeCount) : null;
     70        childLayoutNode.Children = subtree.SubtreeCount > 0 ? new List<LayoutNode<ISymbolicExpressionTreeNode>>(subtree.SubtreeCount) : null;
    7171        layoutNode.Children.Add(childLayoutNode);
    7272        Expand(childLayoutNode, convertFunc);
Note: See TracChangeset for help on using the changeset viewer.