The longest-path ranking algorithm. More...

#include <ogdf/layered/LongestPathRanking.h>

Inheritance diagram for ogdf::LongestPathRanking:

Public Member Functions
	LongestPathRanking ()
	Creates an instance of longest-path ranking.
Algorithm call
void	call (const Graph &G, NodeArray< int > &rank)
	Computes a node ranking of G in rank.
void	call (const Graph &G, const EdgeArray< int > &length, NodeArray< int > &rank)
	Computes a node ranking of G with given minimal edge length in rank.
void	callUML (const GraphAttributes &AG, NodeArray< int > &rank)
	Call for UML graphs with special treatement of inheritance hierarchies.
Optional parameters
bool	separateDeg0Layer () const
	Returns the current setting of option separateDeg0Layer.
void	separateDeg0Layer (bool sdl)
	Sets the option separateDeg0Layer to sdl.
bool	separateMultiEdges () const
	Returns the current setting of option separateMultiEdges.
void	separateMultiEdges (bool b)
	Sets the option separateMultiEdges to b.
bool	optimizeEdgeLength () const
	Returns the current setting of option optimizeEdgeLength.
void	optimizeEdgeLength (bool b)
	Sets the option optimizeEdgeLength to b.
bool	alignBaseClasses () const
	Returns the current setting of alignment of base classes (callUML only).
void	alignBaseClasses (bool b)
	Sets the option for alignment of base classes to b.
bool	alignSiblings () const
	Returns the current setting of option for alignment of siblings.
void	alignSiblings (bool b)
	Sets the option for alignment of siblings to b.
Module options
void	setSubgraph (AcyclicSubgraphModule *pSubgraph)
	Sets the module for the computation of the acyclic subgraph.
Private Member Functions
void	doCall (const Graph &G, NodeArray< int > &rank, EdgeArray< bool > &reversed, const EdgeArray< int > &length)
	Implements the algorithm call.
void	join (GraphCopySimple &GC, NodeArray< node > &superNode, NodeArray< SListPure< node > > &joinedNodes, node v, node w)
void	dfs (node v)
void	getTmpRank (node v, NodeArray< int > &rank)
void	dfsAdd (node v, NodeArray< int > &rank)
Private Attributes
ModuleOption < AcyclicSubgraphModule >	m_subgraph
	The acyclic sugraph module.
bool	m_sepDeg0
	Put isolated nodes on a separate layer?
bool	m_separateMultiEdges
	Separate multi-edges?
bool	m_optimizeEdgeLength
	Optimize for short edges.
bool	m_alignBaseClasses
	Align base classes (callUML only).
bool	m_alignSiblings
	Align siblings (callUML only).
int	m_offset
int	m_maxN
NodeArray< bool >	m_isSource
NodeArray< bool >	m_finished
NodeArray< SListPure< Tuple2 < node, int > > >	m_adjacent
NodeArray< int >	m_ingoing

Detailed Description

The longest-path ranking algorithm.

The class LongestPathRanking implements the well-known longest-path ranking algorithm, which can be used as first phase in SugiyamaLayout. The implementation contains a special optimization for reducing edge lengths, as well as special treatment of mixed-upward graphs (e.g., UML class diagrams).

Optional parameters

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

Option	Type	Default	Description
separateDeg0Layer	bool	true	If set to true, isolated nodes are placed on a separate layer.
separateMultiEdges	bool	true	If set to true, multi-edges will span at least two layers.
optimizeEdgeLength	bool	true	If set to true the ranking algorithm tries to reduce edge length even if this might increase the height of the layout. Choose false if the longest-path ranking known from the literature shall be used.
alignBaseClasses	bool	false	If set to true, base classes (in UML class diagrams) are aligned on the same layer (callUML only).
alignSiblings	bool	false	If set to true, siblings in inheritance trees are aligned on the same layer (callUML only).

Module options

Option	Type	Default	Description
subgraph	AcyclicSubgraphModule	DfsAcyclicSubgraph	The module for the computation of the acyclic subgraph.

Definition at line 115 of file LongestPathRanking.h.

Constructor & Destructor Documentation

ogdf::LongestPathRanking::LongestPathRanking ( )

Creates an instance of longest-path ranking.

Member Function Documentation

bool ogdf::LongestPathRanking::alignBaseClasses ( ) const [inline]

Returns the current setting of alignment of base classes (callUML only).

Definition at line 193 of file LongestPathRanking.h.

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

Sets the option for alignment of base classes to b.

Definition at line 196 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::alignSiblings ( ) const [inline]

Returns the current setting of option for alignment of siblings.

Definition at line 199 of file LongestPathRanking.h.

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

Sets the option for alignment of siblings to b.

Definition at line 202 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::call	(	const Graph &	G,
		NodeArray< int > &	rank
	)		`[virtual]`

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

void ogdf::LongestPathRanking::call	(	const Graph &	G,
		const EdgeArray< int > &	length,
		NodeArray< int > &	rank
	)

Computes a node ranking of G with given minimal edge length in rank.

Parameters:

G	is the input graph.
length	specifies the minimal length of each edge.
rank	is assigned the rank (layer) of each node.

void ogdf::LongestPathRanking::callUML	(	const GraphAttributes &	AG,
		NodeArray< int > &	rank
	)

Call for UML graphs with special treatement of inheritance hierarchies.

void ogdf::LongestPathRanking::dfs ( node v ) [private]

void ogdf::LongestPathRanking::dfsAdd	(	node	v,
		NodeArray< int > &	rank
	)		`[private]`

void ogdf::LongestPathRanking::doCall	(	const Graph &	G,
		NodeArray< int > &	rank,
		EdgeArray< bool > &	reversed,
		const EdgeArray< int > &	length
	)		`[private]`

Implements the algorithm call.

void ogdf::LongestPathRanking::getTmpRank	(	node	v,
		NodeArray< int > &	rank
	)		`[private]`

void ogdf::LongestPathRanking::join	(	GraphCopySimple &	GC,
		NodeArray< node > &	superNode,
		NodeArray< SListPure< node > > &	joinedNodes,
		node	v,
		node	w
	)		`[private]`

bool ogdf::LongestPathRanking::optimizeEdgeLength ( ) const [inline]

Returns the current setting of option optimizeEdgeLength.

If set to true the ranking algorithm tries to reduce edge length even if this might increase the height of the layout. Choose false if the longest-path ranking known from the literature shall be used.

Definition at line 187 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::optimizeEdgeLength ( bool b ) [inline]

Sets the option optimizeEdgeLength to b.

Definition at line 190 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::separateDeg0Layer ( ) const [inline]

Returns the current setting of option separateDeg0Layer.

If set to true, isolated nodes are placed on a separate layer.

Definition at line 164 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::separateDeg0Layer ( bool sdl ) [inline]

Sets the option separateDeg0Layer to sdl.

Definition at line 167 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::separateMultiEdges ( ) const [inline]

Returns the current setting of option separateMultiEdges.

If set to true, multi-edges will span at least two layers. Since each such edge will have at least one dummy node, the edges will automaticall be separated in a Sugiyama drawing.

Definition at line 175 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::separateMultiEdges ( bool b ) [inline]

Sets the option separateMultiEdges to b.

Definition at line 178 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::setSubgraph ( AcyclicSubgraphModule * pSubgraph ) [inline]

Sets the module for the computation of the acyclic subgraph.

Definition at line 211 of file LongestPathRanking.h.