libsemigroups
cong.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_CONG_H_
20 #define LIBSEMIGROUPS_SRC_CONG_H_
21 
22 #include <algorithm>
23 #include <atomic>
24 #include <mutex>
25 #include <stack>
26 #include <string>
27 #include <utility>
28 #include <vector>
29 
30 #include "partition.h"
31 #include "report.h"
32 #include "semigroups.h"
33 
34 #define RETURN_FALSE nullptr
35 
36 namespace libsemigroups {
37 
54  class Congruence {
55  private:
56  // The different types of congruence.
57  enum cong_t {
58  // Left congruence
59  LEFT = 0,
60  // Right congruence
61  RIGHT = 1,
62  // 2-sided congruence
63  TWOSIDED = 2
64  };
65 
68  static const size_t LIMIT_MAX = std::numeric_limits<size_t>::max();
69 
70  public:
72  typedef size_t class_index_t;
73 
104  Congruence(std::string type,
105  size_t nrgens,
106  std::vector<relation_t> const& relations,
107  std::vector<relation_t> const& extra);
108 
129  Congruence(std::string type,
130  Semigroup* semigroup,
131  std::vector<relation_t> const& genpairs);
132 
138  delete_data();
139  }
140 
157  DATA* data = get_data();
158  LIBSEMIGROUPS_ASSERT(data->is_done());
159  return data->word_to_class_index(word);
160  }
161 
171  bool test_equals(word_t const& w1, word_t const& w2) {
172  if (w1 == w2) {
173  return true;
174  }
175  DATA* data;
176  if (is_done()) {
177  data = _data;
178  } else {
179  std::function<bool(DATA*)> words_func = [&w1, &w2](DATA* d) {
180  return d->current_equals(w1, w2) != DATA::result_t::UNKNOWN;
181  };
182  data = get_data(words_func);
183  }
184  DATA::result_t result = data->current_equals(w1, w2);
185  LIBSEMIGROUPS_ASSERT(result != DATA::result_t::UNKNOWN);
186  return result == DATA::result_t::TRUE;
187  }
188 
206  bool test_less_than(word_t const& w1, word_t const& w2) {
207  DATA* data;
208  if (is_done()) {
209  data = _data;
210  } else {
211  std::function<bool(DATA*)> words_func = [&w1, &w2](DATA* d) {
212  return d->current_less_than(w1, w2) != DATA::result_t::UNKNOWN;
213  };
214  data = get_data(words_func);
215  }
216 
217  if (!_partial_data.empty()) {
218  LIBSEMIGROUPS_ASSERT(_data == nullptr);
219  // Delete the losers and clear _partial_data
220  for (size_t i = 0; i < _partial_data.size(); i++) {
221  if (_partial_data[i] != data) {
222  delete _partial_data[i];
223  }
224  }
225  _partial_data.clear();
226  }
227  _data = data;
228 
229  DATA::result_t result = data->current_less_than(w1, w2);
230  LIBSEMIGROUPS_ASSERT(result != DATA::result_t::UNKNOWN);
231  return result == DATA::result_t::TRUE;
232  }
233 
242  size_t nr_classes() {
243  DATA* data = get_data();
244  LIBSEMIGROUPS_ASSERT(data->is_done());
245  return data->nr_classes();
246  }
247 
257 
259  bool is_done() const {
260  if (_data == nullptr) {
261  return false;
262  }
263  return _data->is_done();
264  }
265 
271  std::vector<relation_t> const& relations() {
272  init_relations(_semigroup);
273  return _relations;
274  }
275 
278  std::vector<relation_t> const& extra() const {
279  return _extra;
280  }
281 
288 
289  // FIXME it would be better to provide a constructor from another
290  // congruence that copied the relations.
291  void set_relations(std::vector<relation_t> const& relations) {
292  LIBSEMIGROUPS_ASSERT(_relations.empty()); // _extra can be non-empty!
293  _relations = relations;
294  }
295 
297  //
300  void set_report(bool val) const {
301  glob_reporter.set_report(val);
302  LIBSEMIGROUPS_ASSERT(glob_reporter.get_report() == val);
303  }
304 
321  void set_prefill(RecVec<class_index_t> const& table) {
322  if (_data == nullptr) {
323  _prefill = table;
324  }
325  }
326 
336  void set_max_threads(size_t nr_threads) {
337  unsigned int n
338  = static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads);
339  _max_threads = std::min(n, std::thread::hardware_concurrency());
340  }
341 
346  void set_pack(size_t val) {
347  if (_data != nullptr) {
348  _data->set_pack(val);
349  }
350  }
351 
355  void set_report_interval(size_t val) {
356  if (_data != nullptr) {
357  _data->set_report_interval(val);
358  }
359  }
360 
375  void force_tc();
376 
400  void force_tc_prefill();
401 
419  void force_p();
420 
451  void force_kbp();
452 
475  void force_kbfp();
476 
483  bool is_obviously_infinite();
484 
485  private:
486  // Subclasses of DATA
487  class KBFP; // Knuth-Bendix followed by Froidure-Pin
488  class KBP; // Knuth-Bendix followed by P
489  class P; // Orbit of pairs
490  class TC; // Todd-Coxeter
491 
492  // Abstract base class for nested classes containing methods for actually
493  // enumerating the classes etc of a congruence
494  class DATA {
495  friend KBFP;
496  friend KBP;
497  friend P;
498  friend TC;
499 
500  public:
501  // Default constructor
502  DATA(Congruence& cong,
503  size_t default_nr_steps,
504  size_t report_interval = 1000)
505  : _cong(cong),
506  _default_nr_steps(default_nr_steps),
507  _killed(false),
508  _report_interval(report_interval),
509  _report_next(0) {}
510 
511  // Default destructor, does nothing
512  virtual ~DATA() {}
513 
514  // This method runs the algorithm used to determine the congruence, i.e.
515  // Todd-Coxeter, Knuth-Bendix, etc., until completion.
516  virtual void run() = 0;
517 
518  // This method runs the algorithm for a while, then stops after a
519  // certain amount of work or when done \p steps the amount of work to do
520  // before returning.
521  virtual void run(size_t steps) = 0;
522 
523  // This method returns true if a DATA object's run method has been run to
524  // conclusion, i.e. that it has not been killed by another instance.
525  virtual bool is_done() const = 0;
526 
527  // This method returns the number of classes of the congruence.
528  virtual size_t nr_classes() = 0;
529 
530  // This method returns the index of the congruence class containing the
531  // element of the semigroup defined by word.
532  virtual class_index_t word_to_class_index(word_t const& word) = 0;
533 
534  // Possible result of questions that might not be answerable.
535  enum result_t { TRUE = 0, FALSE = 1, UNKNOWN = 2 };
536 
537  // This method returns \c true if the two words are known to describe
538  // elements in the same congruence class, \c false if they are known to
539  // lie in different classes, and **UNKNOWN** if the information has not
540  // yet been discovered.
541  virtual result_t current_equals(word_t const& w1, word_t const& w2) = 0;
542 
543  // This method returns \c true if the two words are known to be in
544  // distinct classes, where w1's class is less than w2's class by some
545  // total ordering; \c false if this is known to be untrue; and
546  // **UNKNOWN** if the information has not yet been discovered.
547  // \p w1 const reference to the first word
548  // \p w2 const reference to the second word
549  virtual result_t current_less_than(word_t const& w1, word_t const& w2) {
550  if (is_done()) {
552  ? result_t::TRUE
553  : result_t::FALSE;
554  } else if (current_equals(w1, w2) == result_t::TRUE) {
555  return result_t::FALSE; // elements are equal
556  }
557  return result_t::UNKNOWN;
558  }
559 
560  // This method returns the non-trivial classes of the congruence.
561  virtual Partition<word_t>* nontrivial_classes();
562 
563  // This method kills a given instance of a DATA object.
564  void kill() {
565  // TODO add killed-by-thread
566  _killed = true;
567  }
568 
569  // This method sets a given instance of a DATA object to "not killed"
570  void unkill() {
571  _killed = false;
572  }
573 
574  // This method can be used to tell whether or not a given DATA object has
575  // been killed by another instance.
576  std::atomic<bool>& is_killed() {
577  return _killed;
578  }
579 
580  // \p goal_func a function to test whether we can stop running
581  //
582  // This function calls DATA::run in batches until goal_func returns
583  // true. If goal_func is RETURN_FALSE, then the object ! is instead run
584  // to completion.
585  void run_until(std::function<bool(DATA*)> goal_func) {
586  if (is_done()) {
587  return;
588  }
589  if (goal_func != RETURN_FALSE) {
590  while (!_killed && !is_done() && !goal_func(this)) {
591  run(_default_nr_steps);
592  }
593  } else {
594  run();
595  }
596  }
597 
598  virtual void set_pack(size_t val) {
599  (void) val;
600  }
601 
602  void set_report_interval(size_t val) {
603  _report_interval = val;
604  }
605 
606  private:
607  Congruence& _cong;
608  size_t _default_nr_steps;
609  std::atomic<bool> _killed;
610  size_t _report_interval;
611  size_t _report_next;
612  typedef std::vector<word_t*> class_t;
613  typedef std::vector<class_t*> partition_t;
614  };
615 
616  // This deletes all DATA objects stored in this congruence, including
617  // finished objects and partially-enumerated objects.
618  void delete_data();
619 
620  // Set the relations of a Congruence object to the relations of the
621  // semigroup over which the Congruence is defined (if any). Report is here
622  // in case of any enumeration of the underlying semigroup.
623  void init_relations(Semigroup* semigroup, std::atomic<bool>& killed);
624 
625  void init_relations(Semigroup* semigroup) {
626  std::atomic<bool> killed(false);
627  init_relations(semigroup, killed);
628  }
629 
630  DATA* cget_data() const {
631  return _data;
632  }
633 
634  DATA* get_data(std::function<bool(DATA*)> goal_func = RETURN_FALSE);
635 
636  DATA* winning_data(std::vector<DATA*>& data,
637  std::vector<std::function<void(DATA*)>>& funcs,
638  bool ignore_max_threads = false,
639  std::function<bool(DATA*)> goal_func = RETURN_FALSE);
640 
641  Congruence(cong_t type,
642  size_t nrgens,
643  std::vector<relation_t> const& relations,
644  std::vector<relation_t> const& extra);
645 
646  Congruence(cong_t type,
647  Semigroup* semigroup,
648  std::vector<relation_t> const& extra);
649 
650  cong_t type_from_string(std::string);
651 
652  DATA* _data;
653  std::vector<relation_t> _extra;
654  std::mutex _init_mtx;
655  std::mutex _kill_mtx;
656  size_t _max_threads;
657  size_t _nrgens;
658  std::vector<DATA*> _partial_data;
659  RecVec<class_index_t> _prefill;
660  std::vector<relation_t> _relations;
661  std::atomic<bool> _relations_done;
662  Semigroup* _semigroup;
663  cong_t _type;
664 
665  static size_t const INFTY;
666  static size_t const UNDEFINED;
667  };
668 } // namespace libsemigroups
669 #endif // LIBSEMIGROUPS_SRC_CONG_H_
void set_report_interval(size_t val)
Sets how often the core methods of Congruence report.
Definition: cong.h:355
void force_kbp()
Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relatio...
Definition: cong.cc:311
Partition< word_t > * nontrivial_classes()
Returns the non-trivial classes of the congruence.
Definition: cong.cc:323
~Congruence()
A default destructor.
Definition: cong.h:137
bool is_obviously_infinite()
This method tries to quickly determine whether or not the Congruence has infinitely many classes...
Definition: cong.cc:248
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
bool test_equals(word_t const &w1, word_t const &w2)
Returns true if the words w1 and w2 belong to the same congruence class.
Definition: cong.h:171
Class for partitions of a set used by Congruence::nontrivial_classes.
Definition: partition.h:33
bool test_less_than(word_t const &w1, word_t const &w2)
Returns true if the congruence class of w1 is less than that of w2.
Definition: cong.h:206
class_index_t word_to_class_index(word_t const &word)
Returns the index of the congruence class corresponding to word.
Definition: cong.h:156
std::vector< relation_t > const & relations()
Returns the vector of relations used to define the semigroup over which the congruence is defined...
Definition: cong.h:271
void set_prefill(RecVec< class_index_t > const &table)
Specify a partial coset table for the Todd-Coxeter algorithm.
Definition: cong.h:321
void force_tc()
Use the Todd-Coxeter algorithm.
Definition: cong.cc:293
std::vector< relation_t > const & extra() const
Returns the vector of extra relations (or equivalently, generating pairs) used to define the congruen...
Definition: cong.h:278
void force_kbfp()
Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relatio...
Definition: cong.cc:317
Class for congruence on a semigroup or fintely presented semigroup.
Definition: cong.h:54
void set_pack(size_t val)
Set the maximum number of active cosets in Todd-Coxeter before entering packing phase.
Definition: cong.h:346
size_t nr_classes()
Returns the number of congruences classes of this.
Definition: cong.h:242
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
void set_max_threads(size_t nr_threads)
Set the maximum number of threads for a Congruence over a Semigroup.
Definition: cong.h:336
void force_tc_prefill()
Use the Todd-Coxeter algorithm after prefilling the table.
Definition: cong.cc:299
void set_report(bool val) const
Turn reporting on or off.
Definition: cong.h:300
Congruence(std::string type, size_t nrgens, std::vector< relation_t > const &relations, std::vector< relation_t > const &extra)
Constructor for congruences over a finitely presented semigroup.
Definition: cong.cc:64
Class for semigroups generated by instances of Element.
Definition: semigroups.h:68
void set_relations(std::vector< relation_t > const &relations)
Define the relations defining the semigroup over which this is defined.
Definition: cong.h:291
void force_p()
Use an elementary orbit algorithm which enumerates pairs of Element objects that are related in this...
Definition: cong.cc:305
bool is_done() const
Returns true if the structure of the congruence is known.
Definition: cong.h:259
size_t class_index_t
Type for indices of congruence classes in a Congruence object.
Definition: cong.h:72