ogdf::OptimalRanking Class Reference

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. More...
Algorithm call
virtual void	call (const Graph &G, NodeArray< int > &rank) override
	Computes a node ranking of G in rank. More...
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. More...
virtual void	call (const Graph &G, const EdgeArray< int > &length, const EdgeArray< int > &cost, NodeArray< int > &rank) override
	Computes a cost-minimal node ranking of G for given edge costs and minimal edge lengths in rank. More...
Optional parameters
bool	separateMultiEdges () const
	Returns the current setting of option separateMultiEdges. More...
void	separateMultiEdges (bool b)
	Sets the option separateMultiEdges to b. More...
Module options
void	setSubgraph (AcyclicSubgraphModule *pSubgraph)
	Sets the module for the computation of the acyclic subgraph. More...
Public Member Functions inherited from ogdf::RankingModule
	RankingModule ()
	Initializes a ranking module. More...
virtual	~RankingModule ()
void	operator() (const Graph &G, NodeArray< int > &rank)
	Computes a node ranking of the digraph G in rank. More...

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. More...

Private Attributes
bool	m_separateMultiEdges
std::unique_ptr< AcyclicSubgraphModule >	m_subgraph

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 76 of file OptimalRanking.h.

Constructor & Destructor Documentation

OptimalRanking()

ogdf::OptimalRanking::OptimalRanking

(

)

Creates an instance of optimal ranking.

Member Function Documentation

call() [1/3]

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

overridevirtual

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.

call() [2/3]

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.

call() [3/3]

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

overridevirtual

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

doCall()

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.

separateMultiEdges() [1/2]

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 122 of file OptimalRanking.h.

separateMultiEdges() [2/2]

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

inline

Sets the option separateMultiEdges to b.

Definition at line 125 of file OptimalRanking.h.

setSubgraph()

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

inline

Sets the module for the computation of the acyclic subgraph.

Definition at line 133 of file OptimalRanking.h.

Member Data Documentation

m_separateMultiEdges

bool ogdf::OptimalRanking::m_separateMultiEdges

private

Definition at line 78 of file OptimalRanking.h.

m_subgraph

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

private

Definition at line 77 of file OptimalRanking.h.

---

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

• include/ogdf/layered/OptimalRanking.h