libsemigroups
semigroups.h
1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2016 James D. Mitchell
4 //
5 // This program is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program. If not, see <http://www.gnu.org/licenses/>.
17 //
18 
19 #ifndef LIBSEMIGROUPS_SRC_SEMIGROUPS_H_
20 #define LIBSEMIGROUPS_SRC_SEMIGROUPS_H_
21 
22 #include <algorithm>
23 #include <mutex>
24 #include <string>
25 #include <thread>
26 #include <unordered_map>
27 #include <utility>
28 #include <vector>
29 
30 #include "elements.h"
31 #include "libsemigroups-debug.h"
32 #include "recvec.h"
33 #include "report.h"
34 
35 #if (defined(__GNUC__) && __GNUC__ < 5 \
36  && !(defined(__clang__) || defined(__INTEL_COMPILER)))
37 #pragma message( \
38  "GCC version >=5.0 is recommended, some features may not work correctly")
39 #endif
40 
42 namespace libsemigroups {
43 
44  class RWSE;
45 
46  // This object is used for printing information during a computation. The
47  // reason it is global is that we must be able to report from different
48  // threads running concurrently.
49  extern Reporter glob_reporter;
50 
52  typedef size_t letter_t;
53 
55  typedef std::vector<letter_t> word_t;
56 
58  typedef std::pair<word_t, word_t> relation_t;
59 
68  class Semigroup {
69  typedef RecVec<bool> flags_t;
70 
71  // Type used for indexing elements in a Semigroup, use this when not
72  // specifically referring to a position in _elements. It should be possible
73  // to change this type and everything will just work, provided the size of
74  // the semigroup is less than the maximum value of this type of integer.
75  typedef size_t index_t;
76 
77  // The elements of a semigroup are stored in _elements, but because of the
78  // way add_generators/closure work, it might not be the case that all the
79  // words of a given length are contiguous in _elements. Hence we require a
80  // means of finding the next element of a given length. In
81  // _enumerate_order, the first K_1 values are element_index_t's
82  // equal to the positions in _elements of the words of length 1,
83  // the next K_2 values are the element_index_t's equal to the positions in
84  // _elements of the words of length 2, and so on.
85  //
86  // This typedef is used to distinguish variables that refer to positions in
87  // _elements (element_index_t) from those that refer to positions in
88  // _enumerate_order (enumerate_index_t).
89  typedef index_t enumerate_index_t;
90 
91  public:
95  typedef index_t element_index_t;
96 
98  typedef RecVec<element_index_t> cayley_graph_t;
99 
100  public:
107  Semigroup& operator=(Semigroup const& semigroup) = delete;
108 
128  explicit Semigroup(std::vector<Element const*> const* gens);
129 
135  explicit Semigroup(std::vector<Element*> const* gens)
136  : Semigroup(
137  reinterpret_cast<std::vector<Element const*> const*>(gens)) {}
138 
143  explicit Semigroup(std::vector<Element*>* gens)
144  : Semigroup(const_cast<std::vector<Element*> const*>(gens)) {}
145 
151  explicit Semigroup(std::vector<Element const*>* gens)
152  : Semigroup(const_cast<std::vector<Element const*> const*>(gens)) {}
153 
157  explicit Semigroup(std::vector<Element const*> const& gens);
158 
163  explicit Semigroup(std::vector<Element*> const& gens)
164  : Semigroup(
165  reinterpret_cast<std::vector<Element const*> const&>(gens)) {}
166 
171  explicit Semigroup(std::initializer_list<Element*> gens)
172  : Semigroup(static_cast<std::vector<Element*>>(gens)) {}
173 
179  Semigroup(const Semigroup& copy);
180 
181  private:
182  // Partial copy.
183  // \p copy a semigroup
184  // \p coll a collection of additional generators
185  //
186  // This is a constructor for a semigroup generated by the generators of the
187  // Semigroup copy and the (possibly) additional generators coll.
188  //
189  // The relevant parts of the data structure of copy are copied and
190  // \c this will be corrupt unless add_generators or closure is called
191  // subsequently. This is why this method is private.
192  //
193  // The same effect can be obtained by copying copy using the copy
194  // constructor and then calling add_generators or closure. However,
195  // this constructor avoids copying those parts of the data structure of
196  // copy that add_generators invalidates anyway. If copy has not been
197  // enumerated at all, then these two routes for adding more generators are
198  // equivalent.
199  Semigroup(Semigroup const& copy, std::vector<Element const*> const* coll);
200 
201  public:
203  ~Semigroup();
204 
215  element_index_t word_to_pos(word_t const& w) const;
216 
226  Element* word_to_element(word_t const& w) const;
227 
235  size_t current_max_word_length() const {
236  if (is_done()) {
237  return _lenindex.size() - 2;
238  } else if (_nr > _lenindex.back()) {
239  return _lenindex.size();
240  } else {
241  return _lenindex.size() - 1;
242  }
243  }
244 
246  size_t degree() const {
247  return _degree;
248  }
249 
251  size_t nrgens() const {
252  return _gens.size();
253  }
254 
256  Element const* gens(letter_t pos) const {
257  LIBSEMIGROUPS_ASSERT(pos < _gens.size());
258  return _gens[pos];
259  }
260 
266  bool is_done() const {
267  return (_pos >= _nr);
268  }
269 
272  bool is_begun() const {
273  LIBSEMIGROUPS_ASSERT(_lenindex.size() > 1);
274  return (_pos >= _lenindex[1]);
275  }
276 
289  if (x->degree() != _degree) {
290  return UNDEFINED;
291  }
292 
293  auto it = _map.find(x);
294  return (it == _map.end() ? UNDEFINED : it->second);
295  }
296 
302  size_t current_size() const {
303  return _elements.size();
304  }
305 
311  size_t current_nrrules() const {
312  return _nrrules;
313  }
314 
321  LIBSEMIGROUPS_ASSERT(pos < _nr);
322  return _prefix[pos];
323  }
324 
331  LIBSEMIGROUPS_ASSERT(pos < _nr);
332  return _suffix[pos];
333  }
334 
348  LIBSEMIGROUPS_ASSERT(pos < _nr);
349  return _first[pos];
350  }
351 
365  LIBSEMIGROUPS_ASSERT(pos < _nr);
366  return _final[pos];
367  }
368 
371  size_t batch_size() const {
372  return _batch_size;
373  }
374 
380  size_t length_const(element_index_t pos) const {
381  LIBSEMIGROUPS_ASSERT(pos < _nr);
382  return _length[pos];
383  }
384 
390  if (pos >= _nr) {
391  enumerate();
392  }
393  return length_const(pos);
394  }
395 
405  element_index_t j) const;
406 
427 
439  LIBSEMIGROUPS_ASSERT(i < _nrgens);
440  return _letter_to_pos[i];
441  }
442 
448  size_t nridempotents();
449 
455  bool is_idempotent(element_index_t pos);
456 
461  size_t nrrules() {
462  enumerate();
463  return _nrrules;
464  }
465 
477  // FIXME Make _batch_size mutable and this const
478  void set_batch_size(size_t batch_size) {
479  _batch_size = batch_size;
480  }
481 
490  void reserve(size_t n);
491 
493  size_t size() {
494  enumerate();
495  return _elements.size();
496  }
497 
505  bool test_membership(Element const* x) {
506  return (position(x) != UNDEFINED);
507  }
508 
518  element_index_t position(Element const* x);
519 
524 
529 
536  Element const* at(element_index_t pos);
537 
542  Element const* operator[](element_index_t pos) const {
543  return _elements[pos];
544  }
545 
550  Element const* sorted_at(element_index_t pos);
551 
557  enumerate();
558  return _right.get(i, j);
559  }
560 
565  enumerate();
566  return new cayley_graph_t(_right);
567  }
568 
574  enumerate();
575  return _left.get(i, j);
576  }
577 
582  enumerate();
583  return new cayley_graph_t(_left);
584  }
585 
598 
606 
613 
621  minimal_factorisation(word, pos);
622  }
623 
632  return minimal_factorisation(pos);
633  }
634 
640  word_t* factorisation(Element const* x);
641 
649  _relation_pos = UNDEFINED;
650  _relation_gen = 0;
651  }
652 
684  void next_relation(word_t& relation);
685 
707  void enumerate(std::atomic<bool>& killed, size_t limit = LIMIT_MAX);
708 
713  void enumerate(size_t limit = LIMIT_MAX) {
714  std::atomic<bool> killed(false);
715  enumerate(killed, limit);
716  }
717 
747  void add_generators(std::vector<Element const*> const* coll);
748 
752  void add_generators(std::vector<Element*> const* coll) {
754  reinterpret_cast<std::vector<Element const*> const*>(coll));
755  }
756 
760  void add_generators(std::vector<Element const*> const& coll);
761 
765  void add_generators(std::vector<Element*> const& coll) {
767  reinterpret_cast<std::vector<Element const*> const&>(coll));
768  }
769 
773  void add_generators(std::initializer_list<Element*> coll) {
774  add_generators(static_cast<std::vector<Element*>>(coll));
775  }
776 
787  Semigroup*
788  copy_add_generators(std::vector<Element const*> const* coll) const;
789 
793  Semigroup* copy_add_generators(std::vector<Element*> const* coll) const {
794  return copy_add_generators(
795  reinterpret_cast<std::vector<Element const*> const*>(coll));
796  }
797 
818  void closure(std::vector<Element const*> const* coll);
819 
824  void closure(std::vector<Element const*> const& coll);
825 
830  void closure(std::vector<Element*> const& coll) {
831  closure(reinterpret_cast<std::vector<Element const*> const&>(coll));
832  }
833 
838  void closure(std::initializer_list<Element*> coll) {
839  closure(static_cast<std::vector<Element*>>(coll));
840  }
841 
852  Semigroup* copy_closure(std::vector<Element const*> const* coll);
853 
858  Semigroup* copy_closure(std::vector<Element*> const* gens) {
859  return copy_closure(
860  reinterpret_cast<std::vector<Element const*> const*>(gens));
861  }
862 
866  static index_t const UNDEFINED;
867 
870  static index_t const LIMIT_MAX;
871 
873  //
876  void set_report(bool val) const {
877  glob_reporter.set_report(val);
878  }
879 
887  void set_max_threads(size_t nr_threads) {
888  unsigned int n
889  = static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads);
890  _max_threads = std::min(n, std::thread::hardware_concurrency());
891  }
892 
893  private:
894  template <typename T, class C> class iterator_base {
895  public:
896  typedef typename std::vector<Element const*>::size_type size_type;
897  typedef typename std::vector<T>::difference_type difference_type;
898  typedef typename std::vector<Element const*>::value_type value_type;
899  typedef typename std::vector<Element const*>::const_reference reference;
900  typedef typename std::vector<Element const*>::const_pointer pointer;
901  typedef std::random_access_iterator_tag iterator_category;
902 
903  explicit iterator_base(typename std::vector<T>::const_iterator it_vec)
904  : _it_vec(it_vec) {}
905 
906  iterator_base(iterator_base const& that) : iterator_base(that._it_vec) {}
907 
908  iterator_base& operator=(iterator_base const& that) {
909  _it_vec = that._it_vec;
910  return *this;
911  }
912 
913  virtual ~iterator_base() {}
914 
915  bool operator==(iterator_base const& that) const {
916  return _it_vec == that._it_vec;
917  }
918 
919  bool operator!=(iterator_base const& that) const {
920  return _it_vec != that._it_vec;
921  }
922 
923  bool operator<(iterator_base const& that) const {
924  return _it_vec < that._it_vec;
925  }
926 
927  bool operator>(iterator_base const& that) const {
928  return _it_vec > that._it_vec;
929  }
930 
931  bool operator<=(iterator_base const& that) const {
932  return operator<(that) || operator==(that);
933  }
934 
935  bool operator>=(iterator_base const& that) const {
936  return operator>(that) || operator==(that);
937  }
938 
939  iterator_base operator++(int) { // postfix
940  iterator_base tmp(*this);
941  operator++();
942  return tmp;
943  }
944 
945  iterator_base operator--(int) {
946  iterator_base tmp(*this);
947  operator--();
948  return tmp;
949  }
950 
951  iterator_base operator+(size_type val) const {
952  iterator_base out(*this);
953  return out += val;
954  }
955 
956  friend iterator_base operator+(size_type val, iterator_base const& it) {
957  return it + val;
958  }
959 
960  iterator_base operator-(size_type val) const {
961  iterator_base out(*this);
962  return out -= val;
963  }
964 
965  reference operator[](size_type pos) const {
966  return *(*this + pos);
967  }
968 
969  iterator_base& operator++() { // prefix
970  ++_it_vec;
971  return *this;
972  }
973 
974  iterator_base& operator--() {
975  --_it_vec;
976  return *this;
977  }
978 
979  iterator_base& operator+=(size_type val) {
980  _it_vec += val;
981  return *this;
982  }
983 
984  iterator_base& operator-=(size_type val) {
985  _it_vec -= val;
986  return *this;
987  }
988 
989  difference_type operator-(iterator_base that) const {
990  return _it_vec - that._it_vec;
991  }
992 
993  reference operator*() const {
994  return _methods.indirection(_it_vec);
995  }
996 
997  pointer operator->() const {
998  return _methods.addressof(_it_vec);
999  }
1000 
1001  protected:
1002  typename std::vector<T>::const_iterator _it_vec;
1003  static C const _methods;
1004  }; // iterator_base definition ends
1005 
1006  struct IteratorMethods {
1007  IteratorMethods() {}
1008  typename std::vector<Element const*>::const_reference indirection(
1009  typename std::vector<Element const*>::const_iterator it) const {
1010  return *it;
1011  }
1012  typename std::vector<Element const*>::const_pointer
1013  addressof(typename std::vector<Element const*>::const_iterator it) const {
1014  return &(*it);
1015  }
1016  };
1017 
1018  struct IteratorMethodsPairFirst {
1019  IteratorMethodsPairFirst() {}
1020  typename std::vector<Element const*>::const_reference indirection(
1021  typename std::vector<std::pair<Element const*, element_index_t>>::
1022  const_iterator it) const {
1023  return (*it).first;
1024  }
1025 
1026  typename std::vector<Element const*>::const_pointer addressof(
1027  typename std::vector<std::pair<Element const*, element_index_t>>::
1028  const_iterator it) const {
1029  return &((*it).first);
1030  }
1031  };
1032 
1033  typedef iterator_base<Element const*, IteratorMethods> const_iterator;
1034  typedef iterator_base<std::pair<Element const*, element_index_t>,
1035  IteratorMethodsPairFirst>
1036  const_iterator_pair_first;
1037  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1038  typedef std::reverse_iterator<const_iterator_pair_first>
1039  const_reverse_iterator_pair_first;
1040 
1041  typedef const_iterator_pair_first const_iterator_sorted;
1042  typedef const_iterator_pair_first const_iterator_idempotents;
1043  typedef const_reverse_iterator_pair_first const_reverse_iterator_sorted;
1044  typedef const_reverse_iterator_pair_first
1045  const_reverse_iterator_idempotents;
1046 
1047  public:
1055  const_iterator cbegin() const {
1056  return const_iterator(_elements.cbegin());
1057  }
1058 
1066  const_iterator begin() const {
1067  return cbegin();
1068  }
1069 
1077  const_iterator cend() const {
1078  return const_iterator(_elements.cend());
1079  }
1080 
1088  const_iterator end() const {
1089  return cend();
1090  }
1091 
1099  const_reverse_iterator crbegin() const {
1100  return const_reverse_iterator(cend());
1101  }
1102 
1110  const_reverse_iterator crend() const {
1111  return const_reverse_iterator(cbegin());
1112  }
1113 
1120  const_iterator_sorted cbegin_sorted() {
1121  init_sorted();
1122  return const_iterator_pair_first(_sorted.cbegin());
1123  }
1124 
1131  const_iterator_sorted cend_sorted() {
1132  init_sorted();
1133  return const_iterator_pair_first(_sorted.cend());
1134  }
1135 
1142  const_reverse_iterator_sorted crbegin_sorted() {
1143  init_sorted();
1144  return const_reverse_iterator_pair_first(cend_sorted());
1145  }
1146 
1153  const_reverse_iterator_sorted crend_sorted() {
1154  init_sorted();
1155  return const_reverse_iterator_pair_first(cbegin_sorted());
1156  }
1157 
1167  const_iterator_idempotents cbegin_idempotents() {
1168  init_idempotents();
1169  return const_iterator_pair_first(_idempotents.cbegin());
1170  }
1171 
1177  const_iterator_idempotents cend_idempotents() {
1178  init_idempotents();
1179  return const_iterator_pair_first(_idempotents.cend());
1180  }
1181 
1182  private:
1183  // Expand the data structures in the semigroup with space for nr elements
1184  void inline expand(index_t nr) {
1185  _left.add_rows(nr);
1186  _reduced.add_rows(nr);
1187  _right.add_rows(nr);
1188  }
1189 
1190  // Check if an element is the identity, x should be in the position pos
1191  // of _elements.
1192  void inline is_one(Element const* x, element_index_t pos) {
1193  if (!_found_one && *x == *_id) {
1194  _pos_one = pos;
1195  _found_one = true;
1196  }
1197  }
1198 
1199  void copy_gens();
1200 
1201  void inline closure_update(element_index_t i,
1202  letter_t j,
1203  letter_t b,
1204  element_index_t s,
1205  index_t old_nr,
1206  size_t const& thread_id);
1207 
1208  // Initialise the data member _sorted. We store a list of pairs consisting
1209  // of an Element* and element_index_t which is sorted on the first entry
1210  // using the operator< of the Element class. The second component is then
1211  // inverted (as a permutation) so that we can then find the position of an
1212  // element in the sorted list of elements.
1213  void init_sorted();
1214 
1215  typedef std::pair<Element const*, element_index_t> idempotent_value_t;
1216 
1217  // Find the idempotents and store their pointers and positions in a
1218  // std::pair of type idempotent_value_t.
1219  void init_idempotents();
1220 
1221  // Find the idempotents in the range [first, last) and store
1222  // the corresponding std::pair of type idempotent_value_t in the 4th
1223  // parameter. The parameter threshold is the point, calculated in
1224  // init_idempotents, at which it is better to simply multiply elements
1225  // rather than trace in the left/right Cayley graph.
1226  void idempotents(enumerate_index_t const first,
1227  enumerate_index_t const last,
1228  enumerate_index_t const threshold,
1229  std::vector<idempotent_value_t>& idempotents);
1230 
1231  size_t _batch_size;
1232  element_index_t _degree;
1233  std::vector<std::pair<letter_t, letter_t>> _duplicate_gens;
1234  std::vector<Element const*> _elements;
1235  std::vector<element_index_t> _enumerate_order;
1236  std::vector<letter_t> _final;
1237  std::vector<letter_t> _first;
1238  bool _found_one;
1239  std::vector<Element const*> _gens;
1240  Element const* _id;
1241  std::vector<idempotent_value_t> _idempotents;
1242  bool _idempotents_found;
1243  std::vector<uint8_t> _is_idempotent;
1244  cayley_graph_t _left;
1245  std::vector<index_t> _length;
1246  std::vector<enumerate_index_t> _lenindex;
1247  std::vector<element_index_t> _letter_to_pos;
1248  std::unordered_map<Element const*,
1250  Element::Hash,
1251  Element::Equal>
1252  _map;
1253  size_t _max_threads;
1254  std::mutex _mtx;
1255  index_t _nr;
1256  letter_t _nrgens;
1257  size_t _nrrules;
1258  enumerate_index_t _pos;
1259  element_index_t _pos_one;
1260  std::vector<element_index_t> _prefix;
1261  flags_t _reduced;
1262  letter_t _relation_gen;
1263  enumerate_index_t _relation_pos;
1264  cayley_graph_t _right;
1265  std::vector<std::pair<Element const*, element_index_t>> _sorted;
1266  std::vector<element_index_t> _suffix;
1267  Element* _tmp_product;
1268  size_t _wordlen;
1269 
1270  static std::vector<element_index_t> _tmp_inverter;
1271  static std::vector<bool> _old_new;
1272 #ifdef LIBSEMIGROUPS_STATS
1273  size_t _nr_products;
1274 #endif
1275  };
1276 
1280 
1281  template <typename T, typename C>
1282  C const Semigroup::iterator_base<T, C>::_methods;
1283 } // namespace libsemigroups
1284 
1285 #endif // LIBSEMIGROUPS_SRC_SEMIGROUPS_H_
Semigroup(std::initializer_list< Element *> gens)
Construct from generators.
Definition: semigroups.h:171
Semigroup::cayley_graph_t cayley_graph_t
This is just for backwards compatibility and should disappear at some point.
Definition: semigroups.h:1279
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.
Definition: semigroups.cc:397
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 generat...
Definition: semigroups.cc:461
static index_t const LIMIT_MAX
This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumera...
Definition: semigroups.h:870
bool is_begun() const
Returns true if no elements other than the generators have been enumerated so far and false otherwise...
Definition: semigroups.h:272
void add_generators(std::vector< Element const *> const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.cc:720
Semigroup(std::vector< Element *> const *gens)
Construct from generators.
Definition: semigroups.h:135
cayley_graph_t * right_cayley_graph_copy()
Returns a copy of the right Cayley graph of the semigroup.
Definition: semigroups.h:564
size_t current_nrrules() const
Returns the number of relations in the presentation for the semigroup that have been found so far...
Definition: semigroups.h:311
Semigroup * copy_add_generators(std::vector< Element *> const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.h:793
void reset_next_relation()
This method resets Semigroup::next_relation so that when it is next called the resulting relation is ...
Definition: semigroups.h:648
Semigroup(std::vector< Element const *> *gens)
Construct from generators.
Definition: semigroups.h:151
virtual size_t degree() const =0
Returns the degree of an Element.
const_reverse_iterator_sorted crend_sorted()
Returns a const iterator pointing to one before the first element of the semigroup when the elements ...
Definition: semigroups.h:1153
Semigroup(std::vector< Element const *> const *gens)
Construct from generators.
Definition: semigroups.cc:38
void add_generators(std::initializer_list< Element *> coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:773
Semigroup * copy_add_generators(std::vector< Element const *> const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.cc:704
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...
Definition: semigroups.h:556
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...
Definition: semigroups.cc:332
void set_batch_size(size_t batch_size)
Set a new value for the batch size.
Definition: semigroups.h:478
void enumerate(size_t limit=LIMIT_MAX)
Enumerate the semigroup until limit elements are found.
Definition: semigroups.h:713
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).
Definition: semigroups.cc:419
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
const_reverse_iterator_sorted crbegin_sorted()
Returns a const iterator pointing to the last element of the semigroup when the elements are sorted b...
Definition: semigroups.h:1142
const_iterator begin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1066
Abstract base class for semigroup elements.
Definition: elements.h:44
size_t length_non_const(element_index_t pos)
Returns the length of the element in position pos of the semigroup.
Definition: semigroups.h:389
const_iterator cend() const
Returns a const iterator pointing to one past the last currently known element of the semigroup...
Definition: semigroups.h:1077
size_t current_size() const
Returns the number of elements in the semigroup that have been enumerated so far. ...
Definition: semigroups.h:302
element_index_t letter_to_pos(letter_t i) const
Returns the position in this of the generator with index i.
Definition: semigroups.h:438
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 i...
Definition: semigroups.cc:406
const_reverse_iterator crbegin() const
Returns a const reverse iterator pointing to the last currently known element of the semigroup...
Definition: semigroups.h:1099
void closure(std::initializer_list< Element *> coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.h:838
const_iterator_idempotents cbegin_idempotents()
Returns a const iterator pointing at the first idempotent in the semigroup.
Definition: semigroups.h:1167
Element const * operator[](element_index_t pos) const
Returns the element of the semigroup in position pos.
Definition: semigroups.h:542
Semigroup(std::vector< Element *> const &gens)
Construct from generators.
Definition: semigroups.h:163
void enumerate(std::atomic< bool > &killed, size_t limit=LIMIT_MAX)
Enumerate the semigroup until limit elements are found or killed is true.
Definition: semigroups.cc:523
const_iterator_sorted cend_sorted()
Returns a const iterator pointing to one past the last element of the semigroup when the elements are...
Definition: semigroups.h:1131
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).
Definition: semigroups.cc:352
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...
Definition: semigroups.cc:410
letter_t first_letter(element_index_t pos) const
Returns the first letter of the element in position pos.
Definition: semigroups.h:347
void set_report(bool val) const
Turn reporting on or off.
Definition: semigroups.h:876
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...
Definition: semigroups.cc:378
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...
Definition: semigroups.h:631
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...
Definition: semigroups.h:573
size_t length_const(element_index_t pos) const
Returns the length of the element in position pos of the semigroup.
Definition: semigroups.h:380
const_iterator_idempotents cend_idempotents()
Returns a const iterator referring to past the end of the last idempotent in the semigroup.
Definition: semigroups.h:1177
size_t nrrules()
Returns the total number of relations in the presentation defining the semigroup. ...
Definition: semigroups.h:461
const_reverse_iterator crend() const
Returns a const reverse iterator pointing to one before the first element of the semigroup.
Definition: semigroups.h:1110
size_t degree() const
Returns the degree of any (and all) Element&#39;s in the semigroup.
Definition: semigroups.h:246
void set_max_threads(size_t nr_threads)
Set the maximum number of threads that any method of an instance of Semigroup can use...
Definition: semigroups.h:887
Semigroup(std::vector< Element *> *gens)
Construct from generators.
Definition: semigroups.h:143
Semigroup & operator=(Semigroup const &semigroup)=delete
Deleted.
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
const_iterator end() const
Returns a const iterator pointing to one past the last currently known element of the semigroup...
Definition: semigroups.h:1088
bool is_done() const
Returns true if the semigroup is fully enumerated and false if not.
Definition: semigroups.h:266
bool is_idempotent(element_index_t pos)
Returns true if the element in position pos is an idempotent and false if it is not.
Definition: semigroups.cc:370
void reserve(size_t n)
Requests that the capacity (i.e. number of elements) of the semigroup be at least enough to contain n...
Definition: semigroups.cc:279
RecVec< element_index_t > cayley_graph_t
Type for a left or right Cayley graph of a semigroup.
Definition: semigroups.h:98
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...
Definition: semigroups.cc:302
void add_generators(std::vector< Element *> const &coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:765
letter_t final_letter(element_index_t pos) const
Returns the last letter of the element in position pos.
Definition: semigroups.h:364
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 semigr...
Definition: semigroups.h:288
size_t size()
Returns the size of the semigroup.
Definition: semigroups.h:493
static index_t const UNDEFINED
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.
Definition: semigroups.h:866
size_t current_max_word_length() const
Returns the maximum length of a word in the generators so far computed.
Definition: semigroups.h:235
Class for semigroups generated by instances of Element.
Definition: semigroups.h:68
size_t letter_t
Type for the index of a generator of a semigroup.
Definition: semigroups.h:52
size_t nridempotents()
Returns the total number of idempotents in the semigroup.
Definition: semigroups.cc:365
std::pair< word_t, word_t > relation_t
Type for a pair of word_t (a relation) of a semigroup.
Definition: semigroups.h:58
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...
Definition: semigroups.h:620
Element * word_to_element(word_t const &w) const
Returns a pointer to the element of this represented by the word w.
Definition: semigroups.cc:315
~Semigroup()
A default destructor.
Definition: semigroups.cc:264
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...
Definition: semigroups.cc:669
size_t batch_size() const
Returns the current value of the batch size. This is the minimum number of elements enumerated in any...
Definition: semigroups.h:371
bool test_membership(Element const *x)
Returns true if x is an element of this and false if it is not.
Definition: semigroups.h:505
void closure(std::vector< Element const *> const *coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.cc:689
void closure(std::vector< Element *> const &coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.h:830
const_iterator_sorted cbegin_sorted()
Returns a const iterator pointing to the first element of the semigroup when the elements are sorted ...
Definition: semigroups.h:1120
cayley_graph_t * left_cayley_graph_copy()
Returns a copy of the left Cayley graph of the semigroup.
Definition: semigroups.h:581
const_iterator cbegin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1055
Element const * gens(letter_t pos) const
Return a pointer to the generator with index pos.
Definition: semigroups.h:256
Semigroup * copy_closure(std::vector< Element *> const *gens)
Returns a new semigroup generated by this and copies of the non-redundant elements of coll...
Definition: semigroups.h:858
void add_generators(std::vector< Element *> const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:752
index_t element_index_t
Type for the position of an element in an instance of Semigroup. The size of the semigroup being enum...
Definition: semigroups.h:95
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 ...
Definition: semigroups.h:330
size_t nrgens() const
Returns the number of generators of the semigroup.
Definition: semigroups.h:251
void next_relation(word_t &relation)
This method changes relation in-place to contain the next relation of the presentation defining this...
Definition: semigroups.cc:475
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 ...
Definition: semigroups.h:320