19 #ifndef LIBSEMIGROUPS_SRC_CONG_H_ 20 #define LIBSEMIGROUPS_SRC_CONG_H_ 30 #include "partition.h" 32 #include "semigroups.h" 34 #define RETURN_FALSE nullptr 68 static const size_t LIMIT_MAX = std::numeric_limits<size_t>::max();
106 std::vector<relation_t>
const&
relations,
107 std::vector<relation_t>
const&
extra);
131 std::vector<relation_t>
const& genpairs);
157 DATA* data = get_data();
158 LIBSEMIGROUPS_ASSERT(data->is_done());
159 return data->word_to_class_index(word);
179 std::function<bool(DATA*)> words_func = [&w1, &w2](DATA* d) {
180 return d->current_equals(w1, w2) != DATA::result_t::UNKNOWN;
182 data = get_data(words_func);
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;
211 std::function<bool(DATA*)> words_func = [&w1, &w2](DATA* d) {
212 return d->current_less_than(w1, w2) != DATA::result_t::UNKNOWN;
214 data = get_data(words_func);
217 if (!_partial_data.empty()) {
218 LIBSEMIGROUPS_ASSERT(_data ==
nullptr);
220 for (
size_t i = 0; i < _partial_data.size(); i++) {
221 if (_partial_data[i] != data) {
222 delete _partial_data[i];
225 _partial_data.clear();
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;
243 DATA* data = get_data();
244 LIBSEMIGROUPS_ASSERT(data->is_done());
245 return data->nr_classes();
260 if (_data ==
nullptr) {
263 return _data->is_done();
272 init_relations(_semigroup);
278 std::vector<relation_t>
const&
extra()
const {
292 LIBSEMIGROUPS_ASSERT(_relations.empty());
301 glob_reporter.set_report(val);
302 LIBSEMIGROUPS_ASSERT(glob_reporter.get_report() == val);
322 if (_data ==
nullptr) {
338 =
static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads);
339 _max_threads = std::min(n, std::thread::hardware_concurrency());
347 if (_data !=
nullptr) {
348 _data->set_pack(val);
356 if (_data !=
nullptr) {
357 _data->set_report_interval(val);
503 size_t default_nr_steps,
504 size_t report_interval = 1000)
506 _default_nr_steps(default_nr_steps),
508 _report_interval(report_interval),
516 virtual void run() = 0;
521 virtual void run(
size_t steps) = 0;
525 virtual bool is_done()
const = 0;
535 enum result_t { TRUE = 0, FALSE = 1, UNKNOWN = 2 };
541 virtual result_t current_equals(
word_t const& w1,
word_t const& w2) = 0;
549 virtual result_t current_less_than(
word_t const& w1,
word_t const& w2) {
554 }
else if (current_equals(w1, w2) == result_t::TRUE) {
555 return result_t::FALSE;
557 return result_t::UNKNOWN;
576 std::atomic<bool>& is_killed() {
585 void run_until(std::function<
bool(DATA*)> goal_func) {
589 if (goal_func != RETURN_FALSE) {
590 while (!_killed && !
is_done() && !goal_func(
this)) {
591 run(_default_nr_steps);
603 _report_interval = val;
608 size_t _default_nr_steps;
609 std::atomic<bool> _killed;
610 size_t _report_interval;
612 typedef std::vector<word_t*> class_t;
613 typedef std::vector<class_t*> partition_t;
623 void init_relations(Semigroup* semigroup, std::atomic<bool>& killed);
625 void init_relations(Semigroup* semigroup) {
626 std::atomic<bool> killed(
false);
627 init_relations(semigroup, killed);
630 DATA* cget_data()
const {
634 DATA* get_data(std::function<
bool(DATA*)> goal_func = RETURN_FALSE);
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);
643 std::vector<relation_t>
const&
relations,
644 std::vector<relation_t>
const&
extra);
647 Semigroup* semigroup,
648 std::vector<relation_t>
const&
extra);
650 cong_t type_from_string(std::string);
653 std::vector<relation_t> _extra;
654 std::mutex _init_mtx;
655 std::mutex _kill_mtx;
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;
665 static size_t const INFTY;
666 static size_t const UNDEFINED;
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