Action¶
-
template<typename TElementType, typename TPointType, typename TActionType, typename TTraits, side TLeftOrRight>
class Action : public libsemigroups::Runner, private libsemigroups::detail::BruidhinnTraits<TPointType>¶ Defined in
action.hpp
.This page contains details of the Action class in
libsemigroups
for finding actions of semigroups, or groups, on sets. The notion of an “action” in the context oflibsemigroups
is analogous to the notion of an orbit of a group.You are unlikely to want to use this class directly directly, but rather via the more convenient aliases RightAction and LeftAction.
The function
run
finds points that can be obtained by acting on the seeds ofthis
by the generators ofthis
until no further points can be found, orstopped
returnstrue
. This is achieved by performing a breadth first search.See also
libsemigroups::side, ActionTraits, LeftAction, and RightAction.
- Example
using namespace libsemigroups; auto rg = ReportGuard(REPORT); RightAction<PPerm<16>, PPerm<16>, ImageRightAction<PPerm<16>, PPerm<16>>> o; o.add_seed(PPerm<16>::identity(16)); o.add_generator( PPerm<16>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}, 16)); o.add_generator( PPerm<16>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, 16)); o.add_generator( PPerm<16>({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, 16)); o.add_generator( PPerm<16>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, 16)); o.reserve(70000); o.size(); // 65536 o.digraph().number_of_scc(); // 17
- Complexity
The time complexity is \(O(mn)\) where \(m\) is the total number of points in the orbit and \(n\) is the number of generators.
- Template Parameters
TElementType – the type of the elements of the semigroup.
TPointType – the type of the points acted on.
TActionType – the type of the action of elements of type
TElementType
on points of typeTPointType
. This type should be a stateless trivially default constructible class with a call operator of signaturevoid(TPointType&, TPointType const&, TElementType const&)
which computes the action of the 3rd argument on the 2nd argument, and stores it in the 1st argument. See, for example, ImageLeftAction and ImageRightAction.TTraits – the type of a traits class with the requirements of ActionTraits.
TLeftOrRight – the libsemigroups::side of the action (i.e. if it is is a left or a right action).
Member types¶
Type of the action of |
|
The type of a const iterator pointing to a |
|
The type of a const iterator pointing to a single strongly connected component (scc). |
|
The type of a const iterator pointing to a representative of a strongly connected component (scc). |
|
The type of a const iterator pointing to a strongly connected component (scc). |
|
The type of a const pointer to a |
|
The type of a const reference to a |
|
The template parameter |
|
The type of the index of a point. |
|
The template parameter |
|
The type of the index of a strongly connected component. |
Constructors¶
Default constructor. |
|
Default copy constructor. |
|
Default move constructor. |
|
Default copy assignment operator. |
|
Default move assignment operator. |
Initialization¶
Add a generator to the action. |
|
Add a seed to the action. |
|
Increase the capacity to a value that is greater or equal to |
Position, size, empty…¶
Returns a const reference to the point in a given position. |
|
Returns a |
|
Returns a |
|
Returns the number of points found so far. |
|
Checks if the |
|
Returns a const reference to the point in a given position. |
|
Returns the position of a point in the so far discovered points. |
|
Returns the size of the fully enumerated action. |
Strongly connected components¶
Returns whether or not we are caching scc multipliers. |
|
Set whether or not to cache scc multipliers. |
|
Returns the digraph of the completely enumerated action. |
|
Returns a multiplier from a scc root to a given index. |
|
Returns a multiplier from a given index to a scc root. |
|
Returns a const reference to the root point of a strongly connected component. |
|
Returns a const reference to the root point of a strongly connected component. |
Member functions inherited from Runner¶
Check if the runner is dead. |
|
Check if |
|
Stop |
|
Check if it is time to report. |
|
Get the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Report why |
|
Run until |
|
Run for a specified amount of time. |
|
Run for a specified amount of time. |
|
Run until a nullary predicate returns |
|
Run until a nullary predicate returns |
|
Check if currently running. |
|
Check if the runner is currently running for a particular length of time. |
|
Check if the runner is currently running until a nullary predicate returns |
|
Check if |
|
Check if the runner is stopped. |
|
Check if the runner was, or should, stop because of the argument for |
|
Check if the amount of time passed to |