Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SugiyamaLayout Class Reference

Sugiyama's layout algorithm. More...

#include <ogdf/layered/SugiyamaLayout.h>

+ Inheritance diagram for ogdf::SugiyamaLayout:

Public Member Functions

 SugiyamaLayout ()
 Creates an instance of SugiyamaLayout and sets options to default values. More...
 
 ~SugiyamaLayout ()
 
Algorithm call
virtual void call (GraphAttributes &GA) override
 Calls the layout algorithm for graph GA. More...
 
void call (ClusterGraphAttributes &CGA)
 Calls the layout algorithm for clustered graph CGA. More...
 
void call (GraphAttributes &GA, NodeArray< int > &rank)
 Calls the layout algorithm for graph GA with a given level assignment. More...
 
void callUML (GraphAttributes &GA)
 
Optional parameters
int fails () const
 Returns the current setting of option fails. More...
 
void fails (int nFails)
 Sets the option fails to nFails. More...
 
int runs () const
 Returns the current setting of option runs. More...
 
void runs (int nRuns)
 Sets the option runs to nRuns. More...
 
bool transpose () const
 Returns the current setting of option transpose. More...
 
void transpose (bool bTranspose)
 Sets the option transpose to bTranspose. More...
 
bool arrangeCCs () const
 Returns the current setting of option arrangeCCs. More...
 
void arrangeCCs (bool bArrange)
 Sets the options arrangeCCs to bArrange. More...
 
double minDistCC () const
 Returns the current setting of option minDistCC (distance between components). More...
 
void minDistCC (double x)
 Sets the option minDistCC to x. More...
 
double pageRatio () const
 Returns the current setting of option pageRation. More...
 
void pageRatio (double x)
 Sets the option pageRatio to x. More...
 
bool alignBaseClasses () const
 Returns the current setting of option alignBaseClasses. More...
 
void alignBaseClasses (bool b)
 Sets the option alignBaseClasses to b. More...
 
bool alignSiblings () const
 Returns the current setting of option alignSiblings. More...
 
void alignSiblings (bool b)
 Sets the option alignSiblings to b. More...
 
void setSubgraphs (EdgeArray< uint32_t > *esg)
 Sets the subgraphs for simultaneous drawing. More...
 
bool useSubgraphs () const
 Returns true iff subgraphs for simultaneous drawing are set. More...
 
bool permuteFirst () const
 
void permuteFirst (bool b)
 
unsigned int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (unsigned int n)
 Sets the maximal number of used threads to n. More...
 
Module options
void setRanking (RankingModule *pRanking)
 Sets the module option for the node ranking (layer assignment). More...
 
void setCrossMin (LayeredCrossMinModule *pCrossMin)
 Sets the module option for the two-layer crossing minimization. More...
 
void setLayout (HierarchyLayoutModule *pLayout)
 Sets the module option for the computation of the final layout. More...
 
void setClusterLayout (HierarchyClusterLayoutModule *pLayout)
 Sets the module option for the computation of the final layout for clustered graphs. More...
 
void setPacker (CCLayoutPackModule *pPacker)
 Sets the module option for the arrangement of connected components. More...
 
- Public Member Functions inherited from ogdf::LayoutModule
 LayoutModule ()
 Initializes a layout module. More...
 
virtual ~LayoutModule ()
 
void operator() (GraphAttributes &GA)
 Computes a layout of graph GA. More...
 

Protected Attributes

bool m_alignBaseClasses
 Option for aligning base classes. More...
 
bool m_alignSiblings
 Option for aligning siblings in inheritance trees. More...
 
bool m_arrangeCCs
 Option for laying out components separately. More...
 
std::unique_ptr< HierarchyClusterLayoutModulem_clusterLayout
 the hierarchy cluster layout module (final coordinate assignment for clustered graphs) More...
 
std::unique_ptr< LayeredCrossMinModulem_crossMin
 the module for two-layer crossing minimization More...
 
std::unique_ptr< TwoLayerCrossMinSimDrawm_crossMinSimDraw
 
int m_fails
 Option for maximal number of fails. More...
 
std::unique_ptr< HierarchyLayoutModulem_layout
 the hierarchy layout module (final coordinate assignment) More...
 
Array< bool > m_levelChanged
 
unsigned int m_maxThreads
 The maximal number of used threads. More...
 
double m_minDistCC
 Option for distance between connected components. More...
 
int m_nCrossings
 Number of crossings in computed layout. More...
 
RCCrossings m_nCrossingsCluster
 
std::unique_ptr< CCLayoutPackModulem_packer
 The module for arranging connected components. More...
 
double m_pageRatio
 Option for desired page ratio. More...
 
bool m_permuteFirst
 
std::unique_ptr< RankingModulem_ranking
 the ranking module (level assignment) More...
 
int m_runs
 Option for number of runs. More...
 
EdgeArray< uint32_t > * m_subgraphs
 Defines the subgraphs for simultaneous drawing. More...
 
bool m_transpose
 Option for switching on transposal heuristic. More...
 

Information after call

The following information can be accessed after calling the algorithm.

int m_numCC
 
NodeArray< int > m_compGC
 
int m_numLevels
 
int m_maxLevelSize
 
double m_timeReduceCrossings
 
int numberOfCrossings () const
 Returns the number of crossings in the computed layout (usual graph). More...
 
RCCrossings numberOfCrossingsCluster () const
 Returns the number of crossings in the computed layout (cluster graph). More...
 
int numberOfLevels ()
 Return the number of layers/levels}. More...
 
int maxLevelSize ()
 Return the max. number of elements on a layer. More...
 
double timeReduceCrossings ()
 
const EdgeArray< uint32_t > * subgraphs () const
 
int numCC () const
 
const NodeArray< int > & compGC () const
 
void reduceCrossings (ExtendedNestingGraph &H)
 
const HierarchyLevelsBasereduceCrossings (Hierarchy &H)
 
void doCall (GraphAttributes &AG, bool umlCall)
 
void doCall (GraphAttributes &AG, bool umlCall, NodeArray< int > &rank)
 
RCCrossings traverseTopDown (ExtendedNestingGraph &H)
 
RCCrossings traverseBottomUp (ExtendedNestingGraph &H)
 

Detailed Description

Sugiyama's layout algorithm.

The class SugiyamaLayout represents a customizable implementation of Sugiyama's layout algorithm. The class provides three different algorithm calls:

  • Calling the algorithm for a usual graph; this is the well-known Sugiyama algorithm.
  • Calling the algorithm for a cluster graph.
  • Calling the algorithm for mixed-upward graphs (e.g., UML class diagrams), where only some edges are directed and shall point in the same direction.

If the Sugiyama algorithm shall be used for simultaneous drawing, you need to define the different subgraphs by setting the subgraphs option.

The implementation used in SugiyamaLayout is based on the following publications:

Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo: A technique for drawing directed graphs. IEEE Trans. Software Eng. 19(3), pp. 214-230, 1993.

Georg Sander: Layout of compound directed graphs. Technical Report, Universität des Saarlandes, 1996.

Optional parameters

The following options affect the crossing minimization step of the algorithm:

OptionTypeDefaultDescription
runsint15 Determines, how many times the crossing minimization is repeated. Each repetition (except for the first) starts with randomly permuted nodes on each layer. Deterministic behaviour can be achieved by setting runs to 1.
transposebooltrue Determines whether the transpose step is performed after each 2-layer crossing minimization; this step tries to reduce the number of crossings by switching neighbored nodes on a layer.
failsint4 The number of times that the number of crossings may not decrease after a complete top-down bottom-up traversal, before a run is terminated.
arrangeCCsbooltrue If set to true connected components are laid out separately and the resulting layouts are arranged afterwards using the packer module.
minDistCCdouble20.0 Specifies the spacing between connected components of the graph. Other spacing parameters have to be set in the used hierarchy layout module.
alignBaseClassesboolfalse Determines if base classes of inheritance hierarchies shall be aligned (only callUML()).
alignSiblingsboolfalse Determines if siblings in an inheritance tree shall be aligned (only callUML()).

The crossing minimization step of the algorithm is affected by the options runs, transpose, and fails. The options alignBaseClasses and alignSiblings are only relevant for laying out mixed-upward graphs, where directed edges are interpreted as generlizations and undirected egdes as associations in a UML class diagram.

Module options

The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:

OptionTypeDefaultDescription
rankingRankingModuleLongestPathRanking The ranking module determines the layering of the graph.
crossMinLayerByLayerSweepBarycenterHeuristic The crossMin module performs two-layer crossing minimization and is applied during the top-down bottom-up traversals.
crossMinSimDrawTwoLayerCrossMinSimDrawSplitHeuristic The crossMin module used with simultaneous drawing.
layoutHierarchyLayoutModuleFastHierarchyLayout The hierarchy layout module that computes the final layout (call for graph).
clusterLayoutHierarchyClusterLayoutModuleOptimalHierarchyClusterLayout The hierarchy layout module that computes the final layout (call for cluster graph).
packerCCLayoutPackModuleTileToRowsCCPacker The packer module used for arranging connected components.

Definition at line 160 of file SugiyamaLayout.h.

Constructor & Destructor Documentation

◆ SugiyamaLayout()

ogdf::SugiyamaLayout::SugiyamaLayout ( )

Creates an instance of SugiyamaLayout and sets options to default values.

◆ ~SugiyamaLayout()

ogdf::SugiyamaLayout::~SugiyamaLayout ( )
inline

Definition at line 207 of file SugiyamaLayout.h.

Member Function Documentation

◆ alignBaseClasses() [1/2]

bool ogdf::SugiyamaLayout::alignBaseClasses ( ) const
inline

Returns the current setting of option alignBaseClasses.

This option defines whether base classes in inheritance hierarchies shall be aligned.

Definition at line 323 of file SugiyamaLayout.h.

◆ alignBaseClasses() [2/2]

void ogdf::SugiyamaLayout::alignBaseClasses ( bool  b)
inline

Sets the option alignBaseClasses to b.

Definition at line 326 of file SugiyamaLayout.h.

◆ alignSiblings() [1/2]

bool ogdf::SugiyamaLayout::alignSiblings ( ) const
inline

Returns the current setting of option alignSiblings.

This option defines whether siblings in inheritance trees shall be aligned.

Definition at line 334 of file SugiyamaLayout.h.

◆ alignSiblings() [2/2]

void ogdf::SugiyamaLayout::alignSiblings ( bool  b)
inline

Sets the option alignSiblings to b.

Definition at line 337 of file SugiyamaLayout.h.

◆ arrangeCCs() [1/2]

bool ogdf::SugiyamaLayout::arrangeCCs ( ) const
inline

Returns the current setting of option arrangeCCs.

If this option is set to true, connected components are laid out separately and arranged using a packing module.

Definition at line 289 of file SugiyamaLayout.h.

◆ arrangeCCs() [2/2]

void ogdf::SugiyamaLayout::arrangeCCs ( bool  bArrange)
inline

Sets the options arrangeCCs to bArrange.

Definition at line 292 of file SugiyamaLayout.h.

◆ call() [1/3]

void ogdf::SugiyamaLayout::call ( ClusterGraphAttributes CGA)

Calls the layout algorithm for clustered graph CGA.

Returns the computed layout in CGA.

◆ call() [2/3]

virtual void ogdf::SugiyamaLayout::call ( GraphAttributes GA)
overridevirtual

Calls the layout algorithm for graph GA.

Returns the computed layout in GA.

Implements ogdf::LayoutModule.

◆ call() [3/3]

void ogdf::SugiyamaLayout::call ( GraphAttributes GA,
NodeArray< int > &  rank 
)

Calls the layout algorithm for graph GA with a given level assignment.

Returns the computed layout in GA.

Parameters
GAis the input graph (with node size information) and is assigned the computed layout.
rankdefines the level of each node.

◆ callUML()

void ogdf::SugiyamaLayout::callUML ( GraphAttributes GA)

◆ compGC()

const NodeArray<int>& ogdf::SugiyamaLayout::compGC ( ) const
inline

Definition at line 436 of file SugiyamaLayout.h.

◆ doCall() [1/2]

void ogdf::SugiyamaLayout::doCall ( GraphAttributes AG,
bool  umlCall 
)
private

◆ doCall() [2/2]

void ogdf::SugiyamaLayout::doCall ( GraphAttributes AG,
bool  umlCall,
NodeArray< int > &  rank 
)
private

◆ fails() [1/2]

int ogdf::SugiyamaLayout::fails ( ) const
inline

Returns the current setting of option fails.

This option determines, how many times the total number of crossings after a complete top down or bottom up traversal may not decrease before one repetition is stopped.

Definition at line 253 of file SugiyamaLayout.h.

◆ fails() [2/2]

void ogdf::SugiyamaLayout::fails ( int  nFails)
inline

Sets the option fails to nFails.

Definition at line 256 of file SugiyamaLayout.h.

◆ maxLevelSize()

int ogdf::SugiyamaLayout::maxLevelSize ( )
inline

Return the max. number of elements on a layer.

Definition at line 427 of file SugiyamaLayout.h.

◆ maxThreads() [1/2]

unsigned int ogdf::SugiyamaLayout::maxThreads ( ) const
inline

Returns the maximal number of used threads.

Definition at line 350 of file SugiyamaLayout.h.

◆ maxThreads() [2/2]

void ogdf::SugiyamaLayout::maxThreads ( unsigned int  n)
inline

Sets the maximal number of used threads to n.

Definition at line 353 of file SugiyamaLayout.h.

◆ minDistCC() [1/2]

double ogdf::SugiyamaLayout::minDistCC ( ) const
inline

Returns the current setting of option minDistCC (distance between components).

This options defines the minimum distance between connected components of the graph.

Definition at line 300 of file SugiyamaLayout.h.

◆ minDistCC() [2/2]

void ogdf::SugiyamaLayout::minDistCC ( double  x)
inline

Sets the option minDistCC to x.

Definition at line 303 of file SugiyamaLayout.h.

◆ numberOfCrossings()

int ogdf::SugiyamaLayout::numberOfCrossings ( ) const
inline

Returns the number of crossings in the computed layout (usual graph).

Definition at line 418 of file SugiyamaLayout.h.

◆ numberOfCrossingsCluster()

RCCrossings ogdf::SugiyamaLayout::numberOfCrossingsCluster ( ) const
inline

Returns the number of crossings in the computed layout (cluster graph).

Definition at line 421 of file SugiyamaLayout.h.

◆ numberOfLevels()

int ogdf::SugiyamaLayout::numberOfLevels ( )
inline

Return the number of layers/levels}.

Definition at line 424 of file SugiyamaLayout.h.

◆ numCC()

int ogdf::SugiyamaLayout::numCC ( ) const
inline

Definition at line 434 of file SugiyamaLayout.h.

◆ pageRatio() [1/2]

double ogdf::SugiyamaLayout::pageRatio ( ) const
inline

Returns the current setting of option pageRation.

This option defines the desired page ratio of the layout and is used by the packing algorithms used for laying out connected components.

Definition at line 312 of file SugiyamaLayout.h.

◆ pageRatio() [2/2]

void ogdf::SugiyamaLayout::pageRatio ( double  x)
inline

Sets the option pageRatio to x.

Definition at line 315 of file SugiyamaLayout.h.

◆ permuteFirst() [1/2]

bool ogdf::SugiyamaLayout::permuteFirst ( ) const
inline

Definition at line 345 of file SugiyamaLayout.h.

◆ permuteFirst() [2/2]

void ogdf::SugiyamaLayout::permuteFirst ( bool  b)
inline

Definition at line 347 of file SugiyamaLayout.h.

◆ reduceCrossings() [1/2]

void ogdf::SugiyamaLayout::reduceCrossings ( ExtendedNestingGraph H)
protected

◆ reduceCrossings() [2/2]

const HierarchyLevelsBase* ogdf::SugiyamaLayout::reduceCrossings ( Hierarchy H)
protected

◆ runs() [1/2]

int ogdf::SugiyamaLayout::runs ( ) const
inline

Returns the current setting of option runs.

This option determines, how many times the crossing minimization is repeated. Each repetition (except for the first) starts with randomly permuted nodes on each layer. Deterministic behaviour can be achieved by setting runs to 1.

Definition at line 266 of file SugiyamaLayout.h.

◆ runs() [2/2]

void ogdf::SugiyamaLayout::runs ( int  nRuns)
inline

Sets the option runs to nRuns.

Definition at line 269 of file SugiyamaLayout.h.

◆ setClusterLayout()

void ogdf::SugiyamaLayout::setClusterLayout ( HierarchyClusterLayoutModule pLayout)
inline

Sets the module option for the computation of the final layout for clustered graphs.

This module receives as input the computed layer assignment and and order of nodes on each layer, and computes the final coordinates of nodes and bend points.

Definition at line 400 of file SugiyamaLayout.h.

◆ setCrossMin()

void ogdf::SugiyamaLayout::setCrossMin ( LayeredCrossMinModule pCrossMin)
inline

Sets the module option for the two-layer crossing minimization.

This module is called within the top-down and bottom-up traversal of the Sugiyama crossing minimization procedure.

Definition at line 382 of file SugiyamaLayout.h.

◆ setLayout()

void ogdf::SugiyamaLayout::setLayout ( HierarchyLayoutModule pLayout)
inline

Sets the module option for the computation of the final layout.

This module receives as input the computed layer assignment and and order of nodes on each layer, and computes the final coordinates of nodes and bend points.

Definition at line 391 of file SugiyamaLayout.h.

◆ setPacker()

void ogdf::SugiyamaLayout::setPacker ( CCLayoutPackModule pPacker)
inline

Sets the module option for the arrangement of connected components.

If arrangeCCs is set to true, the Sugiyama layout algorithm draws each connected component of the input graph seperately, and then arranges the resulting drawings using this packing module.

Definition at line 409 of file SugiyamaLayout.h.

◆ setRanking()

void ogdf::SugiyamaLayout::setRanking ( RankingModule pRanking)
inline

Sets the module option for the node ranking (layer assignment).

The layer assignment is the first step of the Sugiyama algorithm and distributes the nodes onto layers. The layer assignment usually respects edge directions; if the graph is not acyclic, the ranking module computes an acyclic subgraph. The ranking module specifies which method is used and usually provides a module option for the acyclic subgraph.

Definition at line 374 of file SugiyamaLayout.h.

◆ setSubgraphs()

void ogdf::SugiyamaLayout::setSubgraphs ( EdgeArray< uint32_t > *  esg)
inline

Sets the subgraphs for simultaneous drawing.

Definition at line 340 of file SugiyamaLayout.h.

◆ subgraphs()

const EdgeArray<uint32_t>* ogdf::SugiyamaLayout::subgraphs ( ) const
inline

Definition at line 432 of file SugiyamaLayout.h.

◆ timeReduceCrossings()

double ogdf::SugiyamaLayout::timeReduceCrossings ( )
inline

Definition at line 429 of file SugiyamaLayout.h.

◆ transpose() [1/2]

bool ogdf::SugiyamaLayout::transpose ( ) const
inline

Returns the current setting of option transpose.

If this option is set to true an additional fine tuning step is performed after each traversal, which tries to reduce the total number of crossings by switching adjacent vertices on the same layer.

Definition at line 278 of file SugiyamaLayout.h.

◆ transpose() [2/2]

void ogdf::SugiyamaLayout::transpose ( bool  bTranspose)
inline

Sets the option transpose to bTranspose.

Definition at line 281 of file SugiyamaLayout.h.

◆ traverseBottomUp()

RCCrossings ogdf::SugiyamaLayout::traverseBottomUp ( ExtendedNestingGraph H)
private

◆ traverseTopDown()

RCCrossings ogdf::SugiyamaLayout::traverseTopDown ( ExtendedNestingGraph H)
private

◆ useSubgraphs()

bool ogdf::SugiyamaLayout::useSubgraphs ( ) const
inline

Returns true iff subgraphs for simultaneous drawing are set.

Definition at line 343 of file SugiyamaLayout.h.

Member Data Documentation

◆ m_alignBaseClasses

bool ogdf::SugiyamaLayout::m_alignBaseClasses
protected

Option for aligning base classes.

Definition at line 197 of file SugiyamaLayout.h.

◆ m_alignSiblings

bool ogdf::SugiyamaLayout::m_alignSiblings
protected

Option for aligning siblings in inheritance trees.

Definition at line 198 of file SugiyamaLayout.h.

◆ m_arrangeCCs

bool ogdf::SugiyamaLayout::m_arrangeCCs
protected

Option for laying out components separately.

Definition at line 187 of file SugiyamaLayout.h.

◆ m_clusterLayout

std::unique_ptr<HierarchyClusterLayoutModule> ogdf::SugiyamaLayout::m_clusterLayout
protected

the hierarchy cluster layout module (final coordinate assignment for clustered graphs)

Definition at line 179 of file SugiyamaLayout.h.

◆ m_compGC

NodeArray<int> ogdf::SugiyamaLayout::m_compGC
private

Definition at line 448 of file SugiyamaLayout.h.

◆ m_crossMin

std::unique_ptr<LayeredCrossMinModule> ogdf::SugiyamaLayout::m_crossMin
protected

the module for two-layer crossing minimization

Definition at line 171 of file SugiyamaLayout.h.

◆ m_crossMinSimDraw

std::unique_ptr<TwoLayerCrossMinSimDraw> ogdf::SugiyamaLayout::m_crossMinSimDraw
protected

Definition at line 173 of file SugiyamaLayout.h.

◆ m_fails

int ogdf::SugiyamaLayout::m_fails
protected

Option for maximal number of fails.

Definition at line 184 of file SugiyamaLayout.h.

◆ m_layout

std::unique_ptr<HierarchyLayoutModule> ogdf::SugiyamaLayout::m_layout
protected

the hierarchy layout module (final coordinate assignment)

Definition at line 176 of file SugiyamaLayout.h.

◆ m_levelChanged

Array<bool> ogdf::SugiyamaLayout::m_levelChanged
protected

Definition at line 195 of file SugiyamaLayout.h.

◆ m_maxLevelSize

int ogdf::SugiyamaLayout::m_maxLevelSize
private

Definition at line 464 of file SugiyamaLayout.h.

◆ m_maxThreads

unsigned int ogdf::SugiyamaLayout::m_maxThreads
protected

The maximal number of used threads.

Definition at line 191 of file SugiyamaLayout.h.

◆ m_minDistCC

double ogdf::SugiyamaLayout::m_minDistCC
protected

Option for distance between connected components.

Definition at line 188 of file SugiyamaLayout.h.

◆ m_nCrossings

int ogdf::SugiyamaLayout::m_nCrossings
protected

Number of crossings in computed layout.

Definition at line 193 of file SugiyamaLayout.h.

◆ m_nCrossingsCluster

RCCrossings ogdf::SugiyamaLayout::m_nCrossingsCluster
protected

Definition at line 194 of file SugiyamaLayout.h.

◆ m_numCC

int ogdf::SugiyamaLayout::m_numCC
private

Definition at line 447 of file SugiyamaLayout.h.

◆ m_numLevels

int ogdf::SugiyamaLayout::m_numLevels
private

Definition at line 463 of file SugiyamaLayout.h.

◆ m_packer

std::unique_ptr<CCLayoutPackModule> ogdf::SugiyamaLayout::m_packer
protected

The module for arranging connected components.

Definition at line 182 of file SugiyamaLayout.h.

◆ m_pageRatio

double ogdf::SugiyamaLayout::m_pageRatio
protected

Option for desired page ratio.

Definition at line 189 of file SugiyamaLayout.h.

◆ m_permuteFirst

bool ogdf::SugiyamaLayout::m_permuteFirst
protected

Definition at line 190 of file SugiyamaLayout.h.

◆ m_ranking

std::unique_ptr<RankingModule> ogdf::SugiyamaLayout::m_ranking
protected

the ranking module (level assignment)

Definition at line 168 of file SugiyamaLayout.h.

◆ m_runs

int ogdf::SugiyamaLayout::m_runs
protected

Option for number of runs.

Definition at line 185 of file SugiyamaLayout.h.

◆ m_subgraphs

EdgeArray<uint32_t>* ogdf::SugiyamaLayout::m_subgraphs
protected

Defines the subgraphs for simultaneous drawing.

Definition at line 200 of file SugiyamaLayout.h.

◆ m_timeReduceCrossings

double ogdf::SugiyamaLayout::m_timeReduceCrossings
private

Definition at line 465 of file SugiyamaLayout.h.

◆ m_transpose

bool ogdf::SugiyamaLayout::m_transpose
protected

Option for switching on transposal heuristic.

Definition at line 186 of file SugiyamaLayout.h.


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