1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Drawing;


25  using System.Linq;


26 


27  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {


28  public class Node {


29  public Node Thread;


30  public Node Ancestor;


31 


32  public float Mod; // position modifier


33  public float Prelim;


34  public float Change;


35  public float Shift;


36  public int Number;


37 


38  public float X;


39  public float Y;


40 


41  public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;


42 


43  // public int Number {


44  // get {


45  // var parent = SymbolicExpressionTreeNode.Parent;


46  // if (parent == null) return 1;


47  // return parent.IndexOfSubtree(SymbolicExpressionTreeNode);


48  // }


49  // }


50 


51  public bool IsLeaf {


52  get { return SymbolicExpressionTreeNode.SubtreeCount == 0; }


53  }


54  }


55 


56  public class TreeLayout {


57  private float distance = 5;


58  public float Distance {


59  get { return distance; }


60  set { distance = value; }


61  }


62 


63  private ISymbolicExpressionTree symbolicExpressionTree;


64  public ISymbolicExpressionTree SymbolicExpressionTree {


65  get { return symbolicExpressionTree; }


66  set {


67  symbolicExpressionTree = value;


68  nodes.Clear();


69  var treeNodes = SymbolicExpressionTree.IterateNodesBreadth().ToList();


70  foreach (var treeNode in treeNodes) {


71  var node = new Node { SymbolicExpressionTreeNode = treeNode };


72  node.Ancestor = node;


73  nodes.Add(treeNode, node);


74  }


75  // assign a number to each node, representing its position among its siblings (parent.IndexOfSubtree)


76  foreach (var treeNode in treeNodes.Where(x => x.SubtreeCount > 0)) {


77  for (int i = 0; i != treeNode.SubtreeCount; ++i) {


78  nodes[treeNode.GetSubtree(i)].Number = i;


79  }


80  }


81  var r = nodes[symbolicExpressionTree.Root];


82  FirstWalk(r);


83  SecondWalk(r, r.Prelim);


84  NormalizeCoordinates();


85  }


86  }


87 


88  /// <summary>


89  /// Returns a map of coordinates for each node in the symbolic expression tree.


90  /// </summary>


91  /// <returns></returns>


92  public Dictionary<ISymbolicExpressionTreeNode, PointF> GetNodeCoordinates() {


93  var dict = new Dictionary<ISymbolicExpressionTreeNode, PointF>();


94  if (nodes == null  nodes.Count == 0) return dict;


95  foreach (var node in nodes.Values) {


96  dict.Add(node.SymbolicExpressionTreeNode, new PointF { X = node.X, Y = node.Y });


97  }


98  return dict;


99  }


100 


101  /// <summary>


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


103  /// </summary>


104  /// <returns></returns>


105  public RectangleF Bounds() {


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


107  var list = nodes.Values.ToList();


108  for (int i = 0; i != list.Count; ++i) {


109  float x = list[i].X, y = list[i].Y;


110  if (xmin > x) xmin = x;


111  if (xmax < x) xmax = x;


112  if (ymin > y) ymin = y;


113  if (ymax < y) ymax = y;


114  }


115  return new RectangleF(xmin, ymin, xmax + distance, ymax + distance);


116  }


117 


118  /// <summary>


119  /// Returns a string containing all the coordinates (useful for debugging).


120  /// </summary>


121  /// <returns></returns>


122  public string DumpCoordinates() {


123  if (nodes == null  nodes.Count == 0) return string.Empty;


124  return nodes.Values.Aggregate("", (current, node) => current + (node.X + " " + node.Y + Environment.NewLine));


125  }


126 


127  private readonly Dictionary<ISymbolicExpressionTreeNode, Node> nodes;


128 


129  public TreeLayout() {


130  nodes = new Dictionary<ISymbolicExpressionTreeNode, Node>();


131  }


132 


133  /// <summary>


134  /// Transform node coordinates so that all coordinates are positive and start from 0.


135  /// </summary>


136  private void NormalizeCoordinates() {


137  var list = nodes.Values.ToList();


138  float xmin = 0, ymin = 0;


139  for (int i = 0; i != list.Count; ++i) {


140  if (xmin > list[i].X) xmin = list[i].X;


141  if (ymin > list[i].Y) ymin = list[i].Y;


142  }


143  for (int i = 0; i != list.Count; ++i) {


144  list[i].X = xmin;


145  list[i].Y = ymin;


146  }


147  }


148 


149  private void FirstWalk(Node v) {


150  Node w;


151  if (v.IsLeaf) {


152  w = LeftSibling(v);


153  if (w != null) {


154  v.Prelim = w.Prelim + distance;


155  }


156  } else {


157  var symbExprNode = v.SymbolicExpressionTreeNode;


158  var defaultAncestor = nodes[symbExprNode.GetSubtree(0)]; // let defaultAncestor be the leftmost child of v


159  for (int i = 0; i != symbExprNode.SubtreeCount; ++i) {


160  var s = symbExprNode.GetSubtree(i);


161  w = nodes[s];


162  FirstWalk(w);


163  Apportion(w, ref defaultAncestor);


164  }


165  ExecuteShifts(v);


166  int c = symbExprNode.SubtreeCount;


167  var leftmost = nodes[symbExprNode.GetSubtree(0)];


168  var rightmost = nodes[symbExprNode.GetSubtree(c  1)];


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


170  w = LeftSibling(v);


171  if (w != null) {


172  v.Prelim = w.Prelim + distance;


173  v.Mod = v.Prelim  midPoint;


174  } else {


175  v.Prelim = midPoint;


176  }


177  }


178  }


179 


180  private void SecondWalk(Node v, float m) {


181  v.X = v.Prelim + m;


182  v.Y = symbolicExpressionTree.Root.GetBranchLevel(v.SymbolicExpressionTreeNode) * distance;


183  var symbExprNode = v.SymbolicExpressionTreeNode;


184  foreach (var s in symbExprNode.Subtrees) {


185  SecondWalk(nodes[s], m + v.Mod);


186  }


187  }


188 


189  private void Apportion(Node v, ref Node defaultAncestor) {


190  var w = LeftSibling(v);


191  if (w == null) return;


192  Node vip = v;


193  Node vop = v;


194  Node vim = w;


195  Node vom = LeftmostSibling(vip);


196 


197  float sip = vip.Mod;


198  float sop = vop.Mod;


199  float sim = vim.Mod;


200  float som = vom.Mod;


201 


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


203  vim = NextRight(vim);


204  vip = NextLeft(vip);


205  vom = NextLeft(vom);


206  vop = NextRight(vop);


207  vop.Ancestor = v;


208  float shift = (vim.Prelim + sim)  (vip.Prelim + sip) + distance;


209  if (shift > 0) {


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


211  MoveSubtree(ancestor, v, shift);


212  sip += shift;


213  sop += shift;


214  }


215  sim += vim.Mod;


216  sip += vip.Mod;


217  som += vom.Mod;


218  sop += vop.Mod;


219  }


220  if (NextRight(vim) != null && NextRight(vop) == null) {


221  vop.Thread = NextRight(vim);


222  vop.Mod += (sim  sop);


223  }


224  if (NextLeft(vip) != null && NextLeft(vom) == null) {


225  vom.Thread = NextLeft(vip);


226  vom.Mod += (sip  som);


227  defaultAncestor = v;


228  }


229  }


230 


231  private void MoveSubtree(Node wm, Node wp, float shift) {


232  int subtrees = wp.Number  wm.Number;


233  wp.Change = shift / subtrees;


234  wp.Shift += shift;


235  wm.Change += shift / subtrees;


236  wp.Prelim += shift;


237  wp.Mod += shift;


238  }


239 


240  private void ExecuteShifts(Node v) {


241  if (v.IsLeaf) return;


242  float shift = 0;


243  float change = 0;


244  for (int i = v.SymbolicExpressionTreeNode.SubtreeCount  1; i >= 0; i) {


245  var subtree = v.SymbolicExpressionTreeNode.GetSubtree(i);


246  var w = nodes[subtree];


247  w.Prelim += shift;


248  w.Mod += shift;


249  change += w.Change;


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


251  }


252  }


253 


254  #region Helper functions


255  private Node Ancestor(Node vi, Node v) {


256  var ancestor = vi.Ancestor;


257  return ancestor.SymbolicExpressionTreeNode.Parent == v.SymbolicExpressionTreeNode.Parent ? ancestor : null;


258  }


259 


260  private Node NextLeft(Node v) {


261  int c = v.SymbolicExpressionTreeNode.SubtreeCount;


262  return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(0)]; // return leftmost child


263  }


264 


265  private Node NextRight(Node v) {


266  int c = v.SymbolicExpressionTreeNode.SubtreeCount;


267  return c == 0 ? v.Thread : nodes[v.SymbolicExpressionTreeNode.GetSubtree(c  1)]; // return rightmost child


268  }


269 


270  private Node LeftSibling(Node n) {


271  var parent = n.SymbolicExpressionTreeNode.Parent;


272  if (parent == null) return null;


273  int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);


274  if (i == 0) return null;


275  return nodes[parent.GetSubtree(i  1)];


276  }


277 


278  private Node LeftmostSibling(Node n) {


279  var parent = n.SymbolicExpressionTreeNode.Parent;


280  if (parent == null) return null;


281  int i = parent.IndexOfSubtree(n.SymbolicExpressionTreeNode);


282  if (i == 0) return null;


283  return nodes[parent.GetSubtree(0)];


284  }


285  #endregion


286  }


287  }

