Ranking by Depth First Search ( DfsRanking )

Baseclasses

Definition

The DfsRanking module computes the following ranking of a graph G: We build a DFS forest T of the underlying undirected graph of G and set

$rank(v) = \left\{\begin{array}{cl} 0 & \mbox{if }v\mbox{ is a root of }T\\ rank(pred(v))+1 & \mbox{otherwise} \end{array}\right.$
where pred (v) is the predecessor of v in T. Notice, that DfsRanking only considers the underlying undirected graph and therefore does not take into account edge directions.

General Information

Algorithm
name	DFS-Ranking
long name	DFS-Ranking
author

Implementation
author	C. Gutwenger
date	February 1998
version	1.0

Pre- and Postcondition

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

#include < AGD/DfsRanking.h >

Creation

DfsRanking

R

creates an instance R of type DfsRanking.

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)

Implementation

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