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
istrue
, 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 ifr
is the root of the strongly connected component containingat(pos)
, then afterTActionType()(res, r, x)
the pointres
equalsat(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 afterTActionType()(res, at(pos), x)
the pointres
is the root of the strongly connected component containingat(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.