Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs (revision 10519)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/Formatters/SymbolicExpressionTreeLatexFormatter.cs (revision 10519)
@@ -0,0 +1,98 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Globalization;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
+ [Item("LaTeX/PDF Formatter", "Formatter for symbolic expression trees for use with latex package tikz.")]
+ public class SymbolicExpressionTreeLatexFormatter : NamedItem, ISymbolicExpressionTreeStringFormatter {
+ private readonly static Dictionary symbolNameMap = new Dictionary
+ {
+ {"ProgramRootSymbol", "Prog"},
+ {"StartSymbol","RPB"}
+ };
+ private readonly ReingoldTilfordLayoutEngine layoutEngine = new ReingoldTilfordLayoutEngine();
+ private readonly SymbolicExpressionTreeLayoutAdapter layoutAdapter = new SymbolicExpressionTreeLayoutAdapter();
+
+ public SymbolicExpressionTreeLatexFormatter()
+ : base("LaTeX/PDF Formatter", "Formatter for symbolic expression trees for use with latex package tikz.") {
+ layoutEngine = new ReingoldTilfordLayoutEngine();
+ }
+
+ protected SymbolicExpressionTreeLatexFormatter(SymbolicExpressionTreeLatexFormatter original, Cloner cloner)
+ : base(original, cloner) {
+ }
+
+ public override IDeepCloneable Clone(Cloner cloner) {
+ return new SymbolicExpressionTreeLatexFormatter(this, cloner);
+ }
+
+ public string Format(ISymbolicExpressionTree symbolicExpressionTree) {
+ layoutEngine.Reset();
+ var layoutNodes = layoutAdapter.Convert(symbolicExpressionTree).ToList();
+ layoutEngine.Root = layoutNodes[0];
+ layoutEngine.AddNodes(layoutNodes);
+ layoutEngine.CalculateLayout();
+ var nodeCoordinates = layoutEngine.GetNodeCoordinates();
+ var sb = new StringBuilder();
+ var nl = Environment.NewLine;
+ double ws = 1;
+ double hs = 0.7;
+
+ sb.Append("\\documentclass[class=minimal,border=0pt]{standalone}" + nl +
+ "\\usepackage{tikz}" + nl +
+ "\\begin{document}" + nl +
+ "\\begin{tikzpicture}" + nl +
+ "\\def\\ws{1}" + nl +
+ "\\def\\hs{0.7}" + nl);
+
+ var nodeIndices = new Dictionary();
+ var nodes = symbolicExpressionTree.IterateNodesBreadth().ToList();
+ for (int i = 0; i < nodes.Count; ++i) {
+ var node = nodes[i];
+ nodeIndices.Add(node, i);
+ var coord = nodeCoordinates[node];
+ var nodeName = symbolNameMap.ContainsKey(node.Symbol.Name) ? symbolNameMap[node.Symbol.Name] : node.ToString();
+ sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\node ({0}) at (\\ws*{1},\\hs*{2}) {{{3}}};", i, ws * coord.X, -hs * coord.Y, EscapeLatexString(nodeName)));
+ }
+
+ for (int i = 0; i < nodes.Count; ++i) {
+ foreach (var s in nodes[i].Subtrees) {
+ sb.AppendLine(string.Format(CultureInfo.InvariantCulture, "\\draw ({0}) -- ({1});", i, nodeIndices[s]));
+ }
+ }
+
+ sb.Append("\\end{tikzpicture}" + nl +
+ "\\end{document}" + nl);
+ return sb.ToString();
+ }
+
+ private static string EscapeLatexString(string s) {
+ return s.Replace("\\", "\\\\").Replace("{", "\\{").Replace("}", "\\}").Replace("_", "\\_");
+ }
+ }
+}
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/LayoutNode.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/LayoutNode.cs (revision 10519)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/LayoutNode.cs (revision 10519)
@@ -0,0 +1,81 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see .
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
+ public class LayoutNode where T : class {
+ public float Width { get; set; }
+ public float Height { get; set; }
+
+ public LayoutNode NextLeft {
+ get {
+ return Children == null ? Thread : Children.First();
+ }
+ }
+ public LayoutNode NextRight {
+ get {
+ return Children == null ? Thread : Children.Last();
+ }
+ }
+ public LayoutNode LeftSibling {
+ get {
+ if (Parent == null) return null;
+ return Number == 0 ? null : Parent.Children[Number - 1];
+ }
+ }
+ public LayoutNode LeftmostSibling {
+ get {
+ if (Parent == null) return null;
+ return Number == 0 ? null : Parent.Children[0];
+ }
+ }
+
+ public LayoutNode Thread { get; set; }
+ public LayoutNode Ancestor { get; set; }
+ public LayoutNode Parent { get; set; }
+ public List> Children { get; set; }
+ public float Mod { get; set; }
+ public float Prelim { get; set; }
+ public float Change { get; set; }
+ public float Shift { get; set; }
+ public int Number { get; set; }
+ public int Level { get; set; }
+ public float X { get; set; }
+ public float Y { get; set; }
+
+ public bool IsLeaf {
+ get { return Children == null || Children.Count == 0; }
+ }
+
+ private T content;
+ public T Content {
+ get { return content; }
+ set {
+ if (value == null)
+ throw new ArgumentNullException("LayoutNode: Content cannot be null.");
+ content = value;
+ }
+ }
+ }
+}
Index: /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs (revision 10519)
+++ /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views/3.4/LayoutEngines/ReingoldTilfordLayoutEngine.cs (revision 10519)
@@ -0,0 +1,283 @@
+
+using System;
+using System.Collections.Generic;
+using System.Drawing;
+using System.Linq;
+
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views {
+ public class ReingoldTilfordLayoutEngine where T : class {
+ private readonly Dictionary> nodeMap; // provides a reverse mapping T => LayoutNode
+ public int NodeWidth { get; set; }
+ public int NodeHeight { get; set; }
+
+ public ReingoldTilfordLayoutEngine() {
+ nodeMap = new Dictionary>();
+ }
+
+ public Dictionary> NodeMap { get { return nodeMap; } }
+
+ public void AddNode(T content) {
+ if (nodeMap.ContainsKey(content)) {
+ throw new ArgumentException("Content already present in the dictionary.");
+ }
+ var node = new LayoutNode { Content = content };
+ nodeMap.Add(content, node);
+ }
+
+ public void AddNode(LayoutNode node) {
+ var content = node.Content;
+ if (nodeMap.ContainsKey(content)) {
+ throw new ArgumentException("Content already present in the dictionary.");
+ }
+ nodeMap.Add(content, node);
+ }
+
+ public void AddNodes(IEnumerable> nodes) {
+ foreach (var node in nodes)
+ nodeMap.Add(node.Content, node);
+ }
+
+ public LayoutNode GetNode(T content) {
+ LayoutNode layoutNode;
+ nodeMap.TryGetValue(content, out layoutNode);
+ return layoutNode;
+ }
+
+ private float minHorizontalSpacing = 5;
+ public float MinHorizontalSpacing {
+ get { return minHorizontalSpacing; }
+ set { minHorizontalSpacing = value; }
+ }
+
+ private float minVerticalSpacing = 5;
+ public float MinVerticalSpacing {
+ get { return minVerticalSpacing; }
+ set { minVerticalSpacing = value; }
+ }
+
+ private LayoutNode root;
+ public LayoutNode Root {
+ get { return root; }
+ set { root = value; }
+ }
+
+ public void ResetCoordinates() {
+ foreach (var node in nodeMap.Values) {
+ node.X = 0;
+ node.Y = 0;
+ }
+ }
+
+ ///
+ /// Transform LayoutNode coordinates so that all coordinates are positive and start from (0,0)
+ ///
+ private void NormalizeCoordinates() {
+ var list = nodeMap.Values.ToList();
+ float xmin = 0, ymin = 0;
+ for (int i = 0; i < list.Count; ++i) {
+ if (xmin > list[i].X) xmin = list[i].X;
+ if (ymin > list[i].Y) ymin = list[i].Y;
+ }
+ for (int i = 0; i < list.Count; ++i) {
+ list[i].X -= xmin;
+ list[i].Y -= ymin;
+ }
+ }
+
+ public void FitToBounds(int width, int height) {
+ var bounds = Bounds();
+ var myWidth = bounds.Width;
+ var myHeight = bounds.Height;
+
+ if (myWidth <= width && myHeight <= height) return; // no need to fit since we are within bounds
+
+ var layers = nodeMap.Values.GroupBy(node => node.Level, node => node).ToList();
+
+ if (myWidth > width) {
+ // need to scale horizontally
+ float x = width / myWidth;
+ foreach (var node in layers.SelectMany(g => g)) {
+ node.X *= x;
+ node.Width *= x;
+ }
+ float spacing = minHorizontalSpacing * x;
+ foreach (var layer in layers) {
+ var nodes = layer.ToList();
+ float minWidth = float.MaxValue;
+ for (int i = 0; i < nodes.Count - 1; ++i) { minWidth = Math.Min(minWidth, nodes[i + 1].X - nodes[i].X); }
+ float w = Math.Min(NodeWidth, minWidth - spacing);
+ foreach (var node in nodes) {
+ node.X += (node.Width - w) / 2f;
+ node.Width = w;
+ if (node.X < 0) {
+ // if the adjustment would put the node partially offscreen, we reduce the node width a little bit
+ // this is a simple solution which should work 99% of the time with no noticeable difference
+ node.Width += node.X;
+ node.X = Math.Abs(node.X) / 2f;
+ }
+ }
+ }
+ }
+ }
+
+ public void Reset() {
+ root = null;
+ nodeMap.Clear();
+ }
+
+ public void ResetParameters() {
+ foreach (var layoutNode in nodeMap.Values) {
+ // reset layout-related parameters
+ layoutNode.Ancestor = layoutNode;
+ layoutNode.Thread = null;
+ layoutNode.Change = 0;
+ layoutNode.Shift = 0;
+ layoutNode.Prelim = 0;
+ layoutNode.Mod = 0;
+ }
+ }
+
+ public void CalculateLayout() {
+ if (root == null)
+ throw new Exception("Root cannot be null.");
+ ResetCoordinates(); // reset node X,Y coordinates
+ ResetParameters(); // reset node parameters like Mod, Shift etc.
+ FirstWalk(root);
+ SecondWalk(root, -root.Prelim);
+ NormalizeCoordinates();
+ }
+
+ ///
+ /// Returns a map of coordinates for each LayoutNode in the symbolic expression tree.
+ ///
+ ///
+ public Dictionary GetNodeCoordinates() {
+ return nodeMap.ToDictionary(x => x.Key, x => new PointF(x.Value.X, x.Value.Y));
+ }
+
+ ///
+ /// Returns the bounding box for this layout. When the layout is normalized, the rectangle should be [0,0,xmin,xmax].
+ ///
+ ///
+ public RectangleF Bounds() {
+ float xmin = 0, xmax = 0, ymin = 0, ymax = 0;
+ var list = nodeMap.Values.ToList();
+ for (int i = 0; i < list.Count; ++i) {
+ float x = list[i].X, y = list[i].Y;
+ if (xmin > x) xmin = x;
+ if (xmax < x) xmax = x;
+ if (ymin > y) ymin = y;
+ if (ymax < y) ymax = y;
+ }
+ return new RectangleF(xmin, ymin, xmax + minHorizontalSpacing + NodeWidth, ymax + minVerticalSpacing + NodeHeight);
+ }
+
+ private void FirstWalk(LayoutNode v) {
+ LayoutNode w;
+ if (v.IsLeaf) {
+ w = v.LeftSibling;
+ if (w != null) {
+ v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
+ }
+ } else {
+ var defaultAncestor = v.Children[0]; // leftmost child
+
+ foreach (var child in v.Children) {
+ FirstWalk(child);
+ Apportion(child, ref defaultAncestor);
+ }
+ ExecuteShifts(v);
+ var leftmost = v.Children.First();
+ var rightmost = v.Children.Last();
+ float midPoint = (leftmost.Prelim + rightmost.Prelim) / 2;
+ w = v.LeftSibling;
+ if (w != null) {
+ v.Prelim = w.Prelim + minHorizontalSpacing + NodeWidth;
+ v.Mod = v.Prelim - midPoint;
+ } else {
+ v.Prelim = midPoint;
+ }
+ }
+ }
+
+ private void SecondWalk(LayoutNode v, float m) {
+ v.X = v.Prelim + m;
+ v.Y = v.Level * (minVerticalSpacing + NodeHeight);
+ if (v.IsLeaf) return;
+ foreach (var child in v.Children) {
+ SecondWalk(child, m + v.Mod);
+ }
+ }
+
+ private void Apportion(LayoutNode v, ref LayoutNode defaultAncestor) {
+ var w = v.LeftSibling;
+ if (w == null) return;
+ LayoutNode vip = v;
+ LayoutNode vop = v;
+ LayoutNode vim = w;
+ LayoutNode vom = vip.LeftmostSibling;
+
+ float sip = vip.Mod;
+ float sop = vop.Mod;
+ float sim = vim.Mod;
+ float som = vom.Mod;
+
+ while (vim.NextRight != null && vip.NextLeft != null) {
+ vim = vim.NextRight;
+ vip = vip.NextLeft;
+ vom = vom.NextLeft;
+ vop = vop.NextRight;
+ vop.Ancestor = v;
+ float shift = (vim.Prelim + sim) - (vip.Prelim + sip) + minHorizontalSpacing + NodeWidth;
+ if (shift > 0) {
+ var ancestor = Ancestor(vim, v) ?? defaultAncestor;
+ MoveSubtree(ancestor, v, shift);
+ sip += shift;
+ sop += shift;
+ }
+ sim += vim.Mod;
+ sip += vip.Mod;
+ som += vom.Mod;
+ sop += vop.Mod;
+ }
+ if (vim.NextRight != null && vop.NextRight == null) {
+ vop.Thread = vim.NextRight;
+ vop.Mod += (sim - sop);
+ }
+ if (vip.NextLeft != null && vom.NextLeft == null) {
+ vom.Thread = vip.NextLeft;
+ vom.Mod += (sip - som);
+ defaultAncestor = v;
+ }
+ }
+
+ private void MoveSubtree(LayoutNode wm, LayoutNode wp, float shift) {
+ 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)
+ if (subtrees == 0) throw new Exception("MoveSubtree failed: check if object is really a tree (no cycles)");
+ wp.Change -= shift / subtrees;
+ wp.Shift += shift;
+ wm.Change += shift / subtrees;
+ wp.Prelim += shift;
+ wp.Mod += shift;
+ }
+
+ private void ExecuteShifts(LayoutNode v) {
+ if (v.IsLeaf) return;
+ float shift = 0;
+ float change = 0;
+ for (int i = v.Children.Count - 1; i >= 0; --i) {
+ var w = v.Children[i];
+ w.Prelim += shift;
+ w.Mod += shift;
+ change += w.Change;
+ shift += (w.Shift + change);
+ }
+ }
+
+ private LayoutNode Ancestor(LayoutNode u, LayoutNode v) {
+ var ancestor = u.Ancestor;
+ if (ancestor == null) return null;
+ return ancestor.Parent == v.Parent ? ancestor : null;
+ }
+ }
+}
Index: anches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ILayoutAdapter.cs
===================================================================
--- /branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ILayoutAdapter.cs (revision 10518)
+++ (revision )
@@ -1,8 +1,0 @@
-using System;
-using System.Collections.Generic;
-
-namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
- public interface ILayoutAdapter where T : class {
- IEnumerable> Convert(T root, Func> convertFunc);
- }
-}