▼ |  | Pict: Functional Pictures

1 | Pict Datatype
2 | Basic Pict Constructors
3 | Pict Combiners
4 | Pict Drawing Adjusters
5 | Bounding Box Adjusters
6 | Pict Finders
7 | More Pict Constructors
8 | Animation Helpers
9 | Color Helpers
10 | Shadows
11 | Conditional Combinations
12 | Tree Layout
13 | Miscellaneous
14 | Rendering
15 | Conversion to Picts

On this page:

tree-layout
tree-edge
tree-layout?
binary-tree-layout?
tree-edge?
naive-layered
binary-tidier
hv-alternating

top ← prev up next →

### 12`` Tree Layout

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

(require pict/tree-layout) | package: pict-lib

> > procedure

> > (tree-layout [#:pict node-pict] child ...) → tree-layout?

> node-pict : (or/c #f pict?) = #f
> child : (or/c tree-layout? tree-edge? #f)

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 .

> > procedure

> > (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-color

> :

> (or/c string?
> (is-a?/c color%)
> (list/c byte? byte? byte?))

> =

> "gray"

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

> > procedure

> > (tree-layout? v) → boolean?

> v : any/c

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

> > procedure

> > (binary-tree-layout? v) → boolean?

> v : any/c

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:

> > (binary-tree-layout? (tree-layout #f #f))
> #t
> > (binary-tree-layout? #f)
> #t
> > (binary-tree-layout? (tree-layout (tree-layout) (tree-layout)))
> #f

> > procedure

> > (tree-edge? v) → boolean?

> v : any/c

Recognizes an tree-edge.

> > procedure

> > (naive-layered |  | tree-layout |  |  |  |
> > | [ | #:x-spacing x-spacing |  |  |  |
> > |  | #:y-spacing y-spacing]) |  | → |  | pict?

> tree-layout : tree-layout?
> x-spacing : (or/c (and/c real? positive?) #f) = #f
> y-spacing : (or/c (and/c real? positive?) #f) = #f

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.

Examples:

> > (define (complete d)
> (cond
> [(zero? d) #f]
> [else (define s (complete (- d 1)))
> (tree-layout s s)]))

> > (naive-layered (complete 4))

> > (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)

> > procedure

> > (binary-tidier |  | tree-layout |  |  |  |
> > | [ | #:x-spacing x-spacing |  |  |  |
> > |  | #:y-spacing y-spacing]) |  | → |  | pict?

> tree-layout : binary-tree-layout?
> x-spacing : (or/c (and/c real? positive?) #f) = #f
> y-spacing : (or/c (and/c real? positive?) #f) = #f

Uses the layout algorithm from Tidier 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.

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)

> > procedure

> > (hv-alternating |  | tree-layout |  |  |  |
> > | [ | #:x-spacing x-spacing |  |  |  |
> > |  | #:y-spacing y-spacing]) |  | → |  | pict?

> tree-layout : binary-tree-layout?
> x-spacing : (or/c (and/c real? positive?) #f) = #f
> y-spacing : (or/c (and/c real? positive?) #f) = #f

Uses the “CT” binary tree layout algorithm from A note on optimal area algorithms for upward drawing of binary trees by 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 and y-spacing. If either is #f, 1.5 times the size of the biggest node is used.

Example:

> > (hv-alternating (complete 8))

Added in version 6.0.1.4 of package pict-lib.

top ← prev up next →