Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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...
 
double * breadth
 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...
 

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

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

Member Function Documentation

◆ 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
levelsis the input hierarchy.
AGChas 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
actNodea representative node of the long edge
diris -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
markedArray 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
leftBndcontains 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.
rightBndcontains 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.
leftthe leftmost nonvirtual node of the sequence that has to be placed.
rightthe rightmost nonvirtual node of the sequence that has to be placed.
dthe 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
leftBndcontains 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.
rightBndcontains 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.
actNodean nonvirtual node that has to be placed.
bestthe position that is computed for actNode by placeSingleNode.
dis 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
actNodethe placed node
dirStores the direction of placement: 1 for placing long edges to the left and -1 for placing them to the right.
posArray for all nodes. Stores the computed position.
markedArray for all nodes. Stores for every node, whether sortLongEdges has already been applied to it.
blockArray for all nodes. Stores for every node the block it belongs to.
exDis 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.
distIf 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
actNodethe virtual representative node of the long edge
markedarray 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 147 of file FastHierarchyLayout.h.

◆ breadth

double* ogdf::FastHierarchyLayout::breadth
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<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 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: