The Gabow class

Class implementing Gabow’s [Gab00] algorithm for computing strongly connected components of a WordGraph.

Instances of this class can be used to compute, and provide information about, the strongly connected components of the WordGraph used to construct the instance. The strongly connected components are lazily evaluated when triggered by a relevant member function. The complexity of Gabow’s algorithm is at most \(O(mn)\) where m is WordGraph.number_of_nodes() and n is WordGraph.out_degree().

Contents

Gabow	Class implementing Gabow's [Gab00] algorithm for computing strongly connected components of a WordGraph.
Gabow.component(…)	Returns a list containing the strongly connected component with given index.
Gabow.component_of(…)	Returns a list containing the strongly connected component of a given node.
Gabow.components(…)	This function returns a list of lists containing all of the strongly connected components of the WordGraph (returned by Gabow.word_graph) used to construct the Gabow instance.
Gabow.copy(…)	Copy a Gabow object.
Gabow.has_components(…)	Check whether the strongly connected components have been found.
Gabow.id(…)	Returns the id-number of the strongly connected component of a node.
Gabow.init(…)	This function re-initializes a Gabow object so that it is in the same state as if it had just been constructed from wg.
Gabow.number_of_components(…)	This function returns the number of strongly connected components of the underlying WordGraph (returned by Gabow.word_graph).
Gabow.reverse_spanning_forest(…)	This function returns a Forest comprised of spanning trees for each strongly connected component of a Gabow object, rooted on the minimum node of that component, with edges oriented towards the root.
Gabow.root_of(…)	Returns the root of the strongly connected component containing a given node.
Gabow.roots(…)	Returns an iterator yielding the roots of the strongly connected components of the underlying word graph.
Gabow.spanning_forest(…)	Returns a spanning forest of the strongly connected components.
Gabow.word_graph(…)	This function returns the underlying word graph.

Full API

class Gabow

__init__(self: Gabow, wg: WordGraph) → None

Construct a Gabow from a WordGraph.

This function constructs a Gabow object from a WordGraph wg.

Parameters:

wg (WordGraph) – the WordGraph to construct from.

component(self: Gabow, i: int) → list[int]

Returns a list containing the strongly connected component with given index.

This function returns a list containing the strongly connected components with index i of the WordGraph (returned by Gabow.word_graph) used to construct the Gabow instance.

Parameters:

i (int) – the index of a strongly connected component.

Returns:

The component with index i.

Return type:

list[int]

Raises:

LibsemigroupsError – if there is i is greater than or equal to number_of_components.

Note

This function triggers the computation of the strongly connected components (if they are not already known).

See also

component_of to obtain the component of a node.

component_of(self: Gabow, n: int) → list[int]

Returns a list containing the strongly connected component of a given node.

This function returns a list containing the strongly connected components of the node n of the WordGraph (returned by Gabow.word_graph ) used to construct the Gabow instance.

Parameters:

n (int) – the node.

Returns:

The component of the node n.

Return type:

list[int]

Raises:

LibsemigroupsError – if n is greater than or equal to word_graph().number_of_nodes().

Note

This function triggers the computation of the strongly connected components (if they are not already known).

components(self: Gabow) → list[list[int]]

This function returns a list of lists containing all of the strongly connected components of the WordGraph (returned by Gabow.word_graph) used to construct the Gabow instance.

Returns:

The strongly connected components of Gabow.word_graph.

Return type:

list[list[int]]

Note

This function triggers the computation of the strongly connected components (if they are not already known).

copy(self: Gabow) → Gabow

Copy a Gabow object.

Returns:

A copy.

Return type:

Gabow

has_components(self: Gabow) → bool

Check whether the strongly connected components have been found. This function returns True if the strongly connected components of a Gabow object have already been computed and False if not.

Returns:

Whether or not the strongly connected components have been found already.

Return type:

bool

id(self: Gabow, n: int) → int

Returns the id-number of the strongly connected component of a node. This function can be used to determine the id-number of the node n in the underlying graph of a Gabow instance.

Parameters:

n (int) – the node.

Returns:

The id-number of the strongly connected component of n.

Return type:

int

Raises:

LibsemigroupsError – if n is greater than or equal to word_graph().number_of_nodes().

Note

This function triggers the computation of the strongly connected components (if they are not already known).

init(self: Gabow, wg: WordGraph) → Gabow

This function re-initializes a Gabow object so that it is in the same state as if it had just been constructed from wg.

Parameters:

wg (WordGraph) – The word graph.

Returns:

self.

Return type:

Gabow

number_of_components(self: Gabow) → int

This function returns the number of strongly connected components of the underlying WordGraph (returned by Gabow.word_graph).

Returns:

The number of strongly connected components.

Return type:

int

Note

This function triggers the computation of the strongly connected components (if they are not already known).

reverse_spanning_forest(self: Gabow) → Forest

This function returns a Forest comprised of spanning trees for each strongly connected component of a Gabow object, rooted on the minimum node of that component, with edges oriented towards the root.

Returns:

A reverse spanning forest for the underlying word graph.

Return type:

Forest

Note

This function triggers the computation of the strongly connected components (if they are not already known).

root_of(self: Gabow, n: int) → int

Returns the root of the strongly connected component containing a given node.

This function returns the root of the strongly connected component containing the node n of the underlying WordGraph. Two nodes a and b belong to the same strongly connected component if and only if root_of(a) == root_of(b).

Parameters:

n (int) – the node.

Returns:

The root of the strongly connected component containing the node n.

Return type:

int

Raises:

LibsemigroupsError – if n is greater than or equal to WordGraph.number_of_nodes of the underlying word graph.

Note

This function triggers the computation of the strongly connected components (if they are not already known).

roots(self: Gabow) → collections.abc.Iterator[int]

Returns an iterator yielding the roots of the strongly connected components of the underlying word graph.

Returns:

An iterator to the roots.

Return type:

collections.abc.Iterator[int]

Note

This function triggers the computation of the strongly connected components (if they are not already known).

spanning_forest(self: Gabow) → Forest

Returns a spanning forest of the strongly connected components. This function returns a Forest comprised of spanning trees for each strongly connected component of a Gabow object, rooted on the minimum node of that component, with edges oriented away from the root.

Returns:

A spanning forest for the underlying word graph.

Return type:

Forest

Note

This function triggers the computation of the strongly connected components (if they are not already known).

word_graph(self: Gabow) → WordGraph

This function returns the underlying word graph.

Returns:

The underlying word graph.

Return type:

WordGraph