ogdf::CoffmanGrahamRanking Class Reference

The coffman graham ranking algorithm. More...

#include <ogdf/layered/CoffmanGrahamRanking.h>

Inheritance diagram for ogdf::CoffmanGrahamRanking:

List of all members.

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
void	call (const Graph &G, NodeArray< int > &rank)
	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< Tuple2< node, int > > &ready_nodes)
void	insert (node u, List< node > &ready, const NodeArray< int > &pi)
void	removeTransitiveEdges (Graph &G)

Private Attributes
NodeArray< _int_set >	m_s
ModuleOption < AcyclicSubgraphModule >	m_subgraph
int	m_w
NodeArray< int >	mark
StackPure< node > *	visited

---

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 69 of file CoffmanGrahamRanking.h.

---

Constructor & Destructor Documentation

ogdf::CoffmanGrahamRanking::CoffmanGrahamRanking

(

)

Creates an instance of coffman graham ranking.

---

Member Function Documentation

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

virtual

Computes a node ranking of G in rank.

Implements ogdf::RankingModule.

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

private

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

private

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

private

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

private

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

inline

Sets the module for the computation of the acyclic subgraph.

Definition at line 91 of file CoffmanGrahamRanking.h.

int ogdf::CoffmanGrahamRanking::width ( ) const

inline

Get for the with.

Definition at line 98 of file CoffmanGrahamRanking.h.

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

inline

Set for the with.

Definition at line 103 of file CoffmanGrahamRanking.h.

---

Member Data Documentation

NodeArray<_int_set> ogdf::CoffmanGrahamRanking::m_s

private

Definition at line 149 of file CoffmanGrahamRanking.h.

ModuleOption<AcyclicSubgraphModule> ogdf::CoffmanGrahamRanking::m_subgraph

private

Definition at line 147 of file CoffmanGrahamRanking.h.

int ogdf::CoffmanGrahamRanking::m_w

private

Definition at line 148 of file CoffmanGrahamRanking.h.

NodeArray<int> ogdf::CoffmanGrahamRanking::mark

private

Definition at line 152 of file CoffmanGrahamRanking.h.

StackPure<node>* ogdf::CoffmanGrahamRanking::visited

private

Definition at line 153 of file CoffmanGrahamRanking.h.

---

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

• ogdf/layered/CoffmanGrahamRanking.h