Fast Layout of Hierarchies ( FastHierarchyLayout )

Baseclasses

Definition

The class FastHierarchyLayout represents a simple layout algorithm for hierarchies with given order of nodes on each layer. Thus it can be used as a third phase for the Sugiyama algorithm.

In the layout, all edges will have at most two bends. Additionally, for each edge having exactly two bends, the segment between them is drawn vertically. This applies in particular to the long edges arising in the first phase of the Sugiyama algorithm.

General Information

Algorithm
name	FastHierarchyLayout
long name	Fast Layout of Hierarchies
author

Implementation
author	Ch. Buchheim
date	July 1998
version

Pre- and Postcondition

precondition	=	$\emptyset$
postcondition(PRE)	=	$\emptyset$

Optional Parameters Instances of FastHierarchyLayout provide the following optional parameters:

$\bullet$

double node_distance = 3.0
determines the minimal horizontal distance between two nodes on the same layer.

$\bullet$

double layer_distance = 3.0
determines the minimal vertical distance between two nodes on neighbored layers.

$\bullet$

bool fixed_layer_distance = false
if set to true, the distance between neighbored layers is fixed.

#include < AGD/FastHierarchyLayout.h >

Creation

FastHierarchyLayout

L

creates an instance L of type FastHierarchyLayout.

Operations

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

bool	L.check(const GraphCopy& GC, const Hierarchy& H, AgdKey& p)
void	L.call(const GraphCopy& GC, const Hierarchy& H, LayoutInterface& A)

Access to Options

double	L.node_distance()
void	L.node_distance(double)
double	L.layer_distance()
void	L.layer_distance(double)
bool	L.fixed_layer_distance()
void	L.fixed_layer_distance(bool)

Implementation

The running time of the algorithm is $\protectO$(m(logm)²), where m is the number of edges plus the number of nodes (including dummy nodes) in the input hierarchy.