Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

The coffman graham ranking algorithm. More...

#include <ogdf/layered/CoffmanGrahamRanking.h>

+ Inheritance diagram for ogdf::CoffmanGrahamRanking:

Classes

class  _int_set
 

Public Member Functions

 CoffmanGrahamRanking ()
 Creates an instance of coffman graham ranking. More...
 
int width () const
 Get for the with. More...
 
void width (int w)
 Set for the with. More...
 
Algorithm call
virtual void call (const Graph &G, NodeArray< int > &rank) override
 Computes a node ranking of G in rank. 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 ()
 
virtual void call (const Graph &G, const EdgeArray< int > &, const EdgeArray< int > &, NodeArray< int > &rank)
 
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 insert (node u, List< node > &ready, const NodeArray< int > &pi)
 
void insert (node u, List< Tuple2< node, int > > &ready_nodes)
 
void removeTransitiveEdges (Graph &G)
 

Private Attributes

NodeArray< int > m_mark
 
NodeArray< _int_setm_s
 
std::unique_ptr< AcyclicSubgraphModulem_subgraph
 
int m_w
 

Detailed Description

The coffman graham ranking algorithm.

The class CoffmanGrahamRanking implements a node ranking algorithmn based on the coffman graham scheduling algorithm, which can be used as first phase in SugiyamaLayout. The aim of the algorithm is to ensure that the height of the ranking (the number of layers) is kept small.

Definition at line 52 of file CoffmanGrahamRanking.h.

Constructor & Destructor Documentation

◆ CoffmanGrahamRanking()

ogdf::CoffmanGrahamRanking::CoffmanGrahamRanking ( )

Creates an instance of coffman graham ranking.

Member Function Documentation

◆ call()

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

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

◆ dfs()

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

◆ insert() [1/2]

void ogdf::CoffmanGrahamRanking::insert ( node  u,
List< node > &  ready,
const NodeArray< int > &  pi 
)
private

◆ insert() [2/2]

void ogdf::CoffmanGrahamRanking::insert ( node  u,
List< Tuple2< node, int > > &  ready_nodes 
)
private

◆ removeTransitiveEdges()

void ogdf::CoffmanGrahamRanking::removeTransitiveEdges ( Graph G)
private

◆ setSubgraph()

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

Sets the module for the computation of the acyclic subgraph.

Definition at line 74 of file CoffmanGrahamRanking.h.

◆ width() [1/2]

int ogdf::CoffmanGrahamRanking::width ( ) const
inline

Get for the with.

Definition at line 81 of file CoffmanGrahamRanking.h.

◆ width() [2/2]

void ogdf::CoffmanGrahamRanking::width ( int  w)
inline

Set for the with.

Definition at line 86 of file CoffmanGrahamRanking.h.

Member Data Documentation

◆ m_mark

NodeArray<int> ogdf::CoffmanGrahamRanking::m_mark
private

Definition at line 137 of file CoffmanGrahamRanking.h.

◆ m_s

NodeArray<_int_set> ogdf::CoffmanGrahamRanking::m_s
private

Definition at line 134 of file CoffmanGrahamRanking.h.

◆ m_subgraph

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

Definition at line 132 of file CoffmanGrahamRanking.h.

◆ m_w

int ogdf::CoffmanGrahamRanking::m_w
private

Definition at line 133 of file CoffmanGrahamRanking.h.


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