Strongly connected components

This page contains information about the functionality for strongly connected components in the Action class.

inline bool libsemigroups::Action::cache_scc_multipliers() const noexcept

Returns whether or not we are caching scc multipliers.

If the returned value of this function is true, then the values returned by multiplier_from_scc_root() and multiplier_to_scc_root() are cached, and not recomputed every time one of these functions is called.

Complexity

Constant.

Parameters

(None)

Throws:

(None) – This function is noexcept and is guaranteed never to throw.

Returns:

A value of type bool.

inline Action &libsemigroups::Action::cache_scc_multipliers(bool val) noexcept

Set whether or not to cache scc multipliers.

If the parameter val is true, then the values returned by multiplier_from_scc_root() and multiplier_to_scc_root() are cached, and not recomputed every time one of these functions is called.

Complexity

Constant.

Parameters:

val – the value.

Throws:

(None) – This function is noexcept and is guaranteed never to throw.

Returns:

A reference to this.

inline ActionDigraph<size_t> const &libsemigroups::Action::digraph()

Returns the digraph of the completely enumerated action.

Complexity

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type element_type and \(n\) is the size of the fully enumerated orbit.

Parameters

(None)

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

A const reference to an ActionDigraph<size_t>.

inline element_type libsemigroups::Action::multiplier_from_scc_root(index_type pos)

Returns a multiplier from a scc root to a given index.

Returns an element x of the semigroup generated by the generators in the action such that if r is the root of the strongly connected component containing at(pos), then after TActionType()(res, r, x) the point res equals at(pos).

Complexity

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type element_type and \(n\) is the size of the fully enumerated orbit.

Parameters:

pos – a position in the action.

Throws:

LibsemigroupsException – if there are no generators yet added or the index pos is out of range.

Returns:

An element of type element_type.

inline element_type libsemigroups::Action::multiplier_to_scc_root(index_type pos)

Returns a multiplier from a given index to a scc root.

Returns an element x of the semigroup generated by the generators in the action such that after TActionType()(res, at(pos), x) the point res is the root of the strongly connected component containing at(pos).

Complexity

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type element_type and \(n\) is the size of the fully enumerated orbit.

Parameters:

pos – a position in the action.

Throws:

LibsemigroupsException – if there are no generators yet added or the index pos is out of range.

Returns:

An element of type element_type.

inline const_reference_point_type libsemigroups::Action::root_of_scc(const_reference_point_type x)

Returns a const reference to the root point of a strongly connected component.

Complexity

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type element_type and \(n\) is the size of the fully enumerated orbit.

Parameters:

x – the point whose root we want to find.

Throws:

LibsemigroupsException – if the point x does not belong to the action.

Returns:

A value of type const_reference_point_type.

inline const_reference_point_type libsemigroups::Action::root_of_scc(index_type pos)

Returns a const reference to the root point of a strongly connected component.

Complexity

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type element_type and \(n\) is the size of the fully enumerated orbit.

Parameters:

pos – the index of the point in the action whose root we want to find.

Throws:

LibsemigroupsException – if the index pos is out of range.

Returns:

A value of type const_reference_point_type.