Sugiyama's layout algorithm. More...
#include <ogdf/layered/SugiyamaLayout.h>
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< HierarchyClusterLayoutModule > | m_clusterLayout |
the hierarchy cluster layout module (final coordinate assignment for clustered graphs) More... | |
std::unique_ptr< LayeredCrossMinModule > | m_crossMin |
the module for two-layer crossing minimization More... | |
std::unique_ptr< TwoLayerCrossMinSimDraw > | m_crossMinSimDraw |
int | m_fails |
Option for maximal number of fails. More... | |
std::unique_ptr< HierarchyLayoutModule > | m_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< CCLayoutPackModule > | m_packer |
The module for arranging connected components. More... | |
double | m_pageRatio |
Option for desired page ratio. More... | |
bool | m_permuteFirst |
std::unique_ptr< RankingModule > | m_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 HierarchyLevelsBase * | reduceCrossings (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) |
Sugiyama's layout algorithm.
The class SugiyamaLayout represents a customizable implementation of Sugiyama's layout algorithm. The class provides three different algorithm calls:
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.
The following options affect the crossing minimization step of the algorithm:
Option | Type | Default | Description |
---|---|---|---|
runs | int | 15 | 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. |
transpose | bool | true | 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. |
fails | int | 4 | 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. |
arrangeCCs | bool | true | If set to true connected components are laid out separately and the resulting layouts are arranged afterwards using the packer module. |
minDistCC | double | 20.0 | Specifies the spacing between connected components of the graph. Other spacing parameters have to be set in the used hierarchy layout module. |
alignBaseClasses | bool | false | Determines if base classes of inheritance hierarchies shall be aligned (only callUML()). |
alignSiblings | bool | false | 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.
The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:
Option | Type | Default | Description |
---|---|---|---|
ranking | RankingModule | LongestPathRanking | The ranking module determines the layering of the graph. |
crossMin | LayerByLayerSweep | BarycenterHeuristic | The crossMin module performs two-layer crossing minimization and is applied during the top-down bottom-up traversals. |
crossMinSimDraw | TwoLayerCrossMinSimDraw | SplitHeuristic | The crossMin module used with simultaneous drawing. |
layout | HierarchyLayoutModule | FastHierarchyLayout | The hierarchy layout module that computes the final layout (call for graph). |
clusterLayout | HierarchyClusterLayoutModule | OptimalHierarchyClusterLayout | The hierarchy layout module that computes the final layout (call for cluster graph). |
packer | CCLayoutPackModule | TileToRowsCCPacker | The packer module used for arranging connected components. |
Definition at line 160 of file SugiyamaLayout.h.
ogdf::SugiyamaLayout::SugiyamaLayout | ( | ) |
Creates an instance of SugiyamaLayout and sets options to default values.
|
inline |
Definition at line 207 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the option alignBaseClasses to b
.
Definition at line 326 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the option alignSiblings to b
.
Definition at line 337 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the options arrangeCCs to bArrange
.
Definition at line 292 of file SugiyamaLayout.h.
void ogdf::SugiyamaLayout::call | ( | ClusterGraphAttributes & | CGA | ) |
Calls the layout algorithm for clustered graph CGA
.
Returns the computed layout in CGA
.
|
overridevirtual |
Calls the layout algorithm for graph GA
.
Returns the computed layout in GA
.
Implements ogdf::LayoutModule.
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
.
GA | is the input graph (with node size information) and is assigned the computed layout. |
rank | defines the level of each node. |
void ogdf::SugiyamaLayout::callUML | ( | GraphAttributes & | GA | ) |
|
inline |
Definition at line 436 of file SugiyamaLayout.h.
|
private |
|
private |
|
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.
|
inline |
Sets the option fails to nFails
.
Definition at line 256 of file SugiyamaLayout.h.
|
inline |
Return the max. number of elements on a layer.
Definition at line 427 of file SugiyamaLayout.h.
|
inline |
Returns the maximal number of used threads.
Definition at line 350 of file SugiyamaLayout.h.
|
inline |
Sets the maximal number of used threads to n
.
Definition at line 353 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the option minDistCC to x
.
Definition at line 303 of file SugiyamaLayout.h.
|
inline |
Returns the number of crossings in the computed layout (usual graph).
Definition at line 418 of file SugiyamaLayout.h.
|
inline |
Returns the number of crossings in the computed layout (cluster graph).
Definition at line 421 of file SugiyamaLayout.h.
|
inline |
Return the number of layers/levels}.
Definition at line 424 of file SugiyamaLayout.h.
|
inline |
Definition at line 434 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the option pageRatio to x
.
Definition at line 315 of file SugiyamaLayout.h.
|
inline |
Definition at line 345 of file SugiyamaLayout.h.
|
inline |
Definition at line 347 of file SugiyamaLayout.h.
|
protected |
|
protected |
|
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.
|
inline |
Sets the option runs to nRuns
.
Definition at line 269 of file SugiyamaLayout.h.
|
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.
|
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.
|
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.
|
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.
|
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.
|
inline |
Sets the subgraphs for simultaneous drawing.
Definition at line 340 of file SugiyamaLayout.h.
|
inline |
Definition at line 432 of file SugiyamaLayout.h.
|
inline |
Definition at line 429 of file SugiyamaLayout.h.
|
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.
|
inline |
Sets the option transpose to bTranspose
.
Definition at line 281 of file SugiyamaLayout.h.
|
private |
|
private |
|
inline |
Returns true iff subgraphs for simultaneous drawing are set.
Definition at line 343 of file SugiyamaLayout.h.
|
protected |
Option for aligning base classes.
Definition at line 197 of file SugiyamaLayout.h.
|
protected |
Option for aligning siblings in inheritance trees.
Definition at line 198 of file SugiyamaLayout.h.
|
protected |
Option for laying out components separately.
Definition at line 187 of file SugiyamaLayout.h.
|
protected |
the hierarchy cluster layout module (final coordinate assignment for clustered graphs)
Definition at line 179 of file SugiyamaLayout.h.
|
private |
Definition at line 448 of file SugiyamaLayout.h.
|
protected |
the module for two-layer crossing minimization
Definition at line 171 of file SugiyamaLayout.h.
|
protected |
Definition at line 173 of file SugiyamaLayout.h.
|
protected |
Option for maximal number of fails.
Definition at line 184 of file SugiyamaLayout.h.
|
protected |
the hierarchy layout module (final coordinate assignment)
Definition at line 176 of file SugiyamaLayout.h.
|
protected |
Definition at line 195 of file SugiyamaLayout.h.
|
private |
Definition at line 464 of file SugiyamaLayout.h.
|
protected |
The maximal number of used threads.
Definition at line 191 of file SugiyamaLayout.h.
|
protected |
Option for distance between connected components.
Definition at line 188 of file SugiyamaLayout.h.
|
protected |
Number of crossings in computed layout.
Definition at line 193 of file SugiyamaLayout.h.
|
protected |
Definition at line 194 of file SugiyamaLayout.h.
|
private |
Definition at line 447 of file SugiyamaLayout.h.
|
private |
Definition at line 463 of file SugiyamaLayout.h.
|
protected |
The module for arranging connected components.
Definition at line 182 of file SugiyamaLayout.h.
|
protected |
Option for desired page ratio.
Definition at line 189 of file SugiyamaLayout.h.
|
protected |
Definition at line 190 of file SugiyamaLayout.h.
|
protected |
the ranking module (level assignment)
Definition at line 168 of file SugiyamaLayout.h.
|
protected |
Option for number of runs.
Definition at line 185 of file SugiyamaLayout.h.
|
protected |
Defines the subgraphs for simultaneous drawing.
Definition at line 200 of file SugiyamaLayout.h.
|
private |
Definition at line 465 of file SugiyamaLayout.h.
|
protected |
Option for switching on transposal heuristic.
Definition at line 186 of file SugiyamaLayout.h.