Reduced Digraphs ( ReducedDigraph )

Baseclasses

Definition

The module ReducedDigraph computes a reduced subgraph G' = (V, E) of an acyclic directed input graph G = (V, E $\cup$ F), i.e., F is the set of all transitive edges in G. We say that (v, w) $\in$ G is a transitive edge iff there is a directed path v = v₁,..., v_k = w in G with k > = 3. Thus, self-loops are not considered to be transitive edges. The output graph G' may contain self-loops or multiple edges.

The algorithm performs a depth first search for each node v in order to determine all nodes V(v) which can be reached from v by a directed path of at least three nodes. All edges (v, w) with w $\in$ V(v) are transitive edges.

General Information

Algorithm
name	Reduced Digraph
long name	Reduced Digraph
author

Implementation
author	C. Gutwenger
date	Decembre 1998
version	1.0

Pre- and Postcondition

precondition	=	{directed, acyclic}
postcondition(PRE)	=	{reducedacyclic}

#include < AGD/ReducedDigraph.h >

Creation

ReducedDigraph

S

creates an instance S of type ReducedDigraph.

Operations

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

bool	S.check(const graph& G, AgdKey& p)
bool	S.call(const graph& G, list<edge>& L)
bool	S.call(graph& G)
bool	S.call(GraphCopy& G, list<edge>& L)
int	S.num_del_edges()

Implementation

The algorithm has running time $\protectO$(n(n + m)), where n is the number of nodes and m is the number of edges of the input graph G.