FroidurePin¶
-
template<typename TElementType, typename TTraits = FroidurePinTraits<TElementType>>
class FroidurePin : private libsemigroups::detail::BruidhinnTraits<TElementType>, public libsemigroups::FroidurePinBase¶ Defined in
froidure-pin.hpp
.The class template FroidurePin implements the Froidure-Pin algorithm as described in the article “Algorithms for computing finite semigroups” by Veronique Froidure and Jean-Eric Pin; see this for more details.
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, the left and right Cayley graphs are determined, and a confluent terminating presentation for the semigroup is known.See also
- 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
- Template Parameters
TElementType – the type of the elements in the represented semigroup
TTraits – a traits class holding various adapters used by the implementation (defaults to FroidurePinTraits).
Member types¶
Type of const elements. |
|
Return type of |
|
Return type of |
|
Type of element const pointers. |
|
Type of element const references. |
|
Return type of |
|
Type of the elements. |
|
Type of element references. |
|
Type of the state used for multiplication (if any). |
|
Alias for element_type. |
Adapter member types¶
Adapter for the complexity of multiplication. |
|
Adapter for the degree of an element. |
|
Adapter for testing equality. |
|
Adapter for hashing. |
|
Adapter for increasing the degree of an element. |
|
Adapter for comparisons. |
|
Adapter for the identity element of the given type. |
|
Adapter for the product of two elements. |
|
Adapter for swapping. |
Constructors¶
Default constructor. |
|
Default move constructor. |
|
Copy constructor. |
|
Construct from const reference to state. |
|
Construct from generators. |
|
Construct from std::shared_ptr to state. |
|
Construct from generators. |
Deleted constructors¶
Deleted. |
|
Deleted. |
Initialisation¶
Add a copy of an element to the generators. |
|
Add collection of generators via const reference. |
|
Add collection of generators via iterators. |
|
Add collection of generators via initializer list. |
|
Add non-redundant generators in collection. |
|
Add non-redundant generators in collection. |
|
Copy and add a collection of generators. |
|
Copy and add a collection of generators. |
|
Copy and add non-redundant generators. |
|
Copy and add non-redundant generators. |
|
Returns a std::shared_ptr to the state (if any). |
Factorisation and relations¶
Factorise an element as a word in the generators. |
|
Factorise an element as a word in the generators. |
|
Convert a word in the generators to an element. |
Membership¶
Access element specified by index with bound checks. |
|
Test membership of an element. |
|
Find the position of an element with no enumeration. |
|
Returns the generator with specified index. |
|
Access element specified by index. |
|
Find the position of an element with enumeration if necessary. |
|
Access element specified by sorted index with bound checks. |
|
Returns the sorted index of an element. |
Iterators¶
Returns a const iterator pointing to the first element (ordered by discovery). |
|
Returns a const iterator pointing to the first element (ordered by discovery). |
|
Returns a const iterator pointing at the first idempotent. |
|
Returns a const iterator pointing to the first element (sorted by |
|
Returns a const iterator pointing to one past the last known element. |
|
Returns a const iterator pointing one past the last idempotent. |
|
Returns a const iterator pointing one past the last element (sorted by |
|
Returns a const reverse iterator pointing to the last known element. |
|
Returns a const iterator pointing to the last element (sorted by |
|
Returns a const reverse iterator pointing one before the first element. |
|
Returns a const reverse iterator pointing one before the first element (sorted by |
|
Returns a const iterator pointing one past the last known element. |
Virtual functions from FroidurePinBase¶
|
Check equality of words in the generators. |
|
Multiply elements via their indices. |
Check finiteness. |
|
Check if an element is an idempotent via its index. |
|
Returns the number of generators. |
|
Returns the number of idempotents. |
|
Returns the sorted index of an element via its index. |
|
Requests the given capacity for elements. |
Member functions inherited from FroidurePinBase¶
Returns the current value of the batch size. |
|
Set a new value for the batch size. |
|
Type for a left or right Cayley graph. |
|
Returns a forward iterator pointing to the first rule (if any). |
|
Returns a forward iterator pointing one past the last rule (if any). |
|
Returns the current value of the concurrency threshold. |
|
Set the threshold for concurrency to be used by member functions. |
|
Returns the length of the short-lex least word. |
|
Returns the maximum length of a word in the generators so far computed. |
|
Returns the number of relations that have been found so far. |
|
Returns the position in of the generator with specified index. |
|
|
Returns the position corresponding to a word. |
Returns the position corresponding to a word. |
|
Returns the number of elements so far enumerated. |
|
Returns the degree of any and all elements. |
|
Type for the index of an element. |
|
Enumerate until at least a specified number of elements are found. |
|
Returns a word representing an element given by index. |
|
Obtain a word representing an element given by index. |
|
Returns the last letter of the element with specified index. |
|
Returns the first letter of the element with specified index. |
|
Returns the current immutability. |
|
Set immutability. |
|
Check if the semigroup is a monoid. |
|
Returns the index of the product of a generator and an element. |
|
Returns a const reference to the left Cayley graph. |
|
Returns the length of the short-lex least word. |
|
Returns the current value of the maximum number of threads. |
|
Set the maximum number of threads. |
|
Returns a short-lex least word representing an element given by index. |
|
Obtain a short-lex least word representing an element given by index. |
|
Obtain a short-lex least word representing an element given by index. |
|
Returns the total number of relations in the presentation. |
|
Returns the position of the longest proper prefix. |
|
|
Compute a product using the Cayley graph. |
Returns the index of the product of an element and a generator. |
|
Returns a const reference to the right Cayley graph. |
|
Returns the size. |
|
Unsigned integer type. |
|
Returns the position of the longest proper suffix. |
Member functions inherited from Runner¶
Check if the runner is dead. |
|
Check if |
|
Stop |
|
Check if it is time to report. |
|
Get the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Report why |
|
Run until |
|
Run for a specified amount of time. |
|
Run for a specified amount of time. |
|
Run until a nullary predicate returns |
|
Run until a nullary predicate returns |
|
Check if currently running. |
|
Check if the runner is currently running for a particular length of time. |
|
Check if the runner is currently running until a nullary predicate returns |
|
Check if |
|
Check if the runner is stopped. |
|
Check if the runner was, or should, stop because of the argument for |
|
Check if the amount of time passed to |