OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

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

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 doCall (const Graph &G, NodeArray< int > &rank, EdgeArray< bool > &reversed, const EdgeArray< int > &length, const EdgeArray< int > &cost)
Implements the algorithm call.

Private Attributes

bool m_separateMultiEdges

std::unique_ptr< AcyclicSubgraphModulem_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:

OptionTypeDefaultDescription
separateMultiEdgesbooltrue If set to true, multi-edges will span at least two layers.

Module options

OptionTypeDefaultDescription
subgraphAcyclicSubgraphModuleDfsAcyclicSubgraph The module for the computation of the acyclic subgraph.

Definition at line 75 of file OptimalRanking.h.

◆ OptimalRanking()

 ogdf::OptimalRanking::OptimalRanking ( )

Creates an instance of optimal ranking.

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

◆ separateMultiEdges() [2/2]

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

Sets the option separateMultiEdges to b.

Definition at line 124 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 132 of file OptimalRanking.h.

◆ m_separateMultiEdges

 bool ogdf::OptimalRanking::m_separateMultiEdges
private

Definition at line 77 of file OptimalRanking.h.

◆ m_subgraph

 std::unique_ptr ogdf::OptimalRanking::m_subgraph
private

Definition at line 76 of file OptimalRanking.h.

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