The optimal ranking algorithm. More...
#include <ogdf/layered/OptimalRanking.h>
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 |
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.
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. |
Option | Type | Default | Description |
---|---|---|---|
subgraph | AcyclicSubgraphModule | DfsAcyclicSubgraph | The module for the computation of the acyclic subgraph. |
Definition at line 75 of file OptimalRanking.h.
ogdf::OptimalRanking::OptimalRanking | ( | ) |
Creates an instance of optimal ranking.
|
overridevirtual |
Computes a cost-minimal node ranking of G
for given edge costs and minimal edge lengths in rank
.
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::call | ( | const Graph & | G, |
const EdgeArray< int > & | length, | ||
NodeArray< int > & | rank | ||
) |
Computes a node ranking of G
with given minimal edge length in rank
.
G | is the input graph. |
length | specifies the minimal length of each edge. |
rank | is assigned the rank (layer) of each node. |
|
overridevirtual |
Computes a node ranking of G
in rank
.
Implements ogdf::RankingModule.
|
private |
Implements the algorithm call.
|
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.
|
inline |
Sets the option separateMultiEdges to b
.
Definition at line 124 of file OptimalRanking.h.
|
inline |
Sets the module for the computation of the acyclic subgraph.
Definition at line 132 of file OptimalRanking.h.
|
private |
Definition at line 77 of file OptimalRanking.h.
|
private |
Definition at line 76 of file OptimalRanking.h.