Open
Graph Drawing
Framework

 v.2015.05
 

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
void call (GraphAttributes &GA)
 Calls the layout algorithm for graph GA. More...
 
void call (GraphAttributes &GA, GraphConstraints &GC)
 Computes a layout of graph GA wrt the constraints in GC (if applicable). 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 AG 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 > *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)
 
int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (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...
 
ModuleOption< HierarchyClusterLayoutModulem_clusterLayout
 the hierarchy cluster layout module (final coordinate assignment for clustered graphs) More...
 
ModuleOption< LayeredCrossMinModulem_crossMin
 the module for two-layer crossing minimization More...
 
ModuleOption< TwoLayerCrossMinSimDrawm_crossMinSimDraw
 
int m_fails
 Option for maximal number of fails. More...
 
ModuleOption< HierarchyLayoutModulem_layout
 the hierarchy layout module (final coordinate assignment) More...
 
Array< bool > m_levelChanged
 
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
 
ModuleOption< CCLayoutPackModulem_packer
 The module for arranging connected components. More...
 
double m_pageRatio
 Option for desired page ratio. More...
 
bool m_permuteFirst
 
ModuleOption< RankingModulem_ranking
 the ranking module (level assignment) More...
 
int m_runs
 Option for number of runs. More...
 
EdgeArray< __uint32 > * 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 > * 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 178 of file SugiyamaLayout.h.

Constructor & Destructor Documentation

ogdf::SugiyamaLayout::SugiyamaLayout ( )

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

ogdf::SugiyamaLayout::~SugiyamaLayout ( )
inline

Definition at line 226 of file SugiyamaLayout.h.

Member Function Documentation

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 346 of file SugiyamaLayout.h.

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

Sets the option alignBaseClasses to b.

Definition at line 349 of file SugiyamaLayout.h.

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 357 of file SugiyamaLayout.h.

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

Sets the option alignSiblings to b.

Definition at line 360 of file SugiyamaLayout.h.

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 312 of file SugiyamaLayout.h.

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

Sets the options arrangeCCs to bArrange.

Definition at line 315 of file SugiyamaLayout.h.

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

Calls the layout algorithm for graph GA.

Returns the computed layout in GA.

Implements ogdf::LayoutModule.

void ogdf::SugiyamaLayout::call ( GraphAttributes GA,
GraphConstraints GC 
)
inlinevirtual

Computes a layout of graph GA wrt the constraints in GC (if applicable).

Reimplemented from ogdf::LayoutModule.

Definition at line 241 of file SugiyamaLayout.h.

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

Calls the layout algorithm for clustered graph CGA.

Returns the computed layout in CGA.

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

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

Returns the computed layout in AG.

Parameters
GAis the input graph (with node size information) and is assigned the computed layout.
rankdefines the level of each node.
void ogdf::SugiyamaLayout::callUML ( GraphAttributes GA)
const NodeArray<int>& ogdf::SugiyamaLayout::compGC ( ) const
inline

Definition at line 467 of file SugiyamaLayout.h.

void ogdf::SugiyamaLayout::doCall ( GraphAttributes AG,
bool  umlCall 
)
private
void ogdf::SugiyamaLayout::doCall ( GraphAttributes AG,
bool  umlCall,
NodeArray< int > &  rank 
)
private
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 276 of file SugiyamaLayout.h.

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

Sets the option fails to nFails.

Definition at line 279 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::maxLevelSize ( )
inline

Return the max. number of elements on a layer.

Definition at line 460 of file SugiyamaLayout.h.

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

Returns the maximal number of used threads.

Definition at line 372 of file SugiyamaLayout.h.

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

Sets the maximal number of used threads to n.

Definition at line 375 of file SugiyamaLayout.h.

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 323 of file SugiyamaLayout.h.

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

Sets the option minDistCC to x.

Definition at line 326 of file SugiyamaLayout.h.

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

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

Definition at line 451 of file SugiyamaLayout.h.

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

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

Definition at line 454 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::numberOfLevels ( )
inline

Return the number of layers/levels}.

Definition at line 457 of file SugiyamaLayout.h.

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

Definition at line 466 of file SugiyamaLayout.h.

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 335 of file SugiyamaLayout.h.

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

Sets the option pageRatio to x.

Definition at line 338 of file SugiyamaLayout.h.

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

Definition at line 368 of file SugiyamaLayout.h.

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

Definition at line 369 of file SugiyamaLayout.h.

void ogdf::SugiyamaLayout::reduceCrossings ( ExtendedNestingGraph H)
protected
const HierarchyLevelsBase* ogdf::SugiyamaLayout::reduceCrossings ( Hierarchy H)
protected
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 289 of file SugiyamaLayout.h.

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

Sets the option runs to nRuns.

Definition at line 292 of file SugiyamaLayout.h.

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 429 of file SugiyamaLayout.h.

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 407 of file SugiyamaLayout.h.

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 418 of file SugiyamaLayout.h.

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 440 of file SugiyamaLayout.h.

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 397 of file SugiyamaLayout.h.

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

Sets the subgraphs for simultaneous drawing.

Definition at line 363 of file SugiyamaLayout.h.

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

Definition at line 465 of file SugiyamaLayout.h.

double ogdf::SugiyamaLayout::timeReduceCrossings ( )
inline

Definition at line 462 of file SugiyamaLayout.h.

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 301 of file SugiyamaLayout.h.

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

Sets the option transpose to bTranspose.

Definition at line 304 of file SugiyamaLayout.h.

RCCrossings ogdf::SugiyamaLayout::traverseBottomUp ( ExtendedNestingGraph H)
private
RCCrossings ogdf::SugiyamaLayout::traverseTopDown ( ExtendedNestingGraph H)
private
bool ogdf::SugiyamaLayout::useSubgraphs ( ) const
inline

Returns true iff subgraphs for simultaneous drawing are set.

Definition at line 366 of file SugiyamaLayout.h.

Member Data Documentation

bool ogdf::SugiyamaLayout::m_alignBaseClasses
protected

Option for aligning base classes.

Definition at line 215 of file SugiyamaLayout.h.

bool ogdf::SugiyamaLayout::m_alignSiblings
protected

Option for aligning siblings in inheritance trees.

Definition at line 216 of file SugiyamaLayout.h.

bool ogdf::SugiyamaLayout::m_arrangeCCs
protected

Option for laying out components separately.

Definition at line 205 of file SugiyamaLayout.h.

ModuleOption<HierarchyClusterLayoutModule> ogdf::SugiyamaLayout::m_clusterLayout
protected

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

Definition at line 197 of file SugiyamaLayout.h.

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

Definition at line 478 of file SugiyamaLayout.h.

ModuleOption<LayeredCrossMinModule> ogdf::SugiyamaLayout::m_crossMin
protected

the module for two-layer crossing minimization

Definition at line 189 of file SugiyamaLayout.h.

ModuleOption<TwoLayerCrossMinSimDraw> ogdf::SugiyamaLayout::m_crossMinSimDraw
protected

Definition at line 191 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_fails
protected

Option for maximal number of fails.

Definition at line 202 of file SugiyamaLayout.h.

ModuleOption<HierarchyLayoutModule> ogdf::SugiyamaLayout::m_layout
protected

the hierarchy layout module (final coordinate assignment)

Definition at line 194 of file SugiyamaLayout.h.

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

Definition at line 213 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_maxLevelSize
private

Definition at line 492 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_maxThreads
protected

The maximal number of used threads.

Definition at line 209 of file SugiyamaLayout.h.

double ogdf::SugiyamaLayout::m_minDistCC
protected

Option for distance between connected components.

Definition at line 206 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_nCrossings
protected

Number of crossings in computed layout.

Definition at line 211 of file SugiyamaLayout.h.

RCCrossings ogdf::SugiyamaLayout::m_nCrossingsCluster
protected

Definition at line 212 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_numCC
private

Definition at line 477 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_numLevels
private

Definition at line 491 of file SugiyamaLayout.h.

ModuleOption<CCLayoutPackModule> ogdf::SugiyamaLayout::m_packer
protected

The module for arranging connected components.

Definition at line 200 of file SugiyamaLayout.h.

double ogdf::SugiyamaLayout::m_pageRatio
protected

Option for desired page ratio.

Definition at line 207 of file SugiyamaLayout.h.

bool ogdf::SugiyamaLayout::m_permuteFirst
protected

Definition at line 208 of file SugiyamaLayout.h.

ModuleOption<RankingModule> ogdf::SugiyamaLayout::m_ranking
protected

the ranking module (level assignment)

Definition at line 186 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::m_runs
protected

Option for number of runs.

Definition at line 203 of file SugiyamaLayout.h.

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

Defines the subgraphs for simultaneous drawing.

Definition at line 218 of file SugiyamaLayout.h.

double ogdf::SugiyamaLayout::m_timeReduceCrossings
private

Definition at line 493 of file SugiyamaLayout.h.

bool ogdf::SugiyamaLayout::m_transpose
protected

Option for switching on transposal heuristic.

Definition at line 204 of file SugiyamaLayout.h.


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