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)
  # lw 0.03
  # 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)
  # lw 0.03
  # 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 force-based layout on a binary tree:

{-# LANGUAGE NoMonomorphismRestriction #-}
import Diagrams.Prelude
import Diagrams.TwoD.Layout.Tree

t 0 = Empty
t n = BNode n (t (n-1)) (t (n-1))

Just t' = uniqueXLayout 1 1 (t 4)

fblEx = renderTree (\n -> (text (show n) # fontSize 0.5
                            <> circle 0.3 # fc white))
            (~~)
            (forceLayoutTree t')
        # centerXY # pad 1.1

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.

"Symmetric" layout of rose trees, based on the algorithm described in:

Andrew J. Kennedy. Drawing Trees, J Func. Prog. 6 (3): 527-534, May 1996.

Trees laid out using this algorithm satisfy:

1. Nodes at a given level are always separated by at least a given minimum distance.
2. Parent nodes are centered with respect to their immediate offspring (though not necessarily with respect to the entire subtrees under them).
3. 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.
4. Identical subtrees are always rendered identically. Put another way, the layout of any subtree is independent of the rest of the tree.
5. The layouts are as narrow as possible while satisfying all the above constraints.

Force-directed layout of rose trees.