libsemigroups
|
Class for semigroups generated by instances of Element. More...
#include <semigroups.h>
Public Types | |
typedef RecVec< element_index_t > | cayley_graph_t |
Type for a left or right Cayley graph of a semigroup. More... | |
typedef index_t | element_index_t |
Type for the position of an element in an instance of Semigroup. The size of the semigroup being enumerated must be at most std::numeric_limits<element_index_t>::max() More... | |
Public Member Functions | |
Semigroup (std::vector< Element const *> const *gens) | |
Construct from generators. More... | |
Semigroup (std::vector< Element *> const *gens) | |
Construct from generators. More... | |
Semigroup (std::vector< Element *> *gens) | |
Construct from generators. More... | |
Semigroup (std::vector< Element const *> *gens) | |
Construct from generators. More... | |
Semigroup (std::vector< Element const *> const &gens) | |
Construct from generators. More... | |
Semigroup (std::vector< Element *> const &gens) | |
Construct from generators. More... | |
Semigroup (std::initializer_list< Element *> gens) | |
Construct from generators. More... | |
Semigroup (const Semigroup ©) | |
Copy constructor. More... | |
~Semigroup () | |
A default destructor. More... | |
void | add_generators (std::vector< Element const *> const *coll) |
Add copies of the generators coll to the generators of this . More... | |
void | add_generators (std::vector< Element *> const *coll) |
Add copies of the generators coll to the generators of this . More... | |
void | add_generators (std::vector< Element const *> const &coll) |
Add copies of the generators coll to the generators of this . More... | |
void | add_generators (std::vector< Element *> const &coll) |
Add copies of the generators coll to the generators of this . More... | |
void | add_generators (std::initializer_list< Element *> coll) |
Add copies of the generators coll to the generators of this . More... | |
Element const * | at (element_index_t pos) |
Returns the element of the semigroup in position pos , or a nullptr if there is no such element. More... | |
size_t | batch_size () const |
Returns the current value of the batch size. This is the minimum number of elements enumerated in any call to Semigroup::enumerate. More... | |
const_iterator | begin () const |
Returns a const iterator pointing to the first element of the semigroup. More... | |
const_iterator | cbegin () const |
Returns a const iterator pointing to the first element of the semigroup. More... | |
const_iterator_idempotents | cbegin_idempotents () |
Returns a const iterator pointing at the first idempotent in the semigroup. More... | |
const_iterator_sorted | cbegin_sorted () |
Returns a const iterator pointing to the first element of the semigroup when the elements are sorted by Element::operator<. More... | |
const_iterator | cend () const |
Returns a const iterator pointing to one past the last currently known element of the semigroup. More... | |
const_iterator_idempotents | cend_idempotents () |
Returns a const iterator referring to past the end of the last idempotent in the semigroup. More... | |
const_iterator_sorted | cend_sorted () |
Returns a const iterator pointing to one past the last element of the semigroup when the elements are sorted by Element::operator<. More... | |
void | closure (std::vector< Element const *> const *coll) |
Add copies of the non-redundant generators in coll to the generators of this . More... | |
void | closure (std::vector< Element const *> const &coll) |
Add copies of the non-redundant generators in coll to the generators of this . More... | |
void | closure (std::vector< Element *> const &coll) |
Add copies of the non-redundant generators in coll to the generators of this . More... | |
void | closure (std::initializer_list< Element *> coll) |
Add copies of the non-redundant generators in coll to the generators of this . More... | |
Semigroup * | copy_add_generators (std::vector< Element const *> const *coll) const |
Returns a new semigroup generated by this and coll . More... | |
Semigroup * | copy_add_generators (std::vector< Element *> const *coll) const |
Returns a new semigroup generated by this and coll . More... | |
Semigroup * | copy_closure (std::vector< Element const *> const *coll) |
Returns a new semigroup generated by this and copies of the non-redundant elements of coll . More... | |
Semigroup * | copy_closure (std::vector< Element *> const *gens) |
Returns a new semigroup generated by this and copies of the non-redundant elements of coll . More... | |
const_reverse_iterator | crbegin () const |
Returns a const reverse iterator pointing to the last currently known element of the semigroup. More... | |
const_reverse_iterator_sorted | crbegin_sorted () |
Returns a const iterator pointing to the last element of the semigroup when the elements are sorted by Element::operator<. More... | |
const_reverse_iterator | crend () const |
Returns a const reverse iterator pointing to one before the first element of the semigroup. More... | |
const_reverse_iterator_sorted | crend_sorted () |
Returns a const iterator pointing to one before the first element of the semigroup when the elements are sorted by Element::operator<. More... | |
size_t | current_max_word_length () const |
Returns the maximum length of a word in the generators so far computed. More... | |
size_t | current_nrrules () const |
Returns the number of relations in the presentation for the semigroup that have been found so far. More... | |
element_index_t | current_position (Element const *x) const |
Returns the position of the element x in the semigroup if it is already known to belong to the semigroup. More... | |
size_t | current_size () const |
Returns the number of elements in the semigroup that have been enumerated so far. More... | |
size_t | degree () const |
Returns the degree of any (and all) Element's in the semigroup. More... | |
const_iterator | end () const |
Returns a const iterator pointing to one past the last currently known element of the semigroup. More... | |
void | enumerate (std::atomic< bool > &killed, size_t limit=LIMIT_MAX) |
Enumerate the semigroup until limit elements are found or killed is true . More... | |
void | enumerate (size_t limit=LIMIT_MAX) |
Enumerate the semigroup until limit elements are found. More... | |
void | factorisation (word_t &word, element_index_t pos) |
Changes word in-place to contain a word in the generators equal to the pos element of the semigroup. More... | |
word_t * | factorisation (element_index_t pos) |
Returns a pointer to a libsemigroups::word_t which evaluates to the Element in position pos of this . More... | |
word_t * | factorisation (Element const *x) |
Returns a pointer to a libsemigroups::word_t which evaluates to. More... | |
element_index_t | fast_product (element_index_t i, element_index_t j) const |
Returns the position in this of the product of this->at(i) and this->at(j) . More... | |
letter_t | final_letter (element_index_t pos) const |
Returns the last letter of the element in position pos . More... | |
letter_t | first_letter (element_index_t pos) const |
Returns the first letter of the element in position pos . More... | |
Element const * | gens (letter_t pos) const |
Return a pointer to the generator with index pos . More... | |
bool | is_begun () const |
Returns true if no elements other than the generators have been enumerated so far and false otherwise. More... | |
bool | is_done () const |
Returns true if the semigroup is fully enumerated and false if not. More... | |
bool | is_idempotent (element_index_t pos) |
Returns true if the element in position pos is an idempotent and false if it is not. More... | |
element_index_t | left (element_index_t i, letter_t j) |
Returns the index of the product of the generator with index j and the element in position i . More... | |
cayley_graph_t * | left_cayley_graph_copy () |
Returns a copy of the left Cayley graph of the semigroup. More... | |
size_t | length_const (element_index_t pos) const |
Returns the length of the element in position pos of the semigroup. More... | |
size_t | length_non_const (element_index_t pos) |
Returns the length of the element in position pos of the semigroup. More... | |
element_index_t | letter_to_pos (letter_t i) const |
Returns the position in this of the generator with index i . More... | |
void | minimal_factorisation (word_t &word, element_index_t pos) |
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. More... | |
word_t * | minimal_factorisation (element_index_t pos) |
Returns a pointer to a minimal libsemigroups::word_t which evaluates to the Element in position pos of this . More... | |
word_t * | minimal_factorisation (Element const *x) |
Returns a pointer to a minimal libsemigroups::word_t which evaluates to x . More... | |
void | next_relation (word_t &relation) |
This method changes relation in-place to contain the next relation of the presentation defining this . More... | |
size_t | nrgens () const |
Returns the number of generators of the semigroup. More... | |
size_t | nridempotents () |
Returns the total number of idempotents in the semigroup. More... | |
size_t | nrrules () |
Returns the total number of relations in the presentation defining the semigroup. More... | |
Semigroup & | operator= (Semigroup const &semigroup)=delete |
Deleted. More... | |
Element const * | operator[] (element_index_t pos) const |
Returns the element of the semigroup in position pos . More... | |
element_index_t | position (Element const *x) |
Returns the position of x in this , or Semigroup::UNDEFINED if x is not an element of this . More... | |
element_index_t | position_to_sorted_position (element_index_t pos) |
Returns the position of this->at(pos) in the sorted array of elements of the semigroup, or Semigroup::UNDEFINED if pos is greater than the size of the semigroup. More... | |
element_index_t | prefix (element_index_t pos) const |
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 . More... | |
element_index_t | product_by_reduction (element_index_t i, element_index_t j) const |
Returns the position in this of the product of this->at(i) and this->at(j) by following a path in the Cayley graph. More... | |
void | reserve (size_t n) |
Requests that the capacity (i.e. number of elements) of the semigroup be at least enough to contain n elements. More... | |
void | reset_next_relation () |
This method resets Semigroup::next_relation so that when it is next called the resulting relation is the first one. More... | |
element_index_t | right (element_index_t i, letter_t j) |
Returns the index of the product of the element in position i with the generator with index j . More... | |
cayley_graph_t * | right_cayley_graph_copy () |
Returns a copy of the right Cayley graph of the semigroup. More... | |
void | set_batch_size (size_t batch_size) |
Set a new value for the batch size. More... | |
void | set_max_threads (size_t nr_threads) |
Set the maximum number of threads that any method of an instance of Semigroup can use. More... | |
void | set_report (bool val) const |
Turn reporting on or off. More... | |
size_t | size () |
Returns the size of the semigroup. More... | |
Element const * | sorted_at (element_index_t pos) |
Returns the element of the semigroup in position pos of the sorted array of elements, or nullptr in pos is not valid (i.e. too big). More... | |
element_index_t | sorted_position (Element const *x) |
Returns the position of x in the sorted array of elements of the semigroup, or Semigroup::UNDEFINED if x is not an element of this . More... | |
element_index_t | suffix (element_index_t pos) const |
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 . More... | |
bool | test_membership (Element const *x) |
Returns true if x is an element of this and false if it is not. More... | |
Element * | word_to_element (word_t const &w) const |
Returns a pointer to the element of this represented by the word w . More... | |
element_index_t | word_to_pos (word_t const &w) const |
Returns the position in the semigroup corresponding to the element represented by the word w . More... | |
Static Public Attributes | |
static index_t const | LIMIT_MAX = std::numeric_limits<index_t>::max() |
This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumerate. More... | |
static index_t const | UNDEFINED = std::numeric_limits<index_t>::max() |
This variable is used to indicate that a value is undefined, such as, for example, the position of an element that does not belong to a semigroup. More... | |
Class for semigroups generated by instances of Element.
Semigroups are defined by a generating set, and the main method here is Semigroup::enumerate, which implements the Froidure-Pin Algorithm. When the enumeration of the semigroup is complete, the size, the left and right Cayley graphs are determined, and a confluent terminating presentation for the semigroup is known.
typedef RecVec<element_index_t> libsemigroups::Semigroup::cayley_graph_t |
Type for a left or right Cayley graph of a semigroup.
typedef index_t libsemigroups::Semigroup::element_index_t |
Type for the position of an element in an instance of Semigroup. The size of the semigroup being enumerated must be at most std::numeric_limits<element_index_t>::max()
|
explicit |
Construct from generators.
This is the default constructor for a semigroup generated by gens
. The generators gens
must all be of the same derived subclass of the Element base class. Additionally, gens
must satisfy the following:
if either of these points is not satisfied, then an asssertion failure will occur.
There can be duplicate generators and although they do not count as distinct elements, they do count as distinct generators. In other words, the generators of the semigroup are precisely (a copy of) gens
in the same order they occur in gens
.
The generators gens
are copied by the constructor, and so it is the responsibility of the caller to delete gens
.
|
inlineexplicit |
Construct from generators.
This constructor is for convenience only, and it simply reinterpret_cast's the argument from std::vector<Element*> const* to std::vector<Element const*> const*.
|
inlineexplicit |
Construct from generators.
This constructor is for convenience only, and it simply const_casts the argument from std::vector<Element*>* to std::vector<Element*> const*.
|
inlineexplicit |
Construct from generators.
This constructor is for convenience only, and it simply const_casts the argument from std::vector<Element const*>* to std::vector<Element const*> const*.
|
explicit |
Construct from generators.
This constructor is for convenience only, see Semigroup::Semigroup.
|
inlineexplicit |
Construct from generators.
This constructor is for convenience, and it simply reinterpret_casts its argument to <std::vector<Element const*> const&.
|
inlineexplicit |
Construct from generators.
This constructor is for convenience, and it simply static_casts its argument to std::vector<Element*>.
libsemigroups::Semigroup::Semigroup | ( | const Semigroup & | copy | ) |
Copy constructor.
Constructs a new Semigroup which is an exact copy of copy
. No enumeration is triggered for either copy
or of the newly constructed semigroup.
libsemigroups::Semigroup::~Semigroup | ( | ) |
A default destructor.
void libsemigroups::Semigroup::add_generators | ( | std::vector< Element const *> const * | coll | ) |
Add copies of the generators coll
to the generators of this
.
This method can be used to add new generators to the existing semigroup in such a way that any previously enumerated data is preserved and not recomputed, or copied. This can be faster than recomputing the semigroup generated by the old generators and the new generators in the parameter coll
.
This method changes the semigroup in-place, thereby invalidating possibly previously known data about the semigroup, such as the left or right Cayley graphs, number of idempotents, and so on.
Every generator in coll
is added regardless of whether or not it is already a generator or element of the semigroup (it may belong to the semigroup but just not be known to belong). If coll
is empty, then the semigroup is left unchanged. The order the generators is added is also the order they occur in the parameter coll
.
The semigroup is returned in a state where all of the previously enumerated elements which had been multiplied by all of the old generators, have now been multiplied by all of the old and new generators. This means that after this method is called the semigroup might contain many more elements than before (whether it is fully enumerating or not). It can also be the case that the new generators are the only new elements, unlike, say, in the case of non-trivial groups.
The elements the argument coll
are copied into the semigroup, and should be deleted by the caller.
|
inline |
Add copies of the generators coll
to the generators of this
.
See Semigroup::add_generators for more details.
void libsemigroups::Semigroup::add_generators | ( | std::vector< Element const *> const & | coll | ) |
Add copies of the generators coll
to the generators of this
.
See Semigroup::add_generators for more details.
|
inline |
Add copies of the generators coll
to the generators of this
.
See Semigroup::add_generators for more details.
|
inline |
Add copies of the generators coll
to the generators of this
.
See Semigroup::add_generators for more details.
Element const * libsemigroups::Semigroup::at | ( | element_index_t | pos | ) |
Returns the element of the semigroup in position pos
, or a nullptr
if there is no such element.
This method attempts to enumerate the semigroup until at least pos
+ 1 elements have been found. If pos
is greater than Semigroup::size, then this method returns nullptr
.
|
inline |
Returns the current value of the batch size. This is the minimum number of elements enumerated in any call to Semigroup::enumerate.
|
inline |
Returns a const iterator pointing to the first element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator pointing to the first element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator pointing at the first idempotent in the semigroup.
If the returned iterator is incremented, then it points to the second idempotent in the semigroup (if it exists), and every subsequent increment points to the next idempotent.
This method involves fully enumerating the semigroup, if it is not already fully enumerated.
|
inline |
Returns a const iterator pointing to the first element of the semigroup when the elements are sorted by Element::operator<.
This method fully enumerates the semigroup, the returned iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator pointing to one past the last currently known element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator referring to past the end of the last idempotent in the semigroup.
This method involves fully enumerating the semigroup, if it is not already fully enumerated.
|
inline |
Returns a const iterator pointing to one past the last element of the semigroup when the elements are sorted by Element::operator<.
This method fully enumerates the semigroup, the returned iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
void libsemigroups::Semigroup::closure | ( | std::vector< Element const *> const * | coll | ) |
Add copies of the non-redundant generators in coll
to the generators of this
.
This method can be used to add new generators to an existing semigroup in such a way that any previously enumerated data is preserved and not recomputed, or copied. This can be faster than recomputing the semigroup generated by the old generators and the new in coll
.
This method differs from Semigroup::add_generators in that it tries to add the new generators one by one, and only adds those generators that are not products of existing generators (including any new generators from coll
that were added before). The generators are added in the order they occur in coll
.
This method changes the semigroup in-place, thereby invalidating possibly previously known data about the semigroup, such as the left or right Cayley graphs, or number of idempotents, for example.
The elements the parameter coll
are copied into the semigroup, and should be deleted by the caller.
void libsemigroups::Semigroup::closure | ( | std::vector< Element const *> const & | coll | ) |
Add copies of the non-redundant generators in coll
to the generators of this
.
See Semigroup::closure for more details.
|
inline |
Add copies of the non-redundant generators in coll
to the generators of this
.
See Semigroup::closure for more details.
|
inline |
Add copies of the non-redundant generators in coll
to the generators of this
.
See Semigroup::closure for more details.
Semigroup * libsemigroups::Semigroup::copy_add_generators | ( | std::vector< Element const *> const * | coll | ) | const |
Returns a new semigroup generated by this
and coll
.
This method is equivalent to copying this
using Semigroup::Semigroup(const Semigroup& copy) and then calling Semigroup::add_generators on the copy, but this method avoids copying the parts of this
that are immediately invalidated by Semigroup::add_generators.
The elements the argument coll
are copied into the semigroup, and should be deleted by the caller.
|
inline |
Returns a new semigroup generated by this
and coll
.
See Semigroup::copy_add_generators for more details.
Returns a new semigroup generated by this
and copies of the non-redundant elements of coll
.
This method is equivalent to copying this
and then calling Semigroup::closure on the copy with coll
, but this method avoids copying the parts of this
that are immediately invalidated by Semigroup::closure.
The elements the argument coll
are copied into the semigroup, and should be deleted by the caller.
Returns a new semigroup generated by this
and copies of the non-redundant elements of coll
.
See Semigroup::copy_closure for more details.
|
inline |
Returns a const reverse iterator pointing to the last currently known element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator pointing to the last element of the semigroup when the elements are sorted by Element::operator<.
This method fully enumerates the semigroup, the returned iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const reverse iterator pointing to one before the first element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns a const iterator pointing to one before the first element of the semigroup when the elements are sorted by Element::operator<.
This method fully enumerates the semigroup, the returned iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
|
inline |
Returns the maximum length of a word in the generators so far computed.
Every elements of the semigroup can be expressed as a product of the generators. The elements of the semigroup are enumerated in the short-lex order induced by the order of the generators (as passed to Semigroup::Semigroup). This method returns the length of the longest word in the generators that has so far been enumerated.
|
inline |
Returns the number of relations in the presentation for the semigroup that have been found so far.
This is only the actual number of relations in a presentation defining the semigroup if the semigroup is fully enumerated.
|
inline |
Returns the position of the element x
in the semigroup if it is already known to belong to the semigroup.
This method finds the position of the element x
in the semigroup if it is already known to belong to the semigroup, and libsemigroups::Semigroup::UNDEFINED if not. If the semigroup is not fully enumerated, then this method may return libsemigroups::Semigroup::UNDEFINED when x
is in the semigroup, but not this is not yet known.
|
inline |
Returns the number of elements in the semigroup that have been enumerated so far.
This is only the actual size of the semigroup if the semigroup is fully enumerated.
|
inline |
Returns the degree of any (and all) Element's in the semigroup.
|
inline |
Returns a const iterator pointing to one past the last currently known element of the semigroup.
This method does not perform any enumeration of the semigroup, the iterator returned may be invalidated by any call to a non-const method of the Semigroup class.
void libsemigroups::Semigroup::enumerate | ( | std::atomic< bool > & | killed, |
size_t | limit = LIMIT_MAX |
||
) |
Enumerate the semigroup until limit
elements are found or killed
is true
.
This is the main method of the Semigroup class, where the Froidure-Pin Algorithm is implemented.
If the semigroup is already fully enumerated, or the number of elements previously enumerated exceeds limit
, then calling this method does nothing. Otherwise, enumerate attempts to find at least the maximum of limit
and Semigroup::batch_size elements of the semigroup. If killed
is set to true
(usually by another process), then the enumeration is terminated as soon as possible. It is possible to resume enumeration at some later point after any call to this method, even if it has been killed.
If the semigroup is fully enumerated, then it knows its left and right Cayley graphs, and a minimal factorisation of every element (in terms of its generating set). All of the elements are stored in memory until the object is destroyed.
The parameter limit
defaults to Semigroup::LIMIT_MAX.
|
inline |
Enumerate the semigroup until limit
elements are found.
See Semigroup::enumerate(std::atomic<bool>& killed, size_t limit) for more details.
|
inline |
Changes word
in-place to contain a word in the generators equal to the pos
element of the semigroup.
The key difference between this method and Semigroup::minimal_factorisation(word_t& word, element_index_t pos), is that the resulting factorisation may not be minimal.
|
inline |
Returns a pointer to a libsemigroups::word_t which evaluates to the Element in position pos
of this
.
The key difference between this method and Semigroup::minimal_factorisation(element_index_t pos), is that the resulting factorisation may not be minimal.
Returns a pointer to a libsemigroups::word_t which evaluates to.
The key difference between this method and Semigroup::minimal_factorisation(Element const* x), is that the resulting factorisation may not be minimal.
Semigroup::element_index_t libsemigroups::Semigroup::fast_product | ( | element_index_t | i, |
element_index_t | j | ||
) | const |
Returns the position in this
of the product of this->at(i)
and this->at(j)
.
This method asserts that the parameters i
and j
are less than Semigroup::current_size, and it either:
i
to j
, whichever is shorter using Semigroup::product_by_reduction; ori
and j
together;whichever is better. The method used is determined by comparing Element::complexity and the Semigroup::length_const of i
and j
.
For example, if the Element::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 better to just multiply the transformations together.
|
inline |
Returns the last letter of the element in position pos
.
This method returns the final 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.
Note that Semigroup::gens[Semigroup::final_letter(pos
)] is only equal to Semigroup::at(Semigroup::final_letter(pos
)) if there are no duplicate generators.
The parameter pos
must be a valid position of an already enumerated element of the semigroup, this is asserted in the method.
|
inline |
Returns the first letter of the element in position pos
.
This method 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.
Note that Semigroup::gens[Semigroup::first_letter(pos
)] is only equal to Semigroup::at(Semigroup::first_letter(pos
)) if there are no duplicate generators.
The parameter pos
must be a valid position of an already enumerated element of the semigroup, this is asserted in the method.
Return a pointer to the generator with index pos
.
|
inline |
Returns true
if no elements other than the generators have been enumerated so far and false
otherwise.
|
inline |
Returns true
if the semigroup is fully enumerated and false
if not.
The semigroup is fully enumerated when the product of every element by every generator is known.
bool libsemigroups::Semigroup::is_idempotent | ( | element_index_t | pos | ) |
Returns true
if the element in position pos
is an idempotent and false
if it is not.
This method involves fully enumerating the semigroup, if it is not already fully enumerated.
|
inline |
Returns the index of the product of the generator with index j
and the element in position i
.
This method fully enumerates the semigroup.
|
inline |
Returns a copy of the left Cayley graph of the semigroup.
This method fully enumerates the semigroup.
|
inline |
Returns the length of the element in position pos
of the semigroup.
The parameter pos
must be a valid position of an already enumerated element of the semigroup, this is asserted in the method. This method causes no enumeration of the semigroup.
|
inline |
Returns the length of the element in position pos
of the semigroup.
The parameter pos
must be a valid position of an element of the semigroup, this is asserted in the method.
|
inline |
Returns the position in this
of the generator with index i
.
This method asserts that the value of i
is valid. In many cases letter_to_pos(i)
will equal i
, examples of when this will not be the case are:
void libsemigroups::Semigroup::minimal_factorisation | ( | word_t & | word, |
element_index_t | pos | ||
) |
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 method 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 method enumerates the semigroup until at least the pos
element is known. If pos
is greater than the size of the semigroup, then nothing happens and word is not modified, in particular not cleared.
word_t * libsemigroups::Semigroup::minimal_factorisation | ( | element_index_t | pos | ) |
Returns a pointer to a minimal libsemigroups::word_t which evaluates to the Element in position pos
of this
.
This is the same as the two-argument method for Semigroup::minimal_factorisation, but it returns a pointer to the factorisation instead of modifying an argument in-place.
Returns a pointer to a minimal libsemigroups::word_t which evaluates to x
.
This is the same as the method taking a Semigroup::element_index_t, but it factorises an Element instead of using the position of an element.
void libsemigroups::Semigroup::next_relation | ( | word_t & | relation | ) |
This method changes relation
in-place to contain the next relation of the presentation defining this
.
This method changes relation
in-place so that one of the following holds:
relation
is a vector consisting of a libsemigroups::letter_t and a libsemigroups::letter_t such that Semigroup::gens(relation
[0
]) == Semigroup::gens(relation
[1
]), i.e. if the semigroup was defined with duplicate generators;relation
is a vector consisting of a libsemigroups::element_index_t, libsemigroups::letter_t, and libsemigroups::element_index_t such that relation
is empty if there are no more relations.Semigroup::next_relation is guaranteed to output all relations of length 2 before any relations of length 3. If called repeatedly after Semigroup::reset_next_relation, and until relation is empty, the values placed in relation
correspond to a length-reducing confluent rewriting system that defines the semigroup.
This method can be used in conjunction with Semigroup::factorisation to obtain a presentation defining the semigroup.
|
inline |
Returns the number of generators of the semigroup.
size_t libsemigroups::Semigroup::nridempotents | ( | ) |
Returns the total number of idempotents in the semigroup.
This method involves fully enumerating the semigroup, if it is not already fully enumerated. The value of the positions, and number, of idempotents is stored after they are first computed.
|
inline |
Returns the total number of relations in the presentation defining the semigroup.
|
inline |
Returns the element of the semigroup in position pos
.
This method performs no checks on its argument, and performs no enumeration of the semigroup.
Semigroup::element_index_t libsemigroups::Semigroup::position | ( | Element const * | x | ) |
Returns the position of x
in this
, or Semigroup::UNDEFINED if x
is not an element of this
.
This method can be used to find the Semigroup::element_index_t position of the element x
if it belongs to the semigroup. The semigroup is enumerated in batches until x
is found or the semigroup is fully enumerated but x
was not found (see Semigroup::set_batch_size).
Semigroup::element_index_t libsemigroups::Semigroup::position_to_sorted_position | ( | element_index_t | pos | ) |
Returns the position of this->at(pos)
in the sorted array of elements of the semigroup, or Semigroup::UNDEFINED if pos
is greater than the size of the semigroup.
|
inline |
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
.
The parameter pos
must be a valid position of an already enumerated element of the semigroup, this is asserted in the method.
Semigroup::element_index_t libsemigroups::Semigroup::product_by_reduction | ( | element_index_t | i, |
element_index_t | j | ||
) | const |
Returns the position in this
of the product of this->at(i)
and this->at(j)
by following a path in the Cayley graph.
This method asserts that the values i
and j
are valid, in that they are less than Semigroup::current_size. This method returns the position Semigroup::element_index_t in the semigroup of the product of this->at(i)
and this->at(j)
elements by following the path in the right or left Cayley graph from i
to j
, whichever is shorter.
void libsemigroups::Semigroup::reserve | ( | size_t | n | ) |
Requests that the capacity (i.e. number of elements) of the semigroup be at least enough to contain n elements.
The parameter n
is also used to initialise certain data members, if you know a good upper bound for the size of your semigroup, then it is a good idea to call this method with that upper bound as an argument, this can significantly improve the performance of the Semigroup::enumerate method, and consequently every other method too.
|
inline |
This method resets Semigroup::next_relation so that when it is next called the resulting relation is the first one.
After a call to this function, the next call to Semigroup::next_relation will return the first relation of the presentation defining the semigroup.
|
inline |
Returns the index of the product of the element in position i
with the generator with index j
.
This method fully enumerates the semigroup.
|
inline |
Returns a copy of the right Cayley graph of the semigroup.
This method fully enumerates the semigroup.
|
inline |
Set a new value for the batch size.
The batch size is the number of new elements to be found by any call to Semigroup::enumerate. A call to enumerate returns between 0 and approximately the batch size.
The default value of the batch size is 8192.
This is used by, for example, Semigroup::position so that it is possible to find the position of an element without fully enumerating the semigroup.
|
inline |
Set the maximum number of threads that any method of an instance of Semigroup can use.
This method sets the maximum number of threads to be used by any method of a Semigroup object. The number of threads is limited to the maximum of 1 and the minimum of nr_threads
and the number of threads supported by the hardware.
|
inline |
Turn reporting on or off.
If val
is true, then some methods for a Semigroup object may report information about the progress of the computation.
|
inline |
Returns the size of the semigroup.
Element const * libsemigroups::Semigroup::sorted_at | ( | element_index_t | pos | ) |
Returns the element of the semigroup in position pos
of the sorted array of elements, or nullptr
in pos
is not valid (i.e. too big).
This method fully enumerates the semigroup.
Semigroup::element_index_t libsemigroups::Semigroup::sorted_position | ( | Element const * | x | ) |
Returns the position of x
in the sorted array of elements of the semigroup, or Semigroup::UNDEFINED if x
is not an element of this
.
|
inline |
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
.
The parameter pos
must be a valid position of an already enumerated element of the semigroup, this is asserted in the method.
|
inline |
Returns true
if x
is an element of this
and false
if it is not.
This method can be used to check if the element x
is an element of the semigroup. The semigroup is enumerated in batches until x
is found or the semigroup is fully enumerated but x
was not found (see Semigroup::set_batch_size).
Returns a pointer to the element of this
represented by the word w
.
The parameter w
must consist of non-negative integers less than Semigroup::nrgens. This method returns a pointer to the element of this
obtained by evaluating w
. This is equivalent to finding the product x
of the generators Semigroup::gens(w
[i]).
Semigroup::element_index_t libsemigroups::Semigroup::word_to_pos | ( | word_t const & | w | ) | const |
Returns the position in the semigroup corresponding to the element represented by the word w
.
The parameter w
must consist of non-negative integers less than Semigroup::nrgens. This method returns the position in this
of the element obtained by evaluating w
. This is equivalent to finding the product x
of the generators Semigroup::gens(w
[i]) and then calling Semigroup::position with argument x
.
|
static |
This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumerate.
|
static |
This variable is used to indicate that a value is undefined, such as, for example, the position of an element that does not belong to a semigroup.