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_pair_first  cbegin_idempotents () 
Returns a const iterator pointing at the first idempotent in the semigroup. More...  
const_iterator_pair_first  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_pair_first  cend_idempotents () 
Returns a const iterator referring to past the end of the last idempotent in the semigroup. More...  
const_iterator_pair_first  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 nonredundant generators in coll to the generators of this . More...  
void  closure (std::vector< Element const *> const &coll) 
Add copies of the nonredundant generators in coll to the generators of this . More...  
void  closure (std::vector< Element *> const &coll) 
Add copies of the nonredundant generators in coll to the generators of this . More...  
void  closure (std::initializer_list< Element *> coll) 
Add copies of the nonredundant 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 nonredundant elements of coll . More...  
Semigroup *  copy_closure (std::vector< Element *> const *gens) 
Returns a new semigroup generated by this and copies of the nonredundant 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_pair_first  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_pair_first  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 inplace 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 inplace to contain a minimal word with respect to the shortlex 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 inplace 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 FroidurePin 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 inplace, 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 nontrivial 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 nonconst 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 nonconst 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 nonconst 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 nonconst 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 nonconst method of the Semigroup class.
void libsemigroups::Semigroup::closure  (  std::vector< Element const *> const *  coll  ) 
Add copies of the nonredundant 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 inplace, 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 nonredundant generators in coll
to the generators of this
.
See Semigroup::closure for more details.

inline 
Add copies of the nonredundant generators in coll
to the generators of this
.
See Semigroup::closure for more details.

inline 
Add copies of the nonredundant 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 nonredundant 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 nonredundant 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 nonconst 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 nonconst 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 nonconst 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 nonconst 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 shortlex 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 nonconst 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 FroidurePin 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
inplace 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
inplace to contain a minimal word with respect to the shortlex 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
inplace 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 twoargument method for Semigroup::minimal_factorisation, but it returns a pointer to the factorisation instead of modifying an argument inplace.
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
inplace to contain the next relation of the presentation defining this
.
This method changes relation
inplace 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 lengthreducing 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 nonnegative 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 nonnegative 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.