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
- 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
- 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
- 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.
See also
- 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
.See also
- 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
- 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 equali
, examples of when this will not be the case are:there are duplicate generators;
FroidurePin::add_generators was called after the semigroup was already partially enumerated.
- 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 tow
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 argumentx
.See also
- 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 tow
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 argumentx
.See also
- 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 oflimit
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 thepos
element of the semigroup.If
pos
is less than the size of this semigroup, then this member function changes its first parameterword
in-place by first clearing it and then to contain a factorization of the element in positionpos
of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least thepos
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 toFroidurePin::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 toFroidurePin::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
- 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
- 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 bythis
contains FroidurePin::One, andfalse
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 positioni
.See also
- 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
LibsemigroupsException – if
i
is greater than or equal to size().LibsemigroupsException – if
j
is greater than or equal to FroidurePin::number_of_generators().
- 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
- 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.
See also
- 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
- 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 thepos
element of the semigroup.If
pos
is less than the size of this semigroup, then this member function changes its first parameterword
in-place by first clearing it and then to contain a minimal factorization of the element in positionpos
of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least thepos
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 thepos
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 positionpos
(of the semigroup) of length one less than the length ofx
.- 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)
andat(j)
by following the path in the right Cayley graph fromi
labelled by the wordminimal_factorisation(j)
or, ifminimal_factorisation(i)
is shorter, by following the path in the left Cayley graph fromj
labelled byminimal_factorisation(i)
.- Complexity
\(O(n)\) where \(n\) is the minimum of the lengths of
minimal_factorisation(i)
andminimal_factorisation(j)
.
- Parameters
i – the first index of an element
j – the second index of an element
- Throws
LibsemigroupsException – if
i
orj
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 indexj
.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
LibsemigroupsException – if
i
is greater than or equal to size().LibsemigroupsException – if
j
is greater than or equal to FroidurePin::number_of_generators().
- 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 positionpos
(of the semigroup) of length one less than the length ofx
.- 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
.