template<typename Element, typename Traits = FroidurePinTraits<Element>>
class libsemigroups::FroidurePin< Element, Traits >

Defined in froidure-pin.hpp.

The class template FroidurePin implements the Froidure-Pin algorithm as described in the article [22] by Veronique Froidure and Jean-Eric Pin. A FroidurePin instance is defined by a generating set, and the main function is run, which implements the Froidure-Pin Algorithm. If run is invoked and finished returns true, then the size size, the left and right Cayley graphs left_cayley_graph and right_cayley_graph are determined, and a confluent terminating presentation rules for the semigroup is known.

Template Parameters

Element	the type of the elements in the represented semigroup.
Traits	a traits class holding various adapters used by the implementation (defaults to FroidurePinTraits).

See also: FroidurePinTraits and FroidurePinBase.

Example: template <>

struct Complexity<int> {

constexpr size_t operator()(int) const noexcept {

return 0;

}

};

template <>

struct Degree<int> {

constexpr size_t operator()(int) const noexcept {

return 0;

}

};

template <>

struct IncreaseDegree<int> {

int operator()(int x) const noexcept {

return x;

}

};

template <>

struct One<int> {

constexpr int operator()(int) const noexcept {

return 1;

}

};

template <>

struct Product<int> {

void operator()(int& xy,

int x,

int y,

size_t = 0) const noexcept {

xy = x * y;

}

};

FroidurePin<int> S({2});

S.size(); // 32

S.number_of_idempotents() // 1

*S.cbegin(); // 2

FroidurePin<uint8_t> T({2, 3});

T.size() // 130

T.number_of_idempotents() // 2

*T.cbegin_idempotents(); // 0

*T.cbegin_idempotents() + 1; // 1

libsemigroups::FroidurePin::One
typename Traits::One One
Adapter for the identity element of the given type.
Definition froidure-pin.hpp:304

libsemigroups::FroidurePin::Degree
typename Traits::Degree Degree
Adapter for the degree of an element.
Definition froidure-pin.hpp:289

libsemigroups::FroidurePin::Complexity
typename Traits::Complexity Complexity
Adapter for the complexity of multiplication.
Definition froidure-pin.hpp:286

libsemigroups::FroidurePin::Product
typename Traits::Product Product
Adapter for the product of two elements.
Definition froidure-pin.hpp:307

libsemigroups::FroidurePin::IncreaseDegree
typename Traits::IncreaseDegree IncreaseDegree
Adapter for increasing the degree of an element.
Definition froidure-pin.hpp:298

libsemigroups::FroidurePin::FroidurePin
FroidurePin()
Default constructor.

Inheritance diagram for FroidurePin< Element, Traits >:

[legend]

Public Types
using	cayley_graph_type = FroidurePinBase::cayley_graph_type
	Alias for the types of the left and right Cayley graphs.

using	Complexity = typename Traits::Complexity
	Adapter for the complexity of multiplication.

using	const_element_type
	Type of const elements.

using	const_iterator
	Return type of cbegin and cend.

using	const_iterator_idempotents = const_iterator_pair_first
	Return type of cbegin_idempotents and cend_idempotents.

using	const_iterator_sorted = const_iterator_pair_first
	Return type of cbegin_sorted and cend_sorted.

using	const_pointer
	Type of element const pointers.

using	const_reference
	Type of element const references.

using	Degree = typename Traits::Degree
	Adapter for the degree of an element.

using	element_index_type = FroidurePinBase::element_index_type
	Alias for the index of an element.

using	element_type = typename detail::BruidhinnTraits<Element>::value_type
	Type of the elements.

using	EqualTo = typename Traits::EqualTo
	Adapter for testing equality.

using	Hash = typename Traits::Hash
	Adapter for hashing.

using	IncreaseDegree = typename Traits::IncreaseDegree
	Adapter for increasing the degree of an element.

using	Less = typename Traits::Less
	Adapter for comparisons.

using	One = typename Traits::One
	Adapter for the identity element of the given type.

using	Product = typename Traits::Product
	Adapter for the product of two elements.

using	reference = typename detail::BruidhinnTraits<Element>::reference
	Type of element references.

using	rvalue_reference
	Type of element rvalue references.

using	size_type = FroidurePinBase::size_type
	Alias for the type of the size of the enumerated semigroup.

using	state_type = typename Traits::state_type
	Type of the state used for multiplication (if any).

using	Swap = typename Traits::Swap
	Adapter for swapping.

using	value_type = element_type
	Alias for element_type.

Public Types inherited from FroidurePinBase
using	cayley_graph_type = WordGraph<element_index_type>
	Alias for the types of the left and right Cayley graphs.

using	element_index_type = size_type
	Alias for the index of an element.

using	generator_index_type = size_type
	Alias for the index of a generator.

using	size_type = uint32_t
	Alias for the type of the size of the enumerated semigroup.

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
	FroidurePin ()
	Default constructor.

	FroidurePin (FroidurePin &&)=default
	Default move constructor.

	FroidurePin (FroidurePin const &that)
	Copy constructor.

template<typename Iterator1, typename Iterator2>
	FroidurePin (Iterator1 first, Iterator2 last)
	Construct from a range of generators given by iterators.

template<typename State, typename = std::enable_if_t<IsState<State>>>
	FroidurePin (State const &stt)
	Construct from const reference to state.

template<typename State, typename = std::enable_if_t<IsState<State>>>
	FroidurePin (std::shared_ptr< State > stt)
	Construct from std::shared_ptr to state.

FroidurePin &	add_generator (const_reference x)
	Add a copy of an element to the generators.

FroidurePin &	add_generator_no_checks (const_reference x)
	Add a copy of an element to the generators.

template<typename Iterator1, typename Iterator2>
FroidurePin &	add_generators (Iterator1 first, Iterator2 last)
	Add collection of generators via iterators.

template<typename Iterator1, typename Iterator2>
FroidurePin &	add_generators_no_checks (Iterator1 first, Iterator2 last)
	Add collection of generators via iterators.

const_reference	at (element_index_type i)
	Access element specified by index with bound checks.

const_iterator	begin () const
	Returns a const iterator pointing to the first element (ordered by discovery).

const_iterator	cbegin () const
	Returns a const iterator pointing to the first element (ordered by discovery).

const_iterator_idempotents	cbegin_idempotents ()
	Returns a const iterator pointing at the first idempotent.

const_iterator_sorted	cbegin_sorted ()
	Returns a const iterator pointing to the first element (sorted by Less).

const_iterator	cend () const
	Returns a const iterator pointing to one past the last known element.

const_iterator_idempotents	cend_idempotents ()
	Returns a const iterator pointing one past the last idempotent.

const_iterator_sorted	cend_sorted ()
	Returns a const iterator pointing one past the last element (sorted by Less).

template<typename Iterator1, typename Iterator2>
FroidurePin &	closure (Iterator1 first, Iterator2 last)
	Add non-redundant generators in collection.

template<typename Iterator1, typename Iterator2>
FroidurePin &	closure_no_checks (Iterator1 first, Iterator2 last)
	Add non-redundant generators in collection.

bool	contains (const_reference x)
	Test membership of an element.

template<typename Iterator1, typename Iterator2>
FroidurePin	copy_add_generators (Iterator1 first, Iterator2 last) const
	Copy and add a collection of generators.

template<typename Iterator1, typename Iterator2>
FroidurePin	copy_add_generators_no_checks (Iterator1 first, Iterator2 last) const
	Copy and add a collection of generators.

template<typename Iterator1, typename Iterator2>
FroidurePin	copy_closure (Iterator1 first, Iterator2 last)
	Copy and add non-redundant generators.

template<typename Iterator1, typename Iterator2>
FroidurePin	copy_closure_no_checks (Iterator1 first, Iterator2 last)
	Copy and add non-redundant generators.

element_index_type	current_position (const_reference x) const
	Find the position of an element with no enumeration.

const_iterator	end () const
	Returns a const iterator pointing one past the last known element.

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	equal_to (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check equality of words in the generators.

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	equal_to_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check equality of words in the generators.

element_index_type	fast_product (element_index_type i, element_index_type j) const
	Multiply elements via their indices.

element_index_type	fast_product_no_checks (element_index_type i, element_index_type j) const
	Multiply elements via their indices.

const_reference	generator (generator_index_type i) const
	Returns the generator with specified index.

const_reference	generator_no_checks (generator_index_type i) const
	Returns the generator with specified index.

FroidurePin &	init ()
	Reinitialize a FroidurePin object.

template<typename Iterator1, typename Iterator2>
FroidurePin &	init (Iterator1 first, Iterator2 last)
	Reinitialize a FroidurePin object from a range of generators given by iterators.

template<typename State, typename = std::enable_if_t<IsState<State>>>
FroidurePin &	init (State const &stt)
	Reinitialize a FroidurePin object from state.

template<typename State, typename = std::enable_if_t<IsState<State>>>
FroidurePin &	init (std::shared_ptr< State > stt)
	Reinitialize a FroidurePin object from state.

tril	is_finite () const override
	Check finiteness.

bool	is_idempotent (element_index_type i)
	Check if an element is an idempotent via its index.

bool	is_idempotent_no_checks (element_index_type i)
	Check if an element is an idempotent via its index.

size_t	number_of_generators () const noexcept override
	Returns the number of generators.

size_t	number_of_idempotents ()
	Returns the number of idempotents.

FroidurePin &	operator= (FroidurePin &&)=default
	Default move assignment operator.

FroidurePin &	operator= (FroidurePin const &)
	Copy assignment operator.

const_reference	operator[] (element_index_type i) const
	Access element specified by index.

element_index_type	position (const_reference x)
	Find the position of an element with enumeration if necessary.

FroidurePin &	reserve (size_t val)
	Requests the given capacity for elements.

const_reference	sorted_at (element_index_type i)
	Access element specified by sorted index with bound checks.

const_reference	sorted_at_no_checks (element_index_type i)
	Access element specified by sorted index with bound checks.

element_index_type	sorted_position (const_reference x)
	Returns the sorted index of an element.

std::shared_ptr< state_type >	state () const
	Returns a std::shared_ptr to the state (if any).

template<typename Iterator1, typename Iterator2>
const_reference	to_element (Iterator1 first, Iterator2 last) const
	Convert a word in the generators to an element.

template<typename Iterator1, typename Iterator2>
const_reference	to_element_no_checks (Iterator1 first, Iterator2 last) const
	Convert a word in the generators to an element.

element_index_type	to_sorted_position (element_index_type i)
	Returns the sorted index of an element via its index.

Public Member Functions inherited from FroidurePinBase
	FroidurePinBase ()
	Default constructor.

	FroidurePinBase (FroidurePinBase &&other)=default
	Default move constructor.

	FroidurePinBase (FroidurePinBase const &S)
	Copy constructor.

size_t	batch_size () const noexcept
	Returns the current value of the batch size.

FroidurePinBase &	batch_size (size_t batch_size) noexcept
	Set a new value for the batch size.

const_normal_form_iterator	cbegin_current_normal_forms () const
	Returns an iterator pointing at the first normal form (if any).

const_rule_iterator	cbegin_current_rules () const
	Returns a forward iterator pointing to the first rule (if any).

const_normal_form_iterator	cbegin_normal_forms ()
	Returns an iterator pointing at the first normal form (if any).

const_rule_iterator	cbegin_rules ()
	Returns a forward iterator pointing to the first rule (if any).

const_normal_form_iterator	cend_current_normal_forms () const
	Returns an iterator pointing one beyond the last normal form (if any).

const_rule_iterator	cend_current_rules () const
	Returns a forward iterator pointing one past the last rule (if any).

const_normal_form_iterator	cend_normal_forms ()
	Returns an iterator pointing one beyond the last normal form (if any).

const_rule_iterator	cend_rules ()
	Returns a forward iterator pointing one past the last rule (if any).

bool	contains_one ()
	Check if the categorical multiplicative identity is an element.

template<typename Iterator>
void	current_factorisation_no_checks (Iterator d_first, element_index_type pos) const
	Output to an iterator a word representing an element given by index.

cayley_graph_type const &	current_left_cayley_graph () const noexcept
	Returns a const reference to the left Cayley graph.

size_t	current_length (element_index_type pos) const
	Returns the length of the short-lex least word equal to the element with given index.

size_t	current_length_no_checks (element_index_type pos) const
	Returns the length of the short-lex least word equal to the element with given index.

size_t	current_max_word_length () const noexcept
	Returns the maximum length of a word in the generators so far computed.

template<typename Iterator>
void	current_minimal_factorisation (Iterator d_first, element_index_type pos) const
	Output to an iterator the short-lex least word representing an element given by index.

template<typename Iterator>
void	current_minimal_factorisation_no_checks (Iterator d_first, element_index_type pos) const
	Output to an iterator the short-lex least word representing an element given by index.

size_t	current_number_of_rules () const noexcept
	Returns the number of rules that have been found so far.

template<typename Iterator1, typename Iterator2>
element_index_type	current_position (Iterator1 first, Iterator2 last) const
	Returns the position corresponding to a word.

template<typename Iterator1, typename Iterator2>
element_index_type	current_position_no_checks (Iterator1 first, Iterator2 last) const
	Returns the position corresponding to a word.

cayley_graph_type const &	current_right_cayley_graph () const noexcept
	Returns a const reference to the right Cayley graph.

size_t	current_size () const noexcept
	Returns the number of elements so far enumerated.

bool	currently_contains_one () const noexcept
	Check if the categorical multiplicative identity is known to be an element.

size_t	degree () const noexcept
	Returns the degree of any and all elements.

void	enumerate (size_t limit)
	Enumerate until at least a specified number of elements are found.

template<typename Iterator>
void	factorisation (Iterator d_first, element_index_type pos)
	Output to an iterator a word representing an element given by index.

generator_index_type	final_letter (element_index_type pos) const
	Returns the last letter of the element with specified index.

generator_index_type	final_letter_no_checks (element_index_type pos) const
	Returns the first letter of the element with specified index.

generator_index_type	first_letter (element_index_type pos) const
	Returns the first letter of the element with specified index.

generator_index_type	first_letter_no_checks (element_index_type pos) const
	Returns the first letter of the element with specified index.

FroidurePinBase &	init ()
	Reinitialize a FroidurePinBase object.

cayley_graph_type const &	left_cayley_graph ()
	Returns a const reference to the left Cayley graph.

size_t	length (element_index_type pos)
	Returns the length of the short-lex least word equal to the element with given index.

size_t	length_no_checks (element_index_type pos)
	Returns the length of the short-lex least word equal to the element with given index.

template<typename Iterator>
void	minimal_factorisation (Iterator d_first, element_index_type pos)
	Output to an iterator the short-lex least word representing an element given by index.

size_t	number_of_elements_of_length (size_t len) const
	Returns the number of elements so far enumerated with given length.

size_t	number_of_elements_of_length (size_t min, size_t max) const
	Returns the number of elements so far enumerated with length in a given range.

size_t	number_of_rules ()
	Returns the total number of relations in the presentation.

FroidurePinBase &	operator= (FroidurePinBase &&)=default
	Move assignment operator.

FroidurePinBase &	operator= (FroidurePinBase const &)
	Copy assignment operator.

template<typename Iterator1, typename Iterator2>
element_index_type	position (Iterator1 first, Iterator2 last)
	Returns the position corresponding to a word.

template<typename Iterator1, typename Iterator2>
element_index_type	position_no_checks (Iterator1 first, Iterator2 last)
	Returns the position corresponding to a word.

element_index_type	position_of_generator (generator_index_type i) const
	Returns the position of the generator with specified index.

element_index_type	position_of_generator_no_checks (generator_index_type i) const
	Returns the position of the generator with specified index.

element_index_type	prefix (element_index_type pos) const
	Returns the position of the longest proper prefix.

element_index_type	prefix_no_checks (element_index_type pos) const
	Returns the position of the longest proper prefix.

cayley_graph_type const &	right_cayley_graph ()
	Returns a const reference to the right Cayley graph.

size_t	size ()
	Returns the size of a FroidurePin instance.

element_index_type	suffix (element_index_type pos) const
	Returns the position of the longest proper suffix.

element_index_type	suffix_no_checks (element_index_type pos) const
	Returns the position of the longest proper suffix.

template<typename Iterator1, typename Iterator2>
void	throw_if_any_generator_index_out_of_range (Iterator1 first, Iterator2 last) const
	Throw an exception if any generator index is out of range.

void	throw_if_element_index_out_of_range (element_index_type i) const
	Throw an exception if an index is out of range.

void	throw_if_generator_index_out_of_range (generator_index_type i) const
	Throw an exception if a generator index is out of range.

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.

Static Public Member Functions
template<typename Iterator1, typename Iterator2>
static void	throw_if_inconsistent_degree (Iterator1 first, Iterator2 last)
	Throws if the degrees of the elements in a given range are not all equal.

Related Symbols
(Note that these are not member symbols.)
template<typename Iterator1, typename Iterator2>
	FroidurePin (Iterator1, Iterator2) -> FroidurePin< std::decay_t< decltype(*std::declval< Iterator1 >())> >

template<typename Element, typename Traits>
std::string	to_human_readable_repr (FroidurePin< Element, Traits > const &fp)
	Return a human readable representation of a FroidurePin object.

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

◆ cayley_graph_type

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using cayley_graph_type = FroidurePinBase::cayley_graph_type

◆ Complexity

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Complexity = typename Traits::Complexity

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature size_t operator()(Element const& x) const (possibly noexcept, inline and/or constexpr also).

The return value of the call operator ought to indicate the approximate complexity of multiplying two instances of Element, which may or may not depend on the parameter x. This is used, for example, by FroidurePin in some member functions to determine whether it is better to multiply elements or to follow a path in the Cayley graph.

Template Parameters

Element the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

FroidurePinTraits

Example: template <>

struct Complexity<KBE> {

constexpr size_t operator()(KBE const&) const noexcept {

return LIMIT_MAX;

}

};

libsemigroups::LIMIT_MAX
LimitMax const LIMIT_MAX
Value for the maximum of something.

◆ const_element_type

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_element_type

Initial value:

typename detail::BruidhinnTraits<Element>::const_value_type

◆ const_iterator

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_iterator

Initial value:

detail::BruidhinnConstIterator<element_type,

std::vector<internal_element_type>>

libsemigroups::FroidurePin::element_type

typename detail::BruidhinnTraits< Element >::value_type element_type

Type of the elements.

Definition froidure-pin.hpp:247

std::vector

Return type for const random access iterators pointing at the elements of a FroidurePin object in the order they were enumerated (i.e. in short-lex order of the minimum word in the generators).

◆ const_iterator_idempotents

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_iterator_idempotents = const_iterator_pair_first

A type for const random access iterators through the idempotents, in order of generation (short-lex order).

See also: const_iterator.

◆ const_iterator_sorted

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_iterator_sorted = const_iterator_pair_first

A type for const random access iterators through the elements, sorted according to Less.

◆ const_pointer

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_pointer

Initial value:

typename detail::BruidhinnTraits<Element>::const_pointer

◆ const_reference

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using const_reference

Initial value:

typename detail::BruidhinnTraits<Element>::const_reference

◆ Degree

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Degree = typename Traits::Degree

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature size_t operator()(Element const& x) const (possibly noexcept, inline and/or constexpr also).

The return value of the call operator ought to indicate the degree of a Element instance which may or may not depend on the parameter x. The degree of a permutation, for instance, would be the the number of points it acts on, the degree of a matrix is its dimension, and so on. This is used, for example, by SchreierSimsTraits in some member functions to determine whether it is known a priori that a permutation does not belong to the object, because it acts on too many points.

Template Parameters

Element the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

Example: template <>

struct Degree<BMat8> {

constexpr inline size_t operator()(BMat8 const&) const noexcept {

return 8;

}

};

libsemigroups::BMat8
Fast boolean matrices of dimension up to 8 x 8.
Definition bmat8.hpp:74

◆ element_index_type

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using element_index_type = FroidurePinBase::element_index_type

The size of the semigroup being enumerated must be at most std::numeric_limits<element_index_type>::max().

◆ EqualTo

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using EqualTo = typename Traits::EqualTo

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature bool operator()(Value const&, Value const&) (possibly noexcept, inline and/or constexpr also) for use with, for example, std::unordered_map.

Template Parameters

Value the type of objects to compare.

The second template parameter exists for SFINAE.

Used by:

◆ Hash

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Hash = typename Traits::Hash

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature size_t operator()(Value const&) for use with, for example, std::unordered_map.

Template Parameters

Value the type of objects to compare.

The second template parameter exists for SFINAE.

Used by:

◆ IncreaseDegree

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using IncreaseDegree = typename Traits::IncreaseDegree

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature void operator()(Element& x, size_t n) const (possibly noexcept, inline and/or constexpr also).

The call operator should change the first argument in-place so that if m = Degree<Element>()(x), then after the call to IncreaseDegree<Element>()(x, n), Degree<Element>()(x) returns m + n. This only makes sense for certain types of elements, such as permutations, transformations, or matrices, and not for other types of object. In the latter case, the call operator should simply do nothing. This is used, for example, in the member function FroidurePin::closure, when one of the generators being added has degree larger than the existing generators.

Template Parameters

Element the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

FroidurePinTraits

Example: template <typename Integral>

struct IncreaseDegree<

Integral,

typename std::enable_if<std::is_integral<Integral>::value>::type>

{

void operator()(Integral&, size_t) const noexcept {

}

};

std

◆ Less

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Less = typename Traits::Less

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature bool operator()(Value const&, Value const&) (possibly noexcept, inline and/or constexpr also) which defines a linear order on the objects of type Value.

Template Parameters

Value the type of objects to compare.

The second template parameter exists for SFINAE.

Used by:

FroidurePinTraits

◆ One

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using One = typename Traits::One

Specialisations of this struct should be stateless trivially default constructible with two call operator of signatures:

Element operator()(size_t n) const (possibly noexcept, inline and/or constexpr also) returning a multiplicative identity element for the category Element and with Degree<Element>()(x) equal to the parameter n. For example, if Element is a type of n x n matrices, then this should return the n x n identity matrix.
Element operator()(T const&) const (possibly noexcept, inline and/or constexpr also). This could be implemented as:
Element operator()(Element const& x) const noexcept {

return this->operator()(Degree<Element>()(x));

}

Template Parameters

Element the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

Example: template <typename T>

struct One<

T,

typename std::enable_if<std::is_base_of<PTransf16, T>::value>::type> {

T operator()(size_t = 0) const noexcept {

return T::one();

}

T operator()(T const&) const noexcept {

return T::one();

}

};

◆ Product

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Product = typename Traits::Product

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature void operator()(Element&, Element const&, Element const&, size_t = 0) (possibly noexcept, inline and/or constexpr also).

The call operator should change xy in-place to be the product of x and y. The 4th parameter is optional and it can be used as an index for static thread local storage, that might be required for forming the product of x and y. The purpose of the 1st parameter is to avoid repeated allocations of memory to hold temporary products that are discarded soon after they are created.

Template Parameters

Element the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

Example: template <>

struct Product<size_t> {

void operator()(size_t& xy, size_t x, size_t y, size_t = 0) const

noexcept {

xy = x * y;

}

};

◆ rvalue_reference

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using rvalue_reference

Initial value:

typename detail::BruidhinnTraits<Element>::rvalue_reference

◆ size_type

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using size_type = FroidurePinBase::size_type

◆ Swap

template<typename Element, typename Traits = FroidurePinTraits<Element>>

using Swap = typename Traits::Swap

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature void operator()(Value&, Value&) (possibly noexcept, inline and/or constexpr also) which swaps its arguments.

Template Parameters

Value the type of objects to swap.

The second template parameter exists for SFINAE.

Used by:

Constructor & Destructor Documentation

◆ FroidurePin() [1/5]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin ( )

Constructs a FroidurePin instance with no generators.

See also: add_generator and add_generators.

◆ FroidurePin() [2/5]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename State, typename = std::enable_if_t<IsState<State>>>

FroidurePin ( std::shared_ptr< State > stt )

inlineexplicit

This function allows the construction of a FroidurePin instance with stated given by the parameter stt. This constructor only exists if state_type is not void. This is used when the elements require some shared state to define their multiplication, such as, for example an instance of KnuthBendix or ToddCoxeterImpl.

Parameters

stt	a std::shared_ptr to a state object.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ FroidurePin() [3/5]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename State, typename = std::enable_if_t<IsState<State>>>

FroidurePin ( State const & stt )

inlineexplicit

This function allows the construction of a FroidurePin instance with stated given by the parameter stt. This constructor only exists if state_type is not void. This is used when the elements require some shared state to define their multiplication, such as, for example an instance of KnuthBendix or ToddCoxeterImpl.

Parameters

stt	a const reference to a state object.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: The parameter stt is copied, which might be expensive, use a std::shared_ptr to avoid the copy.

◆ FroidurePin() [4/5]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin	(	Iterator1	first,
		Iterator2	last )

This function constructs a FroidurePin instance with generators in the range pointed to by the iterators first and last.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Warning: This function does not check its arguments. In particular, it is assumed that the generators pointed to by first and last all have the same degree.

◆ FroidurePin() [5/5]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin ( FroidurePin< Element, Traits > const & that )

Constructs a new FroidurePin which is an exact copy of that. No enumeration is triggered for either that or of the newly constructed FroidurePin object.

Parameters

that	the FroidurePin to copy.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Member Function Documentation

◆ add_generator()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin & add_generator ( const_reference x )

This function can be used to add a new generator to an existing FroidurePin instance in such a way that any previously enumerated data is preserved and not recomputed, or copied. This can be faster than recomputing the semigroup generated by the old generators and the new generators.

This function changes the semigroup in-place, thereby invalidating possibly previously known data about the semigroup, such as the left or right Cayley graphs, number of idempotents, and so on.

The generator x is added regardless of whether or not it is already a generator or element of the semigroup (it may belong to the semigroup but just not be known to belong).

There can be duplicate generators and although they do not count as distinct elements, they do count as distinct generators. In other words, the generators are precisely (a copy of) the arguments of any calls to this function in the same order as the function calls.

The FroidurePin instance is returned in a state where all of the previously enumerated elements, which had been multiplied by all of the old generators, have now been multiplied by the old and new generators. This means that after this function is called the semigroup might contain many more elements than before (whether it is fully enumerating or not).

Parameters

x	the generator to add.

Exceptions

LibsemigroupsException if the degree of x is incompatible with the existing degree (if any).

Note: This function triggers a (possibly partial) enumeration if and only if it is called on an already partially enumerated FroidurePin instance (i.e. if started returns true).

◆ add_generator_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin & add_generator_no_checks ( const_reference x )

This function can be used to add new generators to an existing FroidurePin instance in such a way that any previously enumerated data is preserved and not recomputed, or copied. This can be faster than rerunning a FroidurePin instance generated by the old generators and the new generators.

This function changes the FroidurePin object in-place, thereby invalidating possibly previously known data, such as the left or right Cayley graphs, number of idempotents, and so on.

The element x is added regardless of whether or not it is already a generator or element of the semigroup (it may belong to the semigroup but just not be known to belong). The new generator added will be the generator with the current highest index.

The FroidurePin instance is returned in a state where all of the previously enumerated elements which had been multiplied by all of the old generators, have now been multiplied by all of the old and new generators. This means that after this function is called a FroidurePin instance might contain many more elements than before (whether it is fully enumerating or not).

Parameters

x	the generator to add.

Returns: A const reference to *this.

Note: This function triggers a (possibly partial) enumeration if and only if it is called on an already partially enumerated FroidurePin instance (i.e. if started returns true).

Warning: This function does not check its argument. In particular, it is assumed that the element x has the same degree as any existing generators.

◆ add_generators()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin & add_generators	(	Iterator1	first,
		Iterator2	last )

See add_generator for a detailed description.

Template Parameters

the	type of an iterator pointing to an element_type.

Parameters

first	iterator pointing to the first generator to add.
last	iterator pointing one past the last generator to add.

Exceptions

LibsemigroupsException if any of the degree of x is incompatible with the existing degree.

Note: This function triggers a (possibly partial) enumeration if and only if it is called on an already partially enumerated FroidurePin instance (i.e. if started returns true).

◆ add_generators_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin & add_generators_no_checks	(	Iterator1	first,
		Iterator2	last )

See add_generator for a detailed description.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing to the first generator to add.
last	iterator pointing one past the last generator to add.

Note: This function triggers a (possibly partial) enumeration if and only if it is called on an already partially enumerated FroidurePin instance (i.e. if started returns true).

Warning: This function does not check its arguments. In particular, it is assumed that the generators pointed to by first and last all have the same degree.

◆ at()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference at ( element_index_type i )

nodiscard

This function attempts to enumerate until at least i + 1 elements have been found.

Parameters

i	the index of the element to access.

Returns: The element with index i (if any).

Exceptions

LibsemigroupsException if i is greater than or equal to the return value of size().

Note: This function triggers a full enumeration.

◆ begin()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator begin ( ) const

nodiscard

This function does not trigger any enumeration, and the returned iterators may be invalidated by any call to a non-const function of the FroidurePin class.

Returns: A value of type const_iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

See also: cbegin.

◆ cbegin()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator cbegin ( ) const

nodiscard

This function does not trigger any enumeration, and the returned iterators may be invalidated by any call to a non-const function of the FroidurePin class.

Returns: A value of type const_iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

See also: begin.

◆ cbegin_idempotents()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator_idempotents cbegin_idempotents ( )

nodiscard

If the returned iterator is incremented, then it points to the second idempotent in the semigroup (if it exists), and every subsequent increment points to the next idempotent.

Returns: A value of type const_iterator_idempotents.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

◆ cbegin_sorted()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator_sorted cbegin_sorted ( )

nodiscard

This function returns a const iterator pointing to the first element (sorted by Less).

Returns: A value of type const_iterator_sorted.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

◆ cend()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator cend ( ) const

nodiscard

This function does not trigger any enumeration, and the returned iterators may be invalidated by any call to a non-const function of the FroidurePin class.

Returns: A value of type const_iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

See also: end.

◆ cend_idempotents()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator_idempotents cend_idempotents ( )

nodiscard

This function returns a const iterator pointing one past the last idempotent.

Returns: A value of type const_iterator_idempotents.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

◆ cend_sorted()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator_sorted cend_sorted ( )

nodiscard

This function returns a const iterator pointing one past the last element (sorted by Less).

Returns: A value of type const_iterator_sorted.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

◆ closure()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin & closure	(	Iterator1	first,
		Iterator2	last )

inline

See closure_no_checks for full details.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A reference to *this.

Exceptions

LibsemigroupsException	if any of the elements pointed to by `first` and `last` do not have degree compatible with any existing elements of the FroidurePin instance.
LibsemigroupsException	if the elements pointed to by `first` and `last` do not all have the same degree.

Note: This function triggers at least a partial enumeration of the FroidurePin instance on which it is called.

◆ closure_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin & closure_no_checks	(	Iterator1	first,
		Iterator2	last )

Add copies of the non-redundant generators pointed at by first and last to this.

This function differs from add_generators in that it tries to add the new generators one by one, and only adds those generators that are not products of existing generators (including any new generators that were added before). The generators are added in the order they are given (from first to last).

This function changes this in-place, thereby invalidating some previously computed information, such as the left or right Cayley graphs, or number of idempotents, for example.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A reference to *this.

Note: This function triggers at least a partial enumeration of the FroidurePin instance on which it is called.

Warning: This function does not check its arguments. In particular, it is assumed that the elements pointed to by first and last all have the same degree.

◆ contains()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

bool contains ( const_reference x )

nodiscard

This function returns true if x belongs to this and false if it does not.

Parameters

x	a const reference to a possible element.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function may trigger a (partial) enumeration.

◆ copy_add_generators()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin copy_add_generators	(	Iterator1	first,
		Iterator2	last ) const

inlinenodiscard

See copy_add_generators_no_checks for a full description.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A new FroidurePin instance by value generated by the generators of this and coll.

Exceptions

LibsemigroupsException	if any of the elements pointed to by `first` and `last` do not have degree compatible with any existing elements of the FroidurePin instance.
LibsemigroupsException	if the elements pointed to by `first` and `last` do not all have the same degree.

Note: This function does not trigger any enumeration of the object it is called on, it might trigger a (possibly partial) enumeration of the returned copy (see add_generators for details).

◆ copy_add_generators_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin copy_add_generators_no_checks	(	Iterator1	first,
		Iterator2	last ) const

nodiscard

This function is equivalent to copy constructing a new FroidurePin instance and then calling add_generators on the copy. But this function avoids copying the parts of this that are immediately invalidated by add_generators.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A new FroidurePin instance by value generated by the generators of this and the elements in the range from first to last.

Note: This function does not trigger any enumeration of the object it is called on, it might trigger a (possibly partial) enumeration of the returned copy (see add_generators for details).

◆ copy_closure()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin copy_closure	(	Iterator1	first,
		Iterator2	last )

inlinenodiscard

This function is equivalent to copy constructing a new FroidurePin instance and then calling closure on the copy. But this function avoids copying the parts of this that are immediately invalidated by closure.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A new FroidurePin instance by value generated by the generators of this and the non-redundant generators in the range from first to last.

Exceptions

LibsemigroupsException	if any of the elements pointed to by `first` and `last` do not have degree compatible with any existing elements of the FroidurePin instance.
LibsemigroupsException	if the elements pointed to by `first` and `last` do not all have the same degree.

Note: This function may trigger an enumeration of the FroidurePin instance on which it is called, and the returned copy.

◆ copy_closure_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin copy_closure_no_checks	(	Iterator1	first,
		Iterator2	last )

nodiscard

This function is equivalent to copy constructing a new FroidurePin instance and then calling closure on the copy. But this function avoids copying the parts of this that are immediately invalidated by closure.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Returns: A new FroidurePin instance by value generated by the generators of this and the non-redundant generators in the range from first to last.

Note: This function may trigger an enumeration of the FroidurePin instance on which it is called, and the returned copy.

Warning: This function does not check its arguments. In particular, it is assumed that the generators pointed to by first and last all have the same degree.

◆ current_position()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type current_position ( const_reference x ) const

nodiscard

This function returns the position of the element x in the semigroup if it is already known to belong to the semigroup or UNDEFINED. This function finds the position of the element x if it is already known to belong to this, and UNDEFINED if not. If this is not yet fully enumerated, then this function may return UNDEFINED when x does belong to this.

Parameters

x	a const reference to a possible element.

Returns: A value of type element_index_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function does not trigger any enumeration.

See also: position and sorted_position.

◆ end()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_iterator end ( ) const

nodiscard

This function does not trigger any enumeration, and the returned iterators may be invalidated by any call to a non-const function of the FroidurePin class.

Returns: A value of type const_iterator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

See also: cend.

◆ equal_to()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool equal_to	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 ) const

inlinenodiscard

This function returns true if the parameters represent the same element and false otherwise.

Template Parameters

Iterator1	the type of the first argument.
Iterator2	the type of the second argument.
Iterator3	the type of the third argument.
Iterator4	the type of the fourth argument.

Parameters

first1	iterator pointing at the start of the first word.
last1	iterator pointing one beyond the end of the first word.
first2	iterator pointing at the start of the second word.
last2	iterator pointing one beyond the end of the second word.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if w contains a value greater than or equal to number_of_generators.

Note: This function does not trigger any enumeration.

◆ equal_to_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool equal_to_no_checks	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 ) const

nodiscard

This function returns true if the parameters represent the same element and false otherwise.

Template Parameters

Iterator1	the type of the first argument.
Iterator2	the type of the second argument.
Iterator3	the type of the third argument.
Iterator4	the type of the fourth argument.

Parameters

first1	iterator pointing at the start of the first word.
last1	iterator pointing one beyond the end of the first word.
first2	iterator pointing at the start of the second word.
last2	iterator pointing one beyond the end of the second word.

Returns: A value of type bool.

Note: This function does not trigger any enumeration.

Warning: This function does not check its arguments. In particular, it is assumed that every value in the ranges from first1 to last1 and from first2 to last2 is strictly less than number_of_generators.

◆ fast_product()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type fast_product	(	element_index_type	i,
		element_index_type	j ) const

inlinenodiscard

See fast_product_no_checks for a full description.

Parameters

i	the index of the first element to multiply.
j	the index of the second element to multiply.

Returns: The index of the product.

Exceptions

LibsemigroupsException if the values i and j are greater than or equal to current_size.

Note: This function does not trigger any enumeration.

◆ fast_product_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type fast_product_no_checks	(	element_index_type	i,
		element_index_type	j ) const

nodiscard

This function returns the position of the product of the element with index i and the element with index j.

This function either:

follows the path in the right or left Cayley graph from i to j, whichever is shorter using product_by_reduction; or
multiplies the elements in positions i and j together;

whichever is better. The option used is determined by comparing the output of the call operator of the Complexity adapter and the current_length of i and j.

For example, if the complexity of the multiplication is linear and this is a semigroup of transformations of degree 20, and the shortest paths in the left and right Cayley graphs from i to j are of length 100 and 1131, then it is better to just multiply the transformations together.

Parameters

i	the index of the first element to multiply.
j	the index of the second element to multiply.

Returns: The index of the product.

Note: This function does not trigger any enumeration.

Warning: The arguments of this function are not checked. In particular, it is assumed that both i and j are less than current_size.

◆ generator()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference generator ( generator_index_type i ) const

nodiscard

This function returns the generator with index i, where the order is that in which the generators were added at construction, or via init, add_generator, add_generators, closure, copy_closure, or copy_add_generators.

Parameters

i	the index of a generator.

Returns: The generator with given index.

Exceptions

LibsemigroupsException if i is greater than or equal to number_of_generators().

Note: Note that generator(j) is in general not in position j.; This function does not trigger any enumeration.

◆ generator_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference generator_no_checks ( generator_index_type i ) const

nodiscard

This function returns the generator with index i, where the order is that in which the generators were added at construction, or via init, add_generator, add_generators, closure, copy_closure, or copy_add_generators.

Parameters

i	the index of a generator.

Returns: The generator with given index.

Note: Note that generator(j) is in general not in position j.; This function does not trigger any enumeration.

Warning: This function does not check its arguments. In particular it is assumed that i is less than number_of_generators.

◆ init() [1/4]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin & init ( )

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been default constructed.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ init() [2/4]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

FroidurePin & init	(	Iterator1	first,
		Iterator2	last )

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been constructed from first and last.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Warning: This function does not check its arguments. In particular, it is assumed that the generators pointed to by first and last all have the same degree.

◆ init() [3/4]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename State, typename = std::enable_if_t<IsState<State>>>

FroidurePin & init ( State const & stt )

inline

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been constructed from stt.

Parameters

stt	a const reference to the state (if any).

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ init() [4/4]

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename State, typename = std::enable_if_t<IsState<State>>>

FroidurePin & init ( std::shared_ptr< State > stt )

inline

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been constructed from stt.

Parameters

stt	a std::shared_ptr to the state (if any).

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ is_finite()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

tril is_finite ( ) const

inlinenodiscardoverride

This function returns tril::TRUE if the semigroup represented by this is finite, tril::FALSE if it is infinite, and tril::unknown if it is not known.

For some types of elements, such as matrices over the integers, for example, it is undecidable, in general, if the semigroup generated by these elements is finite or infinite. On the other hand, for other types, such as transformation, the semigroup is always finite.

Returns: A value of type tril.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: No enumeration is triggered by calls to this function.

◆ is_idempotent()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

bool is_idempotent ( element_index_type i )

inlinenodiscard

This function returns true if the element in position i is an idempotent and false if it is not.

Parameters

i	the index of the element.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if i is greater than or equal to the size of this.

Note: This function triggers a full enumeration.

◆ is_idempotent_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

bool is_idempotent_no_checks ( element_index_type i )

nodiscard

This function returns true if the element in position i is an idempotent and false if it is not.

Parameters

i	the index of the element.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if i is greater than or equal to the size of this.

Note: This function triggers a full enumeration.

◆ number_of_generators()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

size_t number_of_generators ( ) const

nodiscardoverridenoexcept

This function returns the number of generators.

Returns: The number of generators.

Exceptions: This function is noexcept and is guaranteed never to throw.

Note: This function does not trigger any enumeration.

◆ number_of_idempotents()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

size_t number_of_idempotents ( )

nodiscard

This function returns the number of idempotents in the semigroup represented by a FroidurePin instance.

Returns: The number of idempotents..

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

◆ operator[]()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference operator[] ( element_index_type i ) const

This function attempts to enumerate until at least i + 1 elements have been found.

Parameters

i	the index of the element to access.

Returns: The element with index i (if any).

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function does not trigger any enumeration.

◆ position()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type position ( const_reference x )

nodiscard

This function returns the position of x in this, or UNDEFINED if x is not an element of this.

Parameters

x	a const reference to a possible element.

Returns: A value of type element_index_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

See also: current_position and sorted_position.

◆ reserve()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

FroidurePin & reserve ( size_t val )

The parameter val is also used to initialise certain data members. If you know a good upper bound for the size of your semigroup, then it might be a good idea to call this function with that upper bound as an argument; this can significantly improve the performance of the run function, and consequently every other function too.

Parameters

val	the number of elements to reserve space for.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function does not trigger any enumeration.

◆ sorted_at()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference sorted_at ( element_index_type i )

nodiscard

This function triggers a full enumeration, and the parameter i is the index when the elements are sorted by Less.

Parameters

i	the sorted index of the element to access.

Returns: The element with index i (if any).

Exceptions

LibsemigroupsException if i is greater than or equal to the return value of size().

Note: This function triggers a full enumeration.

◆ sorted_at_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

const_reference sorted_at_no_checks ( element_index_type i )

nodiscard

This function triggers a full enumeration, and the parameter i is the index when the elements are sorted by Less.

Parameters

i	the sorted index of the element to access.

Returns: The element with index i (if any).

Note: This function triggers a full enumeration.

Warning: This function does not check its arguments. In particular, it assumes that i is less than size.

◆ sorted_position()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type sorted_position ( const_reference x )

nodiscard

This function returns the position of x in the elements of this when they are sorted by Less, or UNDEFINED if x is not an element of this.

Parameters

x	a const reference to a possible element.

Returns: A value of type element_index_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

See also: current_position and position.

◆ state()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

std::shared_ptr< state_type > state ( ) const

inline

Returns: std::shared_ptr to state_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ throw_if_inconsistent_degree()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

static void throw_if_inconsistent_degree	(	Iterator1	first,
		Iterator2	last )

static

This function throws a LibsemigroupsException if the elements in the range defined by the iterators first and last do not all have the same degree.

Template Parameters

Iterator1	the type of the first parameter.
Iterator2	the type of the second parameter.

Parameters

first	iterator pointing at the first generator to add.
last	iterator pointing one beyond the last generator to add.

Exceptions

LibsemigroupsException if the elements in the range defined by first and last do not all have the same degree.

◆ to_element()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

const_reference to_element	(	Iterator1	first,
		Iterator2	last ) const

nodiscard

This function returns a const reference to the element obtained by taking the product of the generators with indices in the range from first to last. The returned reference may only be valid until the next function that triggers an enumeration is called, or another call to this function is made.

Template Parameters

Iterator1	the type of the first argument.
Iterator2	the type of the second argument.

Parameters

first	iterator pointing to the first letter of the word.
last	iterator pointing one beyond the last letter of the word.

Returns: A const reference to the element represented by the word given by first and last.

Exceptions

LibsemigroupsException	if the values in pointed at by iterators in the range `first` to `last` are not all strictly less than number_of_generators.
LibsemigroupsException	if `first` and `last` are equal (i.e. the word they represent is empty) and currently_contains_one returns `true`.

Note: This function does not trigger any enumeration.

See also: current_position.

◆ to_element_no_checks()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

template<typename Iterator1, typename Iterator2>

const_reference to_element_no_checks	(	Iterator1	first,
		Iterator2	last ) const

nodiscard

This function returns a const reference to the element obtained by taking the product of the generators with indices in the range from first to last. The returned reference may only be valid until the next function that triggers an enumeration is called, or another call to this function is made.

Template Parameters

Iterator1	the type of the first argument.
Iterator2	the type of the second argument.

Parameters

first	iterator pointing to the first letter of the word.
last	iterator pointing one beyond the last letter of the word.

Returns: A const reference to the element represented by the word given by first and last.

Note: This function does not trigger any enumeration.

Warning: This function does not check its arguments, and it is assumed that the values in w are less than number_of_generators; and if w is empty it is assumed that currently_contains_one returns true (although nothing bad will happen if this doesn't hold, except that this function will return the identity element even though it might not be an element).

See also: current_position.

◆ to_sorted_position()

template<typename Element, typename Traits = FroidurePinTraits<Element>>

element_index_type to_sorted_position ( element_index_type i )

nodiscard

This function returns the position of the element with index i when the elements are sorted using Less, or UNDEFINED if i is greater than size().

Parameters

i	the index of the element.

Returns: A value of type element_index_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function triggers a full enumeration.

Friends And Related Symbol Documentation

◆ FroidurePin()

template<typename Iterator1, typename Iterator2>

FroidurePin	(	Iterator1	,
		Iterator2	) -> FroidurePin< std::decay_t< decltype(*std::declval< Iterator1 >())> >

Deduction guide for constructing FroidurePin<Element> where Element is the type pointed to by Iterator1 and Iterator2.

◆ to_human_readable_repr()

template<typename Element, typename Traits>

std::string to_human_readable_repr ( FroidurePin< Element, Traits > const & fp )

Return a human readable representation of a FroidurePin object.

Template Parameters

Element	the type of the elements in the represented semigroup.
Traits	a traits class holding various adapters used by the implementation.

Parameters

fp	the FroidurePin object.

Returns: A string containing a human readable representation of fp.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

/Users/jdm/libsemigroups/include/libsemigroups/froidure-pin.hpp

Public Types

Public Member Functions

Static Public Member Functions

Related Symbols

Member Typedef Documentation

◆ cayley_graph_type

◆ Complexity

◆ const_element_type

◆ const_iterator

◆ const_iterator_idempotents

◆ const_iterator_sorted

◆ const_pointer

◆ const_reference

◆ Degree

◆ element_index_type

◆ EqualTo

◆ Hash

◆ IncreaseDegree

◆ Less

◆ One

◆ Product

◆ rvalue_reference

◆ size_type

◆ Swap

Constructor & Destructor Documentation

◆ FroidurePin() [1/5]

◆ FroidurePin() [2/5]

◆ FroidurePin() [3/5]

◆ FroidurePin() [4/5]

◆ FroidurePin() [5/5]

Member Function Documentation

◆ add_generator()

◆ add_generator_no_checks()

◆ add_generators()

◆ add_generators_no_checks()

◆ at()

◆ begin()

◆ cbegin()

◆ cbegin_idempotents()

◆ cbegin_sorted()

◆ cend()

◆ cend_idempotents()

◆ cend_sorted()

◆ closure()

◆ closure_no_checks()

◆ contains()

◆ copy_add_generators()

◆ copy_add_generators_no_checks()

◆ copy_closure()

◆ copy_closure_no_checks()

◆ current_position()

◆ end()

◆ equal_to()

◆ equal_to_no_checks()

◆ fast_product()

◆ fast_product_no_checks()

◆ generator()

◆ generator_no_checks()

◆ init() [1/4]

◆ init() [2/4]

◆ init() [3/4]

◆ init() [4/4]

◆ is_finite()

◆ is_idempotent()

◆ is_idempotent_no_checks()

◆ number_of_generators()

◆ number_of_idempotents()

◆ operator[]()

◆ position()

◆ reserve()

◆ sorted_at()

◆ sorted_at_no_checks()

◆ sorted_position()

◆ state()

◆ throw_if_inconsistent_degree()

◆ to_element()

◆ to_element_no_checks()

◆ to_sorted_position()

Friends And Related Symbol Documentation

◆ FroidurePin()