Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


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

--> --------------------

quality83%

¤ Dauer der Verarbeitung: 0.34 Sekunden (vorverarbeitet) ¤

Normalansicht

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.