Ranking with Predefined Width ( CoffmanGrahamRanking )

Baseclasses

Definition

The CoffmanGrahamRanking module computes the following ranking of a graph G = (V, E): First, a feedback set R $\subset$ E is computed, that is, the graph G' resulting from G by reversing all the edges in R is acyclic. In this step, self-loops are simply ignored. For this purpose, we use a subgraph module that computes a maximal acyclic subgraph (that also implies a feedback set R). Then, we compute a ranking with width at most W, in which all edges in G' run downwards. The width of a ranking is the maximal number of vertices on the same layer. Notice that we do not consider dummy vertices at this stage, which are created later when using a ranking with SugiyamaLayout.

The algorithm [CG72] is actually from the theory of multiprocessor scheduling. The relation to the rank assignment problem is shown, e.g., in [DETT99]. The aim of the algorithm is to ensure that the height of the ranking (the number of layers) is kept small. The following performance guarantee is shown in [LS77]: Let h_min be the minimum height of a ranking of width W. Then the height h of the ranking computed by CoffmanGrahamRanking satisfies

$h\leq\left(2-\frac{2}{W}\right) h_{min}$
For W = 2 the height of the ranking is optimal, i.e., h = h_min.

General Information

Algorithm
name	Coffman-Graham Ranking
long name	Coffman-Graham Ranking
author

Implementation
author	C. Gutwenger
date	Decembre 1998
version	1.0

Pre- and Postcondition

precondition	=	{ directed }
postcondition(PRE)	=	$\emptyset$

Exchangeable Modules

Instances of type CoffmanGrahamRanking provide the following module options:

$\bullet$

subgraph
an SubgraphModule option used for computing a maximal acyclic subgraph.

guaranteed precondition:	{directed}
required postcondition:	$\{\emph{ directed, maximal{\_}acyclic }\}$
initial module:	LEDAMakeAcyclic

Optional Parameters

Instances of CoffmanGrahamRanking provide the following optional parameters:

$\bullet$

int width = 3
the maximal number W of vertices on the same layer.

#include < AGD/CoffmanGrahamRanking.h >

Creation

CoffmanGrahamRanking

R

creates an instance R of type CoffmanGrahamRanking.

Operations

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base class (RankAssignment).

bool	R.check(const leda_graph& G, AgdKey& p)
void	R.call(const leda_graph& G, leda_node_array<int>& rank)

Access to Options

bool	R.set_subgraph(const SubgraphModule& M)
int	R.width()
void	R.width(int w)

Implementation

In a preprocessing step, we make G acyclic using the module option subgraph. Then, we delete all transitive edges with ReducedDigraph. This takes time $\protectO$(n(n + m)). The actual Coffman-Graham algorithm (applied to the reduced digraph) takes time $\protectO$(n²).