Simple implementation of of Tarjan's algorithm for computing the strongly connected components of a directed graph, .
More...
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) |
Compute the strongly connected components of a directed graph, ![]() | |
Simple implementation of of Tarjan's algorithm for computing the strongly connected components of a directed graph, .
Run-time complexity is .
The implementation is based on "http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm".
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, .
The components are returned in reverse topological sorted sequence.
[in] | nv | Number of graph vertices. |
[in] | ia | |
[in] | ja | adjacency 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] | vert | Permutation of vertices into topologically sorted sequence of strong components (i.e., loops). Array of size nv . |
[out] | comp | Pointers 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] | ncomp | Number of strong components. Pointer to a single int . |
[out] | work | Pointer to a scratch array represented as a block of memory capable of holding 3 * nv elements of type int . |