Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

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
Gis the input graph.
lengthspecifies the minimal length of each edge.
costspecifies the cost of each edge.
rankis 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
Gis the input graph.
lengthspecifies the minimal length of each edge.
rankis 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.

Member Data Documentation

◆ m_separateMultiEdges

bool ogdf::OptimalRanking::m_separateMultiEdges
private

Definition at line 77 of file OptimalRanking.h.

◆ m_subgraph

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

Definition at line 76 of file OptimalRanking.h.


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