Walker's Algorithm ( TreeLayout )

Baseclasses

Definition

The class TreeLayout represents the layout algorithm by Walker II (Reingold and Tilford, Walker [RT81,Wal90,Lei96]).

This algorithm draws binary and general rooted trees. The graph G = (V, E) has to be directed, connected, and has to have exactly one source. Furthermore the equality | V| - 1 = | E| must hold.

The drawing is straight-line. Nodes of the same level are placed on a horizontal line.

The algorithm works recursively starting on the lowest level of the tree. In each step, the subtrees of a tree vertex (that have been layed out already) are placed as closely to each other as possible. This guarantees to have small layout size. Moreover, isomorphic subtrees are layed out symmetrically.

General Information

Algorithm
name	TreeLayout
long name	Layout algorithm for general trees
author	E. Reingold, J. Tilford, J. Q. Walker II

Implementation
author	S. Leipert
date	May 1997
version	0.1

Pre- and Postcondition

precondition	=	{ simple, tree }
postcondition(PRE)	=	{ straight - line, nocrossings, upwardplanar }

Optional Parameters Instances of TreeLayout provide the following optional parameters:

$\bullet$

double sib_separation = 4.0
The spacing between two sibling nodes.

$\bullet$

double subtree_separation = 4.0
The spacing between two adjacent subtrees.

$\bullet$

double level_separation = 4.0
The spacing between the nodes of two adjacent levels.

$\bullet$

double left_margin = 0.0
Additional spacing at the left side of the drawing.

$\bullet$

double upper_margin = 0.0
Additional spacing at the upper side of the drawing.

#include < AGD/TreeLayout.h >

Creation

TreeLayout

L

creates an instance L of type TreeLayout.

Operations

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base class (LayoutModule).

bool	L.check(const graph& G, AgdKey& p)
void	L.call(const graph& G, LayoutInterface& A)

Access to Options

double	L.sib_separation()
void	L.sib_separation(double s)
double	L.level_separation()
void	L.level_separation(double s)
double	L.subtree_separation()
void	L.subtree_separation(double s)
double	L.left_margin()
void	L.left_margin(double s)
double	L.upper_margin()
void	L.upper_margin(double s)

Implementation

The running time of the algorithm is $\protectO$(| V|).