tarjan.h File Reference

#include <stddef.h>

Include dependency graph for tarjan.h:

Go to the source code of this file.

Classes
struct	TarjanComponent

Functions
struct TarjanWorkSpace *	create_tarjan_workspace (const size_t nvert)
void	destroy_tarjan_workspace (struct TarjanWorkSpace *ws)
void	destroy_tarjan_sccresult (struct TarjanSCCResult *scc)
size_t	tarjan_get_numcomponents (const struct TarjanSCCResult *scc)
struct TarjanComponent	tarjan_get_strongcomponent (const struct TarjanSCCResult *scc, const size_t compID)
struct TarjanSCCResult *	tarjan (const size_t nv, const size_t *ia, const int *ja)

Detailed Description

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

Function Documentation

create_tarjan_workspace()

struct TarjanWorkSpace * create_tarjan_workspace

(

const size_t

nvert

)

Create work-space for Tarjan algorithm on graph with specified number of nodes (vertices).

Parameters

[in]

nvert

Number of graph vertices.

Returns

Backing store for intermediate data created during SCC processing. NULL in case of allocation failure. Dispose of work-space using function destroy_tarjan_workspace().

destroy_tarjan_sccresult()

void destroy_tarjan_sccresult

(

struct TarjanSCCResult *

scc

)

Dispose of backing store for SCC result data.

Parameters

[in,out]

scc

SCC result data from a previous call to function tarjan() or tarjan_reachable_sccs(). Invalid upon return.

destroy_tarjan_workspace()

void destroy_tarjan_workspace

(

struct TarjanWorkSpace *

ws

)

Dispose of backing store for intermediate SCC/Tarjan data.

Parameters

[in,out]

ws

Work-space structure procured in a previous call to function create_tarjan_workspace(). Invalid upon return.

tarjan()

struct TarjanSCCResult * tarjan	(	const size_t	nv,
		const size_t *	ia,
		const int *	ja
	)

Compute the strongly connected components of a directed graph, .

The components are returned in reverse topological sorted sequence.

Parameters

[in]	nv	Number of graph vertices.
[in]	ia	CSR sparse matrix start pointers corresponding to downstream vertices.
[in]	ja	CSR sparse matrix representation of out-neighbours in a directed graph: vertex i has directed edges to vertices ja[ia[i]], ..., ja[ia[i + 1] - 1] .

Returns

Strong component result dataset. Owning pointer. Dispose of associate memory by calling the destructor destroy_tarjan_sccresult(). Returns NULL in case of failure to allocate the result set or internal work-space.

tarjan_get_numcomponents()

size_t tarjan_get_numcomponents

(

const struct TarjanSCCResult *

scc

)

Retrieve number of strong components in result dataset.

Parameters

[in]

scc

Collection of strongly connected components obtained from a previous call to function tarjan() or tarjan_reachable_sccs().

Returns

Number of strong components in result dataset.

tarjan_get_strongcomponent()

struct TarjanComponent tarjan_get_strongcomponent	(	const struct TarjanSCCResult *	scc,
		const size_t	compID
	)

Get access to single strong component from SCC result dataset.

Parameters

[in]	scc	Collection of strongly connected components obtained from a previous call to function tarjan() or tarjan_reachable_sccs().
[in]	compID	Linear ID of single strong component. Must be in the range [0 .. tarjan_get_numcomponents(scc) - 1] .

Returns

Single strong component corresponding to explicit linear ID.