Node Hierarchies ( Hierarchy )

Definition

An instance H of type Hierarchy is an ordered collection L₀,..., L_{n - 1} of layers. The nodes on each layer are numbered 0, 1,...

We call the index of the layer to which a node v of GC belongs the rank of v. H always represents a proper hierarchy, i.e, rank(v) = rank(w) + 1 holds for every edge (v, w) of GC.

Node hierarchies are used by Sugiyama's layout algorithm, which performs iteratively a two layer crossing minimization between two neighbored layers, the fixed and the changeable layer. The crossing minimization proceeds alternatingly downward and upward, and reorders the nodes on the changeable layer depending on the positions of the nodes on the fixed layer.

The class Hierarchy provides a data type Direction, which can be downward or upward, and maintains the current direction of the crossing minimization and the current changeable layer. If L_i is the changeable layer, then L_{i - 1} is the fixed layer if the direction is downward (and i $\geq$ 1), and L_{i + 1} if the direction is upward (and i < = n - 1).

#include < AGD/Hierarchy.h >

Types

Hierarchy::Direction

the direction of the crossing minimization.

Creation

Hierarchy	H(GraphCopy& GC, const leda_node_array<int>& R)
		creates an instance H of type Hierarchy initialized to a proper hierarchy of GC. Places node v on layer R[original(v)]. Changes GC by reversing and splitting edges.

Operations

int	H.number_of_layers()	returns the number of layers of H.
int	H.length(int i)	returns the number of nodes on layer Li.
int	H.rank(leda_node v)	returns the index of the layer to which v belongs.
int	H.pos(leda_node v)	returns the position of v on its layer.
Layer&	H[int i]	returns a reference to layer Li. Precondition: 0 < = i < = n - 1
Direction	H.direction()	returns the current direction of crossing minimization.
void	H.direction(Direction dir)
		sets the current direction of crossing minimization to dir.
void	H.set_changeable_layer(int i)
		sets the current changeable layer to Li.
bool	H.is_dummy(leda_node v)	returns true iff v is a dummy node. Precondition: v is a node of GC.
int	H.calc_crossings(int i)	calculates the number of crossings between layer Li and layer Li + 1. Precondition: 0 < = i < = n - 1
int	H.calc_crossings()	calculates the total number of crossings.
void	H.store_pos(leda_node_map<int>& old_pos)
		stores the current positions of nodes in old_pos.
void	H.restore_pos(const leda_node_map<int>& new_pos)
		sets the positions of all nodes v to new$\_$pos[v]. Precondition: {new$\_$pos[v] | v $\in$ Li} = {0,...,length(i) - 1} holds for 0 < = i < = n - 1.
void	H.shuffle()	permutes the nodes on each layer randomly.