diagrams-contrib-1.4.4: Collection of user contributions to diagrams EDSL

Diagrams.TwoD.Layout.Tree

Description

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 "HIJKLM"), Node 'N' (map lf "OPQR")]]
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 import Diagrams.Prelude hiding (Empty) drawT = maybe mempty (renderTree (const (circle 0.05 # fc black)) (~~)) . symmLayoutBin' (with & slVSep .~ 0.5) tree500 = drawT t # centerXY # pad 1.1 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 hiding (Empty) import Diagrams.TwoD.Layout.Tree gent 0 = Empty gent n = BNode n (gent (n-1)) (gent (n-1)) Just t' = uniqueXLayout 1 1 (gent 4) fblEx = renderTree (\n -> (text (show n) # fontSizeL 0.5 <> circle 0.3 # fc white)) (~~) (forceLayoutTree t') # centerXY # pad 1.1 Using a radial layout: import Diagrams.Prelude import Diagrams.TwoD.Layout.Tree import Data.Tree t = Node 'A' [Node 'B' (map lf "CDE"), Node 'F' [Node 'G' (map lf "HIJKLM"), Node 'N' (map lf "OPQRS")], Node 'T' (map lf "UVWXYZ")] where lf x = Node x [] radialEx = renderTree (\n -> (text (show n) # fontSizeG 0.5 <> circle 0.5 # fc white)) (~~) (radialLayout t) # centerXY # pad 1.1 Synopsis # 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. data BTree a Source # Binary trees with data at internal nodes. Constructors  Empty BNode a (BTree a) (BTree a) Instances  Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methodsfmap :: (a -> b) -> BTree a -> BTree b #(<$) :: a -> BTree b -> BTree a # Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methodsfold :: Monoid m => BTree m -> m #foldMap :: Monoid m => (a -> m) -> BTree a -> m #foldr :: (a -> b -> b) -> b -> BTree a -> b #foldr' :: (a -> b -> b) -> b -> BTree a -> b #foldl :: (b -> a -> b) -> b -> BTree a -> b #foldl' :: (b -> a -> b) -> b -> BTree a -> b #foldr1 :: (a -> a -> a) -> BTree a -> a #foldl1 :: (a -> a -> a) -> BTree a -> a #toList :: BTree a -> [a] #null :: BTree a -> Bool #length :: BTree a -> Int #elem :: Eq a => a -> BTree a -> Bool #maximum :: Ord a => BTree a -> a #minimum :: Ord a => BTree a -> a #sum :: Num a => BTree a -> a #product :: Num a => BTree a -> a # Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methodstraverse :: Applicative f => (a -> f b) -> BTree a -> f (BTree b) #sequenceA :: Applicative f => BTree (f a) -> f (BTree a) #mapM :: Monad m => (a -> m b) -> BTree a -> m (BTree b) #sequence :: Monad m => BTree (m a) -> m (BTree a) # Eq a => Eq (BTree a) Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methods(==) :: BTree a -> BTree a -> Bool #(/=) :: BTree a -> BTree a -> Bool # Ord a => Ord (BTree a) Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methodscompare :: BTree a -> BTree a -> Ordering #(<) :: BTree a -> BTree a -> Bool #(<=) :: BTree a -> BTree a -> Bool #(>) :: BTree a -> BTree a -> Bool #(>=) :: BTree a -> BTree a -> Bool #max :: BTree a -> BTree a -> BTree a #min :: BTree a -> BTree a -> BTree a # Read a => Read (BTree a) Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree MethodsreadsPrec :: Int -> ReadS (BTree a) #readList :: ReadS [BTree a] # Show a => Show (BTree a) Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree MethodsshowsPrec :: Int -> BTree a -> ShowS #show :: BTree a -> String #showList :: [BTree a] -> ShowS #

leaf :: a -> BTree a Source #

Convenient constructor for leaves.

# Layout algorithms

## Unique-x layout

uniqueXLayout :: Num n => n -> n -> BTree a -> Maybe (Tree (a, P2 n)) 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 y-coordinate. The separation distance between levels is given by ySep.
• Every node has a unique x-coordinate. The separation between successive nodes from left to right is given by xSep.

radialLayout :: Tree a -> Tree (a, P2 Double) Source #

Radial layout of rose trees, adapted from Andy Pavlo, "Interactive, Tree-Based Graph Visualization", p. 18 (http://www.cs.cmu.edu/~pavlo/static/papers/APavloThesis032006.pdf)

## Symmetric layout

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

symmLayout :: (Fractional n, Ord n) => Tree a -> Tree (a, P2 n) 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' :: (Fractional n, Ord n) => SymmLayoutOpts n a -> Tree a -> Tree (a, P2 n) Source #

Run the symmetric rose tree layout algorithm on a given tree, resulting in the same tree annotated with node positions.

symmLayoutBin :: (Fractional n, Ord n) => BTree a -> Maybe (Tree (a, P2 n)) 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' :: (Fractional n, Ord n) => SymmLayoutOpts n a -> BTree a -> Maybe (Tree (a, P2 n)) 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 n a Source #

Options for controlling the symmetric tree layout algorithm.

Constructors

 SLOpts Fields_slHSep :: nMinimum horizontal separation between sibling nodes. The default is 1._slVSep :: nVertical separation between adjacent levels of the tree. The default is 1._slWidth :: a -> (n, n)A function for measuring the horizontal extent (a pair of x-coordinates) of an item in the tree. The default is const (0,0), that is, the nodes are considered as taking up no space, so the centers of the nodes will be separated according to the slHSep and slVSep. However, this can be useful, e.g. if you have a tree of diagrams of irregular size and want to make sure no diagrams overlap. In that case you could use fromMaybe (0,0) . extentX._slHeight :: a -> (n, n)A function for measuring the vertical extent of an item in the tree. The default is const (0,0). See the documentation for slWidth for more information.
Instances
 Num n => Default (SymmLayoutOpts n a) Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methodsdef :: SymmLayoutOpts n a #

slHSep :: forall n a. Lens' (SymmLayoutOpts n a) n Source #

slVSep :: forall n a. Lens' (SymmLayoutOpts n a) n Source #

slWidth :: forall n a. Lens' (SymmLayoutOpts n a) (a -> (n, n)) Source #

slHeight :: forall n a. Lens' (SymmLayoutOpts n a) (a -> (n, n)) Source #

## Force-directed layout

Force-directed layout of rose trees.

forceLayoutTree :: (Floating n, Ord n) => Tree (a, P2 n) -> Tree (a, P2 n) Source #

Force-directed 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 y-coordinate.

The input could be a tree already laid out by some other method, such as uniqueXLayout.

forceLayoutTree' :: (Floating n, Ord n) => ForceLayoutTreeOpts n -> Tree (a, P2 n) -> Tree (a, P2 n) Source #

Force-directed layout of rose trees, with configurable parameters.

Constructors

 FLTOpts Fields_forceLayoutOpts :: ForceLayoutOpts nOptions to the force layout simulator, including damping._edgeLen :: nHow long edges should be, ideally. This will be the resting length for the springs._springK :: nSpring constant. The bigger the constant, the more the edges push/pull towards their resting length._staticK :: nCoulomb constant. The bigger the constant, the more sibling nodes repel each other.
Instances
 Source # Instance detailsDefined in Diagrams.TwoD.Layout.Tree Methods

treeToEnsemble :: forall a n. Floating n => ForceLayoutTreeOpts n -> Tree (a, P2 n) -> (Tree (a, PID), Ensemble V2 n) Source #

Assign unique ID numbers to the nodes of a tree, and generate an Ensemble suitable for simulating in order to do force-directed layout of the tree. In particular,

• edges are modeled as springs
• nodes are modeled as point charges
• nodes are constrained to keep the same y-coordinate.

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, Num n) => Ensemble V2 n -> t (a, PID) -> t (a, P2 n) 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, Floating n, Ord n) => (a -> QDiagram b V2 n m) -> (P2 n -> P2 n -> QDiagram b V2 n m) -> Tree (a, P2 n) -> QDiagram b V2 n m Source #

Draw a tree annotated with node positions, given functions specifying how to draw nodes and edges.

renderTree' :: (Monoid' m, Floating n, Ord n) => (a -> QDiagram b V2 n m) -> ((a, P2 n) -> (a, P2 n) -> QDiagram b V2 n m) -> Tree (a, P2 n) -> QDiagram b V2 n m Source #

Draw a tree annotated with node positions, given functions specifying how to draw nodes and edges. Unlike renderTree, this version gives the edge-drawing function access to the actual values stored at the nodes rather than just their positions.