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>>>
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 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`
`const_iterator`	The type of a const iterator pointing to a `point_type` .
`const_iterator_scc`
`const_iterator_scc_roots`
`const_iterator_sccs`
`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`
`index_type`	The type of the index of a point.
`point_type`
`scc_index_type`

Constructors¶

`Action()`
`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_seed(const_reference_point_type)`
`reserve(size_t)`

Position, size, empty…¶

`at(size_t) const`
`cbegin() const noexcept`
`cend() const noexcept`
`current_size() const noexcept`
`empty() const noexcept`
`operator[](size_t) const noexcept`
`position(const_reference_point_type) const`
`size()`

Strongly connected components¶

`cache_scc_multipliers() const noexcept`
`cache_scc_multipliers(bool) noexcept`
`digraph()`
`multiplier_from_scc_root(index_type)`
`multiplier_to_scc_root(index_type)`
`root_of_scc(const_reference_point_type)`
`root_of_scc(index_type)`

`dead() const noexcept`
`finished() const`
`kill() noexcept`
`report() const`
`report_every() const noexcept`
`report_every(TIntType)`
`report_every(std::chrono::nanoseconds)`
`report_why_we_stopped() const`
`run()`
`run_for(TIntType)`
`run_for(std::chrono::nanoseconds)`
`run_until(T&&)`
`run_until(bool(*)())`
`running() const noexcept`
`running_for() const noexcept`
`running_until() const noexcept`
`started() const`
`stopped() const`
`stopped_by_predicate() const`
`timed_out() const`