The optimal ranking algorithm. More...

#include <ogdf/layered/OptimalRanking.h>

Inheritance diagram for ogdf::OptimalRanking:

Public Member Functions
	OptimalRanking ()
	Creates an instance of optimal 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	call (const Graph &G, const EdgeArray< int > &length, const EdgeArray< int > &cost, NodeArray< int > &rank)
	Computes a cost-minimal node ranking of G for given edge costs and minimal edge lengths in rank.
Optional parameters
bool	separateMultiEdges () const
	Returns the current setting of option separateMultiEdges.
void	separateMultiEdges (bool b)
	Sets the option separateMultiEdges 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, const EdgeArray< int > &cost)
	Implements the algorithm call.
Private Attributes
ModuleOption < AcyclicSubgraphModule >	m_subgraph
bool	m_separateMultiEdges

Detailed Description

The optimal ranking algorithm.

The class OptimalRanking implements the LP-based algorithm for computing a node ranking with minimal edge lengths, which can be used as first phase in SugiyamaLayout.

Optional parameters

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

Option	Type	Default	Description
separateMultiEdges	bool	true	If set to true, multi-edges will span at least two layers.

Module options

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

Definition at line 91 of file OptimalRanking.h.

Constructor & Destructor Documentation

ogdf::OptimalRanking::OptimalRanking ( )

Creates an instance of optimal ranking.

Member Function Documentation

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

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

void ogdf::OptimalRanking::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::OptimalRanking::call	(	const Graph &	G,
		const EdgeArray< int > &	length,
		const EdgeArray< int > &	cost,
		NodeArray< int > &	rank
	)		`[virtual]`

Computes a cost-minimal node ranking of G for given edge costs and minimal edge lengths in rank.

Parameters:

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

Reimplemented from ogdf::RankingModule.

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

Implements the algorithm call.

bool ogdf::OptimalRanking::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 142 of file OptimalRanking.h.

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

Sets the option separateMultiEdges to b.

Definition at line 145 of file OptimalRanking.h.

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

Sets the module for the computation of the acyclic subgraph.

Definition at line 154 of file OptimalRanking.h.

Member Data Documentation

bool ogdf::OptimalRanking::m_separateMultiEdges [private]

Definition at line 94 of file OptimalRanking.h.

ModuleOption<AcyclicSubgraphModule> ogdf::OptimalRanking::m_subgraph [private]

Definition at line 93 of file OptimalRanking.h.

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

ogdf/layered/OptimalRanking.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions