# 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 of libsemigroups 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 of this by the generators of this until no further points can be found, or stopped returns true. This is achieved by performing a breadth first search.

Example

using namespace libsemigroups;
auto rg = ReportGuard(REPORT);
RightAction<PPerm<16>, PPerm<16>, ImageRightAction<PPerm<16>, PPerm<16>>>
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));
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));
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));
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 type TPointType. This type should be a stateless trivially default constructible class with a call operator of signature void(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¶

 action_type Type of the action of element_type on point_type . const_iterator The type of a const iterator pointing to a point_type . const_iterator_scc The type of a const iterator pointing to a single strongly connected component (scc). const_iterator_scc_roots The type of a const iterator pointing to a representative of a strongly connected component (scc). const_iterator_sccs The type of a const iterator pointing to a strongly connected component (scc). const_pointer_point_type The type of a const pointer to a point_type . const_reference_point_type The type of a const reference to a point_type . element_type The template parameter TElementType. index_type The type of the index of a point. point_type The template parameter TPointType. scc_index_type The type of the index of a strongly connected component.

## Constructors¶

 Action() Default constructor. Action(Action const&) = default Default copy constructor. Action(Action&&) = default Default move constructor. operator=(Action const&) = default Default copy assignment operator. operator=(Action&&) = default Default move assignment operator.

## Initialization¶

 add_generator(element_type) Add a generator to the action. add_seed(const_reference_point_type) Add a seed to the action. reserve(size_t) Increase the capacity to a value that is greater or equal to val.

## Position, size, empty…¶

 at(size_t) const Returns a const reference to the point in a given position. cbegin() const noexcept Returns a const_iterator (random access iterator) pointing at the first point. cend() const noexcept Returns a const_iterator (random access iterator) pointing one past the last point. current_size() const noexcept Returns the number of points found so far. empty() const noexcept Checks if the Action contains any points. operator[](size_t) const noexcept Returns a const reference to the point in a given position. position(const_reference_point_type) const Returns the position of a point in the so far discovered points. size() Returns the size of the fully enumerated action.

## Strongly connected components¶

 cache_scc_multipliers() const noexcept Returns whether or not we are caching scc multipliers. cache_scc_multipliers(bool) noexcept Set whether or not to cache scc multipliers. digraph() Returns the digraph of the completely enumerated action. multiplier_from_scc_root(index_type) Returns a multiplier from a scc root to a given index. multiplier_to_scc_root(index_type) Returns a multiplier from a given index to a scc root. root_of_scc(const_reference_point_type) Returns a const reference to the root point of a strongly connected component. root_of_scc(index_type) Returns a const reference to the root point of a strongly connected component.

## Member functions inherited from Runner¶

 dead() const noexcept Check if the runner is dead. finished() const Check if run has been run to completion or not. kill() noexcept Stop run from running (thread-safe). report() const Check if it is time to report. report_every() const noexcept Get the minimum elapsed time between reports. report_every(TIntType) Set the minimum elapsed time between reports. report_every(std::chrono::nanoseconds) Set the minimum elapsed time between reports. report_why_we_stopped() const Report why run stopped. run() Run until finished . run_for(TIntType) Run for a specified amount of time. run_for(std::chrono::nanoseconds) Run for a specified amount of time. run_until(T&&) Run until a nullary predicate returns true or finished . run_until(bool(*)()) Run until a nullary predicate returns true or finished . running() const noexcept Check if currently running. running_for() const noexcept Check if the runner is currently running for a particular length of time. running_until() const noexcept Check if the runner is currently running until a nullary predicate returns true. started() const Check if run has been called at least once before. stopped() const Check if the runner is stopped. stopped_by_predicate() const Check if the runner was, or should, stop because of the argument for run_until . timed_out() const Check if the amount of time passed to run_for has elapsed.