|
|||
|
|
|
|||
|
|
#include <SugiyamaLayout.h>
Public Member Functions | |
| SugiyamaLayout () | |
| Creates an instance of SugiyamaLayout and sets options to default values. | |
| ~SugiyamaLayout () | |
Algorithm call | |
| void | call (GraphAttributes &AG) |
| Calls the layout algorithm for graph AG. | |
| void | call (ClusterGraphAttributes &AG) |
| Calls the layout algorithm for clustered graph AG. | |
| void | call (GraphAttributes &AG, NodeArray< int > &rank) |
| Calls the layout algorithm for graph AG with a given level assignment. | |
| void | callUML (GraphAttributes &AG) |
Optional parameters | |
| int | fails () const |
| Returns the current setting of option fails. | |
| void | fails (int nFails) |
| Sets the option fails to nFails. | |
| int | runs () const |
| Returns the current setting of option runs. | |
| void | runs (int nRuns) |
| Sets the option runs to nRuns. | |
| bool | transpose () const |
| Returns the current setting of option transpose. | |
| void | transpose (bool bTranspose) |
| Sets the option transpose to bTranspose. | |
| bool | arrangeCCs () const |
| Returns the current setting of option arrangeCCs. | |
| void | arrangeCCs (bool bArrange) |
| Sets the options arrangeCCs to bArrange. | |
| double | minDistCC () const |
| Returns the current setting of option minDistCC (distance between components). | |
| void | minDistCC (double x) |
| Sets the option minDistCC to x. | |
| double | pageRatio () const |
| Returns the current setting of option pageRation. | |
| void | pageRatio (double x) |
| Sets the option pageRatio to x. | |
| bool | alignBaseClasses () const |
| Returns the current setting of option alignBaseClasses. | |
| void | alignBaseClasses (bool b) |
| Sets the option alignBaseClasses to b. | |
| bool | alignSiblings () const |
| Returns the current setting of option alignSiblings. | |
| void | alignSiblings (bool b) |
| Sets the option alignSiblings to b. | |
| void | setSubgraphs (EdgeArray< unsigned int > *esg) |
| Sets the subgraphs for simultaneous drawing. | |
| bool | useSubgraphs () const |
| Returns true iff subgraphs for simultaneous drawing are set. | |
Module options | |
| void | setRanking (RankingModule *pRanking) |
| Sets the module option for the node ranking (layer assignment). | |
| void | setCrossMin (TwoLayerCrossMin *pCrossMin) |
| Sets the module option for the two-layer crossing minimization. | |
| void | setLayout (HierarchyLayoutModule *pLayout) |
| Sets the module option for the computation of the final layout. | |
| void | setClusterLayout (HierarchyClusterLayoutModule *pLayout) |
| Sets the module option for the computation of the final layout for clustered graphs. | |
| void | setPacker (CCLayoutPackModule *pPacker) |
| Sets the module option for the arrangement of connected components. | |
Information after call | |
The following information can be accessed after calling the algorithm. | |
| int | numberOfCrossings () const |
| Returns the number of crossings in the computed layout (usual graph). | |
| RCCrossings | numberOfCrossingsCluster () const |
| Returns the number of crossings in the computed layout (cluster graph). | |
Protected Member Functions | |
| void | reduceCrossings (Hierarchy &H) |
| void | reduceCrossings (ExtendedNestingGraph &H) |
Protected Attributes | |
| ModuleOption< RankingModule > | m_ranking |
| the ranking module (level assignment) | |
| ModuleOption< TwoLayerCrossMin > | m_crossMin |
| the module for two-layer crossing minimization | |
| ModuleOption < TwoLayerCrossMinSimDraw > | m_crossMinSimDraw |
| ModuleOption < HierarchyLayoutModule > | m_layout |
| the hierarchy layout module (final coordinate assignment) | |
| ModuleOption < HierarchyClusterLayoutModule > | m_clusterLayout |
| the hierarchy cluster layout module (final coordinate assignment for clustered graphs) | |
| ModuleOption< CCLayoutPackModule > | m_packer |
| The module for arranging connected components. | |
| int | m_fails |
| Option for maximal number of fails. | |
| int | m_runs |
| Option for number of runs. | |
| bool | m_transpose |
| Option for switching on transposal heuristic. | |
| bool | m_arrangeCCs |
| Option for laying out components separately. | |
| double | m_minDistCC |
| Option for distance between connected components. | |
| double | m_pageRatio |
| Option for desired page ratio. | |
| int | m_nCrossings |
| Number of crossings in computed layout. | |
| RCCrossings | m_nCrossingsCluster |
| Array< bool > | m_levelChanged |
| bool | m_alignBaseClasses |
| Option for aligning base classes. | |
| bool | m_alignSiblings |
| Option for aligning siblings in inheritance trees. | |
| EdgeArray< unsigned int > * | m_subgraphs |
| Defines the subgraphs for simultaneous drawing. | |
Private Member Functions | |
| void | doCall (GraphAttributes &AG, bool umlCall) |
| void | doCall (GraphAttributes &AG, bool umlCall, NodeArray< int > &rank) |
| int | traverseTopDown (Hierarchy &H) |
| int | traverseBottomUp (Hierarchy &H) |
| bool | transposeLevel (int i, Hierarchy &H) |
| void | doTranspose (Hierarchy &H) |
| void | doTransposeRev (Hierarchy &H) |
| RCCrossings | traverseTopDown (ExtendedNestingGraph &H) |
| RCCrossings | traverseBottomUp (ExtendedNestingGraph &H) |
Private Attributes | |
| int | m_numCC |
| NodeArray< int > | m_compGC |
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 | The number of top-down and bottom-up traversals that the crossing minimization procedure performs. |
| 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 alignSiblingsare 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 | TwoLayerCrossMin | 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 183 of file SugiyamaLayout.h.
| 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.
| void ogdf::SugiyamaLayout::call | ( | GraphAttributes & | AG | ) | [virtual] |
Calls the layout algorithm for graph AG.
Returns the computed layout in AG.
Implements ogdf::LayoutModule.
| void ogdf::SugiyamaLayout::call | ( | ClusterGraphAttributes & | AG | ) |
Calls the layout algorithm for clustered graph AG.
Returns the computed layout in AG.
| void ogdf::SugiyamaLayout::call | ( | GraphAttributes & | AG, | |
| NodeArray< int > & | rank | |||
| ) |
Calls the layout algorithm for graph AG with a given level assignment.
Returns the computed layout in AG.
| AG | is the input graph (with node soze information) and is assigned the computed layout. | |
| rank | defines the level of each node. |
| void ogdf::SugiyamaLayout::callUML | ( | GraphAttributes & | AG | ) |
| 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 274 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::fails | ( | int | nFails | ) | [inline] |
| 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 287 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::runs | ( | int | nRuns | ) | [inline] |
| 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 299 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::transpose | ( | bool | bTranspose | ) | [inline] |
| 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 310 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::arrangeCCs | ( | bool | bArrange | ) | [inline] |
| 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 321 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::minDistCC | ( | double | x | ) | [inline] |
| 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 333 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::pageRatio | ( | double | x | ) | [inline] |
| 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 344 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::alignBaseClasses | ( | bool | b | ) | [inline] |
| 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 355 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::alignSiblings | ( | bool | b | ) | [inline] |
| void ogdf::SugiyamaLayout::setSubgraphs | ( | EdgeArray< unsigned int > * | esg | ) | [inline] |
| bool ogdf::SugiyamaLayout::useSubgraphs | ( | ) | const [inline] |
Returns true iff subgraphs for simultaneous drawing are set.
Definition at line 364 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 382 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::setCrossMin | ( | TwoLayerCrossMin * | 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 392 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 403 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 414 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 425 of file SugiyamaLayout.h.
| int ogdf::SugiyamaLayout::numberOfCrossings | ( | ) | const [inline] |
Returns the number of crossings in the computed layout (usual graph).
Definition at line 436 of file SugiyamaLayout.h.
| RCCrossings ogdf::SugiyamaLayout::numberOfCrossingsCluster | ( | ) | const [inline] |
Returns the number of crossings in the computed layout (cluster graph).
Definition at line 439 of file SugiyamaLayout.h.
| void ogdf::SugiyamaLayout::reduceCrossings | ( | Hierarchy & | H | ) | [protected] |
| void ogdf::SugiyamaLayout::reduceCrossings | ( | ExtendedNestingGraph & | H | ) | [protected] |
| void ogdf::SugiyamaLayout::doCall | ( | GraphAttributes & | AG, | |
| bool | umlCall | |||
| ) | [private] |
| void ogdf::SugiyamaLayout::doCall | ( | GraphAttributes & | AG, | |
| bool | umlCall, | |||
| NodeArray< int > & | rank | |||
| ) | [private] |
| int ogdf::SugiyamaLayout::traverseTopDown | ( | Hierarchy & | H | ) | [private] |
| int ogdf::SugiyamaLayout::traverseBottomUp | ( | Hierarchy & | H | ) | [private] |
| bool ogdf::SugiyamaLayout::transposeLevel | ( | int | i, | |
| Hierarchy & | H | |||
| ) | [private] |
| void ogdf::SugiyamaLayout::doTranspose | ( | Hierarchy & | H | ) | [private] |
| void ogdf::SugiyamaLayout::doTransposeRev | ( | Hierarchy & | H | ) | [private] |
| RCCrossings ogdf::SugiyamaLayout::traverseTopDown | ( | ExtendedNestingGraph & | H | ) | [private] |
| RCCrossings ogdf::SugiyamaLayout::traverseBottomUp | ( | ExtendedNestingGraph & | H | ) | [private] |
ModuleOption<RankingModule> ogdf::SugiyamaLayout::m_ranking [protected] |
ModuleOption<TwoLayerCrossMin> ogdf::SugiyamaLayout::m_crossMin [protected] |
Definition at line 193 of file SugiyamaLayout.h.
the hierarchy layout module (final coordinate assignment)
Definition at line 196 of file SugiyamaLayout.h.
the hierarchy cluster layout module (final coordinate assignment for clustered graphs)
Definition at line 199 of file SugiyamaLayout.h.
ModuleOption<CCLayoutPackModule> ogdf::SugiyamaLayout::m_packer [protected] |
int ogdf::SugiyamaLayout::m_fails [protected] |
int ogdf::SugiyamaLayout::m_runs [protected] |
bool ogdf::SugiyamaLayout::m_transpose [protected] |
bool ogdf::SugiyamaLayout::m_arrangeCCs [protected] |
double ogdf::SugiyamaLayout::m_minDistCC [protected] |
double ogdf::SugiyamaLayout::m_pageRatio [protected] |
int ogdf::SugiyamaLayout::m_nCrossings [protected] |
RCCrossings ogdf::SugiyamaLayout::m_nCrossingsCluster [protected] |
Definition at line 212 of file SugiyamaLayout.h.
Array<bool> ogdf::SugiyamaLayout::m_levelChanged [protected] |
Definition at line 213 of file SugiyamaLayout.h.
bool ogdf::SugiyamaLayout::m_alignBaseClasses [protected] |
bool ogdf::SugiyamaLayout::m_alignSiblings [protected] |
EdgeArray<unsigned int>* ogdf::SugiyamaLayout::m_subgraphs [protected] |
int ogdf::SugiyamaLayout::m_numCC [private] |
Definition at line 449 of file SugiyamaLayout.h.
NodeArray<int> ogdf::SugiyamaLayout::m_compGC [private] |
Definition at line 450 of file SugiyamaLayout.h.
