# 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.

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¶

 `const_element_type` Type of const elements. `const_iterator` Return type of `cbegin` and `cend` . `const_iterator_idempotents` Return type of `cbegin_idempotents` and `cend_idempotents` . `const_iterator_sorted` Return type of `cbegin_sorted` and `cend_sorted` . `const_pointer` Type of element const pointers. `const_reference` Type of element const references. `const_reverse_iterator` Return type of `crbegin` and `crend` . `const_reverse_iterator_sorted` Return type of `crbegin_sorted` and `crend_sorted` . `element_type` Type of the elements. `reference` Type of element references. `state_type` Type of the state used for multiplication (if any). `value_type` Alias for element_type.

 `Complexity` Adapter for the complexity of multiplication. `Degree` Adapter for the degree of an element. `EqualTo` Adapter for testing equality. `Hash` Adapter for hashing. `IncreaseDegree` Adapter for increasing the degree of an element. `Less` Adapter for comparisons. `One` Adapter for the identity element of the given type. `Product` Adapter for the product of two elements. `Swap` Adapter for swapping.

## Constructors¶

 `FroidurePin()` Default constructor. `FroidurePin(FroidurePin &&) = default` Default move constructor. `FroidurePin(FroidurePin const&)` Copy constructor. `FroidurePin(T const &)` Construct from const reference to state. `FroidurePin(std::initializer_list)` Construct from generators. `FroidurePin(std::shared_ptr)` Construct from std::shared_ptr to state. `FroidurePin(std::vector const&)` Construct from generators.

## Initialisation¶

 `add_generator(const_reference)` Add a copy of an element to the generators. `add_generators(T const&)` Add collection of generators via const reference. `add_generators(T const&, T const&)` Add collection of generators via iterators. `add_generators(std::initializer_list)` Add collection of generators via initializer list. `closure(T const&)` Add non-redundant generators in collection. `closure(std::initializer_list)` Add non-redundant generators in collection. `copy_add_generators(T const &) const` Copy and add a collection of generators. `copy_add_generators(std::initializer_list< element_type >)` Copy and add a collection of generators. `copy_closure(T const &)` Copy and add non-redundant generators. `copy_closure(std::initializer_list< element_type >)` Copy and add non-redundant generators. `state() const` Returns a std::shared_ptr to the state (if any).

## Factorisation and relations¶

 `factorisation(const_reference)` Factorise an element as a word in the generators. `minimal_factorisation(const_reference)` Factorise an element as a word in the generators. `word_to_element(word_type const &) const` Convert a word in the generators to an element.

## Membership¶

 `at(element_index_type)` Access element specified by index with bound checks. `contains(const_reference)` Test membership of an element. `current_position(const_reference) const` Find the position of an element with no enumeration. `generator(letter_type) const` Returns the generator with specified index. `operator[](element_index_type) const` Access element specified by index. `position(const_reference)` Find the position of an element with enumeration if necessary. `sorted_at(element_index_type)` Access element specified by sorted index with bound checks. `sorted_position(const_reference)` Returns the sorted index of an element.

## Iterators¶

 `begin() const` Returns a const iterator pointing to the first element (ordered by discovery). `cbegin() const` Returns a const iterator pointing to the first element (ordered by discovery). `cbegin_idempotents()` Returns a const iterator pointing at the first idempotent. `cbegin_sorted()` Returns a const iterator pointing to the first element (sorted by `Less` ). `cend() const` Returns a const iterator pointing to one past the last known element. `cend_idempotents()` Returns a const iterator pointing one past the last idempotent. `cend_sorted()` Returns a const iterator pointing one past the last element (sorted by `Less` ). `crbegin() const` Returns a const reverse iterator pointing to the last known element. `crbegin_sorted()` Returns a const iterator pointing to the last element (sorted by `Less` ). `crend() const` Returns a const reverse iterator pointing one before the first element. `crend_sorted()` Returns a const reverse iterator pointing one before the first element (sorted by `Less` ). `end() const` Returns a const iterator pointing one past the last known element.

## Virtual functions from FroidurePinBase¶

 `equal_to(word_type const &,word_type const &) const override` Check equality of words in the generators. `fast_product(element_index_type,element_index_type) const override` Multiply elements via their indices. `is_finite() const override` Check finiteness. `is_idempotent(element_index_type) override` Check if an element is an idempotent via its index. `number_of_generators() const noexcept override` Returns the number of generators. `number_of_idempotents() override` Returns the number of idempotents. `position_to_sorted_position(element_index_type) override` Returns the sorted index of an element via its index. `reserve(size_t) override` Requests the given capacity for elements.

## Member functions inherited from FroidurePinBase¶

 `batch_size() const noexcept` Returns the current value of the batch size. `batch_size(size_t) noexcept` Set a new value for the batch size. `cayley_graph_type` Type for a left or right Cayley graph. `cbegin_rules() const` Returns a forward iterator pointing to the first rule (if any). `cend_rules() const` Returns a forward iterator pointing one past the last rule (if any). `concurrency_threshold() const noexcept` Returns the current value of the concurrency threshold. `concurrency_threshold(size_t) noexcept` Set the threshold for concurrency to be used by member functions. `current_length(element_index_type) const` Returns the length of the short-lex least word. `current_max_word_length() const noexcept` Returns the maximum length of a word in the generators so far computed. `current_number_of_rules() const noexcept` Returns the number of relations that have been found so far. `current_position(letter_type) const` Returns the position in of the generator with specified index. `current_position(std::initializer_list< size_t > const &) const` Returns the position corresponding to a word. `current_position(word_type const &) const` Returns the position corresponding to a word. `current_size() const noexcept` Returns the number of elements so far enumerated. `degree() const noexcept` Returns the degree of any and all elements. `element_index_type` Type for the index of an element. `enumerate(size_t)` Enumerate until at least a specified number of elements are found. `factorisation(element_index_type)` Returns a word representing an element given by index. `factorisation(word_type&, element_index_type)` Obtain a word representing an element given by index. `final_letter(element_index_type) const` Returns the last letter of the element with specified index. `first_letter(element_index_type) const` Returns the first letter of the element with specified index. `immutable() const noexcept` Returns the current immutability. `immutable(bool) noexcept` Set immutability. `is_monoid()` Check if the semigroup is a monoid. `left(element_index_type,letter_type)` Returns the index of the product of a generator and an element. `left_cayley_graph()` Returns a const reference to the left Cayley graph. `length(element_index_type)` Returns the length of the short-lex least word. `max_threads() const noexcept` Returns the current value of the maximum number of threads. `max_threads(size_t) noexcept` Set the maximum number of threads. `minimal_factorisation(element_index_type)` Returns a short-lex least word representing an element given by index. `minimal_factorisation(word_type &,element_index_type)` Obtain a short-lex least word representing an element given by index. `minimal_factorisation(word_type &,element_index_type) const` Obtain a short-lex least word representing an element given by index. `number_of_rules()` Returns the total number of relations in the presentation. `prefix(element_index_type) const` Returns the position of the longest proper prefix. `product_by_reduction(element_index_type,element_index_type) const` Compute a product using the Cayley graph. `right(element_index_type,letter_type)` Returns the index of the product of an element and a generator. `right_cayley_graph()` Returns a const reference to the right Cayley graph. `size()` Returns the size. `size_type` Unsigned integer type. `suffix(element_index_type) const` Returns the position of the longest proper suffix.

## Member functions inherited from Runner¶

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