▼Pict:   Functional Pictures
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 image.

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

image

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

image

> (naive-layered (tree-layout
                  (tree-layout)
                  (tree-layout)
                  (tree-layout
                   (tree-layout)
                   (tree-layout)
                   (tree-layout
                    (tree-layout)
                    (tree-layout)))))

image

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

image

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

image

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

image

> (binary-tidier right-subtree-with-left-chain)

image

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

image

Added in version 6.0.1.4 of package pict-lib.

  top  ← prev  up  next →