Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches

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.
 
FastHierarchyLayoutoperator= (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.
 
doublebreadth
 for every node : breadth[node] = width of the node.
 
intfirst
 Stores for every layer the index of the first node.
 
doubleheight
 for every layer : height[layer] = height of max{height of node on layer}.
 
int k
 The number of layers.
 
intlayer
 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.
 
doublemDist
 Similar to totalB, used for temporary storage.
 
int n
 The number of nodes including virtual nodes.
 
doubletotalB
 for every node : minimal possible distance between the center of a node and first[layer[node]].
 
boolvirt
 for every node : virt[node] = 1 if node is virtual, 0 otherwise.
 
doublex
 for every node : x coordinate of node.
 
doubley
 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

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