libsemigroups
Classes | Public Types | Public Member Functions | Static Public Attributes | List of all members
libsemigroups::Semigroup Class Reference

Class for semigroups generated by instances of Element. More...

#include <semigroups.h>

Public Types

typedef RecVec< element_index_tcayley_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)
 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...
 
Semigroupcopy_add_generators (std::vector< Element const *> const *coll) const
 Returns a new semigroup generated by this and coll. More...
 
Semigroupcopy_add_generators (std::vector< Element *> const *coll) const
 Returns a new semigroup generated by this and coll. More...
 
Semigroupcopy_closure (std::vector< Element const *> const *coll)
 Returns a new semigroup generated by this and copies of the non-redundant elements of coll. More...
 
Semigroupcopy_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_tfactorisation (element_index_t pos)
 Returns a pointer to a libsemigroups::word_t which evaluates to the Element in position pos of this. More...
 
word_tfactorisation (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_tleft_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_tminimal_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_tminimal_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...
 
Semigroupoperator= (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_tright_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...
 
Elementword_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...
 

Detailed Description

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.

Member Typedef Documentation

◆ cayley_graph_t

Type for a left or right Cayley graph of a 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()

Constructor & Destructor Documentation

◆ Semigroup() [1/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element const *> const *  gens)
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:

  1. there must be at least one generator
  2. the generators must have equal degree Element::degree

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.

◆ Semigroup() [2/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element *> const *  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*.

◆ Semigroup() [3/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element *> *  gens)
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*.

◆ Semigroup() [4/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element const *> *  gens)
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*.

◆ Semigroup() [5/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element const *> const &  gens)
explicit

Construct from generators.

This constructor is for convenience only, see Semigroup::Semigroup.

◆ Semigroup() [6/8]

libsemigroups::Semigroup::Semigroup ( std::vector< Element *> const &  gens)
inlineexplicit

Construct from generators.

This constructor is for convenience, and it simply reinterpret_casts its argument to <std::vector<Element const*> const&.

◆ Semigroup() [7/8]

libsemigroups::Semigroup::Semigroup ( std::initializer_list< Element *>  gens)
inlineexplicit

Construct from generators.

This constructor is for convenience, and it simply static_casts its argument to std::vector<Element*>.

◆ Semigroup() [8/8]

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.

◆ ~Semigroup()

libsemigroups::Semigroup::~Semigroup ( )

A default destructor.

Member Function Documentation

◆ add_generators() [1/5]

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.

◆ add_generators() [2/5]

void libsemigroups::Semigroup::add_generators ( std::vector< Element *> const *  coll)
inline

Add copies of the generators coll to the generators of this.

See Semigroup::add_generators for more details.

◆ add_generators() [3/5]

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.

◆ add_generators() [4/5]

void libsemigroups::Semigroup::add_generators ( std::vector< Element *> const &  coll)
inline

Add copies of the generators coll to the generators of this.

See Semigroup::add_generators for more details.

◆ add_generators() [5/5]

void libsemigroups::Semigroup::add_generators ( std::initializer_list< Element *>  coll)
inline

Add copies of the generators coll to the generators of this.

See Semigroup::add_generators for more details.

◆ at()

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.

◆ batch_size()

size_t libsemigroups::Semigroup::batch_size ( ) const
inline

Returns the current value of the batch size. This is the minimum number of elements enumerated in any call to Semigroup::enumerate.

◆ begin()

const_iterator libsemigroups::Semigroup::begin ( ) const
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.

◆ cbegin()

const_iterator libsemigroups::Semigroup::cbegin ( ) const
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.

◆ cbegin_idempotents()

const_iterator_idempotents libsemigroups::Semigroup::cbegin_idempotents ( )
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.

◆ cbegin_sorted()

const_iterator_sorted libsemigroups::Semigroup::cbegin_sorted ( )
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.

◆ cend()

const_iterator libsemigroups::Semigroup::cend ( ) const
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.

◆ cend_idempotents()

const_iterator_idempotents libsemigroups::Semigroup::cend_idempotents ( )
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.

◆ cend_sorted()

const_iterator_sorted libsemigroups::Semigroup::cend_sorted ( )
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.

◆ closure() [1/4]

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.

◆ closure() [2/4]

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.

◆ closure() [3/4]

void libsemigroups::Semigroup::closure ( std::vector< Element *> const &  coll)
inline

Add copies of the non-redundant generators in coll to the generators of this.

See Semigroup::closure for more details.

◆ closure() [4/4]

void libsemigroups::Semigroup::closure ( std::initializer_list< Element *>  coll)
inline

Add copies of the non-redundant generators in coll to the generators of this.

See Semigroup::closure for more details.

◆ copy_add_generators() [1/2]

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.

◆ copy_add_generators() [2/2]

Semigroup* libsemigroups::Semigroup::copy_add_generators ( std::vector< Element *> const *  coll) const
inline

Returns a new semigroup generated by this and coll.

See Semigroup::copy_add_generators for more details.

◆ copy_closure() [1/2]

Semigroup * libsemigroups::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.

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.

◆ copy_closure() [2/2]

Semigroup* libsemigroups::Semigroup::copy_closure ( std::vector< Element *> const *  gens)
inline

Returns a new semigroup generated by this and copies of the non-redundant elements of coll.

See Semigroup::copy_closure for more details.

◆ crbegin()

const_reverse_iterator libsemigroups::Semigroup::crbegin ( ) const
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.

◆ crbegin_sorted()

const_reverse_iterator_sorted libsemigroups::Semigroup::crbegin_sorted ( )
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.

◆ crend()

const_reverse_iterator libsemigroups::Semigroup::crend ( ) const
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.

◆ crend_sorted()

const_reverse_iterator_sorted libsemigroups::Semigroup::crend_sorted ( )
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.

◆ current_max_word_length()

size_t libsemigroups::Semigroup::current_max_word_length ( ) const
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.

◆ current_nrrules()

size_t libsemigroups::Semigroup::current_nrrules ( ) const
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.

◆ current_position()

element_index_t libsemigroups::Semigroup::current_position ( Element const *  x) const
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.

See also
Semigroup::position and Semigroup::sorted_position.

◆ current_size()

size_t libsemigroups::Semigroup::current_size ( ) const
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.

◆ degree()

size_t libsemigroups::Semigroup::degree ( ) const
inline

Returns the degree of any (and all) Element's in the semigroup.

◆ end()

const_iterator libsemigroups::Semigroup::end ( ) const
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.

◆ enumerate() [1/2]

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.

◆ enumerate() [2/2]

void libsemigroups::Semigroup::enumerate ( size_t  limit = LIMIT_MAX)
inline

Enumerate the semigroup until limit elements are found.

See Semigroup::enumerate(std::atomic<bool>& killed, size_t limit) for more details.

◆ factorisation() [1/3]

void libsemigroups::Semigroup::factorisation ( word_t word,
element_index_t  pos 
)
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.

◆ factorisation() [2/3]

word_t* libsemigroups::Semigroup::factorisation ( element_index_t  pos)
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.

◆ factorisation() [3/3]

word_t * libsemigroups::Semigroup::factorisation ( Element const *  x)

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.

◆ fast_product()

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:

  • follows the path in the right or left Cayley graph from i to j, whichever is shorter using Semigroup::product_by_reduction; or
  • multiplies the elements in postions i 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.

◆ final_letter()

letter_t libsemigroups::Semigroup::final_letter ( element_index_t  pos) const
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.

◆ first_letter()

letter_t libsemigroups::Semigroup::first_letter ( element_index_t  pos) const
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.

◆ gens()

Element const* libsemigroups::Semigroup::gens ( letter_t  pos) const
inline

Return a pointer to the generator with index pos.

◆ is_begun()

bool libsemigroups::Semigroup::is_begun ( ) const
inline

Returns true if no elements other than the generators have been enumerated so far and false otherwise.

◆ is_done()

bool libsemigroups::Semigroup::is_done ( ) const
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.

◆ is_idempotent()

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.

◆ left()

element_index_t libsemigroups::Semigroup::left ( element_index_t  i,
letter_t  j 
)
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.

◆ left_cayley_graph_copy()

cayley_graph_t* libsemigroups::Semigroup::left_cayley_graph_copy ( )
inline

Returns a copy of the left Cayley graph of the semigroup.

This method fully enumerates the semigroup.

◆ length_const()

size_t libsemigroups::Semigroup::length_const ( element_index_t  pos) const
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.

◆ length_non_const()

size_t libsemigroups::Semigroup::length_non_const ( element_index_t  pos)
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.

◆ letter_to_pos()

element_index_t libsemigroups::Semigroup::letter_to_pos ( letter_t  i) const
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:

◆ minimal_factorisation() [1/3]

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.

◆ minimal_factorisation() [2/3]

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.

◆ minimal_factorisation() [3/3]

word_t * libsemigroups::Semigroup::minimal_factorisation ( Element const *  x)

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.

◆ next_relation()

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:

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.

See also
Semigroup::reset_next_relation.

◆ nrgens()

size_t libsemigroups::Semigroup::nrgens ( ) const
inline

Returns the number of generators of the semigroup.

◆ nridempotents()

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.

◆ nrrules()

size_t libsemigroups::Semigroup::nrrules ( )
inline

Returns the total number of relations in the presentation defining the semigroup.

See also
Semigroup::next_relation.

◆ operator=()

Semigroup& libsemigroups::Semigroup::operator= ( Semigroup const &  semigroup)
delete

Deleted.

The Semigroup class does not support an assignment contructor to avoid accidental copying. An object in Semigroup may use many gigabytes of memory and might be extremely expensive to copy. A copy constructor is provided in case such a copy should it be required anyway.

◆ operator[]()

Element const* libsemigroups::Semigroup::operator[] ( element_index_t  pos) const
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.

◆ position()

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).

◆ position_to_sorted_position()

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.

◆ prefix()

element_index_t libsemigroups::Semigroup::prefix ( element_index_t  pos) const
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.

◆ product_by_reduction()

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.

◆ reserve()

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.

◆ reset_next_relation()

void libsemigroups::Semigroup::reset_next_relation ( )
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.

◆ right()

element_index_t libsemigroups::Semigroup::right ( element_index_t  i,
letter_t  j 
)
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.

◆ right_cayley_graph_copy()

cayley_graph_t* libsemigroups::Semigroup::right_cayley_graph_copy ( )
inline

Returns a copy of the right Cayley graph of the semigroup.

This method fully enumerates the semigroup.

◆ set_batch_size()

void libsemigroups::Semigroup::set_batch_size ( size_t  batch_size)
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.

◆ set_max_threads()

void libsemigroups::Semigroup::set_max_threads ( size_t  nr_threads)
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.

◆ set_report()

void libsemigroups::Semigroup::set_report ( bool  val) const
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.

◆ size()

size_t libsemigroups::Semigroup::size ( )
inline

Returns the size of the semigroup.

◆ sorted_at()

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.

◆ sorted_position()

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.

◆ suffix()

element_index_t libsemigroups::Semigroup::suffix ( element_index_t  pos) const
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.

◆ test_membership()

bool libsemigroups::Semigroup::test_membership ( Element const *  x)
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).

◆ word_to_element()

Element * libsemigroups::Semigroup::word_to_element ( word_t const &  w) const

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]).

See also
Semigroup::word_to_pos.

◆ word_to_pos()

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.

See also
Semigroup::word_to_element.

Member Data Documentation

◆ LIMIT_MAX

Semigroup::index_t const libsemigroups::Semigroup::LIMIT_MAX = std::numeric_limits<index_t>::max()
static

This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumerate.

◆ UNDEFINED

Semigroup::index_t const libsemigroups::Semigroup::UNDEFINED = std::numeric_limits<index_t>::max()
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.


The documentation for this class was generated from the following files: