template<typename Node>
class libsemigroups::Gabow< Node >

Defined in gabow.hpp.

This page contains class implements Gabow's algorithm [23] for computing the 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 out_degree().

Template Parameters

Node	the type of the nodes of the underlying WordGraph.

Public Types
using	label_type = typename WordGraph<node_type>::label_type
	Type of the edge labels in the underlying WordGraph.

using	node_type = Node
	Type of the nodes in the underlying WordGraph.

using	size_type = size_t
	Size type used for indices of strongly connected components.

Public Member Functions
	Gabow ()=delete
	Deleted.

	Gabow (Gabow &&)=default
	Default move constructor.

	Gabow (Gabow const &)=default
	Default copy constructor.

	Gabow (WordGraph< node_type > const &wg)
	Construct from WordGraph.

std::vector< node_type > const &	component (size_type i) const
	Returns a const reference to a vector containing the strongly connected component with given index.

std::vector< node_type >	component_no_checks (size_type i) const
	Returns a const reference to a vector containing the strongly connected component with given index.

std::vector< node_type > const &	component_of (node_type n) const
	Returns a const reference to a vector containing the strongly connected component of a given node.

std::vector< node_type > const &	component_of_no_checks (node_type n) const
	Returns a const reference to a vector containing the strongly connected component of a given node.

std::vector< std::vector< node_type > > const &	components () const
	Returns a const reference to a vector of vectors containing the strongly connected components.

bool	has_components () const noexcept
	Check whether the strongly connected components have been found.

size_type	id (node_type n) const
	Returns the id-number of the strongly connected component of a node.

size_type	id_no_checks (node_type n) const
	Get the id of a strongly connected component of a node.

Gabow &	init (WordGraph< node_type > const &wg)
	Reinitialize a Gabow object.

size_t	number_of_components () const
	Returns the number of strongly connected components.

Gabow &	operator= (Gabow &&)=default
	Default move assignment operator.

Gabow &	operator= (Gabow const &)=default
	Default copy assignment operator.

Forest const &	reverse_spanning_forest () const
	Returns a reverse spanning forest of the strongly connected components (if they are not already known).

node_type	root_of (node_type n) const
	Returns the root of the strongly connected component containing a given node.

node_type	root_of_no_checks (node_type n) const
	Returns the root of the strongly connected component containing a given node.

auto	roots () const
	Returns a range object consisting of roots of the strongly connected components.

Forest const &	spanning_forest () const
	Returns a spanning forest of the strongly connected components.

WordGraph< Node > const &	word_graph () const noexcept
	Returns a const reference to the underlying word graph.

Related Symbols
(Note that these are not member symbols.)
template<typename Node>
	Gabow (WordGraph< Node > const &) -> Gabow< Node >
	Deduction guide for Gabow objects.

template<typename Node>
std::string	to_human_readable_repr (Gabow< Node > const &g)
	Return a human readable representation of a Gabow object.

Constructor & Destructor Documentation

◆ Gabow() [1/4]

template<typename Node>

Gabow ( )

delete

To avoid the situation where the underlying WordGraph is not defined, it is not possible to default construct a Gabow object.

◆ Gabow() [2/4]

template<typename Node>

Gabow ( Gabow< Node > const & )

default

Default copy constructor.

◆ Gabow() [3/4]

template<typename Node>

Gabow ( Gabow< Node > && )

default

Default move constructor.

◆ Gabow() [4/4]

template<typename Node>

Gabow ( WordGraph< node_type > const & wg )

inlineexplicit

This function constructs a Gabow object from the WordGraph wg.

Note: This function does not trigger the computation of the strongly connected components.

Warning: The Gabow object only holds a reference to the underlying WordGraph wg, and so that object must outlive the corresponding Gabow object.

Member Function Documentation

◆ component()

template<typename Node>

std::vector< node_type > const & component ( size_type i ) const

inlinenodiscard

This function returns a const reference to a vector containing the strongly connected components with index i of the WordGraph (word_graph) used to construct the Gabow instance.

Parameters

i	the index of a strongly connected component.

Returns: A vector of node_type.

Exceptions

LibsemigroupsException if 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_no_checks()

template<typename Node>

std::vector< node_type > component_no_checks ( size_type i ) const

inlinenodiscard

This function returns a const reference to a vector containing the strongly connected components with index i of the WordGraph (word_graph) used to construct the Gabow instance.

Parameters

i	the index of a strongly connected component.

Returns: A vector of node_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

Warning: This function does not check that its argument i.

See also: component_of_no_checks to obtain the strongly connected component of a node.

◆ component_of()

template<typename Node>

std::vector< node_type > const & component_of ( node_type n ) const

inlinenodiscard

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

Parameters

n the node.

Returns: A vector of node_type.

Exceptions

LibsemigroupsException 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).

◆ component_of_no_checks()

template<typename Node>

std::vector< node_type > const & component_of_no_checks ( node_type n ) const

inlinenodiscard

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

Parameters

n the node.

Returns: A vector of node_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

Warning: This function does not check that its argument n.

◆ components()

template<typename Node>

std::vector< std::vector< node_type > > const & components ( ) const

inlinenodiscard

This function returns a const reference to a vector of vectors containing all of the strongly connected components of the WordGraph (word_graph) used to construct the Gabow instance.

Returns: A vector of vectors of node_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ has_components()

template<typename Node>

bool has_components ( ) const

inlinenodiscardnoexcept

This function returns true if the strongly connected components of a Gabow object have already been computed and false if not.

Returns: A bool.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ id()

template<typename Node>

size_type id ( node_type n ) const

inlinenodiscard

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

Parameters

n the node.

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

Exceptions

LibsemigroupsException 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).

◆ id_no_checks()

template<typename Node>

size_type id_no_checks ( node_type n ) const

inlinenodiscard

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

Parameters

n the node.

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

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

Warning: This function does not check that its argument n is actually a node of the underlying word graph.

◆ init()

template<typename Node>

Gabow & init ( WordGraph< node_type > const & wg )

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

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function does not trigger the computation of the strongly connected components.

Warning: The Gabow object only holds a reference to the underlying WordGraph wg, and so that object must outlive the corresponding Gabow object.

◆ number_of_components()

template<typename Node>

size_t number_of_components ( ) const

inlinenodiscard

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

Returns: A size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ operator=() [1/2]

template<typename Node>

Gabow & operator= ( Gabow< Node > && )

default

Default move assignment operator.

◆ operator=() [2/2]

template<typename Node>

Gabow & operator= ( Gabow< Node > const & )

default

Default copy assignment operator.

◆ reverse_spanning_forest()

template<typename Node>

Forest const & reverse_spanning_forest ( ) const

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 const reference to a Forest.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ root_of()

template<typename Node>

node_type root_of ( node_type n ) const

inlinenodiscard

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 the node.

Returns: The root of the strongly connected component containing the node n, a value of node_type.

Exceptions

LibsemigroupsException 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).

◆ root_of_no_checks()

template<typename Node>

node_type root_of_no_checks ( node_type n ) const

inlinenodiscard

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_no_checks(a) == root_of_no_checks(b).

Parameters

n the node.

Returns: The root of the strongly connected component containing the node n, a value of node_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

Warning: This function does not check that its argument n.

◆ roots()

template<typename Node>

auto roots ( ) const

inlinenodiscard

This function returns a range object consisting of roots of the strongly connected components; see Ranges for more details.

Returns: A range object by value.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ spanning_forest()

template<typename Node>

Forest const & spanning_forest ( ) const

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 const reference to a Forest.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ word_graph()

template<typename Node>

WordGraph< Node > const & word_graph ( ) const

inlinenoexcept

This function returns a const reference to the underlying word graph.

Returns: A const reference to a WordGraph<Node>.

Exceptions: This function is noexcept and is guaranteed never to throw.

Note: This function does not trigger the computation of the strongly connected components.

Friends And Related Symbol Documentation

◆ to_human_readable_repr()

template<typename Node>

std::string to_human_readable_repr ( Gabow< Node > const & g )

Return a human readable representation of a Gabow object.

Template Parameters

Node	the type of the nodes in the underlying WordGraph.

Parameters

g	the Gabow object.

Returns: A string containing a human readable representation of g.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

The documentation for this class was generated from the following file:

/Users/jdm/libsemigroups/include/libsemigroups/gabow.hpp

Public Types

Public Member Functions

Related Symbols

Constructor & Destructor Documentation

◆ Gabow() [1/4]

◆ Gabow() [2/4]

◆ Gabow() [3/4]

◆ Gabow() [4/4]

Member Function Documentation

◆ component()

◆ component_no_checks()

◆ component_of()

◆ component_of_no_checks()

◆ components()

◆ has_components()

◆ id()

◆ id_no_checks()

◆ init()

◆ number_of_components()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ reverse_spanning_forest()

◆ root_of()

◆ root_of_no_checks()

◆ roots()

◆ spanning_forest()

◆ word_graph()

Friends And Related Symbol Documentation

◆ to_human_readable_repr()