Virtual functions from FroidurePinBase

bool libsemigroups::FroidurePin::equal_to(word_type const &x, word_type const &y) const override

Check equality of words in the generators.

Returns true if the parameters represent the same element and false otherwise.

Parameters:

  • x – the first word for comparison

  • y – the second word for comparison

Throws:

LibsemigroupsException – if w contains an value exceeding number_of_generators.

Returns:

A value of type bool.

element_index_type libsemigroups::FroidurePin::fast_product(element_index_type i, element_index_type j) const override

Multiply elements via their indices.

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 function used is determined by comparing the output of the call operator of Complexity 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

Throws:

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

Returns:

A value of type element_index_type.

inline tril libsemigroups::FroidurePin::is_finite() const override

Check finiteness.

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.

Parameters

(None)

Note

No enumeration is triggered by calls to this function.

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

A value of type tril.

bool libsemigroups::FroidurePin::is_idempotent(element_index_type i) override

Check if an element is an idempotent via its index.

Returns true if the element in position i is an idempotent and false if it is not.

Note

This function triggers a full enumeration.

Parameters:

i – the index of the element

Throws:

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

Returns:

A value of type bool.

size_t libsemigroups::FroidurePin::number_of_generators() const noexcept override

Returns the number of generators.

Parameters

(None)

Throws:

(None) – This function is noexcept and is guaranteed never to throw.

Returns:

A value of type size_t.

size_t libsemigroups::FroidurePin::number_of_idempotents() override

Returns the number of idempotents.

Parameters

(None)

Note

This function triggers a full enumeration.

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

A value of type size_t.

element_index_type libsemigroups::FroidurePin::position_to_sorted_position(element_index_type i) override

Returns the sorted index of an element via its index.

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

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

A value of type element_index_type.

void libsemigroups::FroidurePin::reserve(size_t val) override

Requests the given capacity for elements.

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.

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

(None)