graphs_tarjan.h File Reference

Implementation of Tarjan's algorithm. More...

#include "type_partitions.h"
#include "graphs.h"
#include <stdbool.h>

Go to the source code of this file.

Functions
parti *	tarjan (graph *g)
	Tarjan's algorihtm for unlabeled graphs.
parti *	ltarjan (lgraph *g, bool *alph)
	Tarjan's algorihtm for labeled graphs.
parti *	dtarjan (dgraph *g, bool *alph, bool ismor)
	Tarjan's algorihtm for complete deterministic labeled graphs.
parti *	dualdtarjan (dgraph *g1, dgraph *g2, bool *alph, bool ismor)
	Tarjan's algorihtm for two complete deterministic labeled graphs sharing the same state set and alphabet. Computation is done in the merge of the two graphs.
dgraph *	dgraph_extract (dgraph *g, parti *P, uint *inv, uint j)
	Extracts a single SCC of a dgraph and makes it a new dgraph.
void	dgraph_compute_alph_scc (dgraph *g, parti *sccs, uint scc, bool *alph)
	Computes the alphabet of a strongly connected component of a labeled graph.
bool	dgraph_common_alph_loop (dgraph *g, parti *sccs, uint *inv_sccs, uint q1, uint q2, bool *alph)
	Computes the alphabet of a strongly connected component of a labeled graph.
void	dgraph_discard_nonscc_edges (dgraph *g, parti *sccs)
	Modifies a dgraph by discarding all edges that are not internal to an SCC.
dgraph *	dgraph_copy_discard_nonscc_edges (dgraph *g, parti *sccs)
	Copies a dgraph while discarding all edges that go from a state to a different SCC.
bool	dgraph_ntrivial_loop (dgraph *g, parti *sccs, uint q)
	Tests if there exists a non-trivial loop on a given state q of a dgraph.

Detailed Description

Implementation of Tarjan's algorithm.

Function Documentation

dgraph_common_alph_loop()

bool dgraph_common_alph_loop	(	dgraph *	g,
		parti *	sccs,
		uint *	inv_sccs,
		uint	q1,
		uint	q2,
		bool *	alph )

Computes the alphabet of a strongly connected component of a labeled graph.

Remarks

The alphabet is computed as an array of Booleans indexed by the letters. If a letter is in the alphabet, the corresponding cell is set to true.

Returns

True if the alphabet is not empty, false otherwise.

Parameters

g	The graph.
sccs	The partition of the graph into strongly connected components.
inv_sccs	The inverse mapping of the partition.
q1	The index of the state in the first SCC.
q2	The index of the state in the second SCC.
alph	The alphabet of the SCC (an array indexed by the letters).

dgraph_compute_alph_scc()

void dgraph_compute_alph_scc	(	dgraph *	g,
		parti *	sccs,
		uint	scc,
		bool *	alph )

Computes the alphabet of a strongly connected component of a labeled graph.

Remarks

The alphabet is computed as an array of Booleans indexed by the letters. This array muste be allocated by the caller and must have a size equal to the number of labels in the graph.

Parameters

g	The graph.
sccs	The partition of the graph into strongly connected components.
scc	The index of the SCC.
alph	The array used to store the computed alphabet (an array indexed by the letters).

dgraph_copy_discard_nonscc_edges()

dgraph * dgraph_copy_discard_nonscc_edges	(	dgraph *	g,
		parti *	sccs )

Copies a dgraph while discarding all edges that go from a state to a different SCC.

Returns

A pointer to the resulting dgraph.

Parameters

g	The dgraph to copy.
sccs	The SCCs of the dgraph.

dgraph_discard_nonscc_edges()

void dgraph_discard_nonscc_edges	(	dgraph *	g,
		parti *	sccs )

Modifies a dgraph by discarding all edges that are not internal to an SCC.

Remarks

Discarded edges are give the destination value UINT_MAX.

Parameters

g	The dgraph to modify.
sccs	The partition of the dgraph into sccs.

dgraph_extract()

dgraph * dgraph_extract	(	dgraph *	g,
		parti *	P,
		uint *	inv,
		uint	j )

Extracts a single SCC of a dgraph and makes it a new dgraph.

Returns

A pointer to the extracted dgraph.

Parameters

g	The dgraph to extract the SCC from.
P	The partition of the dgraph.
inv	The inverse mapping of the partition.
j	The index of the SCC to extract.

dgraph_ntrivial_loop()

bool dgraph_ntrivial_loop	(	dgraph *	g,
		parti *	sccs,
		uint	q )

Tests if there exists a non-trivial loop on a given state q of a dgraph.

Remarks

This function checks if the scc of q contains at least two states or if there is an edge from q to itself labeled by a letter in the alphabet.

Returns

A Boolean indicating whether there exists a non-trivial loop on the state q.

Parameters

g	The dgraph to test.
sccs	The SCCs of the dgraph.
q	The state q.

dtarjan()

parti * dtarjan	(	dgraph *	g,
		bool *	alph,
		bool	ismor )

Tarjan's algorihtm for complete deterministic labeled graphs.

Remarks

The classes are sorted in topological order.

Returns

The partition of the graph into strongly connected components.

Parameters

g	The complete deterministic labeled graph.
alph	An array of Booleans indexed by the labels. Only the edges labeled by a letter marked true are considered. NULL means all labels are considered.
ismor	If true, the algorithm is run on a Cayley graph (all vertices are reachable from ONE = 0).

dualdtarjan()

parti * dualdtarjan	(	dgraph *	g1,
		dgraph *	g2,
		bool *	alph,
		bool	ismor )

Tarjan's algorihtm for two complete deterministic labeled graphs sharing the same state set and alphabet. Computation is done in the merge of the two graphs.

Remarks

The classes are sorted in topological order.

Returns

The partition of the graph into strongly connected components.

Parameters

g1	The first complete deterministic labeled graph.
g2	The second complete deterministic labeled graph.
alph	An array of Booleans indexed by the labels. Only the edges labeled by a letter marked true are considered. NULL means all labels are considered.
ismor	If true, the algorithm is run on Cayley graphs (all vertices are reachable from ONE = 0).

ltarjan()

parti * ltarjan	(	lgraph *	g,
		bool *	alph )

Tarjan's algorihtm for labeled graphs.

Remarks

The classes are sorted in topological order.

Returns

The partition of the graph into strongly connected components.

Parameters

g	The labeled graph.
alph	An array of Booleans indexed by the labels. Only the edges labeled by a letter marked true are considered. NULL means all labels are considered.

tarjan()

parti * tarjan

(

graph *

g

)

Tarjan's algorihtm for unlabeled graphs.

Remarks

The classes are sorted in topological order.

Returns

The partition of the graph into strongly connected components.

Parameters

g	The unlabeled graph.