Ranking to Minimize Height ( LongestPathRanking )

Baseclasses

Definition

The LongestPathRanking 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 satisfying

• If v, w are two nodes in G' with v is a source, w is a sink, and there is a path from v to w in G', then exists also a path v = u₁,..., u_p = w with rank(u_{i + 1}) = 1 + rank(u_i) for 1 < = i < p.
• min{rank(v) | v $\in$ V} = 0

Hence, the so-computed ranking of the acyclic graph G' uses the minimum number of layers, that is, the height of the layering is minimal if we constrain each edge in G' to run downward. Optionally, all nodes with degree 0 can be placed on a separate layer.

General Information

Algorithm
name	Longest-Path Ranking
long name	Longest-Path Ranking
author

Implementation
author	C. Gutwenger
date	May 1998
version	1.0

Pre- and Postcondition

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

Exchangeable Modules Instances of type LongestPathRanking 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 LongestPathRanking provide the following optional parameters:

$\bullet$

bool separate_deg0_layer = true
a boolean value determining if the nodes with degree 0 are placed on a separate layer, i.e., they get the highest rank.

#include < AGD/LongestPathRanking.h >

Creation

LongestPathRanking

R(bool sdl = true)

creates an instance R of type LongestPathRanking. Sets the option separate_deg0_layer to sdl.

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)
bool	R.separate_deg0_layer()
void	R.separate_deg0_layer(bool sdl)

Implementation

The computation of the ranking takes time $\protectO$(| V| + | E|).