Functions
tarjan.h File Reference

Go to the source code of this file.

Functions

void tarjan (int nv, const int *ia, const int *ja, int *vert, int *comp, int *ncomp, int *work)
 

Detailed Description

Simple implementation of of Tarjan's algorithm for computing the strongly connected components of a directed graph, $G(V,E)$. Run-time complexity is $O(|V| + |E|)$.

The implementation is based on "http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm".

Function Documentation

void tarjan ( int  nv,
const int *  ia,
const int *  ja,
int *  vert,
int *  comp,
int *  ncomp,
int *  work 
)

Compute the strongly connected components of a directed graph, $G(V,E)$.

The components are returned in reverse topological sorted sequence.

Parameters
[in]nvNumber of graph vertices.
[in]ia
[in]jaadjacency matrix for directed graph in compressed sparse row format: vertex i has directed edges to vertices ja[ia[i]], ..., ja[ia[i+1]-1].
[out]vertPermutation of vertices into topologically sorted sequence of strong components (i.e., loops). Array of size nv.
[out]compPointers to start of each strongly connected component in vert, the i'th component has vertices vert[comp[i]], ..., vert[comp[i+1] - 1]. Array of size nv + 1.
[out]ncompNumber of strong components. Pointer to a single int.
[out]workPointer to a scratch array represented as a block of memory capable of holding 3 * nv elements of type int.