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.
	~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.
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.
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
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).
int	numberOfLevels ()
	Return the number of layers/levels}.
int	maxLevelSize ()
	Return the max. number of elements on a layer.
void	reduceCrossings (Hierarchy &H)
void	reduceCrossings (ExtendedNestingGraph &H)
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)

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:

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.

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:

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 187 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 230 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 348 of file SugiyamaLayout.h.

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

Sets the option alignBaseClasses to b.

Definition at line 351 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 359 of file SugiyamaLayout.h.

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

Sets the option alignSiblings to b.

Definition at line 362 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 314 of file SugiyamaLayout.h.

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

Sets the options arrangeCCs to bArrange.

Definition at line 317 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.

Parameters:

	AG	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 & AG )

void ogdf::SugiyamaLayout::doCall	(	GraphAttributes &	AG,
		bool	umlCall
	)			`[private]`

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

void ogdf::SugiyamaLayout::doTranspose ( Hierarchy & H ) [private]

void ogdf::SugiyamaLayout::doTransposeRev ( Hierarchy & H ) [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 278 of file SugiyamaLayout.h.

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

Sets the option fails to nFails.

Definition at line 281 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::maxLevelSize ( ) [inline]

Return the max. number of elements on a layer.

Definition at line 449 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 325 of file SugiyamaLayout.h.

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

Sets the option minDistCC to x.

Definition at line 328 of file SugiyamaLayout.h.

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

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

Definition at line 440 of file SugiyamaLayout.h.

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

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

Definition at line 443 of file SugiyamaLayout.h.

int ogdf::SugiyamaLayout::numberOfLevels ( ) [inline]

Return the number of layers/levels}.

Definition at line 446 of file SugiyamaLayout.h.

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

Sets the option pageRatio to x.

Definition at line 340 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 337 of file SugiyamaLayout.h.

void ogdf::SugiyamaLayout::reduceCrossings ( Hierarchy & H ) [protected]

void ogdf::SugiyamaLayout::reduceCrossings ( ExtendedNestingGraph & H ) [protected]

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

Sets the option runs to nRuns.

Definition at line 294 of file SugiyamaLayout.h.

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 291 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 418 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 396 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 407 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 429 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 386 of file SugiyamaLayout.h.

void ogdf::SugiyamaLayout::setSubgraphs ( EdgeArray< unsigned int > * esg ) [inline]

Sets the subgraphs for simultaneous drawing.

Definition at line 365 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 303 of file SugiyamaLayout.h.

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

Sets the option transpose to bTranspose.

Definition at line 306 of file SugiyamaLayout.h.