| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/src/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.5.2025 mit Größe 125 kB |
|
Quelle todd-coxeter.cpp Sprache: C |
|||||||||
|
//
// libsemigroups - C++ library for semigroups and monoids // Copyright (C) 2019-21 James D. Mitchell // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // This file contains an implementation of the Todd-Coxeter algorithm for // semigroups. //////////////////////////////////////////////////////////////////////////////// // TODO(later) // // * Make process_deductions_dfs non-recursive, this will likely only be an // issue for presentations with extremely long relations. // // * Wreath product standardize mem fn. // //////////////////////////////////////////////////////////////////////////////// // // Notes // // 1. It's suggested in Sims' book in the implementation appendix that using // the actual index of the coset referenced rather than the "row", to // avoid multiplication in get. I implemented this in 2021 and it made no // difference whatsoever, so I backed the changes. // // 2. In 2021, I couldn't figure out a low-cost way of implementing the "fill" // factor. The idea is that we should check that a certain percentage of the // entries in the table are filled before we use preferred definitions. // This doesn't seem to be necessary in any of the examples or tests, i.e. // the resulting enumerations are valid and terminate if we just always use // the preferred definitions and don't try to keep a particular percentage // of the entries in the table filled. It's possible that not using the // preferred definitions when the table is not filled enough, would make the // enumeration terminate faster, but it didn't seem worth the extra cost or // complexity of implementing the fill factor. // // 3. In 2021, I tried in felsch_lookahead to default to hlt_lookahead if there // are more paths (nodes) in the Felsch tree than the number of active // cosets times the number of relations, but found no examples where this // was invoked. So, I scrapped this too. // // 4. In 2021, I tried putting the options save() + standardize() outside the // main loop (+ duplicating a lot of the code) in ToddCoxeter::hlt and this // produced no measurable difference to the performance, so I backed these // changes out too. #include "libsemigroups/todd-coxeter.hpp" #include <algorithm> // for reverse #include <array> // for array #include <chrono> // for nanoseconds etc #include <cstddef> // for size_t #include <iterator> // for distance #include <limits> // for numeric_limits #include <memory> // for shared_ptr #include <numeric> // for iota, accumulate #include <ostream> // for operator<< #include <queue> // for queue #include <random> // for mt19937 #include <string> // for operator+, basic_string #include <tuple> // for tie #include <unordered_map> // for unordered_map #include <unordered_set> // for unordered_set #include <utility> // for pair #ifdef LIBSEMIGROUPS_DEBUG #include <set> // for set #endif #include "libsemigroups/config.hpp" // for LIBSEMIGROUPS_DEBUG #include "libsemigroups/adapters.hpp" // for Hash #include "libsemigroups/cong-intf.hpp" // for CongruenceInterface #include "libsemigroups/coset.hpp" // for CosetManager #include "libsemigroups/debug.hpp" // for LIBSEMIGROUPS_ASSERT #include "libsemigroups/digraph-helper.hpp" // for follow_path_nc, last_... #include "libsemigroups/exception.hpp" // for LIBSEMIGROUPS_EXCEPTION #include "libsemigroups/felsch-tree.hpp" // for FelschTree #include "libsemigroups/froidure-pin-base.hpp" // for FroidurePinBase #include "libsemigroups/froidure-pin.hpp" // for FroidurePin #include "libsemigroups/knuth-bendix.hpp" // for fpsemigroup::KnuthBendix #include "libsemigroups/obvinf.hpp" // for IsObviouslyInfinite #include "libsemigroups/report.hpp" // for PrintTable, Reporter #include "libsemigroups/string.hpp" // for to_string #include "libsemigroups/tce.hpp" // for TCE #include "libsemigroups/timer.hpp" // for detail::Timer #include "libsemigroups/types.hpp" // for letter_type #include "libsemigroups/uf.hpp" // for Duf #include "libsemigroups/ukkonen.hpp" // for Ukkonen // This file is organised as follows: // // 1. Helper functions, types etc in anonymous namespace // 2. ToddCoxeter - inner classes - private // 3. ToddCoxeter - constructors and destructor - public // 4. CongruenceInterface - non-pure virtual member functions - public // 5. CongruenceInterface - non-pure virtual member functions - private // 6. CongruenceInterface - pure virtual member functions - private // 7. ToddCoxeter - member functions (init + settings) - public // 8. ToddCoxeter - member functions (sorting gen. pairs etc) - public // 9. ToddCoxeter - member functions (container-like) - public // 10. ToddCoxeter - member functions (state) - public // 11. ToddCoxeter - member functions (standardization) - public // 12. ToddCoxeter - member functions (attributes) - public // 13. ToddCoxeter - member functions (reporting + stats) - public // 14. ToddCoxeter - member functions (reporting + stats) - private // 15. ToddCoxeter - member functions (validation) - private // 16. ToddCoxeter - member functions (initialisation + settings) - private // 17. ToddCoxeter - member functions (cosets) - private // 18. ToddCoxeter - member functions (main strategies) - private // 19. ToddCoxeter - member functions (deduction processing) - private // 20. ToddCoxeter - member functions (lookahead) - private // 21. ToddCoxeter - member functions (standardize) - private // 22. ToddCoxeter - member functions (debug) - private //////////////////////////////////////////////////////////////////////// // 1. Helper functions, types etc in anonymous namespace //////////////////////////////////////////////////////////////////////// using coset_type = libsemigroups::detail::CosetManager::coset_type; namespace { using class_index_type = libsemigroups::CongruenceInterface::class_index_type; using word_type = libsemigroups::word_type; using Perm = typename libsemigroups::detail::CosetManager::Perm; template <typename T> using EqualTo = typename libsemigroups::EqualTo<T>; template <typename T> using Hash = typename libsemigroups::Hash<T>; void reverse_if_necessary_and_push_back( libsemigroups::congruence::ToddCoxeter const* tc, word_type w, std::vector<word_type>& v) { if (tc->kind() == libsemigroups::congruence_kind::left) { std::reverse(w.begin(), w.end()); } v.push_back(std::move(w)); } void sort_generating_pairs(Perm& perm, std::vector<word_type>& vec) { // Apply the permutation (adapted from stl.hpp:apply_permutation) size_t const n = perm.size(); for (size_t i = 0; i < n; ++i) { size_t current = i; while (i != perm[current]) { size_t next = perm[current]; std::swap(vec[2 * current], vec[2 * next]); std::swap(vec[2 * current + 1], vec[2 * next + 1]); perm[current] = current; current = next; } perm[current] = current; } } void sort_generating_pairs( std::function<bool(word_type const&, word_type const&)> func, Perm& perm, std::vector<word_type>& vec) { // Sort each relation so that the lhs is greater than the rhs according // to func. for (auto it = vec.begin(); it < vec.end(); it += 2) { if (func(*it, *(it + 1))) { std::swap(*it, *(it + 1)); } } // Create a permutation of the even indexed entries in vec perm.resize(vec.size() / 2); std::iota(perm.begin(), perm.end(), 0); std::sort(perm.begin(), perm.end(), [&func, &vec](class_index_type x, class_index_type y) -> bool { return func(vec[2 * x], vec[2 * y]); }); sort_generating_pairs(perm, vec); } // Attempts to reduce the length of the words in "words" by finding the // equivalence relation on the union of "wrt" and "words" generated by the // pairs in "wrt". If A = {u_1, u_2, ..., u_n} are the distinct words in an // equivalence class on "words" and u_1 is the short-lex minimum word in the // class, then the words in "words" involving the words in A are replaced by: // u_1 = u_2, u_1 = u_3, ..., u_1 = u_n. class PairsSimplifier { public: PairsSimplifier() = default; PairsSimplifier& add(std::vector<word_type> const& words) { LIBSEMIGROUPS_ASSERT(words.size() % 2 == 0); _duf.resize(_duf.size() + words.size()); // Create equivalence relation of the equal relations for (size_t i = 0; i < words.size(); ++i) { if (i % 2 == 0) { _duf.unite(i, i + 1); } auto const& current_word = words[i]; decltype(_map)::iterator it; bool inserted; std::tie(it, inserted) = _map.emplace(current_word, i); if (!inserted) { _duf.unite(it->second, i); } } return *this; } bool trivial() const { return (_duf.number_of_blocks() == _map.size()); } void apply(std::vector<word_type>& words) { using libsemigroups::shortlex_compare; LIBSEMIGROUPS_ASSERT(words.size() % 2 == 0); // Class index -> index of min. length words in wrt + words std::unordered_map<size_t, word_type> mins; if (words.empty()) { return; } // Find index of minimum length word in every class for (auto const& word : words) { auto i = _map.find(word)->second; auto j = _duf.find(i); decltype(mins)::iterator it; bool inserted; std::tie(it, inserted) = mins.emplace(j, word); auto const& min_word = it->second; if (!inserted && shortlex_compare(word, min_word)) { it->second = word; } } std::vector<word_type> result; for (auto it = _map.cbegin(); it != _map.cend(); ++it) { auto const& word = it->first; auto const& index = it->second; auto const& min_word = mins.find(_duf.find(index))->second; if (min_word != word) { result.push_back(min_word); result.push_back(word); } } std::swap(words, result); } private: libsemigroups::detail::Duf<> _duf; std::unordered_map<word_type, size_t, Hash<word_type>, EqualTo<word_type>> _map; }; struct Noop { template <typename... Args> void operator()(Args...) const noexcept {} template <typename T> void operator()(libsemigroups::congruence::ToddCoxeter*) const noexcept {} }; using DoNotProcessCoincidences = Noop; using NoPreferredDefs = Noop; using DoNotStackDeductions = Noop; } // namespace namespace libsemigroups { using detail::FelschTree; namespace congruence { //////////////////////////////////////////////////////////////////////// // 2. ToddCoxeter - inner classes - private //////////////////////////////////////////////////////////////////////// // A class for managing Deductions (recently changed or defined values of // the form std::pair(coset_type, letter_type). class ToddCoxeter::Deductions { public: explicit Deductions(ToddCoxeter* tc) : _any_skipped(false), _deduct(), _tc(tc) {} Deduction pop() { auto res = _deduct.top(); _deduct.pop(); return res; } void emplace(coset_type c, letter_type x) { using opt = options::deductions; if (_deduct.size() < _tc->max_deductions()) { _deduct.emplace(c, x); #ifdef LIBSEMIGROUPS_ENABLE_STATS _tc->_stats.max_deduct = std::max( _tc->_stats.max_deduct, static_cast<uint64_t>(_deduct.size())); #endif } else { _any_skipped = true; if (_tc->deduction_policy() & opt::purge_from_top) { while (!_deduct.empty() && !_tc->is_active_coset(_deduct.top().first)) { _deduct.pop(); } } else if (_tc->deduction_policy() & opt::purge_all) { std::stack<Deduction> copy; while (!_deduct.empty()) { auto d = pop(); if (_tc->is_active_coset(d.first)) { copy.push(d); } } std::swap(copy, _deduct); } else if (_tc->deduction_policy() & opt::discard_all_if_no_space) { clear(); } } } bool any_skipped() const noexcept { return _any_skipped; } // noexcept correct? bool empty() const noexcept { return _deduct.empty(); } size_t size() const noexcept { return _deduct.size(); } void clear() { if (!_deduct.empty()) { _any_skipped = true; std::stack<Deduction> copy; std::swap(copy, _deduct); } } private: bool _any_skipped; std::stack<Deduction> _deduct; ToddCoxeter* _tc; }; struct ToddCoxeter::Settings { bool use_relations_in_extra = false; size_t deduct_max = 2'000; options::deductions deduct_policy = options::deductions::no_stack_if_no_space | options::deductions::v2; size_t f_defs = 100'000; options::froidure_pin froidure_pin = options::froidure_pin::none; size_t hlt_defs = 200'000; size_t large_collapse = 100'000; options::lookahead lookahead = options::lookahead::partial | options::lookahead::hlt; float lookahead_growth_factor = 2.0; size_t lookahead_growth_threshold = 4; size_t lower_bound = UNDEFINED; size_t max_preferred_defs = 256; size_t min_lookahead = 10'000; size_t next_lookahead = 5'000'000; options::preferred_defs preferred_defs = options::preferred_defs::deferred; std::chrono::nanoseconds random_interval = std::chrono::milliseconds(200); bool restandardize = false; bool save = false; bool standardize = false; options::strategy strategy = options::strategy::hlt; }; class ToddCoxeter::PreferredDefs { public: explicit PreferredDefs(ToddCoxeter* tc) : _defs(), _tc(tc) {} bool empty() const noexcept { return _defs.empty(); } Deduction pop() { Deduction d = _defs.front(); _defs.pop(); return d; } void emplace(coset_type c, letter_type x) { #ifdef LIBSEMIGROUPS_ENABLE_STATS _tc->_stats.total_preferred_defs++; #endif _defs.emplace(c, x); if (_defs.size() > _tc->max_preferred_defs()) { _defs.pop(); } #ifdef LIBSEMIGROUPS_ENABLE_STATS _tc->_stats.max_preferred_defs = std::max(_tc->_stats.max_preferred_defs, uint64_t(_defs.size())); #endif } void purge_from_top() { while (!_defs.empty() && (!_tc->is_active_coset(_defs.front().first) || _tc->_word_graph.unsafe_neighbor(_defs.front().first, _defs.front().second) != UNDEFINED)) { _defs.pop(); } } private: std::queue<Deduction> _defs; ToddCoxeter* _tc; }; struct ToddCoxeter::TreeNode { TreeNode() : parent(UNDEFINED), gen(UNDEFINED) {} TreeNode(coset_type p, letter_type g) : parent(p), gen(g) {} coset_type parent; letter_type gen; }; struct ToddCoxeter::QueuePreferredDefs { void operator()(ToddCoxeter* tc, coset_type x, letter_type a, coset_type y, letter_type b) { tc->_preferred_defs->emplace(x, a); tc->_preferred_defs->emplace(y, b); } }; struct ToddCoxeter::StackDeductions { inline void operator()(ToddCoxeter::Deductions* stck, coset_type c, letter_type a) const noexcept { stck->emplace(c, a); } }; template <typename TStackDeduct> struct ToddCoxeter::ImmediateDef { void operator()(ToddCoxeter* tc, coset_type x, letter_type a, coset_type y, letter_type b) const { coset_type d = tc->new_coset(); tc->def_edge<TStackDeduct>(x, a, d); #ifdef LIBSEMIGROUPS_ENABLE_STATS tc->_stats.tc2_good_appl++; if (tc->strategy() == options::strategy::hlt) { tc->_stats.tc1_hlt_appl++; } else { tc->_stats.tc1_f_appl++; } #endif if (a != b || x != y) { tc->def_edge<TStackDeduct>(y, b, d); #ifdef LIBSEMIGROUPS_ENABLE_STATS tc->_stats.tc2_good_appl++; #endif } } }; //////////////////////////////////////////////////////////////////////// // 3. ToddCoxeter - constructors and destructor - public //////////////////////////////////////////////////////////////////////// ToddCoxeter::ToddCoxeter(congruence_kind type) : CongruenceInterface(type), CosetManager(), _coinc(), _deduct(new Deductions(this)), _extra(), _felsch_tree(nullptr), _nr_pairs_added_earlier(0), _prefilled(false), _preferred_defs(new PreferredDefs(this)), _relations(), _settings(new Settings()), _standard_max(0), _standardized(order::none), _state(state::constructed), _tree(nullptr), _word_graph() {} ToddCoxeter::ToddCoxeter(ToddCoxeter const& copy) : CongruenceInterface(copy), CosetManager(copy), _coinc(copy._coinc), _deduct(std::make_unique<Deductions>(*copy._deduct)), _extra(copy._extra), _felsch_tree(nullptr), _nr_pairs_added_earlier(copy._nr_pairs_added_earlier), _prefilled(copy._prefilled), _preferred_defs( std::make_unique<PreferredDefs>(*copy._preferred_defs)), _relations(copy._relations), _settings(std::make_unique<Settings>(*copy._settings)), _standard_max(copy._standard_max), _standardized(copy._standardized), _state(copy._state), _tree(nullptr), _word_graph(copy._word_graph) { if (copy._felsch_tree != nullptr) { _felsch_tree = std::make_unique<FelschTree>(*copy._felsch_tree); } if (copy._tree != nullptr) { _tree = std::make_unique<Tree>(*copy._tree); } } ToddCoxeter::ToddCoxeter(congruence_kind type, std::shared_ptr<FroidurePinBase> S, options::froidure_pin p) : ToddCoxeter(type) { froidure_pin_policy(p); set_parent_froidure_pin(S); set_number_of_generators(S->number_of_generators()); } // Construct a ToddCoxeter object representing a congruence over the // semigroup defined by copy (the quotient that is). ToddCoxeter::ToddCoxeter(congruence_kind typ, ToddCoxeter& copy) : ToddCoxeter(typ) { if (copy.kind() != congruence_kind::twosided && typ != copy.kind()) { LIBSEMIGROUPS_EXCEPTION("incompatible types of congruence, found (" + congruence_kind_to_string(copy.kind()) + " / " + congruence_kind_to_string(typ) + ") but only (left / left), (right / " "right), (two-sided / *) are valid"); } copy_relations_for_quotient(copy); } ToddCoxeter::ToddCoxeter(congruence_kind typ, fpsemigroup::ToddCoxeter& copy) : ToddCoxeter(typ) { set_parent_froidure_pin(copy); if (copy.finished()) { set_number_of_generators(copy.froidure_pin()->number_of_generators()); froidure_pin_policy(options::froidure_pin::use_cayley_graph); } else { copy_relations_for_quotient(copy.congruence()); froidure_pin_policy(options::froidure_pin::use_relations); } } ToddCoxeter::ToddCoxeter(congruence_kind typ, fpsemigroup::KnuthBendix& kb) : ToddCoxeter(typ) { set_number_of_generators(kb.alphabet().size()); // TODO(later) use active rules when available for (auto it = kb.cbegin_rules(); it < kb.cend_rules(); ++it) { add_pair(kb.string_to_word(it->first), kb.string_to_word(it->second)); } // Note that something goes horribly wrong if the next line is above the // for loop above. set_parent_froidure_pin(kb); if (kb.finished() && kb.is_obviously_finite()) { LIBSEMIGROUPS_ASSERT(froidure_pin_policy() == options::froidure_pin::none); froidure_pin_policy(options::froidure_pin::use_cayley_graph); } } ToddCoxeter::~ToddCoxeter() { while (!_setting_stack.empty()) { pop_settings(); } } //////////////////////////////////////////////////////////////////////// // 4. CongruenceInterface - non-pure virtual member functions - public //////////////////////////////////////////////////////////////////////// bool ToddCoxeter::contains(word_type const& lhs, word_type const& rhs) { validate_word(lhs); validate_word(rhs); init_generating_pairs(); if (empty()) { // Note that it's possible to be not _prefilled, and have _relations, // and _extra empty, because shrink_to_fit clears _relations and // _extra. That's why we use empty() here instead of checking // _prefilled && _relations.empty() && _extra.empty(), as used to be // the case. This defines the free semigroup return lhs == rhs; } return CongruenceInterface::contains(lhs, rhs); } //////////////////////////////////////////////////////////////////////// // 5. CongruenceInterface - non-pure virtual member functions - private //////////////////////////////////////////////////////////////////////// class_index_type ToddCoxeter::const_word_to_class_index(word_type const& w) const { validate_word(w); coset_type c = _id_coset; if (kind() == congruence_kind::left) { c = action_digraph_helper::follow_path_nc( _word_graph, c, w.crbegin(), w.crend()); } else { c = action_digraph_helper::follow_path_nc( _word_graph, c, w.cbegin(), w.cend()); } return (c == UNDEFINED ? UNDEFINED : static_cast<class_index_type>(c - 1)); } bool ToddCoxeter::is_quotient_obviously_finite_impl() { if (finished()) { return true; } init_generating_pairs(); return _prefilled; // _prefilled means that either we were created from a FroidurePinBase* // with froidure_pin_policy() == use_cayley_graph and we successfully // prefilled the table, or we manually prefilled the table. In this // case the semigroup defined by _relations must be finite. } bool ToddCoxeter::is_quotient_obviously_infinite_impl() { if (finished()) { return false; } init_generating_pairs(); if (_prefilled) { return false; } else if (number_of_generators() > _relations.size() + _extra.size()) { return true; } detail::IsObviouslyInfinite ioi(number_of_generators()); ioi.add_rules(_relations.cbegin(), _relations.cend()); ioi.add_rules(_extra.cbegin(), _extra.cend()); return ioi.result(); } void ToddCoxeter::set_number_of_generators_impl(size_t n) { LIBSEMIGROUPS_ASSERT(_word_graph.out_degree() == 0); LIBSEMIGROUPS_ASSERT(_word_graph.number_of_nodes() == 0); _word_graph.add_nodes(1); _word_graph.add_to_out_degree(n); } void ToddCoxeter::add_generators_impl(size_t n) { LIBSEMIGROUPS_ASSERT(_word_graph.out_degree() != 0); LIBSEMIGROUPS_ASSERT(_word_graph.number_of_nodes() == 1); _word_graph.add_to_out_degree(n); } //////////////////////////////////////////////////////////////////////// // 5. CongruenceInterface - pure virtual member functions - private //////////////////////////////////////////////////////////////////////// word_type ToddCoxeter::class_index_to_word_impl(class_index_type i) { run(); if (!is_standardized()) { standardize(order::shortlex); } LIBSEMIGROUPS_ASSERT(finished()); word_type w; TreeNode tn = (*_tree)[i + 1]; while (tn.parent != UNDEFINED) { w.push_back(tn.gen); tn = (*_tree)[tn.parent]; } if (kind() != congruence_kind::left) { std::reverse(w.begin(), w.end()); } return w; } size_t ToddCoxeter::number_of_classes_impl() { run(); LIBSEMIGROUPS_ASSERT(finished()); return number_of_cosets_active() - 1; } std::shared_ptr<FroidurePinBase> ToddCoxeter::quotient_impl() { using detail::TCE; run(); standardize(order::shortlex); shrink_to_fit(); // Ensure class indices and letters are equal! auto table = std::make_shared<table_type>(_word_graph.table()); size_t n = number_of_generators(); for (letter_type a = 0; a < n;) { if (table->get(0, a) != a + 1) { table->erase_column(a); n--; } else { ++a; } } auto ptr = std::make_shared< FroidurePin<TCE, FroidurePinTraits<TCE, table_type>>>(table); for (size_t i = 0; i < number_of_generators(); ++i) { // We use table.get(0, i) instead of just i, because there might be // more generators than cosets. ptr->add_generator(TCE(_word_graph.unsafe_neighbor(0, i))); } return ptr; } void ToddCoxeter::run_impl() { if (is_quotient_obviously_infinite()) { LIBSEMIGROUPS_EXCEPTION( "there are infinitely many classes in the congruence and " "Todd-Coxeter will never terminate"); } if (strategy() == options::strategy::felsch) { felsch(); } else if (strategy() == options::strategy::hlt) { hlt(); } else if (strategy() == options::strategy::random) { if (running_for()) { LIBSEMIGROUPS_EXCEPTION( "the strategy \"%s\" is incompatible with run_for!", detail::to_string(strategy()).c_str()); } random(); } else { if (running_until()) { LIBSEMIGROUPS_EXCEPTION( "the strategy \"%s\" is incompatible with run_until!", detail::to_string(strategy()).c_str()); } if (strategy() == options::strategy::CR) { CR_style(); } else if (strategy() == options::strategy::R_over_C) { R_over_C_style(); } else if (strategy() == options::strategy::Cr) { Cr_style(); } else if (strategy() == options::strategy::Rc) { Rc_style(); } } } bool ToddCoxeter::finished_impl() const { return _state == state::finished; } class_index_type ToddCoxeter::word_to_class_index_impl(word_type const& w) { run(); LIBSEMIGROUPS_ASSERT(finished()); if (!is_standardized()) { standardize(order::shortlex); } return const_word_to_class_index(w); // c is in the range 1, ..., number_of_cosets_active() because 0 // represents the identity coset, and does not correspond to an element. } //////////////////////////////////////////////////////////////////////// // 7. ToddCoxeter - member functions (init_generating_pairs + settings) - // public //////////////////////////////////////////////////////////////////////// // Settings ToddCoxeter& ToddCoxeter::froidure_pin_policy(options::froidure_pin x) noexcept { _settings->froidure_pin = x; return *this; } ToddCoxeter::options::froidure_pin ToddCoxeter::froidure_pin_policy() const noexcept { return _settings->froidure_pin; } ToddCoxeter& ToddCoxeter::lookahead(options::lookahead x) noexcept { if (!(x & options::lookahead::felsch) && !(x & options::lookahead::hlt)) { x = x | options::lookahead::hlt; } _settings->lookahead = x; return *this; } ToddCoxeter::options::lookahead ToddCoxeter::lookahead() const noexcept { return _settings->lookahead; } ToddCoxeter& ToddCoxeter::lower_bound(size_t n) noexcept { _settings->lower_bound = n; return *this; } size_t ToddCoxeter::lower_bound() const noexcept { return _settings->lower_bound; } ToddCoxeter& ToddCoxeter::next_lookahead(size_t n) noexcept { _settings->next_lookahead = n; return *this; } size_t ToddCoxeter::next_lookahead() const noexcept { return _settings->next_lookahead; } ToddCoxeter& ToddCoxeter::min_lookahead(size_t n) noexcept { _settings->min_lookahead = n; return *this; } size_t ToddCoxeter::min_lookahead() const noexcept { return _settings->min_lookahead; } ToddCoxeter& ToddCoxeter::standardize(bool x) noexcept { _settings->standardize = x; return *this; } bool ToddCoxeter::standardize() const noexcept { return _settings->standardize; } ToddCoxeter& ToddCoxeter::save(bool x) { if ((_prefilled || (has_parent_froidure_pin() && parent_froidure_pin()->is_finite() == tril::TRUE && (_settings->froidure_pin == options::froidure_pin::none || _settings->froidure_pin == options::froidure_pin::use_cayley_graph))) && x) { LIBSEMIGROUPS_EXCEPTION("cannot use the save setting with a " "prefilled ToddCoxeter instance"); } _settings->save = x; return *this; } bool ToddCoxeter::save() const noexcept { return _settings->save; } ToddCoxeter& ToddCoxeter::strategy(options::strategy x) { if ((_prefilled || (has_parent_froidure_pin() && parent_froidure_pin()->is_finite() == tril::TRUE && (_settings->froidure_pin == options::froidure_pin::none || _settings->froidure_pin == options::froidure_pin::use_cayley_graph))) && x == options::strategy::felsch) { LIBSEMIGROUPS_EXCEPTION("cannot use the Felsch strategy with a " "prefilled ToddCoxeter instance"); } _settings->strategy = x; return *this; } ToddCoxeter::options::strategy ToddCoxeter::strategy() const noexcept { return _settings->strategy; } ToddCoxeter& ToddCoxeter::random_interval(std::chrono::nanoseconds x) noexcept { _settings->random_interval = x; return *this; } std::chrono::nanoseconds ToddCoxeter::random_interval() const noexcept { return _settings->random_interval; } ToddCoxeter& ToddCoxeter::use_relations_in_extra(bool val) noexcept { _settings->use_relations_in_extra = val; return *this; } bool ToddCoxeter::use_relations_in_extra() const noexcept { return _settings->use_relations_in_extra; } ToddCoxeter& ToddCoxeter::deduction_policy(options::deductions val) { using int_type = std::underlying_type_t<ToddCoxeter::options::deductions>; if (static_cast<int_type>(val) % 2 == 0 || static_cast<int_type>(val) < 4) { LIBSEMIGROUPS_EXCEPTION("invalid option %s!", detail::to_string(val).c_str()) } _settings->deduct_policy = val; if (val & options::deductions::unlimited) { _settings->deduct_max = POSITIVE_INFINITY; } return *this; } ToddCoxeter::options::deductions ToddCoxeter::deduction_policy() const noexcept { return _settings->deduct_policy; } ToddCoxeter& ToddCoxeter::max_deductions(size_t val) noexcept { _settings->deduct_max = val; return *this; } size_t ToddCoxeter::max_deductions() const noexcept { return _settings->deduct_max; } ToddCoxeter& ToddCoxeter::preferred_defs(options::preferred_defs val) noexcept { if (val == options::preferred_defs::none) { // Don't call preferred_defs() here because ends up in infinite loop. _settings->max_preferred_defs = 0; } _settings->preferred_defs = val; return *this; } ToddCoxeter::options::preferred_defs ToddCoxeter::preferred_defs() const noexcept { return _settings->preferred_defs; } ToddCoxeter& ToddCoxeter::restandardize(bool val) noexcept { _settings->restandardize = val; return *this; } bool ToddCoxeter::restandardize() const noexcept { return _settings->restandardize; } ToddCoxeter& ToddCoxeter::max_preferred_defs(size_t val) noexcept { if (val == 0) { // Don't call preferred_defs() here because ends up in infinite loop. _settings->preferred_defs = options::preferred_defs::none; } _settings->max_preferred_defs = val; return *this; } size_t ToddCoxeter::max_preferred_defs() const noexcept { return _settings->max_preferred_defs; } ToddCoxeter& ToddCoxeter::hlt_defs(size_t val) { if (val < length_of_generating_pairs()) { LIBSEMIGROUPS_EXCEPTION("Expected a value >= %llu, found %llu!", uint64_t(length_of_generating_pairs()), uint64_t(val)); } _settings->hlt_defs = val; return *this; } size_t ToddCoxeter::hlt_defs() const noexcept { return _settings->hlt_defs; } ToddCoxeter& ToddCoxeter::f_defs(size_t val) { if (val == 0) { LIBSEMIGROUPS_EXCEPTION("Expected a value != 0!"); } _settings->f_defs = val; return *this; } size_t ToddCoxeter::f_defs() const noexcept { return _settings->f_defs; } ToddCoxeter& ToddCoxeter::lookahead_growth_factor(float val) { if (val < 1.0) { LIBSEMIGROUPS_EXCEPTION("Expected a value >= 1.0, found %f", val); } _settings->lookahead_growth_factor = val; return *this; } float ToddCoxeter::lookahead_growth_factor() const noexcept { return _settings->lookahead_growth_factor; } ToddCoxeter& ToddCoxeter::lookahead_growth_threshold(size_t val) noexcept { _settings->lookahead_growth_threshold = val; return *this; } size_t ToddCoxeter::lookahead_growth_threshold() const noexcept { return _settings->lookahead_growth_threshold; } ToddCoxeter& ToddCoxeter::large_collapse(size_t val) noexcept { _settings->large_collapse = val; return *this; } size_t ToddCoxeter::large_collapse() const noexcept { return _settings->large_collapse; } // Private settings! void ToddCoxeter::push_settings() { Settings* prev_settings = _settings.get(); _settings.release(); _setting_stack.push(prev_settings); _settings = std::make_unique<Settings>(*prev_settings); } void ToddCoxeter::pop_settings() { if (!_setting_stack.empty()) { _settings.reset(_setting_stack.top()); _setting_stack.pop(); } } //////////////////////////////////////////////////////////////////////// // 8. ToddCoxeter - member functions (sorting gen. pairs etc) - public //////////////////////////////////////////////////////////////////////// ToddCoxeter& ToddCoxeter::sort_generating_pairs( std::function<bool(word_type const&, word_type const&)> func) { if (started()) { LIBSEMIGROUPS_EXCEPTION( "Cannot sort relations, the enumeration has started!") } init_generating_pairs(); Perm perm; ::sort_generating_pairs(func, perm, _relations); ::sort_generating_pairs(func, perm, _extra); return *this; } ToddCoxeter& ToddCoxeter::random_shuffle_generating_pairs() { if (started()) { LIBSEMIGROUPS_EXCEPTION("Cannot shuffle the generating pairs, the " "enumeration has started!") } init_generating_pairs(); Perm perm(0, _relations.size()); std::iota(perm.begin(), perm.end(), 0); std::random_device rd; std::mt19937 g(rd()); std::shuffle(perm.begin(), perm.end(), g); ::sort_generating_pairs(perm, _relations); ::sort_generating_pairs(perm, _extra); return *this; } ToddCoxeter& ToddCoxeter::remove_duplicate_generating_pairs() { if (started()) { LIBSEMIGROUPS_EXCEPTION("Cannot remove duplicate generating pairs, the " "enumeration has started!") } init_generating_pairs(); std::unordered_set<relation_type, Hash<relation_type>> relations_set; for (size_t i = 0; i < _relations.size(); i += 2) { if (shortlex_compare(_relations[i], _relations[i + 1])) { relations_set.emplace(_relations[i], _relations[i + 1]); } else { relations_set.emplace(_relations[i + 1], _relations[i]); } } _relations.clear(); for (auto const& p : relations_set) { _relations.push_back(p.first); _relations.push_back(p.second); } std::unordered_set<relation_type, Hash<relation_type>> extra_set; for (size_t i = 0; i < _extra.size(); i += 2) { if (shortlex_compare(_extra[i], _extra[i + 1])) { if (relations_set.emplace(_extra[i], _extra[i + 1]).second) { extra_set.emplace(_extra[i], _extra[i + 1]); } } else { if (relations_set.emplace(_extra[i + 1], _extra[i]).second) { extra_set.emplace(_extra[i + 1], _extra[i]); } } } _extra.clear(); for (auto const& p : extra_set) { _extra.push_back(p.first); _extra.push_back(p.second); } return *this; } ToddCoxeter& ToddCoxeter::simplify(size_t n) { init_generating_pairs(); if (started()) { LIBSEMIGROUPS_EXCEPTION("the enumeration has started, it is no longer " "possible to change the generating pairs!"); } else if (_prefilled) { // There's no actual reason that we cannot do this here, just reducing // complexity of introducing this feature. But it would mean making a // fundamental change away from assuming that _relations is empty if // _prefilled is true. So, I am opting not to do this now. LIBSEMIGROUPS_EXCEPTION("the table has been prefilled, it is no longer " "possible to change the generating pairs!"); } if (_felsch_tree != nullptr) { _felsch_tree = nullptr; } PairsSimplifier p; // Replace words in _relations with min. equiv. word in _relations p.add(_relations).apply(_relations); p.add(_extra).apply(_extra); remove_duplicate_generating_pairs(); // Reduce the length of the presentation by introducing new generators, // until either we reach n, or we cannot reduce the presentation any // further for (size_t i = 0; i < n; ++i) { if (!reduce_length_once()) { return *this; } } return *this; } bool ToddCoxeter::reduce_length_once() { LIBSEMIGROUPS_ASSERT(_felsch_tree == nullptr); using const_iterator_word = typename ukkonen::detail::GreedyReduceHelper::const_iterator; if (_relations.empty() && _extra.empty()) { return false; } Ukkonen u; ukkonen::add_words(u, _relations); ukkonen::add_words(u, _extra); ukkonen::detail::GreedyReduceHelper helper(u); const_iterator_word first, last; // Get the best word [first, last) so that replacing every // non-overlapping occurrence of [first, last) in _relations and // _extra with a new generator "x", and adding "x = [first, last)" as // a relation reduces the length of the presentation as much as // possible. std::tie(first, last) = ukkonen::dfs(u, helper); if (first == last) { return false; // no change } letter_type const x = number_of_generators(); add_generators(1); auto replace_subword = [&first, &last, &x](word_type& word) { auto it = std::search(word.begin(), word.end(), first, last); while (it != word.end()) { // found [first, last) *it = x; auto pos = it - word.begin(); word.erase(it + 1, it + (last - first)); // it not valid it = std::search(word.begin() + pos + 1, word.end(), first, last); } }; std::for_each(_relations.begin(), _relations.end(), replace_subword); _relations.emplace_back(word_type({x})); _relations.emplace_back(first, last); std::for_each(_extra.begin(), _extra.end(), replace_subword); return true; } //////////////////////////////////////////////////////////////////////// // 9. ToddCoxeter - member functions (container-like) - public //////////////////////////////////////////////////////////////////////// bool ToddCoxeter::empty() const { return _relations.empty() && _extra.empty() && number_of_cosets_active() == 1; } void ToddCoxeter::reserve(size_t n) { size_t m = coset_capacity(); if (n > m) { m = n - m; _word_graph.add_nodes(m); add_free_cosets(m); } } void ToddCoxeter::shrink_to_fit() { if (!finished()) { return; } if (!is_standardized()) { standardize(order::shortlex); } _word_graph.shrink_to_fit(number_of_cosets_active()); _relations.clear(); _relations.shrink_to_fit(); _extra.clear(); _extra.shrink_to_fit(); erase_free_cosets(); } //////////////////////////////////////////////////////////////////////// // 10. ToddCoxeter - member functions (state) - public //////////////////////////////////////////////////////////////////////// bool ToddCoxeter::complete() const noexcept { size_t const n = number_of_generators(); coset_type c = _id_coset; while (c != first_free_coset()) { for (size_t a = 0; a < n; ++a) { if (_word_graph.unsafe_neighbor(c, a) == UNDEFINED) { return false; } } c = next_active_coset(c); } return true; } template <typename T> bool ToddCoxeter::compatible(coset_type c, T first, T last) const { for (auto it = first; it < last; it += 2) { coset_type x = action_digraph_helper::follow_path_nc( _word_graph, c, (*it).cbegin(), (*it).cend()); LIBSEMIGROUPS_ASSERT(is_active_coset(x) || x == UNDEFINED); coset_type y = action_digraph_helper::follow_path_nc( _word_graph, c, (*(it + 1)).cbegin(), (*(it + 1)).cend()); LIBSEMIGROUPS_ASSERT(is_active_coset(y) || y == UNDEFINED); if (x != y || x == UNDEFINED) { return false; } } return true; } bool ToddCoxeter::compatible() const noexcept { coset_type c = _id_coset; if (!compatible(c, _extra.cbegin(), _extra.cend())) { return false; } while (c != first_free_coset()) { if (!compatible(c, _relations.cbegin(), _relations.cend())) { return false; } c = next_active_coset(c); } return true; } size_t ToddCoxeter::length_of_generating_pairs() { init_generating_pairs(); auto op = [](size_t val, word_type const& x) { return val + x.size(); }; size_t N = std::accumulate( _relations.cbegin(), _relations.cend(), size_t(0), op); N += std::accumulate(_extra.cbegin(), _extra.cend(), size_t(0), op); return N; } size_t ToddCoxeter::felsch_tree_height() { init_generating_pairs(); init_run(); init_felsch_tree(); return _felsch_tree->height(); } size_t ToddCoxeter::felsch_tree_number_of_nodes() { init_generating_pairs(); init_run(); init_felsch_tree(); return _felsch_tree->number_of_nodes(); } //////////////////////////////////////////////////////////////////////// // 11. ToddCoxeter - member functions (standardization) - public //////////////////////////////////////////////////////////////////////// bool ToddCoxeter::is_standardized() const noexcept { return _standardized != order::none; } ToddCoxeter::order ToddCoxeter::standardization_order() const noexcept { return _standardized; } bool ToddCoxeter::standardize(order rdr) { if (_standardized == rdr || empty()) { return false; } LIBSEMIGROUPS_ASSERT(_coinc.empty()); LIBSEMIGROUPS_ASSERT(_deduct->empty()); bool result = false; switch (rdr) { case order::shortlex: init_standardize(); result = shortlex_standardize(); break; case order::lex: init_standardize(); result = lex_standardize(); break; case order::recursive: init_standardize(); result = recursive_standardize(); break; case order::none: default: break; } if (finished()) { _standardized = rdr; } else { _standard_max = number_of_cosets_active(); } return result; } //////////////////////////////////////////////////////////////////////// // 12. ToddCoxeter - member functions (attributes) - public //////////////////////////////////////////////////////////////////////// tril ToddCoxeter::is_non_trivial(size_t tries, std::chrono::milliseconds try_for, float threshold) { if (is_quotient_obviously_infinite()) { return tril::TRUE; } else if (finished()) { return number_of_classes() == 1 ? tril::FALSE : tril::TRUE; } detail::Timer tmr; static std::random_device rd; static std::mt19937 g(rd()); for (size_t try_ = 0; try_ < tries; ++try_) { REPORT_DEFAULT( "trying to show non-triviality: %d / %d\n", try_ + 1, tries); ToddCoxeter tc(*this); tc.init_felsch_tree(); tc.standardize(true); tc.save(true); while (!tc.finished()) { tc.run_for(try_for); size_t limit = tc.number_of_cosets_active(); while (tc.number_of_cosets_active() >= threshold * limit && !tc.finished()) { std::uniform_int_distribution<> d(0, tc.number_of_cosets_active() - 1); size_t N = d(g); auto c1 = tc._id_coset; for (size_t i = 0; i < N; ++i) { c1 = tc.next_active_coset(c1); } N = d(g); auto c2 = tc._id_coset; for (size_t i = 0; i < N; ++i) { c2 = tc.next_active_coset(c2); } tc._coinc.emplace(c1, c2); tc.process_coincidences(stack_deductions::yes); tc.process_deductions(); tc.run_for(try_for); } } if (tc.number_of_classes() > 1) { REPORT_DEFAULT("successfully showed non-triviality!\n"); report_time(__func__, tmr); return tril::TRUE; } } REPORT_DEFAULT("failed to show non-triviality!\n"); report_time(__func__, tmr); return tril::unknown; } //////////////////////////////////////////////////////////////////////// // 13. ToddCoxeter - member functions (reporting + stats) - public //////////////////////////////////////////////////////////////////////// std::string ToddCoxeter::stats_string() const { detail::PrintTable pt; pt.header("Summary of statistics"); pt("Number of generators:", "%'14llu", uint64_t(number_of_generators())); pt("Number of relations:", "%'14llu", uint64_t(_relations.size() / 2)); pt("Number of generating pairs:", "%'14llu", uint64_t(_extra.size() / 2)); pt("Total length of generating pairs:", "%'14llu", uint64_t( const_cast<ToddCoxeter*>(this)->length_of_generating_pairs())); pt.divider(); pt("cosets defined (hlt)", "%'14llu", uint64_t(_stats.tc1_hlt_appl)); pt("cosets defined (felsch)", "%'14llu", uint64_t(_stats.tc1_f_appl)); pt("total cosets defined", "%'14llu", uint64_t(number_of_cosets_defined() - 2)); pt("coset capacity", "%'14llu", uint64_t(coset_capacity())); pt("cosets killed", "%'14llu", uint64_t(number_of_cosets_killed())); pt("killed / defined", "%13f%%", static_cast<float>(100 * number_of_cosets_killed()) / number_of_cosets_defined()); pt("defined / capacity", "%13f%%", static_cast<float>(100 * number_of_cosets_defined()) / coset_capacity()); #ifdef LIBSEMIGROUPS_ENABLE_STATS pt.divider(); pt("relations pushed (good)", "%'14llu", uint64_t(_stats.tc2_good_appl)); pt("relations pushed (total)", "%'14llu", uint64_t(_stats.tc2_appl)); pt("relations pushed (% good)", "%13f%%", static_cast<double>(100 * _stats.tc2_good_appl) / _stats.tc2_appl); pt.divider(); pt("calls to process_coincidences", "%'14llu", uint64_t(_stats.tc3_appl)); pt("maximum coincidences", "%'14llu", uint64_t(_stats.max_coinc)); pt("total active coincidences", "%'14llu", uint64_t(_stats.nr_active_coinc)); pt("total coincidences", "%'14llu", uint64_t(_stats.total_coinc)); pt.divider(); pt("calls to process_deductions", "%'14llu", uint64_t(_stats.total_deduct)); pt("maximum deductions", "%'14llu", uint64_t(_stats.max_deduct)); pt("total active deductions", "%'14llu", uint64_t(_stats.nr_active_deduct)); pt("total deductions", "%'14llu", uint64_t(_stats.total_deduct)); pt.divider(); pt("maximum preferred defs", "%'14llu", uint64_t(_stats.max_preferred_defs)); pt("total active preferred defs", "%'14llu", uint64_t(_stats.nr_active_preferred_defs)); pt("total preferred defs", "%'14llu", uint64_t(_stats.total_preferred_defs)); pt.divider(); pt("calls to lookahead (hlt)", "%'14llu", uint64_t(_stats.hlt_lookahead_calls)); pt("calls to lookahead (felsch)", "%'14llu", uint64_t(_stats.f_lookahead_calls)); #endif pt.footer("End of summary"); return pt.emit(); } std::string ToddCoxeter::settings_string() const { detail::PrintTable pt; pt.header("Summary of settings (Todd-Coxeter algorithm)"); pt("deduction_policy:", deduction_policy()); pt("f_defs:", "%'14llu", uint64_t(f_defs())); pt("froidure_pin_policy:", froidure_pin_policy()); pt("hlt_defs:", "%'14llu", uint64_t(hlt_defs())); pt("lookahead:", lookahead()); pt("lookahead_growth_factor:", "%14f", lookahead_growth_factor()); pt("lookahead_growth_threshold:", "%14llu", uint64_t(lookahead_growth_threshold())); if (lower_bound() == UNDEFINED) { pt("lower_bound:", "\u221E"); } else { pt("lower_bound:", "%'14llu", uint64_t(lower_bound())); } pt("max_deductions:", "%'14llu", uint64_t(max_deductions())); pt("max_preferred_defs:", "%'14llu", uint64_t(max_preferred_defs())); pt("next_lookahead:", "%'14llu", uint64_t(next_lookahead())); pt("preferred_defs:", preferred_defs()); pt("random_interval:", detail::Timer::string(random_interval())); pt("save: ", save() ? "true" : "false"); pt("standardize:", standardize() ? "true" : "false"); pt("strategy: ", strategy()); pt("use_relations_in_extra:", use_relations_in_extra() ? "true" : "false"); pt.footer("End of summary"); return pt.emit(); } std::string ToddCoxeter::to_gap_string() { std::string const alphabet = "abcdefghijklmnopqrstuvwxyzABCDFGHIJKLMNOPQRSTUVWY"; if (kind() != congruence_kind::twosided) { LIBSEMIGROUPS_EXCEPTION( "expected congruence kind to be twosided, found " + congruence_kind_to_string(kind())); } if (number_of_generators() > 49) { LIBSEMIGROUPS_EXCEPTION("expected at most 49 generators, found %llu!", uint64_t(number_of_generators())); } init_generating_pairs(); auto to_gap_word = [&alphabet](word_type const& w) -> std::string { std::string out; for (auto it = w.cbegin(); it < w.cend() - 1; ++it) { out += alphabet[*it]; out += " * "; } out += alphabet[w.back()]; return out; }; std::string out = "free := FreeSemigroup("; for (size_t i = 0; i < number_of_generators(); ++i) { out += std::string("\"") + alphabet[i] + "\""; if (i != number_of_generators() - 1) { out += ", "; } } out += ");\n"; out += "DoAssignGenVars(GeneratorsOfSemigroup(free));\n"; out += "rules := [\n"; for (auto it = _relations.cbegin(); it < _relations.cend(); it += 2) { out += " ["; out += to_gap_word(*it); out += ", "; out += to_gap_word(*(it + 1)); if (it != _relations.cend() - 2) { out += "],\n"; } else { out += "]\n"; } } for (auto it = _extra.cbegin(); it < _extra.cend(); it += 2) { out += " ["; out += to_gap_word(*it); out += ", "; out += to_gap_word(*(it + 1)); if (it != _extra.cend() - 2) { out += "],\n"; } else { out += "]\n"; } } out += " ];\n"; out += "S := free / rules;\n"; return out; } //////////////////////////////////////////////////////////////////////// // 14. ToddCoxeter - member functions (reporting + stats) - private //////////////////////////////////////////////////////////////////////// namespace { std::string fmt_line() { #if defined(LIBSEMIGROUPS_FMT_ENABLED) && defined(LIBSEMIGROUPS_ENABLE_STATS) return "\t{:12L} {:+12L} ({})\n"; #elif defined(LIBSEMIGROUPS_FMT_ENABLED) && !defined(LIBSEMIGROUPS_ENABLE_STATS) return "\t{:12L} {:>12} ({})\n"; #elif !defined(LIBSEMIGROUPS_FMT_ENABLED) && defined(LIBSEMIGROUPS_ENABLE_STATS) return "\t%'12llu %+'12lld (%s)\n"; #elif !defined(LIBSEMIGROUPS_FMT_ENABLED) \ && !defined(LIBSEMIGROUPS_ENABLE_STATS) return "\t%'12llu %12s (%s)\n"; #endif } } // namespace #ifdef LIBSEMIGROUPS_ENABLE_STATS void ToddCoxeter::report_coincidences(char const* fnam) { if (report::should_report()) { REPORT_DEFAULT(FORMAT("coincidences:" + fmt_line(), _coinc.size(), int64_t(_coinc.size() - _stats.prev_coincidences), fnam)); _stats.prev_coincidences = _coinc.size(); } } #else void ToddCoxeter::report_coincidences(char const* fnam) { REPORT_DEFAULT( FORMAT("coincidences:" + fmt_line(), _coinc.size(), "", fnam)); } #endif #ifdef LIBSEMIGROUPS_ENABLE_STATS void ToddCoxeter::report_active_cosets(char const* fnam) { if (report::should_report()) { REPORT_DEFAULT(FORMAT( "active cosets:" + fmt_line(), number_of_cosets_active(), int64_t(number_of_cosets_active() - _stats.prev_active_cosets), fnam)); _stats.prev_active_cosets = number_of_cosets_active(); } } #else void ToddCoxeter::report_active_cosets(char const* fnam) { REPORT_DEFAULT(FORMAT( "active cosets:" + fmt_line(), number_of_cosets_active(), "", fnam)); } #endif void ToddCoxeter::report_cosets_killed(char const* fnam, int64_t N) const { if (report::should_report()) { #ifdef LIBSEMIGROUPS_FMT_ENABLED std::string fmt = "\t{:>12} {:+12L} ({})\n"; #else std::string fmt = "\t%12s %+'12lld (%s)\n"; #endif REPORT_DEFAULT(FORMAT("cosets killed:" + fmt, "", -1 * N, fnam)); } } void ToddCoxeter::report_inc_lookahead(char const* fnam, size_t new_value) const { if (report::should_report()) { #if defined(LIBSEMIGROUPS_FMT_ENABLED) std::string fmt = "\t{:12L} {:+12L} ({})\n"; #else std::string fmt = "\t%'12llu %+'12lld (%s)\n"; #endif REPORT_DEFAULT(FORMAT("lookahead at:" + fmt, new_value, int64_t(new_value - next_lookahead()), fnam)); } } void ToddCoxeter::report_time(char const* fnam, detail::Timer& t) const { if (report::should_report()) { auto tt = t.string(); size_t width = 12; // Check if we contain a \mu if (tt.find("\u03BC") != std::string::npos) { width = 13; } #ifdef LIBSEMIGROUPS_FMT_ENABLED std::string fmt = "\t{:>" + std::to_string(width) + "} {:>{}} ({})\n"; REPORT_DEFAULT(FORMAT("elapsed time:" + fmt, tt.c_str(), "", 12, fnam)); #else std::string fmt = "\t%" + std::to_string(width) + "s %*s (%s)\n"; REPORT_DEFAULT(FORMAT("elapsed time:" + fmt, tt.c_str(), 12, "", fnam)); #endif } } // Cannot test this void ToddCoxeter::report_at_coset(char const* fnam, size_t N) const { if (report::should_report()) { #ifdef LIBSEMIGROUPS_FMT_ENABLED std::string fmt = "\t{:12L} {:12L} ({})\n"; #else std::string fmt = "\t%'12llu %'12lld (%s)\n"; #endif REPORT_DEFAULT( FORMAT("at coset:" + fmt, N, number_of_cosets_active(), fnam)); } } //////////////////////////////////////////////////////////////////////// // 15. ToddCoxeter - member functions (validation) - private //////////////////////////////////////////////////////////////////////// void ToddCoxeter::validate_table(table_type const& table, size_t const first, size_t const last) const { REPORT_DEBUG_DEFAULT("validating coset table...\n"); if (number_of_generators() == UNDEFINED) { LIBSEMIGROUPS_EXCEPTION("no generators have been defined"); } else if (table.number_of_cols() != number_of_generators()) { LIBSEMIGROUPS_EXCEPTION("invalid table, expected %d columns, found %d", number_of_generators(), table.number_of_cols()); } else if (last - first == 0) { LIBSEMIGROUPS_EXCEPTION( "invalid table, expected at least 1 rows, found 0!"); } for (size_t i = first; i < last; ++i) { for (size_t j = 0; j < table.number_of_cols(); ++j) { coset_type c = table.get(i, j); if (c < first || c >= last) { LIBSEMIGROUPS_EXCEPTION("invalid table, expected entries in the " "range [%d, %d), found " "%d in row %d, column %d", i, j, first, last, c); } } } REPORT_DEBUG_DEFAULT("...coset table ok\n"); } //////////////////////////////////////////////////////////////////////// // 16. ToddCoxeter - member functions (initialisation) - private //////////////////////////////////////////////////////////////////////// //! Copy all _relations and _extra from copy into _relations of this void ToddCoxeter::copy_relations_for_quotient(ToddCoxeter& copy) { REPORT_DEBUG_DEFAULT("copying relations for quotient...\n"); LIBSEMIGROUPS_ASSERT(empty()); copy.init_generating_pairs(); if (copy.number_of_generators() == UNDEFINED) { return; } set_number_of_generators(copy.number_of_generators()); _state = state::relation_extra_initialized; _relations = copy._relations; _relations.insert( _relations.end(), copy._extra.cbegin(), copy._extra.cend()); if (kind() == congruence_kind::left && copy.kind() != congruence_kind::left) { for (auto& w : _relations) { std::reverse(w.begin(), w.end()); } } _nr_pairs_added_earlier = 0; } void ToddCoxeter::init_generating_pairs() { if (_state == state::constructed) { REPORT_DEBUG_DEFAULT("initializing...\n"); // Add the relations/Cayley graph from parent() if any. if (has_parent_froidure_pin() && parent_froidure_pin()->is_finite() == tril::TRUE) { if (froidure_pin_policy() == options::froidure_pin::use_cayley_graph || froidure_pin_policy() == options::froidure_pin::none) { REPORT_DEBUG_DEFAULT("using Cayley graph...\n"); LIBSEMIGROUPS_ASSERT(_relations.empty()); prefill(*parent_froidure_pin()); #ifdef LIBSEMIGROUPS_DEBUG // This is a check of program logic, since we use parent() to fill // the table, so we only validate in debug mode. validate_table( _word_graph.table(), 1, parent_froidure_pin()->size() + 1); #endif } else { REPORT_DEBUG_DEFAULT("using presentation...\n"); LIBSEMIGROUPS_ASSERT(froidure_pin_policy() == options::froidure_pin::use_relations); auto fp = parent_froidure_pin(); fp->run(); for (auto it = fp->cbegin_rules(); it != fp->cend_rules(); ++it) { reverse_if_necessary_and_push_back(this, it->first, _relations); reverse_if_necessary_and_push_back(this, it->second, _relations); } #ifdef LIBSEMIGROUPS_DEBUG // This is a check of program logic, since we use parent() to // obtain the relations, so we only validate in debug mode. for (auto const& rel : _relations) { validate_word(rel); } // We don't add anything to _extra here so no need to check. #endif } } _state = state::relation_extra_initialized; } // Get new generating pairs (if any) from CongruenceInterface (if any) auto it = cbegin_generating_pairs() + _nr_pairs_added_earlier; if (kind() != congruence_kind::twosided) { for (; it < cend_generating_pairs(); ++it) { reverse_if_necessary_and_push_back(this, it->first, _extra); reverse_if_necessary_and_push_back(this, it->second, _extra); } } else { for (; it < cend_generating_pairs(); ++it) { reverse_if_necessary_and_push_back(this, it->first, _relations); reverse_if_necessary_and_push_back(this, it->second, _relations); } } _nr_pairs_added_earlier = cend_generating_pairs() - cbegin_generating_pairs(); } --> -------------------- --> maximum size reached --> -------------------- ¤ Dauer der Verarbeitung: 0.31 Sekunden ¤*© Formatika GbR, Deutschland |
|
2026-03-28