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.