Action< Element, Point, Func, Traits, LeftOrRight >

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>
class libsemigroups::Action< Element, Point, Func, Traits, LeftOrRight >

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.

Template Parameters

Element	the type of the elements of the semigroup.
Point	the type of the points acted on.
Func	the type of the action of elements of type Element on points of type Point. This type should be a stateless trivially default constructible class with a call operator of signature void(Point&, Point const&, Element const&) which computes the action of its 3rd argument on its 2nd argument, and stores it in its 1st argument. See, for example, ImageLeftAction and ImageRightAction.
Traits	the type of a traits class with the requirements of ActionTraits.
LeftOrRight	the libsemigroups::side of the action (i.e. if it is a left or a right action).

See also

libsemigroups::side, ActionTraits, LeftAction, and RightAction.

Example

using namespace libsemigroups;
auto rg = ReportGuard(true);
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.scc().number_of_components(); // 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.

Inheritance diagram for Action< Element, Point, Func, Traits, LeftOrRight >:

Public Types
using	action_type = Func
	Type of the action of element_type on point_type.
using	const_iterator
	The type of a const iterator pointing to a point_type.
using	const_pointer_point_type
	The type of a const pointer to a point_type.
using	const_reference_point_type
	The type of a const reference to a point_type.
using	element_type = Element
	The template parameter Element.
using	index_type = size_t
	The type of the index of a point.
using	point_type = Point
	The template parameter Point.
Public Types inherited from Runner
enum class	state {   never_run = 0 , running_to_finish = 1 , running_for = 2 , running_until = 3 ,   timed_out = 4 , stopped_by_predicate = 6 , not_running = 7 , dead = 8 }
	Enum class for the state of the Runner. More...
Public Types inherited from Reporter
using	nanoseconds = std::chrono::nanoseconds
	Alias for std::chrono::nanoseconds.
using	time_point = std::chrono::high_resolution_clock::time_point
	Alias for std::chrono::high_resolution_clock::time_point.

Public Member Functions
	Action ()
	Default constructor.
	Action (Action &&that)
	Default move constructor.
	Action (Action const &that)
	Default copy constructor.
Action &	add_generator (element_type const &gen)
	Add a generator to the action.
Action &	add_seed (const_reference_point_type seed)
	Add a seed to the action.
const_reference_point_type	at (index_type pos) const
	Returns a const reference to the point in a given position.
const_iterator	begin () const noexcept
	Returns a const_iterator (random access iterator) pointing at the first point.
bool	cache_scc_multipliers () const noexcept
	Returns whether or not we are caching scc multipliers.
Action &	cache_scc_multipliers (bool val) noexcept
	Set whether or not to cache scc multipliers.
const_iterator	cbegin () const noexcept
	Returns a const_iterator (random access iterator) pointing at the first point.
const_iterator	cend () const noexcept
	Returns a const_iterator (random access iterator) pointing one past the last point.
size_t	current_size () const noexcept
	Returns the number of points found so far.
bool	empty () const noexcept
	Checks if the Action contains any points.
const_iterator	end () const noexcept
	Returns a const_iterator (random access iterator) pointing one past the last point.
std::vector< Element > const &	generators () const noexcept
	Returns a const reference to the vector of generators.
Action &	init ()
	Initialize an existing Action object.
element_type	multiplier_from_scc_root (index_type pos)
	Returns a multiplier from a scc root to a given index.
element_type	multiplier_to_scc_root (index_type pos)
	Returns a multiplier from a given index to a scc root.
size_t	number_of_generators () const noexcept
	Returns the number of generators.
Action &	operator= (Action &&)
	Default move assignment operator.
Action &	operator= (Action const &)
	Default copy assignment operator.
const_reference_point_type	operator[] (index_type pos) const noexcept
	Returns a const reference to the point in a given position.
index_type	position (const_reference_point_type pt) const
	Returns the position of a point in the so far discovered points.
auto	range () const noexcept
	Returns a range object containing the current points in the action.
Action &	reserve (size_t val)
	Increase the capacity to a value that is greater or equal to val.
const_reference_point_type	root_of_scc (const_reference_point_type x)
	Returns a const reference to the root point of a strongly connected component.
const_reference_point_type	root_of_scc (index_type pos)
	Returns a const reference to the root point of a strongly connected component.
Gabow< uint32_t > const &	scc ()
	Returns a reference to a Gabow object for strongly connected components.
size_t	size ()
	Returns the size of the fully enumerated action.
WordGraph< uint32_t > const &	word_graph ()
Public Member Functions inherited from Runner
	Runner ()
	Default constructor.
	Runner (Runner &&other)
	Move constructor.
	Runner (Runner const &other)
	Copy constructor.
state	current_state () const noexcept
	Return the current state.
bool	dead () const noexcept
	Check if the runner is dead.
bool	finished () const
	Check if run has been run to completion or not.
Runner &	init ()
	Initialize an existing Runner object.
void	kill () noexcept
	Stop run from running (thread-safe).
Runner &	operator= (Runner &&other)
	Move assignment operator.
Runner &	operator= (Runner const &other)
	Copy assignment operator.
void	report_why_we_stopped () const
	Report why run stopped.
void	run ()
	Run until finished.
void	run_for (std::chrono::nanoseconds t)
	Run for a specified amount of time.
template<typename Time>
void	run_for (Time t)
	Run for a specified amount of time.
void	run_until (bool(*func)())
	Run until a nullary predicate returns true or finished.
template<typename Func>
void	run_until (Func &&func)
	Run until a nullary predicate returns true or finished.
bool	running () const noexcept
	Check if currently running.
bool	running_for () const noexcept
	Check if the runner is currently running for a particular length of time.
bool	running_until () const noexcept
	Check if the runner is currently running until a nullary predicate returns true.
bool	started () const noexcept
	Check if run has been called at least once before.
bool	stopped () const
	Check if the runner is stopped.
bool	stopped_by_predicate () const
	Check if the runner was stopped, or should stop, because of the argument last passed to run_until.
virtual bool	success () const
	Check if run has been run to completion successfully.
bool	timed_out () const
	Check if the amount of time passed to run_for has elapsed.
Public Member Functions inherited from Reporter
	Reporter ()
	Default constructor.
	Reporter (Reporter &&that)
	Default move constructor.
	Reporter (Reporter const &that)
	Default copy constructor.
void	emit_divider ()
Reporter &	init ()
	Initialize an existing Reporter object.
time_point	last_report () const noexcept
	Get the time point of the last report.
Reporter &	operator= (Reporter &&that)
	Default move assignment operator.
Reporter &	operator= (Reporter const &that)
	Default copy assignment operator.
bool	report () const
	Check if it is time to report.
std::string const &	report_divider () const noexcept
Reporter &	report_divider (std::string const &val)
nanoseconds	report_every () const noexcept
	Get the minimum elapsed time between reports.
Reporter &	report_every (nanoseconds val) noexcept
	Set the minimum elapsed time between reports in nanoseconds.
template<typename Time>
Reporter &	report_every (Time t) noexcept
	Set the minimum elapsed time between reports in a unit of time other than nanoseconds.
std::string const &	report_prefix () const noexcept
	Get the current prefix string for reporting.
Reporter &	report_prefix (std::string const &val)
	Set the prefix string for reporting.
Reporter const &	reset_last_report () const
	Set the last report time point to now.
Reporter const &	reset_start_time () const
	Reset the start time (and last report) to now.
time_point	start_time () const noexcept
	Get the start time.

Additional Inherited Members
Related Symbols inherited from Reporter
static std::chrono::nanoseconds	delta (std::chrono::high_resolution_clock::time_point const &t)
	The time between a given point and now.

Member Typedef Documentation

action_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using action_type = Func

The type of the action of elements of type Element on points of type Point. This type should be a stateless trivially default constructible class with a call operator of signature void(Point&, Point const&, Element const&) which computes the action of its 3rd argument on its 2nd argument, and stores it in its 1st argument.

See also

ImageRightAction, ImageLeftAction

const_iterator

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using const_iterator

Initial value:

 detail::BruidhinnConstIterator<point_type,
                                         std::vector<internal_point_type>>

The type of a const iterator pointing to the point_type values contained in an Action object.

const_pointer_point_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using const_pointer_point_type

Initial value:

 
        typename detail::BruidhinnTraits<Point>::const_pointer

The type of a const pointer to the point_type values contained in an Action object.

const_reference_point_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using const_reference_point_type

Initial value:

 
        typename detail::BruidhinnTraits<Point>::const_reference

The type of a const reference to the point_type values contained in an Action object.

element_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using element_type = Element

The template parameter Element, which is the type of the elements of the semigroup whose action is represented by an Action instance.

index_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using index_type = size_t

Type of indices for values in an Action instance.

See also

operator[] and at.

point_type

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

using point_type = Point

The template parameter Point, which is the type of the points of acted on in an Action instance.

Constructor & Destructor Documentation

Action()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action

(

)

A constructor that creates an uninitialized Action instance representing a left or right action.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Member Function Documentation

add_generator()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action & add_generator ( element_type const & gen )

inline

An Action instance represents the action of the semigroup generated by the elements added via this member function.

Parameters

gen	the generator to add.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

add_seed()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action & add_seed

(

const_reference_point_type

seed

)

A seed is just a starting point for the action, it will belong to the action, as will every point that can be obtained from the seed by acting with the generators of the action.

Parameters

seed	the seed to add.

Returns

A reference to *this

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

at()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_reference_point_type at ( index_type pos ) const

inlinenodiscard

Parameters

pos	the index of a point.

Returns

A const_reference_point_type to the point in position pos of the currently enumerated points.

Exceptions

std::out_of_range

if !(pos < current_size()).

Complexity

Constant.

begin()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_iterator begin ( ) const

inlinenodiscardnoexcept

This function returns a const_iterator to the first point in the action (if any). No enumeration is triggered by calling this function.

Returns

A const iterator to the first point.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

cache_scc_multipliers() [1/2]

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

bool cache_scc_multipliers ( ) const

inlinenodiscardnoexcept

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.

Returns

A value of type bool.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

cache_scc_multipliers() [2/2]

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action & cache_scc_multipliers ( bool val )

inlinenoexcept

If the parameter val 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.

Parameters

val	the value.

Returns

A reference to *this.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

cbegin()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_iterator cbegin ( ) const

inlinenodiscardnoexcept

This function returns a const_iterator to the first point in the action (if any). No enumeration is triggered by calling this function.

Returns

A const iterator to the first point.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

cend()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_iterator cend ( ) const

inlinenodiscardnoexcept

This function returns a const_iterator pointing one beyond the last point in the action (if any). No enumeration is triggered by calling this function.

Returns

A const iterator to one past the end.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

current_size()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

size_t current_size ( ) const

inlinenodiscardnoexcept

Returns the number of points found so far.

Returns

A value of type size_t.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

empty()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

bool empty ( ) const

inlinenodiscardnoexcept

Returns

true if the action contains no points (including seeds), and false if not.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

end()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_iterator end ( ) const

inlinenodiscardnoexcept

This function returns a const_iterator pointing one beyond the last point in the action (if any). No enumeration is triggered by calling this function.

Returns

A const iterator to one past the end.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

generators()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

std::vector< Element > const & generators ( ) const

inlinenodiscardnoexcept

Returns

A value of type std::vector<Element>.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

init()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action & init

(

)

This function puts a Action object back into the same state as if it had been newly default constructed.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

multiplier_from_scc_root()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

element_type multiplier_from_scc_root ( index_type pos )

inlinenodiscard

Returns an element x of the semigroup generated by the generators in the action such that if r is the root of the strongly connected component containing at(pos), then after Func()(res, r, x) the point res equals at(pos).

Parameters

pos	a position in the action.

Returns

An element of type element_type.

Exceptions

LibsemigroupsException

if there are no generators yet added or the index pos is out of range.

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.

multiplier_to_scc_root()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

element_type multiplier_to_scc_root ( index_type pos )

inlinenodiscard

Returns an element x of the semigroup generated by the generators in the action such that after Func()(res, at(pos), x) the point res is the root of the strongly connected component containing at(pos).

Parameters

pos	a position in the action.

Returns

An element of type element_type.

Exceptions

LibsemigroupsException

if there are no generators yet added or the index pos is out of range.

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.

number_of_generators()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

size_t number_of_generators ( ) const

inlinenodiscardnoexcept

Returns

The number of generators.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

operator[]()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_reference_point_type operator[] ( index_type pos ) const

inlinenodiscardnoexcept

Parameters

pos	the index of a point.

Returns

A const_reference_point_type to the point in position pos of the currently enumerated points.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

position()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

index_type position ( const_reference_point_type pt ) const

nodiscard

Returns the position of a point in the so far discovered points.

Parameters

pt	the point whose position is sought.

Returns

The index of pt in this or UNDEFINED.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

range()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

auto range ( ) const

inlinenodiscardnoexcept

Returns a range object containing the current points in the action.

Returns

A range object.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

reserve()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Action & reserve

(

size_t

val

)

Increase the capacity to a value that is greater or equal to val.

Parameters

val	new capacity of an action instance.

Returns

A reference to *this.

Exceptions

std::length_error

if val is too large.

Complexity

At most linear in the size() of the Action.

root_of_scc() [1/2]

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_reference_point_type root_of_scc ( const_reference_point_type x )

inlinenodiscard

Returns a const reference to the root point of a strongly connected component.

Parameters

x	the point whose root we want to find.

Returns

A value of type const_reference_point_type.

Exceptions

LibsemigroupsException

if the point x does not belong to the 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.

root_of_scc() [2/2]

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

const_reference_point_type root_of_scc ( index_type pos )

inlinenodiscard

Returns a const reference to the root point of a strongly connected component.

Parameters

pos	the index of the point in the action whose root we want to find.

Returns

A value of type const_reference_point_type.

Exceptions

LibsemigroupsException

if the index pos is out of range.

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.

scc()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

Gabow< uint32_t > const & scc ( )

inlinenodiscard

Returns a reference to a Gabow object for strongly connected components.

Returns

A const reference to a Gabow object.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

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.

size()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

size_t size ( )

inlinenodiscard

Returns the size of the fully enumerated action.

Returns

The size of the action, a value of type size_t.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

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.

word_graph()

template<typename Element, typename Point, typename Func, typename Traits, side LeftOrRight>

WordGraph< uint32_t > const & word_graph ( )

inlinenodiscard

Returns the word graph of the completely enumerated action.

Returns

A const reference to a WordGraph<uint32_t>.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

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.

---

The documentation for this class was generated from the following file:

• /Users/jdm/libsemigroups/include/libsemigroups/action.hpp