ogdf::CoffmanGrahamRanking Class Reference

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.
int	width () const
	Get for the with.
void	width (int w)
	Set for the with.
Algorithm call
virtual void	call (const Graph &G, NodeArray< int > &rank) override
	Computes a node ranking of G in rank.
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 ()
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.

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_set >	m_s
std::unique_ptr< AcyclicSubgraphModule >	m_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 53 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 73 of file CoffmanGrahamRanking.h.

width() [1/2]

int ogdf::CoffmanGrahamRanking::width ( ) const

inline

Get for the with.

Definition at line 78 of file CoffmanGrahamRanking.h.

width() [2/2]

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

inline

Set for the with.

Definition at line 81 of file CoffmanGrahamRanking.h.

Member Data Documentation

m_mark

NodeArray<int> ogdf::CoffmanGrahamRanking::m_mark

private

Definition at line 127 of file CoffmanGrahamRanking.h.

m_s

NodeArray<_int_set> ogdf::CoffmanGrahamRanking::m_s

private

Definition at line 124 of file CoffmanGrahamRanking.h.

m_subgraph

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

private

Definition at line 122 of file CoffmanGrahamRanking.h.

m_w

int ogdf::CoffmanGrahamRanking::m_w

private

Definition at line 123 of file CoffmanGrahamRanking.h.

---

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

• include/ogdf/layered/CoffmanGrahamRanking.h