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
virtual void	call (const Graph &G, NodeArray< int > &rank) override
	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`.

virtual void	call (const Graph &G, const EdgeArray< int > &length, const EdgeArray< int > &cost, NodeArray< int > &rank) override
	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 ()

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?

std::unique_ptr< 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 97 of file LongestPathRanking.h.

Constructor & Destructor Documentation

◆ LongestPathRanking()

ogdf::LongestPathRanking::LongestPathRanking ( )

Creates an instance of longest-path ranking.

Member Function Documentation

◆ alignBaseClasses() [1/2]

bool ogdf::LongestPathRanking::alignBaseClasses ( ) const

inline

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

Definition at line 187 of file LongestPathRanking.h.

◆ alignBaseClasses() [2/2]

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

inline

Sets the option for alignment of base classes to b.

Definition at line 190 of file LongestPathRanking.h.

◆ alignSiblings() [1/2]

bool ogdf::LongestPathRanking::alignSiblings ( ) const

inline

Returns the current setting of option for alignment of siblings.

Definition at line 193 of file LongestPathRanking.h.

◆ alignSiblings() [2/2]

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

inline

Sets the option for alignment of siblings to b.

Definition at line 196 of file LongestPathRanking.h.

◆ call() [1/3]

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

inlineoverridevirtual

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

Parameter cost is just ignored by the implementation.

Parameters

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

Reimplemented from ogdf::RankingModule.

Definition at line 141 of file LongestPathRanking.h.

◆ call() [2/3]

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.

◆ call() [3/3]

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

overridevirtual

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

◆ callUML()

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

Call for UML graphs with special treatement of inheritance hierarchies.

◆ dfs()

void ogdf::LongestPathRanking::dfs ( node v )

private

◆ dfsAdd()

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

private

◆ doCall()

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

private

Implements the algorithm call.

◆ getTmpRank()

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

private

◆ join()

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

private

◆ optimizeEdgeLength() [1/2]

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

◆ optimizeEdgeLength() [2/2]

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

inline

Sets the option optimizeEdgeLength to b.

Definition at line 184 of file LongestPathRanking.h.

◆ separateDeg0Layer() [1/2]

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

◆ separateDeg0Layer() [2/2]

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

inline

Sets the option separateDeg0Layer to sdl.

Definition at line 161 of file LongestPathRanking.h.

◆ separateMultiEdges() [1/2]

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

◆ separateMultiEdges() [2/2]

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

inline

Sets the option separateMultiEdges to b.

Definition at line 172 of file LongestPathRanking.h.

◆ setSubgraph()

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

inline

Sets the module for the computation of the acyclic subgraph.

Definition at line 204 of file LongestPathRanking.h.

Member Data Documentation

◆ m_adjacent

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

private

Definition at line 108 of file LongestPathRanking.h.

◆ m_alignBaseClasses

bool ogdf::LongestPathRanking::m_alignBaseClasses

private

Align base classes (callUML only).

Definition at line 102 of file LongestPathRanking.h.

◆ m_alignSiblings

bool ogdf::LongestPathRanking::m_alignSiblings

private

Align siblings (callUML only).

Definition at line 103 of file LongestPathRanking.h.

◆ m_finished

NodeArray<bool> ogdf::LongestPathRanking::m_finished

private

Definition at line 107 of file LongestPathRanking.h.

◆ m_ingoing

NodeArray<int> ogdf::LongestPathRanking::m_ingoing

private

Definition at line 109 of file LongestPathRanking.h.

◆ m_isSource

NodeArray<bool> ogdf::LongestPathRanking::m_isSource

private

Definition at line 107 of file LongestPathRanking.h.

◆ m_maxN

int ogdf::LongestPathRanking::m_maxN

private

Definition at line 105 of file LongestPathRanking.h.

◆ m_offset

int ogdf::LongestPathRanking::m_offset

private

Definition at line 105 of file LongestPathRanking.h.

◆ m_optimizeEdgeLength

bool ogdf::LongestPathRanking::m_optimizeEdgeLength

private

Optimize for short edges.

Definition at line 101 of file LongestPathRanking.h.

◆ m_separateMultiEdges

bool ogdf::LongestPathRanking::m_separateMultiEdges

private

Separate multi-edges?

Definition at line 100 of file LongestPathRanking.h.

◆ m_sepDeg0

bool ogdf::LongestPathRanking::m_sepDeg0

private

Put isolated nodes on a separate layer?

Definition at line 99 of file LongestPathRanking.h.

◆ m_subgraph

std::unique_ptr<AcyclicSubgraphModule> ogdf::LongestPathRanking::m_subgraph

private

The acyclic sugraph module.

Definition at line 98 of file LongestPathRanking.h.

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

include/ogdf/layered/LongestPathRanking.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Optional parameters

Module options

Constructor & Destructor Documentation

◆ LongestPathRanking()

Member Function Documentation

◆ alignBaseClasses() [1/2]

◆ alignBaseClasses() [2/2]

◆ alignSiblings() [1/2]

◆ alignSiblings() [2/2]

◆ call() [1/3]

◆ call() [2/3]

◆ call() [3/3]

◆ callUML()

◆ dfs()

◆ dfsAdd()

◆ doCall()

◆ getTmpRank()

◆ join()

◆ optimizeEdgeLength() [1/2]

◆ optimizeEdgeLength() [2/2]

◆ separateDeg0Layer() [1/2]

◆ separateDeg0Layer() [2/2]

◆ separateMultiEdges() [1/2]

◆ separateMultiEdges() [2/2]

◆ setSubgraph()

Member Data Documentation

◆ m_adjacent

◆ m_alignBaseClasses

◆ m_alignSiblings

◆ m_finished

◆ m_ingoing

◆ m_isSource

◆ m_maxN

◆ m_offset

◆ m_optimizeEdgeLength

◆ m_separateMultiEdges

◆ m_sepDeg0

◆ m_subgraph

Open
Graph Drawing
Framework