OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::FastHierarchyLayout Class Reference

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. More...

FastHierarchyLayout (const FastHierarchyLayout &)
Copy constructor. More...

virtual ~FastHierarchyLayout ()

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

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

double layerDistance () const
Returns the option layer distance. More...

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

double nodeDistance () const
Returns the option node distance. More...

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

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

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

virtual ~HierarchyLayoutModule ()

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

Protected Member Functions

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

Private Member Functions

void decrTo (double &d, double t)

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

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. More...

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

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

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. More...

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

Private Attributes

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

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

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

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

int k
The number of layers. More...

int * layer
Stores for every node its layer. More...

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

int m
The number edge sections. More...

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

double m_minLayerDist
The minimal distance between layers. More...

double m_minNodeDist
The minimal node distance on a layer. More...

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

int n
The number of nodes including virtual nodes. More...

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

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

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

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

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. More...

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. More...

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

OptionTypeDefaultDescription
node distancedouble3.0 the minimal horizontal distance between two nodes on the same layer
layer distancedouble3.0 the minimal vertical distance between two nodes on neighbored layers
fixed layer distanceboolfalse if true, the distance between neighbored layers is fixed, otherwise variable

Definition at line 76 of file FastHierarchyLayout.h.

◆ 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 89 of file FastHierarchyLayout.h.

◆ decrTo()

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

Definition at line 178 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 117 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 122 of file FastHierarchyLayout.h.

◆ incrTo()

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

Definition at line 174 of file FastHierarchyLayout.h.

◆ isFirst()

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

Definition at line 188 of file FastHierarchyLayout.h.

◆ isLast()

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

Definition at line 194 of file FastHierarchyLayout.h.

◆ layerDistance() [1/2]

 double ogdf::FastHierarchyLayout::layerDistance ( ) const
inline

Returns the option layer distance.

Definition at line 107 of file FastHierarchyLayout.h.

◆ layerDistance() [2/2]

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

Sets the option layer distance to dist.

Definition at line 112 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 97 of file FastHierarchyLayout.h.

◆ nodeDistance() [2/2]

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

Sets the option node distance to dist.

Definition at line 102 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 182 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

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 147 of file FastHierarchyLayout.h.

private

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

Definition at line 159 of file FastHierarchyLayout.h.

◆ first

 int* ogdf::FastHierarchyLayout::first
private

Stores for every layer the index of the first node.

Definition at line 133 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 160 of file FastHierarchyLayout.h.

◆ k

 int ogdf::FastHierarchyLayout::k
private

The number of layers.

Definition at line 131 of file FastHierarchyLayout.h.

◆ layer

 int* ogdf::FastHierarchyLayout::layer
private

Stores for every node its layer.

Definition at line 132 of file FastHierarchyLayout.h.

◆ longEdge

 List** 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 155 of file FastHierarchyLayout.h.

◆ m

 int ogdf::FastHierarchyLayout::m
private

The number edge sections.

Definition at line 130 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 171 of file FastHierarchyLayout.h.

◆ m_minLayerDist

 double ogdf::FastHierarchyLayout::m_minLayerDist
private

The minimal distance between layers.

Definition at line 158 of file FastHierarchyLayout.h.

◆ m_minNodeDist

 double ogdf::FastHierarchyLayout::m_minNodeDist
private

The minimal node distance on a layer.

Definition at line 157 of file FastHierarchyLayout.h.

◆ mDist

 double* ogdf::FastHierarchyLayout::mDist
private

Similar to totalB, used for temporary storage.

Definition at line 169 of file FastHierarchyLayout.h.

◆ n

 int ogdf::FastHierarchyLayout::n
private

The number of nodes including virtual nodes.

Definition at line 129 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 167 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 172 of file FastHierarchyLayout.h.

◆ x

 double* ogdf::FastHierarchyLayout::x
private

for every node : x coordinate of node.

Definition at line 162 of file FastHierarchyLayout.h.

◆ y

 double* ogdf::FastHierarchyLayout::y
private

for every layer : y coordinate of layer.

Definition at line 161 of file FastHierarchyLayout.h.

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