Coordinate assignment phase for the Sugiyama algorithm by Buchheim et al. More...

#include <ogdf/layered/FastHierarchyLayout.h>

Inheritance diagram for ogdf::FastHierarchyLayout:

Public Member Functions
	FastHierarchyLayout ()
	Creates an instance of fast hierarchy layout.

	FastHierarchyLayout (const FastHierarchyLayout &)
	Copy constructor.

virtual	~FastHierarchyLayout ()

bool	fixedLayerDistance () const
	Returns the option fixed layer distance.

void	fixedLayerDistance (bool b)
	Sets the option fixed layer distance to `b`.

double	layerDistance () const
	Returns the option layer distance.

void	layerDistance (double dist)
	Sets the option layer distance to `dist`.

double	nodeDistance () const
	Returns the option node distance.

void	nodeDistance (double dist)
	Sets the option node distance to `dist`.

FastHierarchyLayout &	operator= (const FastHierarchyLayout &)
	Assignment operator.

Public Member Functions inherited from ogdf::HierarchyLayoutModule
	HierarchyLayoutModule ()
	Initializes a hierarchy layout module.

virtual	~HierarchyLayoutModule ()

void	call (const HierarchyLevelsBase &levels, GraphAttributes &GA)
	Computes a hierarchy layout of `levels` in `GA`.

Protected Member Functions
virtual void	doCall (const HierarchyLevelsBase &levels, GraphAttributes &AGC) override
	Implements the actual algorithm call.

Private Member Functions
void	decrTo (double &d, double t)

void	findPlacement ()
	Computes the layout of an embedded layered graph.

void	incrTo (double &d, double t)

bool	isFirst (int actNode) const

bool	isLast (int actNode) const

void	moveLongEdge (int actNode, int dir, bool *marked)
	Used for postprocessing the layout.

void	placeNodes (int leftBnd, int rightBnd, int left, int right, int d)
	Places a sequence of nonvirtual nodes.

bool	placeSingleNode (int leftBnd, int rightBnd, int actNode, double &best, int d)
	Places a sequence of nonvirtual nodes containing exactly one node.

bool	sameLayer (int n1, int n2) const

void	sortLongEdges (int actNode, int dir, double pos, bool &exD, double &dist, int block, bool *marked)
	Places the node actNode as far as possible to the left (if `dir` = 1) or to the right (if `dir` = -1) within a block.

void	straightenEdge (int actNode, bool *marked)
	Tries to remove a bend at the position of the virtual node by straightening the edge.

Private Attributes
List< int > *	adj [2]
	The list of neighbors in previous / next layer.

double *	breadth
	for every node : breadth[node] = width of the node.

int *	first
	Stores for every layer the index of the first node.

double *	height
	for every layer : height[layer] = height of max{height of node on layer}.

int	k
	The number of layers.

int *	layer
	Stores for every node its layer.

List< int > **	longEdge
	The nodes belonging to a long edge.

int	m
	The number edge sections.

bool	m_fixedLayerDist
	0 if distance between layers should be variable, 1 otherwise.

double	m_minLayerDist
	The minimal distance between layers.

double	m_minNodeDist
	The minimal node distance on a layer.

double *	mDist
	Similar to totalB, used for temporary storage.

int	n
	The number of nodes including virtual nodes.

double *	totalB
	for every node : minimal possible distance between the center of a node and first[layer[node]].

bool *	virt
	for every node : virt[node] = 1 if node is virtual, 0 otherwise.

double *	x
	for every node : x coordinate of node.

double *	y
	for every layer : y coordinate of layer.

Additional Inherited Members
Static Public Member Functions inherited from ogdf::HierarchyLayoutModule
static void	dynLayerDistance (GraphAttributes &AGC, HierarchyLevelsBase &levels)

Static Protected Member Functions inherited from ogdf::HierarchyLayoutModule
static double	getHeight (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v)
	Returns the `GA` height of node `v` or 0 if it is a dummy node in the hierarchy of `levels`.

static double	getWidth (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v)
	Returns the `GA` width of node `v` or 0 if it is a dummy node in the hierarchy of `levels`.

Detailed Description

Coordinate assignment phase for the Sugiyama algorithm by Buchheim et al.

This class implements a hierarchy layout algorithm, i.e., it layouts hierarchies with a given order of nodes on each layer. It is used as a third phase of the Sugiyama algorithm.

All edges of the layout 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.

The implementation is based on:

Christoph Buchheim, Michael Jünger, Sebastian Leipert: A Fast Layout Algorithm for k-Level Graphs. LNCS 1984 (Proc. Graph Drawing 2000), pp. 229-240, 2001.

Optional Parameters

Option	Type	Default	Description
node distance	double	3.0	the minimal horizontal distance between two nodes on the same layer
layer distance	double	3.0	the minimal vertical distance between two nodes on neighbored layers
fixed layer distance	bool	false	if true, the distance between neighbored layers is fixed, otherwise variable

Definition at line 76 of file FastHierarchyLayout.h.

Constructor & Destructor Documentation

◆ FastHierarchyLayout() [1/2]

ogdf::FastHierarchyLayout::FastHierarchyLayout ( )

Creates an instance of fast hierarchy layout.

◆ FastHierarchyLayout() [2/2]

ogdf::FastHierarchyLayout::FastHierarchyLayout ( const FastHierarchyLayout & )

Copy constructor.

◆ ~FastHierarchyLayout()

virtual ogdf::FastHierarchyLayout::~FastHierarchyLayout ( )

inlinevirtual

Definition at line 88 of file FastHierarchyLayout.h.

Member Function Documentation

◆ decrTo()

void ogdf::FastHierarchyLayout::decrTo	(	double &	d,
		double	t
	)

inlineprivate

Definition at line 164 of file FastHierarchyLayout.h.

◆ doCall()

virtual void ogdf::FastHierarchyLayout::doCall	(	const HierarchyLevelsBase &	levels,
		GraphAttributes &	AGC
	)

overrideprotectedvirtual

Implements the actual algorithm call.

Must be implemented by derived classes.

Parameters

levels	is the input hierarchy.
AGC	has to be assigned the hierarchy layout.

Implements ogdf::HierarchyLayoutModule.

◆ findPlacement()

void ogdf::FastHierarchyLayout::findPlacement ( )

private

Computes the layout of an embedded layered graph.

◆ fixedLayerDistance() [1/2]

bool ogdf::FastHierarchyLayout::fixedLayerDistance ( ) const

inline

Returns the option fixed layer distance.

Definition at line 106 of file FastHierarchyLayout.h.

◆ fixedLayerDistance() [2/2]

void ogdf::FastHierarchyLayout::fixedLayerDistance ( bool b )

inline

Sets the option fixed layer distance to b.

Definition at line 109 of file FastHierarchyLayout.h.

◆ incrTo()

void ogdf::FastHierarchyLayout::incrTo	(	double &	d,
		double	t
	)

inlineprivate

Definition at line 158 of file FastHierarchyLayout.h.

◆ isFirst()

bool ogdf::FastHierarchyLayout::isFirst ( int actNode ) const

inlineprivate

Definition at line 174 of file FastHierarchyLayout.h.

◆ isLast()

bool ogdf::FastHierarchyLayout::isLast ( int actNode ) const

inlineprivate

Definition at line 178 of file FastHierarchyLayout.h.

◆ layerDistance() [1/2]

double ogdf::FastHierarchyLayout::layerDistance ( ) const

inline

Returns the option layer distance.

Definition at line 100 of file FastHierarchyLayout.h.

◆ layerDistance() [2/2]

void ogdf::FastHierarchyLayout::layerDistance ( double dist )

inline

Sets the option layer distance to dist.

Definition at line 103 of file FastHierarchyLayout.h.

◆ moveLongEdge()

void ogdf::FastHierarchyLayout::moveLongEdge	(	int	actNode,
		int	dir,
		bool *	marked
	)

private

Used for postprocessing the layout.

If the two nonvirtual ndoes of the long edge are both to the left (right) of the virtual nodes, the function moveLongEdge tries to reduce the length of the two outermost segments by moving the virtual nodes simultaneously as far as possible to the left (right). If both non virtual nodes are on different sides of the virtual nodes, moveLongEdge tries to remove one of the edge bends by moving the virtual nodes.

If there exists a conflict with another long edge on the left (right) side of the current long edge, the function moveLongEdge is first applied recursively to this long edge.

Parameters

actNode	a representative node of the long edge
dir	is -1 if it is preferred to move the long edge to the left, 1 if it is preferred to move the long edge to the right, 0 if there is no preference
marked	Array for all nodes. Stores for every node, whether moveLongEdge has already been applied to it.

◆ nodeDistance() [1/2]

double ogdf::FastHierarchyLayout::nodeDistance ( ) const

inline

Returns the option node distance.

Definition at line 94 of file FastHierarchyLayout.h.

◆ nodeDistance() [2/2]

void ogdf::FastHierarchyLayout::nodeDistance ( double dist )

inline

Sets the option node distance to dist.

Definition at line 97 of file FastHierarchyLayout.h.

◆ operator=()

FastHierarchyLayout & ogdf::FastHierarchyLayout::operator= ( const FastHierarchyLayout & )

Assignment operator.

◆ placeNodes()

void ogdf::FastHierarchyLayout::placeNodes	(	int	leftBnd,
		int	rightBnd,
		int	left,
		int	right,
		int	d
	)

private

Places a sequence of nonvirtual nodes.

The function partitions the sequence, applying a divide and conquer strategy using recursive calls on the two subsequences.

Parameters

leftBnd	contains the number of the next virtual sibling to the left of the sequence, if it exists; -1 otherwise. Observe that between leftBnd and actNode there may be other nonvirtual nodes.
rightBnd	contains the number of the next virtual sibling to the right of the sequence, if it exists; -1 otherwise. Observe that between rightBnd and actNode there may be other nonvirtual nodes.
left	the leftmost nonvirtual node of the sequence that has to be placed.
right	the rightmost nonvirtual node of the sequence that has to be placed.
d	the direction of traversal. If 0 we traverse the graph top to bottom. 1 otherwise.

The total length of all edges of the sequence to the previous layer (if d = 0) or next layer (if d = 1) is minimized observing the bounds given by leftBnd and rightBnd.

The position that is computed for every node of the sequence is stored in the global variable x. The position of the neighbours is given by the global variable x.

◆ placeSingleNode()

bool ogdf::FastHierarchyLayout::placeSingleNode	(	int	leftBnd,
		int	rightBnd,
		int	actNode,
		double &	best,
		int	d
	)

private

Places a sequence of nonvirtual nodes containing exactly one node.

Parameters

leftBnd	contains the number of the next virtual sibling to the left of actNode, if it exists; -1 otherwise. Observe that between leftBnd and actNode there may be other nonvirtual nodes.
rightBnd	contains the number of the next virtual sibling to the right of actNode, if it exists; -1 otherwise. Observe that between rightBnd and actNode there may be other nonvirtual nodes.
actNode	an nonvirtual node that has to be placed.
best	the position that is computed for actNode by placeSingleNode.
d	is the direction of traversal. If 0 we traverse the graph top to bottom, 1 otherwise.

The total length of all edges of actnode to the previous layer (if d = 0) or next layer (if d = 1) is minimized observing the bounds given by leftBnd and rightBnd. The optimal position is the median of its neighbours adapted to leftBnd and rightBnd. The position of the neighbours is given by the global variable x.

The funcion returns 0 if actNode does not have neighbours on the previous (next) layer, 1 otherwise.

◆ sameLayer()

bool ogdf::FastHierarchyLayout::sameLayer	(	int	n1,
		int	n2
	)		const

inlineprivate

Definition at line 170 of file FastHierarchyLayout.h.

◆ sortLongEdges()

void ogdf::FastHierarchyLayout::sortLongEdges	(	int	actNode,
		int	dir,
		double *	pos,
		bool &	exD,
		double &	dist,
		int *	block,
		bool *	marked
	)

private

Places the node actNode as far as possible to the left (if dir = 1) or to the right (if dir = -1) within a block.

A proper definition of blocks is given in Techreport zpr99-368, pp 5, where blocks are named classes. If actNode is virtual (and thus belongs to a long edge), the function sortLongEdges places the actNode as far as possible to the left such that the corresponding long edge will be vertical.

Parameters

actNode	the placed node
dir	Stores the direction of placement: 1 for placing long edges to the left and -1 for placing them to the right.
pos	Array for all nodes. Stores the computed position.
marked	Array for all nodes. Stores for every node, whether sortLongEdges has already been applied to it.
block	Array for all nodes. Stores for every node the block it belongs to.
exD	is 1 if there exists a node w on the longEdge of actNode, that has a direct right sibling (if moving to the left (depending on the direction)) on the same layer which belongs to a different block.
dist	If exD is 1, it gives the minimal distance between any w of long edge (see exD) and its direct right (left) sibling if the sibling belongs to ANOTHER block. if exD is 0, dist is not relevant.

◆ straightenEdge()

void ogdf::FastHierarchyLayout::straightenEdge	(	int	actNode,
		bool *	marked
	)

private

Tries to remove a bend at the position of the virtual node by straightening the edge.

The method is applied to long edges with exactly one virtual node.

Parameters

actNode	the virtual representative node of the long edge
marked	array for all nodes. Stores for every node, whether straightenEdge has already been applied to it.

If there exists a conflict with a direct sibling to the left (right) side of the current node, the function straightenEdge is first applied recursively to this node.

Member Data Documentation

◆ adj

List<int>* ogdf::FastHierarchyLayout::adj[2]

private

The list of neighbors in previous / next layer.

for every node : adj[0][node] list of neighbors in previous layer; for every node : adj[1][node] list of neighbors in next layer

Definition at line 131 of file FastHierarchyLayout.h.

◆ breadth

double* ogdf::FastHierarchyLayout::breadth

private

for every node : breadth[node] = width of the node.

Definition at line 143 of file FastHierarchyLayout.h.

◆ first

int* ogdf::FastHierarchyLayout::first

private

Stores for every layer the index of the first node.

Definition at line 117 of file FastHierarchyLayout.h.

◆ height

double* ogdf::FastHierarchyLayout::height

private

for every layer : height[layer] = height of max{height of node on layer}.

Definition at line 144 of file FastHierarchyLayout.h.

◆ k

int ogdf::FastHierarchyLayout::k

private

The number of layers.

Definition at line 115 of file FastHierarchyLayout.h.

◆ layer

int* ogdf::FastHierarchyLayout::layer

private

Stores for every node its layer.

Definition at line 116 of file FastHierarchyLayout.h.

◆ longEdge

List<int>** ogdf::FastHierarchyLayout::longEdge

private

The nodes belonging to a long edge.

for every node : longEdge[node] is a pointer to a list containing all nodes that belong to the same long edge as node.

Definition at line 139 of file FastHierarchyLayout.h.

◆ m

int ogdf::FastHierarchyLayout::m

private

The number edge sections.

Definition at line 114 of file FastHierarchyLayout.h.

◆ m_fixedLayerDist

bool ogdf::FastHierarchyLayout::m_fixedLayerDist

private

0 if distance between layers should be variable, 1 otherwise.

Definition at line 155 of file FastHierarchyLayout.h.

◆ m_minLayerDist

double ogdf::FastHierarchyLayout::m_minLayerDist

private

The minimal distance between layers.

Definition at line 142 of file FastHierarchyLayout.h.

◆ m_minNodeDist

double ogdf::FastHierarchyLayout::m_minNodeDist

private

The minimal node distance on a layer.

Definition at line 141 of file FastHierarchyLayout.h.

◆ mDist

double* ogdf::FastHierarchyLayout::mDist

private

Similar to totalB, used for temporary storage.

Definition at line 153 of file FastHierarchyLayout.h.

◆ n

int ogdf::FastHierarchyLayout::n

private

The number of nodes including virtual nodes.

Definition at line 113 of file FastHierarchyLayout.h.

◆ totalB

double* ogdf::FastHierarchyLayout::totalB

private

for every node : minimal possible distance between the center of a node and first[layer[node]].

Definition at line 151 of file FastHierarchyLayout.h.

◆ virt

bool* ogdf::FastHierarchyLayout::virt

private

for every node : virt[node] = 1 if node is virtual, 0 otherwise.

Definition at line 156 of file FastHierarchyLayout.h.

◆ x

double* ogdf::FastHierarchyLayout::x

private

for every node : x coordinate of node.

Definition at line 146 of file FastHierarchyLayout.h.

◆ y

double* ogdf::FastHierarchyLayout::y

private

for every layer : y coordinate of layer.

Definition at line 145 of file FastHierarchyLayout.h.

The documentation for this class was generated from the following file:

include/ogdf/layered/FastHierarchyLayout.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Optional Parameters

Constructor & Destructor Documentation

◆ FastHierarchyLayout() [1/2]

◆ FastHierarchyLayout() [2/2]

◆ ~FastHierarchyLayout()

Member Function Documentation

◆ decrTo()

◆ doCall()

◆ findPlacement()

◆ fixedLayerDistance() [1/2]

◆ fixedLayerDistance() [2/2]

◆ incrTo()

◆ isFirst()

◆ isLast()

◆ layerDistance() [1/2]

◆ layerDistance() [2/2]

◆ moveLongEdge()

◆ nodeDistance() [1/2]

◆ nodeDistance() [2/2]

◆ operator=()

◆ placeNodes()

◆ placeSingleNode()

◆ sameLayer()

◆ sortLongEdges()

◆ straightenEdge()

Member Data Documentation

◆ adj

◆ breadth

◆ first

◆ height

◆ k

◆ layer

◆ longEdge

◆ m

◆ m_fixedLayerDist

◆ m_minLayerDist

◆ m_minNodeDist

◆ mDist

◆ n

◆ totalB

◆ virt

◆ x

◆ y

Open
Graph Drawing
Framework