Copyright  (c) 2011 Brent Yorgey 

License  BSDstyle (see LICENSE) 
Maintainer  byorgey@cis.upenn.edu 
Safe Haskell  None 
Language  Haskell2010 
A collection of methods for laying out various kinds of trees. This module is still experimental, and more layout methods will probably be added over time.
Laying out a rose tree using a symmetric layout:
import Data.Tree import Diagrams.TwoD.Layout.Tree t1 = Node 'A' [Node 'B' (map lf "CDE"), Node 'F' [Node 'G' (map lf "HIJ")]] where lf x = Node x [] exampleSymmTree = renderTree ((<> circle 1 # fc white) . text . (:[])) (~~) (symmLayout' (with & slHSep .~ 4 & slVSep .~ 4) t1) # centerXY # pad 1.1
Laying out a rose tree of diagrams, with spacing automatically adjusted for the size of the diagrams:
import Data.Tree import Data.Maybe (fromMaybe) import Diagrams.TwoD.Layout.Tree tD = Node (rect 1 3) [ Node (circle 0.2) [] , Node (hcat . replicate 3 $ circle 1) [] , Node (eqTriangle 5) [] ] exampleSymmTreeWithDs = renderTree id (~~) (symmLayout' (with & slWidth .~ fromMaybe (0,0) . extentX & slHeight .~ fromMaybe (0,0) . extentY) tD) # centerXY # pad 1.1
Using a variant symmetric layout algorithm specifically for binary trees:
import Diagrams.TwoD.Layout.Tree drawT = maybe mempty (renderTree (const (circle 0.05 # fc black)) (~~)) . symmLayoutBin' (with & slVSep .~ 0.5) tree500 = drawT t # centerXY # pad 1.1 # sized (Width 4) where t = genTree 500 0.05  genTree 500 0.05 randomly generates trees of size 500 +/ 5%,  definition not shown
Using forcebased layout on a binary tree:
{# LANGUAGE NoMonomorphismRestriction #} import Diagrams.Prelude import Diagrams.TwoD.Layout.Tree t 0 = Empty t n = BNode n (t (n1)) (t (n1)) Just t' = uniqueXLayout 1 1 (t 4) fblEx = renderTree (\n > (text (show n) # fontSizeL 0.5 <> circle 0.3 # fc white)) (~~) (forceLayoutTree t') # centerXY # pad 1.1
 data BTree a
 leaf :: a > BTree a
 uniqueXLayout :: Double > Double > BTree a > Maybe (Tree (a, P2))
 symmLayout :: Tree a > Tree (a, P2)
 symmLayout' :: SymmLayoutOpts a > Tree a > Tree (a, P2)
 symmLayoutBin :: BTree a > Maybe (Tree (a, P2))
 symmLayoutBin' :: SymmLayoutOpts a > BTree a > Maybe (Tree (a, P2))
 data SymmLayoutOpts a = SLOpts {}
 slHSep :: forall a. Lens' (SymmLayoutOpts a) Double
 slVSep :: forall a. Lens' (SymmLayoutOpts a) Double
 slWidth :: forall a. Lens' (SymmLayoutOpts a) (a > (Double, Double))
 slHeight :: forall a. Lens' (SymmLayoutOpts a) (a > (Double, Double))
 forceLayoutTree :: Tree (a, P2) > Tree (a, P2)
 forceLayoutTree' :: ForceLayoutTreeOpts > Tree (a, P2) > Tree (a, P2)
 data ForceLayoutTreeOpts = FLTOpts {}
 forceLayoutOpts :: Lens' ForceLayoutTreeOpts (ForceLayoutOpts R2)
 edgeLen :: Lens' ForceLayoutTreeOpts Double
 springK :: Lens' ForceLayoutTreeOpts Double
 staticK :: Lens' ForceLayoutTreeOpts Double
 treeToEnsemble :: forall a. ForceLayoutTreeOpts > Tree (a, P2) > (Tree (a, PID), Ensemble R2)
 label :: Traversable t => t a > t (a, PID)
 reconstruct :: Functor t => Ensemble R2 > t (a, PID) > t (a, P2)
 renderTree :: Monoid' m => (a > QDiagram b R2 m) > (P2 > P2 > QDiagram b R2 m) > Tree (a, P2) > QDiagram b R2 m
 renderTree' :: Monoid' m => (a > QDiagram b R2 m) > ((a, P2) > (a, P2) > QDiagram b R2 m) > Tree (a, P2) > QDiagram b R2 m
Binary trees
There is a standard type of rose trees (Tree
) defined in the
containers
package, but there is no standard type for binary
trees, so we define one here. Note, if you want to draw binary
trees with data of type a
at the leaves, you can use something
like BTree (Maybe a)
with Nothing
at internal nodes;
renderTree
lets you specify how to draw each node.
Binary trees with data at internal nodes.
Layout algorithms
Uniquex layout
uniqueXLayout :: Double > Double > BTree a > Maybe (Tree (a, P2)) Source
uniqueXLayout xSep ySep t
lays out the binary tree t
using a
simple recursive algorithm with the following properties:
 Every left subtree is completely to the left of its parent, and similarly for right subtrees.
 All the nodes at a given depth in the tree have the same
ycoordinate. The separation distance between levels is given by
ySep
.  Every node has a unique xcoordinate. The separation between
successive nodes from left to right is given by
xSep
.
Symmetric layout
"Symmetric" layout of rose trees, based on the algorithm described in:
Andrew J. Kennedy. Drawing Trees, J Func. Prog. 6 (3): 527534, May 1996.
Trees laid out using this algorithm satisfy:
 Nodes at a given level are always separated by at least a given minimum distance.
 Parent nodes are centered with respect to their immediate offspring (though not necessarily with respect to the entire subtrees under them).
 Layout commutes with mirroring: that is, the layout of a given tree is the mirror image of the layout of the tree's mirror image. Put another way, there is no inherent left or right bias.
 Identical subtrees are always rendered identically. Put another way, the layout of any subtree is independent of the rest of the tree.
 The layouts are as narrow as possible while satisfying all the above constraints.
symmLayout :: Tree a > Tree (a, P2) Source
Run the symmetric rose tree layout algorithm on a given tree using default options, resulting in the same tree annotated with node positions.
symmLayout' :: SymmLayoutOpts a > Tree a > Tree (a, P2) Source
Run the symmetric rose tree layout algorithm on a given tree, resulting in the same tree annotated with node positions.
symmLayoutBin :: BTree a > Maybe (Tree (a, P2)) Source
Lay out a binary tree using a slight variant of the symmetric
layout algorithm, using default options. In particular, if a
node has only a left child but no right child (or vice versa),
the child will be offset from the parent horizontally by half the
horizontal separation parameter. Note that the result will be
Nothing
if and only if the input tree is Empty
.
symmLayoutBin' :: SymmLayoutOpts a > BTree a > Maybe (Tree (a, P2)) Source
Lay out a binary tree using a slight variant of the symmetric
layout algorithm. In particular, if a node has only a left child
but no right child (or vice versa), the child will be offset from
the parent horizontally by half the horizontal separation
parameter. Note that the result will be Nothing
if and only if
the input tree is Empty
.
data SymmLayoutOpts a Source
Options for controlling the symmetric tree layout algorithm.
SLOpts  

Default (SymmLayoutOpts a) 
slHSep :: forall a. Lens' (SymmLayoutOpts a) Double Source
slVSep :: forall a. Lens' (SymmLayoutOpts a) Double Source
Forcedirected layout
Forcedirected layout of rose trees.
forceLayoutTree :: Tree (a, P2) > Tree (a, P2) Source
Forcedirected layout of rose trees, with default parameters (for
more options, see forceLayoutTree'
). In particular,
 edges are modeled as springs
 nodes are modeled as point charges
 nodes are constrained to keep the same ycoordinate.
The input could be a tree already laid out by some other method,
such as uniqueXLayout
.
forceLayoutTree' :: ForceLayoutTreeOpts > Tree (a, P2) > Tree (a, P2) Source
Forcedirected layout of rose trees, with configurable parameters.
data ForceLayoutTreeOpts Source
FLTOpts  

Default ForceLayoutTreeOpts 
forceLayoutOpts :: Lens' ForceLayoutTreeOpts (ForceLayoutOpts R2) Source
treeToEnsemble :: forall a. ForceLayoutTreeOpts > Tree (a, P2) > (Tree (a, PID), Ensemble R2) Source
Assign unique ID numbers to the nodes of a tree, and generate an
Ensemble
suitable for simulating in order to do forcedirected
layout of the tree. In particular,
 edges are modeled as springs
 nodes are modeled as point charges
 nodes are constrained to keep the same ycoordinate.
The input to treeToEnsemble
could be a tree already laid out by
some other method, such as uniqueXLayout
.
label :: Traversable t => t a > t (a, PID) Source
Assign unique IDs to every node in a tree (or other traversable structure).
reconstruct :: Functor t => Ensemble R2 > t (a, PID) > t (a, P2) Source
Reconstruct a tree (or any traversable structure) from an
Ensemble
, given unique identifier annotations matching the
identifiers used in the Ensemble
.
Rendering
renderTree :: Monoid' m => (a > QDiagram b R2 m) > (P2 > P2 > QDiagram b R2 m) > Tree (a, P2) > QDiagram b R2 m Source
Draw a tree annotated with node positions, given functions specifying how to draw nodes and edges.
renderTree' :: Monoid' m => (a > QDiagram b R2 m) > ((a, P2) > (a, P2) > QDiagram b R2 m) > Tree (a, P2) > QDiagram b R2 m Source
Draw a tree annotated with node positions, given functions
specifying how to draw nodes and edges. Unlike renderTree
,
this version gives the edgedrawing function access to the actual
values stored at the nodes rather than just their positions.