Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

The longest-path ranking algorithm. More...

#include <ogdf/layered/LongestPathRanking.h>

+ Inheritance diagram for ogdf::LongestPathRanking:

Public Member Functions

 LongestPathRanking ()
 Creates an instance of longest-path 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 node ranking of G with given minimal edge length in rank. More...
 
void callUML (const GraphAttributes &AG, NodeArray< int > &rank)
 Call for UML graphs with special treatement of inheritance hierarchies. More...
 
Optional parameters
bool separateDeg0Layer () const
 Returns the current setting of option separateDeg0Layer. More...
 
void separateDeg0Layer (bool sdl)
 Sets the option separateDeg0Layer to sdl. More...
 
bool separateMultiEdges () const
 Returns the current setting of option separateMultiEdges. More...
 
void separateMultiEdges (bool b)
 Sets the option separateMultiEdges to b. More...
 
bool optimizeEdgeLength () const
 Returns the current setting of option optimizeEdgeLength. More...
 
void optimizeEdgeLength (bool b)
 Sets the option optimizeEdgeLength to b. More...
 
bool alignBaseClasses () const
 Returns the current setting of alignment of base classes (callUML only). More...
 
void alignBaseClasses (bool b)
 Sets the option for alignment of base classes to b. More...
 
bool alignSiblings () const
 Returns the current setting of option for alignment of siblings. More...
 
void alignSiblings (bool b)
 Sets the option for alignment of siblings 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 dfs (node v)
 
void dfsAdd (node v, NodeArray< int > &rank)
 
void doCall (const Graph &G, NodeArray< int > &rank, EdgeArray< bool > &reversed, const EdgeArray< int > &length)
 Implements the algorithm call. More...
 
void getTmpRank (node v, NodeArray< int > &rank)
 
void join (GraphCopySimple &GC, NodeArray< node > &superNode, NodeArray< SListPure< node > > &joinedNodes, node v, node w)
 

Private Attributes

NodeArray< SListPure< Tuple2< node, int > > > m_adjacent
 
bool m_alignBaseClasses
 Align base classes (callUML only). More...
 
bool m_alignSiblings
 Align siblings (callUML only). More...
 
NodeArray< bool > m_finished
 
NodeArray< int > m_ingoing
 
NodeArray< bool > m_isSource
 
int m_maxN
 
int m_offset
 
bool m_optimizeEdgeLength
 Optimize for short edges. More...
 
bool m_separateMultiEdges
 Separate multi-edges? More...
 
bool m_sepDeg0
 Put isolated nodes on a separate layer? More...
 
std::unique_ptr< AcyclicSubgraphModulem_subgraph
 The acyclic sugraph module. More...
 

Detailed Description

The longest-path ranking algorithm.

The class LongestPathRanking implements the well-known longest-path ranking algorithm, which can be used as first phase in SugiyamaLayout. The implementation contains a special optimization for reducing edge lengths, as well as special treatment of mixed-upward graphs (e.g., UML class diagrams).

Optional parameters

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

OptionTypeDefaultDescription
separateDeg0Layerbooltrue If set to true, isolated nodes are placed on a separate layer.
separateMultiEdgesbooltrue If set to true, multi-edges will span at least two layers.
optimizeEdgeLengthbooltrue If set to true the ranking algorithm tries to reduce edge length even if this might increase the height of the layout. Choose false if the longest-path ranking known from the literature shall be used.
alignBaseClassesboolfalse If set to true, base classes (in UML class diagrams) are aligned on the same layer (callUML only).
alignSiblingsboolfalse If set to true, siblings in inheritance trees are aligned on the same layer (callUML only).

Module options

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

Definition at line 96 of file LongestPathRanking.h.

Constructor & Destructor Documentation

◆ LongestPathRanking()

ogdf::LongestPathRanking::LongestPathRanking ( )

Creates an instance of longest-path ranking.

Member Function Documentation

◆ alignBaseClasses() [1/2]

bool ogdf::LongestPathRanking::alignBaseClasses ( ) const
inline

Returns the current setting of alignment of base classes (callUML only).

Definition at line 192 of file LongestPathRanking.h.

◆ alignBaseClasses() [2/2]

void ogdf::LongestPathRanking::alignBaseClasses ( bool  b)
inline

Sets the option for alignment of base classes to b.

Definition at line 195 of file LongestPathRanking.h.

◆ alignSiblings() [1/2]

bool ogdf::LongestPathRanking::alignSiblings ( ) const
inline

Returns the current setting of option for alignment of siblings.

Definition at line 198 of file LongestPathRanking.h.

◆ alignSiblings() [2/2]

void ogdf::LongestPathRanking::alignSiblings ( bool  b)
inline

Sets the option for alignment of siblings to b.

Definition at line 201 of file LongestPathRanking.h.

◆ call() [1/3]

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

Computes a node ranking of G with given minimal edge length in rank.

Parameter cost is just ignored by the implementation.

Parameters
Gis the input graph.
lengthspecifies the minimal length of each edge.
costspecifies the edge costs (ignored)
rankis assigned the rank (layer) of each node.

Reimplemented from ogdf::RankingModule.

Definition at line 141 of file LongestPathRanking.h.

◆ call() [2/3]

void ogdf::LongestPathRanking::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::LongestPathRanking::call ( const Graph G,
NodeArray< int > &  rank 
)
overridevirtual

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

◆ callUML()

void ogdf::LongestPathRanking::callUML ( const GraphAttributes AG,
NodeArray< int > &  rank 
)

Call for UML graphs with special treatement of inheritance hierarchies.

◆ dfs()

void ogdf::LongestPathRanking::dfs ( node  v)
private

◆ dfsAdd()

void ogdf::LongestPathRanking::dfsAdd ( node  v,
NodeArray< int > &  rank 
)
private

◆ doCall()

void ogdf::LongestPathRanking::doCall ( const Graph G,
NodeArray< int > &  rank,
EdgeArray< bool > &  reversed,
const EdgeArray< int > &  length 
)
private

Implements the algorithm call.

◆ getTmpRank()

void ogdf::LongestPathRanking::getTmpRank ( node  v,
NodeArray< int > &  rank 
)
private

◆ join()

void ogdf::LongestPathRanking::join ( GraphCopySimple GC,
NodeArray< node > &  superNode,
NodeArray< SListPure< node > > &  joinedNodes,
node  v,
node  w 
)
private

◆ optimizeEdgeLength() [1/2]

bool ogdf::LongestPathRanking::optimizeEdgeLength ( ) const
inline

Returns the current setting of option optimizeEdgeLength.

If set to true the ranking algorithm tries to reduce edge length even if this might increase the height of the layout. Choose false if the longest-path ranking known from the literature shall be used.

Definition at line 186 of file LongestPathRanking.h.

◆ optimizeEdgeLength() [2/2]

void ogdf::LongestPathRanking::optimizeEdgeLength ( bool  b)
inline

Sets the option optimizeEdgeLength to b.

Definition at line 189 of file LongestPathRanking.h.

◆ separateDeg0Layer() [1/2]

bool ogdf::LongestPathRanking::separateDeg0Layer ( ) const
inline

Returns the current setting of option separateDeg0Layer.

If set to true, isolated nodes are placed on a separate layer.

Definition at line 163 of file LongestPathRanking.h.

◆ separateDeg0Layer() [2/2]

void ogdf::LongestPathRanking::separateDeg0Layer ( bool  sdl)
inline

Sets the option separateDeg0Layer to sdl.

Definition at line 166 of file LongestPathRanking.h.

◆ separateMultiEdges() [1/2]

bool ogdf::LongestPathRanking::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 174 of file LongestPathRanking.h.

◆ separateMultiEdges() [2/2]

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

Sets the option separateMultiEdges to b.

Definition at line 177 of file LongestPathRanking.h.

◆ setSubgraph()

void ogdf::LongestPathRanking::setSubgraph ( AcyclicSubgraphModule pSubgraph)
inline

Sets the module for the computation of the acyclic subgraph.

Definition at line 210 of file LongestPathRanking.h.

Member Data Documentation

◆ m_adjacent

NodeArray<SListPure<Tuple2<node,int> > > ogdf::LongestPathRanking::m_adjacent
private

Definition at line 108 of file LongestPathRanking.h.

◆ m_alignBaseClasses

bool ogdf::LongestPathRanking::m_alignBaseClasses
private

Align base classes (callUML only).

Definition at line 102 of file LongestPathRanking.h.

◆ m_alignSiblings

bool ogdf::LongestPathRanking::m_alignSiblings
private

Align siblings (callUML only).

Definition at line 103 of file LongestPathRanking.h.

◆ m_finished

NodeArray<bool> ogdf::LongestPathRanking::m_finished
private

Definition at line 107 of file LongestPathRanking.h.

◆ m_ingoing

NodeArray<int> ogdf::LongestPathRanking::m_ingoing
private

Definition at line 109 of file LongestPathRanking.h.

◆ m_isSource

NodeArray<bool> ogdf::LongestPathRanking::m_isSource
private

Definition at line 107 of file LongestPathRanking.h.

◆ m_maxN

int ogdf::LongestPathRanking::m_maxN
private

Definition at line 105 of file LongestPathRanking.h.

◆ m_offset

int ogdf::LongestPathRanking::m_offset
private

Definition at line 105 of file LongestPathRanking.h.

◆ m_optimizeEdgeLength

bool ogdf::LongestPathRanking::m_optimizeEdgeLength
private

Optimize for short edges.

Definition at line 101 of file LongestPathRanking.h.

◆ m_separateMultiEdges

bool ogdf::LongestPathRanking::m_separateMultiEdges
private

Separate multi-edges?

Definition at line 100 of file LongestPathRanking.h.

◆ m_sepDeg0

bool ogdf::LongestPathRanking::m_sepDeg0
private

Put isolated nodes on a separate layer?

Definition at line 99 of file LongestPathRanking.h.

◆ m_subgraph

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

The acyclic sugraph module.

Definition at line 98 of file LongestPathRanking.h.


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