12 Tree Layout (original) (raw)

12 Tree Layout🔗ℹ

These functions specify tree layouts and functions that render them as picts.

Specifies an interior node of a tree for use with one of the renderers below.

If the children are tree-layout?s, then they have edges created by passing the corresponding tree-layout?s directly to tree-edge. Children that are #f correspond to leaf nodes that are not drawn.

The default node-pict (used when node-pict is #f) is .

(tree-edge node [#:edge-color edge-color #:edge-width edge-width #:edge-style edge-style]) → tree-edge?
node : (and/c tree-layout? (not/c #f))
edge-width : (or/c 'unspecified real? #f) = 'unspecified
edge-style : (or/c 'unspecified 'transparent 'solid 'xor 'hilite 'dot 'long-dash 'short-dash 'dot-dash 'xor-dot 'xor-long-dash 'xor-short-dash 'xor-dot-dash) = 'unspecified

This function specifies an edge from some parent to the given node. It it intended to be used with tree-layout, on a non-#f node.

When edge-width is 'unspecified, the line width will not be set. This is intended to allow the line width to be set for the whole pict via linewidth. Otherwise, edge-width is interpreted the same way as the width argument for the linewidth function.edge-style behaves similarly, its argument interpreted as the style argument for the linestyle function.

Example:

> (naive-layered (tree-layout (tree-edge #:edge-width 3 (tree-layout)) (tree-edge #:edge-color "red" #:edge-style 'dot (tree-layout))))

Changed in version 1.3 of package pict-lib: Added the #:edge-width option.
Changed in version 1.9: Added the #:edge-style option.

Recognizes a tree layout. It returns #twhen given #f or the result of tree-layout.

Recognizes a tree-layout? that represents a binary tree. That is, each interior node has either two children or is #f. Note that a node with zero children does not count as a leaf for the purposes of binary-tree-layout?.

Examples:

Recognizes an tree-edge.

Uses a naive algorithm that ensures that all nodes at a fixed depth are the same vertical distance from the root (dubbed “layered”). It recursively lays out subtrees and then horizontally combines them, aligning them at their tops. Then it places the root node centered over the children nodes.

The transform argument applies a coordinate transformation to each of the nodes after it has been layed out. The bounding box of the resulting pict encompasses the corners of the original bounding box after the transformation has been applied to them.

Examples:

> (naive-layered (complete 4))
> (naive-layered (complete 4) #:transform (lambda (x y) (values y x)))
> (naive-layered (tree-layout (tree-layout) (tree-layout) (tree-layout (tree-layout) (tree-layout) (tree-layout (tree-layout) (tree-layout)))))
> (define right-subtree-with-left-chain (tree-layout (tree-layout (tree-layout #f #f) (tree-layout (tree-layout #f #f) #f)) (tree-layout (tree-layout (tree-layout (tree-layout (tree-layout #f #f) #f) #f) #f) #f)))
> (naive-layered right-subtree-with-left-chain)

Changed in version 1.13 of package pict-lib: Added the #:transform option.

Uses the layout algorithm fromTidier Drawing of Trees by Edward M. Reingold and John S. Tilford (IEEE Transactions on Software Engineering, Volume 7, Number 2, March 1981) to lay out tree-layout.

The layout algorithm guarantees a number of properties, namely:

• nodes at the same level of tree appear at the same vertical distance from the top of the pict
• parents are centered over their children, which are placed from left to right,
• isomorphic subtrees are drawn the same way, no matter where they appear in the complete tree, and
• a tree and its mirror image produce picts that are mirror images of each other (which also holds for subtrees of the complete tree).

Within those constraints, the algorithm tries to make as narrow a drawing as it can, even to the point that one subtree of a given node might cross under the other one.

More precisely, it recursively lays out the two subtree and then, without adjusting the layout of the two subtrees, moves them as close together as it can, putting the root of the new tree centered on top of its children. (It does this in linear time, using clever techniques as discussed in the paper.)

The x-spacing and y-spacing are the amount of space that each row and each column takes up, measured in pixels. If x-spacing is #f, it is the width of the widest node pict? in the tree. If y-spacing is #f, it is 1.5 times the width of the widest node pict? in the tree. The transform is the same as in naive-layered.

Examples:

> (binary-tidier (complete 4))
> (define (dl t) (tree-layout (tree-layout #f #f) t))
> (define (dr t) (tree-layout t (tree-layout #f #f)))
> (binary-tidier (tree-layout (dr (dr (dr (dl (dl (dl (complete 2))))))) (dl (dl (dl (dr (dr (dr (complete 2)))))))))
> (binary-tidier right-subtree-with-left-chain)

Changed in version 1.13 of package pict-lib: Added the #:transform option.

Uses the “CT” binary tree layout algorithm fromA note on optimal area algorithms for upward drawing of binary treesby P. Crescenzi, G. Di Battista, and A. Piperno (Computational Geometry, Theory and Applications, 1992) to lay out tree-layout.

It adds horizontal and vertical space between layers based on x-spacing andy-spacing. If either is #f, 1.5 times the size of the biggest node is used. The transform is the same as in naive-layered.

Example:

> (hv-alternating (complete 8))

Changed in version 1.13 of package pict-lib: Added the #:transform option.

Added in version 6.0.1.4 of package pict-lib.