Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf. More...

#include <ogdf/layered/FastSimpleHierarchyLayout.h>

+ Inheritance diagram for ogdf::FastSimpleHierarchyLayout:

Public Member Functions

 FastSimpleHierarchyLayout ()
 Creates an instance of fast simple hierarchy layout. More...
 
 FastSimpleHierarchyLayout (const FastSimpleHierarchyLayout &)
 Copy constructor. More...
 
virtual ~FastSimpleHierarchyLayout ()
 
bool balanced () const
 Returns the option balanced. More...
 
void balanced (bool b)
 Sets the option balanced to b. More...
 
bool downward () const
 Returns the option downward. More...
 
void downward (bool d)
 Sets the option downward to d. More...
 
double layerDistance () const
 Returns the option layer distance. More...
 
void layerDistance (double dist)
 Sets the option layer distance to dist. More...
 
bool leftToRight () const
 Returns the option left-to-right. More...
 
void leftToRight (bool b)
 Sets the option left-to-right to b. More...
 
double nodeDistance () const
 Returns the option node distance. More...
 
void nodeDistance (double dist)
 Sets the option node distance to dist. More...
 
FastSimpleHierarchyLayoutoperator= (const FastSimpleHierarchyLayout &)
 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 computeBlockWidths (const GraphCopy &GC, const GraphAttributes &GCA, NodeArray< node > &root, NodeArray< double > &blockWidth)
 Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block. More...
 
void horizontalCompactation (const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< node > &root, const NodeArray< double > &blockWidth, NodeArray< double > &x, const bool leftToRight, bool downward)
 Calculate the coordinates for each node. More...
 
void markType1Conflicts (const HierarchyLevelsBase &levels, bool downward, NodeArray< NodeArray< bool > > &type1Conflicts)
 Preprocessing step to find all type1 conflicts. More...
 
void placeBlock (node v, NodeArray< node > &sink, NodeArray< double > &shift, NodeArray< double > &x, const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< double > &blockWidth, const NodeArray< node > &root, const bool leftToRight)
 Calculate the coordinate for root nodes (placing) More...
 
node pred (const node v, const HierarchyLevelsBase &levels, const bool leftToRight)
 Predecessor of v on the same level,. More...
 
void verticalAlignment (const HierarchyLevelsBase &levels, NodeArray< node > &root, NodeArray< node > &align, const NodeArray< NodeArray< bool > > &type1Conflicts, const bool downward, const bool leftToRight)
 Align each node to a node on the next higher level. More...
 
node virtualTwinNode (const HierarchyLevelsBase &levels, const node v, const HierarchyLevelsBase::TraversingDir dir) const
 The twin of an inner Segment. More...
 

Private Attributes

bool m_balanced
 stores the option balanced. More...
 
bool m_downward
 stores the option downward. More...
 
bool m_leftToRight
 stores the option left-to-right. More...
 
double m_minXSep
 stores the option node distance. More...
 
double m_ySep
 stores the option layer distance. 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 Ulrik Brandes and Boris Köpf.

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.

The Algorithm runs in three phases.

  • Alignment (4x)
  • Horizontal Compactation (4x)
  • Balancing

The Alignment and Horzontal Compactation phase are calculated downward, upward, left-to-right and right-to-left. The four resulting layouts are combined in a balancing step.

The implementation is based on:

Ulrik Brandes, Boris Köpf: Fast and Simple Horizontal Coordinate Assignment. LNCS 2002, Volume 2265/2002, pp. 33-36

Optional Parameters

OptionTypeDefaultDescription
node distanceint150 the minimal horizontal distance between two nodes on the same layer
layer distanceint75 the minimal vertical distance between two nodes on adjacent layers
balancedbooltrue determines whether balancing is used
left-to-rightbooltrue determines whether block alignment is computed by a left-to-right (true) or right-to-left traversal
downwardbooltrue determines whether block alignment is computed by a downward (true) or upward traversal

Definition at line 86 of file FastSimpleHierarchyLayout.h.

Constructor & Destructor Documentation

◆ FastSimpleHierarchyLayout() [1/2]

ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout ( )

Creates an instance of fast simple hierarchy layout.

Sets the options to default values, i.e., use balanced layout with left-to-right node direction on each layer, node distance as given by LayoutStandards, and layer distance as 1.5 times node distance.

◆ FastSimpleHierarchyLayout() [2/2]

ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout ( const FastSimpleHierarchyLayout )

Copy constructor.

◆ ~FastSimpleHierarchyLayout()

virtual ogdf::FastSimpleHierarchyLayout::~FastSimpleHierarchyLayout ( )
inlinevirtual

Definition at line 112 of file FastSimpleHierarchyLayout.h.

Member Function Documentation

◆ balanced() [1/2]

bool ogdf::FastSimpleHierarchyLayout::balanced ( ) const
inline

Returns the option balanced.

Definition at line 160 of file FastSimpleHierarchyLayout.h.

◆ balanced() [2/2]

void ogdf::FastSimpleHierarchyLayout::balanced ( bool  b)
inline

Sets the option balanced to b.

Definition at line 165 of file FastSimpleHierarchyLayout.h.

◆ computeBlockWidths()

void ogdf::FastSimpleHierarchyLayout::computeBlockWidths ( const GraphCopy GC,
const GraphAttributes GCA,
NodeArray< node > &  root,
NodeArray< double > &  blockWidth 
)
private

Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block.

Parameters
GCThe input graph copy
GCAThe input graph copies (gives in particular the widths of nodes)
rootThe root for each node (calculated by this method)
blockWidthIs assigned the width of each block (stored for the root)

◆ doCall()

virtual void ogdf::FastSimpleHierarchyLayout::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.

◆ downward() [1/2]

bool ogdf::FastSimpleHierarchyLayout::downward ( ) const
inline

Returns the option downward.

Definition at line 140 of file FastSimpleHierarchyLayout.h.

◆ downward() [2/2]

void ogdf::FastSimpleHierarchyLayout::downward ( bool  d)
inline

Sets the option downward to d.

Definition at line 145 of file FastSimpleHierarchyLayout.h.

◆ horizontalCompactation()

void ogdf::FastSimpleHierarchyLayout::horizontalCompactation ( const NodeArray< node > &  align,
const HierarchyLevelsBase levels,
const NodeArray< node > &  root,
const NodeArray< double > &  blockWidth,
NodeArray< double > &  x,
const bool  leftToRight,
bool  downward 
)
private

Calculate the coordinates for each node.

Parameters
alignThe alignment to the next level node (align(v)=u <=> u is aligned to v)
levelsThe Hierarchy
rootThe root for each node
blockWidthThe width of each block
xThe x-coordinates for each node (calculated by this method)
leftToRightThe node direction on each level
downwardThe level direction

◆ layerDistance() [1/2]

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

Returns the option layer distance.

Definition at line 130 of file FastSimpleHierarchyLayout.h.

◆ layerDistance() [2/2]

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

Sets the option layer distance to dist.

Definition at line 135 of file FastSimpleHierarchyLayout.h.

◆ leftToRight() [1/2]

bool ogdf::FastSimpleHierarchyLayout::leftToRight ( ) const
inline

Returns the option left-to-right.

Definition at line 150 of file FastSimpleHierarchyLayout.h.

◆ leftToRight() [2/2]

void ogdf::FastSimpleHierarchyLayout::leftToRight ( bool  b)
inline

Sets the option left-to-right to b.

Definition at line 155 of file FastSimpleHierarchyLayout.h.

◆ markType1Conflicts()

void ogdf::FastSimpleHierarchyLayout::markType1Conflicts ( const HierarchyLevelsBase levels,
bool  downward,
NodeArray< NodeArray< bool > > &  type1Conflicts 
)
private

Preprocessing step to find all type1 conflicts.

A type1 conflict is a crossing of a inner segment with a non-inner segment.

This is for preferring straight inner segments.

Parameters
levelsThe Hierarchy
downwardThe level direction
type1Conflictsis assigned the conflicts, (type1Conflicts[v])[u]=true means (u,v) is marked, u is the upper node

◆ nodeDistance() [1/2]

double ogdf::FastSimpleHierarchyLayout::nodeDistance ( ) const
inline

Returns the option node distance.

Definition at line 120 of file FastSimpleHierarchyLayout.h.

◆ nodeDistance() [2/2]

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

Sets the option node distance to dist.

Definition at line 125 of file FastSimpleHierarchyLayout.h.

◆ operator=()

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

Assignment operator.

◆ placeBlock()

void ogdf::FastSimpleHierarchyLayout::placeBlock ( node  v,
NodeArray< node > &  sink,
NodeArray< double > &  shift,
NodeArray< double > &  x,
const NodeArray< node > &  align,
const HierarchyLevelsBase levels,
const NodeArray< double > &  blockWidth,
const NodeArray< node > &  root,
const bool  leftToRight 
)
private

Calculate the coordinate for root nodes (placing)

Parameters
vThe root node to place
sinkThe Sink for each node. A sink identifies each block class (calculated by this method)
shiftThe shift for each class (calculated by this method)
xThe class relative x-coordinate for each node (calculated by this method)
alignThe alignment to the next level node (align(v)=u <=> u is aligned to v)
levelsThe Hierarchy
blockWidthThe width of each block
rootThe root for each node
leftToRightThe node direction on each level

◆ pred()

node ogdf::FastSimpleHierarchyLayout::pred ( const node  v,
const HierarchyLevelsBase levels,
const bool  leftToRight 
)
private

Predecessor of v on the same level,.

Parameters
vThe node for which the predecessor should be calculated.
levelsThe Hierarchy
leftToRightIf true the left predecessor is choosen. Otherwise the right predecessor.
Returns
Predescessor on the same level. nullptr if there is no predecessor.

◆ verticalAlignment()

void ogdf::FastSimpleHierarchyLayout::verticalAlignment ( const HierarchyLevelsBase levels,
NodeArray< node > &  root,
NodeArray< node > &  align,
const NodeArray< NodeArray< bool > > &  type1Conflicts,
const bool  downward,
const bool  leftToRight 
)
private

Align each node to a node on the next higher level.

The result is a blockgraph where each node is in a block whith a nother node when they have the same root.

Parameters
levelsThe Hierarchy
rootThe root for each node (calculated by this method)
alignThe alignment to the next level node (align(v)=u <=> u is aligned to v) (calculated by this method)
type1ConflictsType1 conflicts to prefer straight inner segments
downwardThe level direction
leftToRightThe node direction on each level

◆ virtualTwinNode()

node ogdf::FastSimpleHierarchyLayout::virtualTwinNode ( const HierarchyLevelsBase levels,
const node  v,
const HierarchyLevelsBase::TraversingDir  dir 
) const
private

The twin of an inner Segment.

Returns
Parent node which is connected by an inner segment. nullptr if there is no parent segment or if the segment is not an inner segment.

Member Data Documentation

◆ m_balanced

bool ogdf::FastSimpleHierarchyLayout::m_balanced
private

stores the option balanced.

Definition at line 91 of file FastSimpleHierarchyLayout.h.

◆ m_downward

bool ogdf::FastSimpleHierarchyLayout::m_downward
private

stores the option downward.

Definition at line 92 of file FastSimpleHierarchyLayout.h.

◆ m_leftToRight

bool ogdf::FastSimpleHierarchyLayout::m_leftToRight
private

stores the option left-to-right.

Definition at line 93 of file FastSimpleHierarchyLayout.h.

◆ m_minXSep

double ogdf::FastSimpleHierarchyLayout::m_minXSep
private

stores the option node distance.

Definition at line 89 of file FastSimpleHierarchyLayout.h.

◆ m_ySep

double ogdf::FastSimpleHierarchyLayout::m_ySep
private

stores the option layer distance.

Definition at line 90 of file FastSimpleHierarchyLayout.h.


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