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  // postfix
940  iterator_base operator++(int) {
941  iterator_base tmp(*this);
942  iterator_base::operator++();
943  return tmp;
944  }
945 
946  iterator_base operator--(int) {
947  iterator_base tmp(*this);
948  iterator_base::operator--();
949  return tmp;
950  }
951 
952  iterator_base operator+(size_type val) const {
953  iterator_base out(*this);
954  return out += val;
955  }
956 
957  friend iterator_base operator+(size_type val, iterator_base const& it) {
958  return it + val;
959  }
960 
961  iterator_base operator-(size_type val) const {
962  iterator_base out(*this);
963  return out -= val;
964  }
965 
966  reference operator[](size_type pos) const {
967  return *(*this + pos);
968  }
969 
970  iterator_base& operator++() { // prefix
971  ++_it_vec;
972  return *this;
973  }
974 
975  iterator_base& operator--() {
976  --_it_vec;
977  return *this;
978  }
979 
980  iterator_base& operator+=(size_type val) {
981  _it_vec += val;
982  return *this;
983  }
984 
985  iterator_base& operator-=(size_type val) {
986  _it_vec -= val;
987  return *this;
988  }
989 
990  difference_type operator-(iterator_base that) const {
991  return _it_vec - that._it_vec;
992  }
993 
994  reference operator*() const {
995  return _methods.indirection(_it_vec);
996  }
997 
998  pointer operator->() const {
999  return _methods.addressof(_it_vec);
1000  }
1001 
1002  protected:
1003  typename std::vector<T>::const_iterator _it_vec;
1004  static C const _methods;
1005  }; // iterator_base definition ends
1006 
1007  struct IteratorMethods {
1008  IteratorMethods() {}
1009  typename std::vector<Element const*>::const_reference indirection(
1010  typename std::vector<Element const*>::const_iterator it) const {
1011  return *it;
1012  }
1013  typename std::vector<Element const*>::const_pointer
1014  addressof(typename std::vector<Element const*>::const_iterator it) const {
1015  return &(*it);
1016  }
1017  };
1018 
1019  struct IteratorMethodsPairFirst {
1020  IteratorMethodsPairFirst() {}
1021  typename std::vector<Element const*>::const_reference indirection(
1022  typename std::vector<std::pair<Element const*, element_index_t>>::
1023  const_iterator it) const {
1024  return (*it).first;
1025  }
1026 
1027  typename std::vector<Element const*>::const_pointer
1028  addressof(typename std::vector<
1029  std::pair<Element const*, element_index_t>>::const_iterator it)
1030  const {
1031  return &((*it).first);
1032  }
1033  };
1034 
1035  typedef iterator_base<Element const*, IteratorMethods> const_iterator;
1036  typedef iterator_base<std::pair<Element const*, element_index_t>,
1037  IteratorMethodsPairFirst>
1038  const_iterator_pair_first;
1039  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1040  typedef std::reverse_iterator<const_iterator_pair_first>
1041  const_reverse_iterator_pair_first;
1042 
1043  typedef const_iterator_pair_first const_iterator_sorted;
1044  typedef const_iterator_pair_first const_iterator_idempotents;
1045  typedef const_reverse_iterator_pair_first const_reverse_iterator_sorted;
1046  typedef const_reverse_iterator_pair_first
1047  const_reverse_iterator_idempotents;
1048 
1049  public:
1057  const_iterator cbegin() const {
1058  return const_iterator(_elements.cbegin());
1059  }
1060 
1068  const_iterator begin() const {
1069  return cbegin();
1070  }
1071 
1079  const_iterator cend() const {
1080  return const_iterator(_elements.cend());
1081  }
1082 
1090  const_iterator end() const {
1091  return cend();
1092  }
1093 
1101  const_reverse_iterator crbegin() const {
1102  return const_reverse_iterator(cend());
1103  }
1104 
1112  const_reverse_iterator crend() const {
1113  return const_reverse_iterator(cbegin());
1114  }
1115 
1122  const_iterator_sorted cbegin_sorted() {
1123  init_sorted();
1124  return const_iterator_pair_first(_sorted.cbegin());
1125  }
1126 
1133  const_iterator_sorted cend_sorted() {
1134  init_sorted();
1135  return const_iterator_pair_first(_sorted.cend());
1136  }
1137 
1144  const_reverse_iterator_sorted crbegin_sorted() {
1145  init_sorted();
1146  return const_reverse_iterator_pair_first(cend_sorted());
1147  }
1148 
1155  const_reverse_iterator_sorted crend_sorted() {
1156  init_sorted();
1157  return const_reverse_iterator_pair_first(cbegin_sorted());
1158  }
1159 
1169  const_iterator_idempotents cbegin_idempotents() {
1170  init_idempotents();
1171  return const_iterator_pair_first(_idempotents.cbegin());
1172  }
1173 
1179  const_iterator_idempotents cend_idempotents() {
1180  init_idempotents();
1181  return const_iterator_pair_first(_idempotents.cend());
1182  }
1183 
1184  private:
1185  // Expand the data structures in the semigroup with space for nr elements
1186  void inline expand(index_t nr) {
1187  _left.add_rows(nr);
1188  _reduced.add_rows(nr);
1189  _right.add_rows(nr);
1190  }
1191 
1192  // Check if an element is the identity, x should be in the position pos
1193  // of _elements.
1194  void inline is_one(Element const* x, element_index_t pos) {
1195  if (!_found_one && *x == *_id) {
1196  _pos_one = pos;
1197  _found_one = true;
1198  }
1199  }
1200 
1201  void copy_gens();
1202 
1203  void inline closure_update(element_index_t i,
1204  letter_t j,
1205  letter_t b,
1206  element_index_t s,
1207  index_t old_nr,
1208  size_t const& thread_id);
1209 
1210  // Initialise the data member _sorted. We store a list of pairs consisting
1211  // of an Element* and element_index_t which is sorted on the first entry
1212  // using the operator< of the Element class. The second component is then
1213  // inverted (as a permutation) so that we can then find the position of an
1214  // element in the sorted list of elements.
1215  void init_sorted();
1216 
1217  typedef std::pair<Element const*, element_index_t> idempotent_value_t;
1218 
1219  // Find the idempotents and store their pointers and positions in a
1220  // std::pair of type idempotent_value_t.
1221  void init_idempotents();
1222 
1223  // Find the idempotents in the range [first, last) and store
1224  // the corresponding std::pair of type idempotent_value_t in the 4th
1225  // parameter. The parameter threshold is the point, calculated in
1226  // init_idempotents, at which it is better to simply multiply elements
1227  // rather than trace in the left/right Cayley graph.
1228  void idempotents(enumerate_index_t const first,
1229  enumerate_index_t const last,
1230  enumerate_index_t const threshold,
1231  std::vector<idempotent_value_t>& idempotents);
1232 
1233  size_t _batch_size;
1234  element_index_t _degree;
1235  std::vector<std::pair<letter_t, letter_t>> _duplicate_gens;
1236  std::vector<Element const*> _elements;
1237  std::vector<element_index_t> _enumerate_order;
1238  std::vector<letter_t> _final;
1239  std::vector<letter_t> _first;
1240  bool _found_one;
1241  std::vector<Element const*> _gens;
1242  Element const* _id;
1243  std::vector<idempotent_value_t> _idempotents;
1244  bool _idempotents_found;
1245  std::vector<uint8_t> _is_idempotent;
1246  cayley_graph_t _left;
1247  std::vector<index_t> _length;
1248  std::vector<enumerate_index_t> _lenindex;
1249  std::vector<element_index_t> _letter_to_pos;
1250  std::unordered_map<Element const*,
1252  Element::Hash,
1253  Element::Equal>
1254  _map;
1255  size_t _max_threads;
1256  std::mutex _mtx;
1257  index_t _nr;
1258  letter_t _nrgens;
1259  size_t _nrrules;
1260  enumerate_index_t _pos;
1261  element_index_t _pos_one;
1262  std::vector<element_index_t> _prefix;
1263  flags_t _reduced;
1264  letter_t _relation_gen;
1265  enumerate_index_t _relation_pos;
1266  cayley_graph_t _right;
1267  std::vector<std::pair<Element const*, element_index_t>> _sorted;
1268  std::vector<element_index_t> _suffix;
1269  Element* _tmp_product;
1270  size_t _wordlen;
1271 
1272  static std::vector<element_index_t> _tmp_inverter;
1273  static std::vector<bool> _old_new;
1274 #ifdef LIBSEMIGROUPS_STATS
1275  size_t _nr_products;
1276 #endif
1277  };
1278 
1282 
1283  template <typename T, typename C>
1284  C const Semigroup::iterator_base<T, C>::_methods;
1285 } // namespace libsemigroups
1286 
1287 #endif // LIBSEMIGROUPS_SRC_SEMIGROUPS_H_
Semigroup::cayley_graph_t cayley_graph_t
This is just for backwards compatibility and should disappear at some point.
Definition: semigroups.h:1281
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,...
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
Semigroup(std::initializer_list< Element * > gens)
Construct from generators.
Definition: semigroups.h:171
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
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
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
void add_generators(std::vector< Element * > const &coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:765
Semigroup * copy_add_generators(std::vector< Element * > const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.h:793
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:1155
Semigroup(std::vector< Element * > const *gens)
Construct from generators.
Definition: semigroups.h:135
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,...
Definition: semigroups.cc:419
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
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:687
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:1144
const_iterator begin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1068
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:1079
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:1101
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
const_iterator_idempotents cbegin_idempotents()
Returns a const iterator pointing at the first idempotent in the semigroup.
Definition: semigroups.h:1169
Element const * operator[](element_index_t pos) const
Returns the element of the semigroup in position pos.
Definition: semigroups.h:542
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:1133
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
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:667
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:1179
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:1112
size_t degree() const
Returns the degree of any (and all) Element'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 & operator=(Semigroup const &semigroup)=delete
Deleted.
void add_generators(std::vector< Element * > const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:752
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:1090
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
Semigroup(std::vector< Element const * > const *gens)
Construct from generators.
Definition: semigroups.cc:38
Semigroup(std::vector< Element * > const &gens)
Construct from generators.
Definition: semigroups.h:163
Semigroup * copy_add_generators(std::vector< Element const * > const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.cc:702
Semigroup(std::vector< Element const * > *gens)
Construct from generators.
Definition: semigroups.h:151
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
void add_generators(std::initializer_list< Element * > coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:773
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
void add_generators(std::vector< Element const * > const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.cc:718
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,...
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
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
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:1122
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:1057
Element const * gens(letter_t pos) const
Return a pointer to the generator with index pos.
Definition: semigroups.h:256
Semigroup(std::vector< Element * > *gens)
Construct from generators.
Definition: semigroups.h:143
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