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.
Public Member Functions inherited from ogdf::RankingModule
	RankingModule ()
	Initializes a ranking module.
virtual	~RankingModule ()
virtual void	call (const Graph &G, const EdgeArray< int > &, const EdgeArray< int > &, NodeArray< int > &rank)
void	operator() (const Graph &G, NodeArray< int > &rank)
	Computes a node ranking of the digraph G in rank.

Private Member Functions
void	dfs (node v)
void	dfsAdd (node v, NodeArray< int > &rank)
void	doCall (const Graph &G, NodeArray< int > &rank, EdgeArray< bool > &reversed, const EdgeArray< int > &length)
	Implements the algorithm call.
void	getTmpRank (node v, NodeArray< int > &rank)
void	join (GraphCopySimple &GC, NodeArray< node > &superNode, NodeArray< SListPure< node > > &joinedNodes, node v, node w)

Private Attributes
NodeArray< SListPure< Tuple2 < node, int > > >	m_adjacent
bool	m_alignBaseClasses
	Align base classes (callUML only).
bool	m_alignSiblings
	Align siblings (callUML only).
NodeArray< bool >	m_finished
NodeArray< int >	m_ingoing
NodeArray< bool >	m_isSource
int	m_maxN
int	m_offset
bool	m_optimizeEdgeLength
	Optimize for short edges.
bool	m_separateMultiEdges
	Separate multi-edges?
bool	m_sepDeg0
	Put isolated nodes on a separate layer?
ModuleOption < AcyclicSubgraphModule >	m_subgraph
	The acyclic sugraph module.

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 116 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 194 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::alignBaseClasses ( bool b )

inline

Sets the option for alignment of base classes to b.

Definition at line 197 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::alignSiblings ( ) const

inline

Returns the current setting of option for alignment of siblings.

Definition at line 200 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::alignSiblings ( bool b )

inline

Sets the option for alignment of siblings to b.

Definition at line 203 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 188 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::optimizeEdgeLength ( bool b )

inline

Sets the option optimizeEdgeLength to b.

Definition at line 191 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 165 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::separateDeg0Layer ( bool sdl )

inline

Sets the option separateDeg0Layer to sdl.

Definition at line 168 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 176 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::separateMultiEdges ( bool b )

inline

Sets the option separateMultiEdges to b.

Definition at line 179 of file LongestPathRanking.h.

void ogdf::LongestPathRanking::setSubgraph ( AcyclicSubgraphModule * pSubgraph )

inline

Sets the module for the computation of the acyclic subgraph.

Definition at line 212 of file LongestPathRanking.h.

Member Data Documentation

NodeArray<SListPure<Tuple2<node,int> > > ogdf::LongestPathRanking::m_adjacent

private

Definition at line 128 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::m_alignBaseClasses

private

Align base classes (callUML only).

Definition at line 122 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::m_alignSiblings

private

Align siblings (callUML only).

Definition at line 123 of file LongestPathRanking.h.

NodeArray<bool> ogdf::LongestPathRanking::m_finished

private

Definition at line 127 of file LongestPathRanking.h.

NodeArray<int> ogdf::LongestPathRanking::m_ingoing

private

Definition at line 129 of file LongestPathRanking.h.

NodeArray<bool> ogdf::LongestPathRanking::m_isSource

private

Definition at line 127 of file LongestPathRanking.h.

int ogdf::LongestPathRanking::m_maxN

private

Definition at line 125 of file LongestPathRanking.h.

int ogdf::LongestPathRanking::m_offset

private

Definition at line 125 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::m_optimizeEdgeLength

private

Optimize for short edges.

Definition at line 121 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::m_separateMultiEdges

private

Separate multi-edges?

Definition at line 120 of file LongestPathRanking.h.

bool ogdf::LongestPathRanking::m_sepDeg0

private

Put isolated nodes on a separate layer?

Definition at line 119 of file LongestPathRanking.h.

ModuleOption<AcyclicSubgraphModule> ogdf::LongestPathRanking::m_subgraph

private

The acyclic sugraph module.

Definition at line 118 of file LongestPathRanking.h.

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

ogdf/layered/LongestPathRanking.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Optional parameters

Module options

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework