Member functions inherited from FroidurePinBase

This page contains a description of the member functions of the FroidurePin class inherited from FroidurePinBase.

size_t libsemigroups::FroidurePin::batch_size() const noexcept

Returns the current value of the batch size.

See also

This is the minimum number of elements enumerated in any call to run, see batch_size(size_t).

Complexity

Constant.

Parameters

None.

Throws

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

Returns

A size_t.

FroidurePinBase &libsemigroups::FroidurePin::batch_size(size_t batch_size) noexcept

Set a new value for the batch size.

The batch size is the number of new elements to be found by any call to run. This is used by, for example, FroidurePin::position so that it is possible to find the position of an element after only partially enumerating the semigroup.

The default value of the batch size is 8192.

See also

batch_size().

Complexity

Constant.

Parameters

batch_size – the new value for the batch size.

Throws

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

Returns

A reference to this.

using libsemigroups::FroidurePin::cayley_graph_type = FroidurePinBase::cayley_graph_type

Type for a left or right Cayley graph.

inline const_rule_iterator libsemigroups::FroidurePin::cbegin_rules() const

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

Returns a forward iterator pointing to the first rule in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then it is necessary to call run() first.

See also

cend_rules

Parameters

(None).

Complexity

Constant

Iterator validity

The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Example

FroidurePin<BMat8> S;
S.add_generator(BMat8({{1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0}}));
S.add_generator(BMat8({{0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0}}));
S.add_generator(BMat8({{0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0}}));
S.add_generator(BMat8({{0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1}}));
S.size(); // 4
std::vector<relation_type>(S.cbegin_rules(), S.cend_rules());
// {{{0, 0}, {0}},
//  {{0, 1}, {1}},
//  {{0, 2}, {2}},
//  {{0, 3}, {3}},
//  {{1, 0}, {0}},
//  {{1, 1}, {1}},
//  {{1, 2}, {2}},
//  {{1, 3}, {3}},
//  {{2, 0}, {0}},
//  {{2, 1}, {1}},
//  {{2, 2}, {2}},
//  {{2, 3}, {3}},
//  {{3, 0}, {0}},
//  {{3, 1}, {1}},
//  {{3, 2}, {2}},
//  {{3, 3}, {3}}}

Throws

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

Returns

An iterator of type FroidurePinBase::const_rule_iterator pointing to a relation_type.

inline const_rule_iterator libsemigroups::FroidurePin::cend_rules() const

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

Returns a forward iterator pointing one-past-the-last rule (currently known) in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then it is necessary to call run() first.

See also

cbegin_rules

Parameters

(None).

Complexity

Constant

Iterator validity

The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Example

FroidurePin<BMat8> S;
S.add_generator(BMat8({{1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0}}));
S.add_generator(BMat8({{0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0}}));
S.add_generator(BMat8({{0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0}}));
S.add_generator(BMat8({{0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1}}));
S.size(); // 4
std::vector<relation_type>(S.cbegin_rules(), S.cend_rules());
// {{{0, 0}, {0}},
//  {{0, 1}, {1}},
//  {{0, 2}, {2}},
//  {{0, 3}, {3}},
//  {{1, 0}, {0}},
//  {{1, 1}, {1}},
//  {{1, 2}, {2}},
//  {{1, 3}, {3}},
//  {{2, 0}, {0}},
//  {{2, 1}, {1}},
//  {{2, 2}, {2}},
//  {{2, 3}, {3}},
//  {{3, 0}, {0}},
//  {{3, 1}, {1}},
//  {{3, 2}, {2}},
//  {{3, 3}, {3}}}

Throws

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

Returns

An iterator of type FroidurePinBase::const_rule_iterator pointing to a relation_type.

size_t libsemigroups::FroidurePin::concurrency_threshold() const noexcept

Returns the current value of the concurrency threshold.

Complexity

Constant.

Parameters

None.

Throws

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

Returns

A size_t.

FroidurePinBase &libsemigroups::FroidurePin::concurrency_threshold(size_t thrshld) noexcept

Set the threshold for concurrency to be used by member functions.

This member function sets the threshold such that if size() exceeds this value, then the following functions may use a concurrent implementation:

The default value is 823543.

Complexity

Constant.

Parameters

thrshld – the new threshold.

Throws

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

Returns

A reference to this.

inline size_t libsemigroups::FroidurePin::current_length(element_index_type pos) const

Returns the length of the short-lex least word.

See also

length.

Complexity

Constant.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to current_size.

Returns

A value of type letter_type.

inline size_t libsemigroups::FroidurePin::current_max_word_length() const noexcept

Returns the maximum length of a word in the generators so far computed.

Every elements of the semigroup can be expressed as the short-lex least product of the generators that equals that element. This function returns the length of the longest short-lex least word in the generators that has so far been enumerated.

Parameters

(None)

Complexity

Constant.

Throws

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

Returns

A value of type size_t.

inline size_t libsemigroups::FroidurePin::current_number_of_rules() const noexcept

Returns the number of relations that have been found so far.

This is only guaranteed to be the actual number of relations in a presentation defining the semigroup if the semigroup is fully enumerated.

Parameters

(None)

Complexity

Constant.

Throws

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

Returns

A value of type size_t.

inline element_index_type libsemigroups::FroidurePin::current_position(letter_type i) const

Returns the position in of the generator with specified index.

In many cases current_position(i) will equal i, examples of when this will not be the case are:

Complexity

Constant.

Parameters

i – the index of the generators

Throws

LibsemigroupsException – if i is greater than or equal to FroidurePin::number_of_generators.

Returns

A value of type element_index_type.

inline element_index_type libsemigroups::FroidurePin::current_position(std::initializer_list<size_t> const &w) const

Returns the position corresponding to a word.

Returns the position in the semigroup corresponding to the element represented by the word w.

This function returns the position corresponding to the element obtained by evaluating the word in the generators w. No enumeration is performed, and UNDEFINED is returned if the position of the element corresponding to w cannot be determined.

This is equivalent to finding the product x of the generators FroidurePin::generator(w[i]) and then calling FroidurePin::current_position with argument x.

Complexity

\(O(n)\) where \(n\) is the length of the word w.

Parameters

w – a word in the generators

Throws

LibsemigroupsException – if w contains an value exceeding FroidurePin::number_of_generators.

Returns

A value of type element_index_type or UNDEFINED.

element_index_type libsemigroups::FroidurePin::current_position(word_type const &w) const

Returns the position corresponding to a word.

Returns the position in the semigroup corresponding to the element represented by the word w.

This function returns the position corresponding to the element obtained by evaluating the word in the generators w. No enumeration is performed, and UNDEFINED is returned if the position of the element corresponding to w cannot be determined.

This is equivalent to finding the product x of the generators FroidurePin::generator(w[i]) and then calling FroidurePin::current_position with argument x.

Complexity

\(O(n)\) where \(n\) is the length of the word w.

Parameters

w – a word in the generators

Throws

LibsemigroupsException – if w contains an value exceeding FroidurePin::number_of_generators.

Returns

A value of type element_index_type or UNDEFINED.

inline size_t libsemigroups::FroidurePin::current_size() const noexcept

Returns the number of elements so far enumerated.

This is only the actual size of the semigroup if the semigroup is fully enumerated.

Parameters

(None)

Complexity

Constant.

Throws

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

Returns

A value of type size_t.

inline size_t libsemigroups::FroidurePin::degree() const noexcept

Returns the degree of any and all elements.

Parameters

(None)

Complexity

Constant.

Throws

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

Returns

A value of type size_t.

using libsemigroups::FroidurePin::element_index_type = FroidurePinBase::element_index_type

Type for the index of an element.

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

void libsemigroups::FroidurePin::enumerate(size_t limit)

Enumerate until at least a specified number of elements are found.

If the semigroup is already fully enumerated, or the number of elements previously enumerated exceeds limit, then calling this function does nothing. Otherwise, run attempts to find at least the maximum of limit and batch_size elements of the semigroup.

Complexity

At worst \(O(mn)\) where \(m\) equals limit and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

limit – the limit for current_size()

Throws

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

Returns

(None)

inline word_type libsemigroups::FroidurePin::factorisation(element_index_type pos)

Returns a word representing an element given by index.

This is the same as the two-argument member function for factorisation, but it returns a word_type by value instead of modifying an argument in-place.

The key difference between this function and minimal_factorisation(element_index_type) is that the resulting factorisation may not be minimal.

Complexity

At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

A value of type word_type.

inline void libsemigroups::FroidurePin::factorisation(word_type &word, element_index_type pos)

Obtain a word representing an element given by index.

Changes word in-place to contain a word in the generators equal to the pos element of the semigroup.

If pos is less than the size of this semigroup, then this member function changes its first parameter word in-place by first clearing it and then to contain a factorization of the element in position pos of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least the pos element is known.

The key difference between this function and minimal_factorisation(element_index_type) is that the resulting factorisation may not be minimal.

Complexity

At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters
  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

(None)

inline letter_type libsemigroups::FroidurePin::final_letter(element_index_type pos) const

Returns the last letter of the element with specified index.

This function returns the final letter of the element in position pos of the semigroup, which is the index of the generator corresponding to the final letter of the element.

Complexity

Constant.

Note

Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to current_size.

Returns

A value of type letter_type.

inline letter_type libsemigroups::FroidurePin::first_letter(element_index_type pos) const

Returns the first letter of the element with specified index.

This function returns the first letter of the element in position pos of the semigroup, which is the index of the generator corresponding to the first letter of the element.

Complexity

Constant.

Note

Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to current_size.

Returns

A value of type letter_type.

bool libsemigroups::FroidurePin::immutable() const noexcept

Returns the current immutability.

See also

immutable(bool).

Complexity

Constant.

Parameters

None.

Throws

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

Returns

A bool.

FroidurePinBase &libsemigroups::FroidurePin::immutable(bool val) noexcept

Set immutability.

Prevent further changes to the mathematical semigroup represented by an instance of FroidurePinBase.

This member function prevents certain member functions from being applied to a FroidurePinBase, such as FroidurePin::add_generators, if they would change the mathematical object represented by this.

The default value is false.

See also

immutable().

Complexity

Constant.

Parameters

val – the new value.

Throws

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

Returns

A reference to this.

inline bool libsemigroups::FroidurePin::is_monoid()

Check if the semigroup is a monoid.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

(None).

Throws

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

Returns

true if the semigroup represented by this contains FroidurePin::One, and false if not.

inline element_index_type libsemigroups::FroidurePin::left(element_index_type i, letter_type j)

Returns the index of the product of a generator and an element.

Returns the index of the product of the generator with index j with the element in position i.

See also

right.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters
  • i – the index of the element

  • j – the index of the generator

Throws
Returns

A value of type element_index_type.

inline cayley_graph_type const &libsemigroups::FroidurePin::left_cayley_graph()

Returns a const reference to the left Cayley graph.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

None.

Throws

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

Returns

A const reference to cayley_graph_type.

inline size_t libsemigroups::FroidurePin::length(element_index_type pos)

Returns the length of the short-lex least word.

See also

current_length.

Complexity

Constant.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to size.

Returns

A value of type letter_type.

size_t libsemigroups::FroidurePin::max_threads() const noexcept

Returns the current value of the maximum number of threads.

Complexity

Constant.

Parameters

None.

Throws

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

Returns

A size_t.

FroidurePinBase &libsemigroups::FroidurePin::max_threads(size_t number_of_threads) noexcept

Set the maximum number of threads.

This member function sets the maximum number of threads to be used by any member function of a FroidurePin object. The number of threads is limited to the maximum of 1 and the minimum of number_of_threads and the number of threads supported by the hardware.

The default value is std::thread::hardware_concurrency().

See also

max_threads().

Complexity

Constant.

Parameters

number_of_threads – the maximum number of threads to use.

Throws

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

Returns

A reference to this.

inline word_type libsemigroups::FroidurePin::minimal_factorisation(element_index_type pos)

Returns a short-lex least word representing an element given by index.

This is the same as the two-argument member function for minimal_factorisation, but it returns a word_type by value instead of modifying an argument in-place.

Complexity

At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

A value of type word_type.

inline void libsemigroups::FroidurePin::minimal_factorisation(word_type &word, element_index_type pos)

Obtain a short-lex least word representing an element given by index.

Changes word in-place to contain a minimal word with respect to the short-lex ordering in the generators equal to the pos element of the semigroup.

If pos is less than the size of this semigroup, then this member function changes its first parameter word in-place by first clearing it and then to contain a minimal factorization of the element in position pos of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least the pos element is known.

Complexity

At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters
  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

(None)

inline void libsemigroups::FroidurePin::minimal_factorisation(word_type &word, element_index_type pos) const

Obtain a short-lex least word representing an element given by index.

Changes word in-place to contain a minimal word with respect to the short-lex ordering in the generators equal to the pos element of the semigroup. No further enumeration is performed.

Complexity

Constant.

Parameters
  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to current_size().

Returns

(None)

inline size_t libsemigroups::FroidurePin::number_of_rules()

Returns the total number of relations in the presentation.

See also

cbegin_rules and cend_rules.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

(None)

Throws

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

Returns

A value of type size_t.

inline element_index_type libsemigroups::FroidurePin::prefix(element_index_type pos) const

Returns the position of the longest proper prefix.

Returns the position of the prefix of the element x in position pos (of the semigroup) of length one less than the length of x.

Complexity

Constant.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to current_size.

Returns

A value of type element_index_type.

element_index_type libsemigroups::FroidurePin::product_by_reduction(element_index_type i, element_index_type j) const

Compute a product using the Cayley graph.

This function finds the product of at(i) and at(j) by following the path in the right Cayley graph from i labelled by the word minimal_factorisation(j) or, if minimal_factorisation(i) is shorter, by following the path in the left Cayley graph from j labelled by minimal_factorisation(i).

Complexity

\(O(n)\) where \(n\) is the minimum of the lengths of minimal_factorisation(i) and minimal_factorisation(j).

Parameters
  • i – the first index of an element

  • j – the second index of an element

Throws

LibsemigroupsException – if i or j is greater than or equal to current_size.

Returns

A value of type element_index_type.

inline element_index_type libsemigroups::FroidurePin::right(element_index_type i, letter_type j)

Returns the index of the product of an element and a generator.

Returns the index of the product of the element in position i with the generator with index j.

See also

left.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters
  • i – the index of the element

  • j – the index of the generator

Throws
Returns

A value of type element_index_type.

inline cayley_graph_type const &libsemigroups::FroidurePin::right_cayley_graph()

Returns a const reference to the right Cayley graph.

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Parameters

None.

Throws

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

Returns

A const reference to cayley_graph_type.

inline size_t libsemigroups::FroidurePin::size()

Returns the size.

Parameters

(None)

Complexity

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Throws

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

Returns

A value of type size_t.

using libsemigroups::FroidurePin::size_type = FroidurePinBase::size_type

Unsigned integer type.

inline element_index_type libsemigroups::FroidurePin::suffix(element_index_type pos) const

Returns the position of the longest proper suffix.

Returns the position of the suffix of the element x in position pos (of the semigroup) of length one less than the length of x.

Complexity

Constant.

Parameters

pos – the position

Throws

LibsemigroupsException – if pos is greater than or equal to current_size.

Returns

A value of type element_index_type.