# congruence::ToddCoxeter¶

class `ToddCoxeter` : public libsemigroups::CongruenceInterface, public libsemigroups::detail::CosetManager

Defined in `todd-coxeter.hpp`.

This class contains the main implementation of the Todd-Coxeter algorithm for computing left, right, and 2-sided congruences on semigroups and monoids.

This page contains a summary of the main member functions of the class congruence::ToddCoxeter, and related things in libsemigroups.

In this documentation we use the term “coset enumeration” to mean the execution of (any version of) the Todd-Coxeter algorithm.

See
Example 1

```ToddCoxeter tc(congruence_kind::left);  // construct a left congruence
tc.set_number_of_generators(2);                // 2 generators
tc.add_pair({0, 0}, {0});               // generator 0 squared is itself
tc.add_pair({0}, {1});                  // generator 0 equals 1
tc.strategy(options::strategy::felsch);  // set the strategy
tc.number_of_classes();                        // calculate number of
classes tc.contains({0, 0, 0, 0}, {0, 0});      // check if 2 words are
equal tc.word_to_class_index({0, 0, 0, 0});   // get the index of a
class tc.standardize(order::lex);             // standardize to lex
order
```

Example 2

```ToddCoxeter tc(congruence_kind::twosided);
tc.set_number_of_generators(4);
tc.add_pair({1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}, {0});
tc.add_pair({1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3,
1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3},
{0});
tc.strategy(options::strategy::hlt)
.standardize(false)
.save(false)
tc.number_of_classes()  // 10752
tc.complete();   // true
tc.compatible(); // true
auto& S = tc.quotient_semigroup();  // FroidurePin<TCE>
S.size()                            // 10752
S.number_of_idempotents()                  // 1
tc.standardize(order::recursive);
std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cbegin_normal_forms() + 10);
// {{0},
//  {1},
//  {2},
//  {2, 1},
//  {1, 2},
//  {1, 2, 1},
//  {2, 2},
//  {2, 2, 1},
//  {2, 1, 2},
//  {2, 1, 2, 1}};
tc.standardize(order::lex);
std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cbegin_normal_forms() + 10);
// {{0},
//  {0, 1},
//  {0, 1, 2},
//  {0, 1, 2, 1},
//  {0, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1},
//  {0, 1, 2, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1, 2, 1},
//  {0, 1, 2, 1, 2, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1, 2, 1, 2, 1}};
```

## Member types¶

 `coset_type` Type of the indices of cosets. `normal_form_iterator` The type of a const iterator pointing to a normal form. `options` Holds values of various options. `options::froidure_pin` Values for specifying whether to use relations or Cayley graph. `options::lookahead` Values for specifying the type of lookahead to perform. `options::strategy` Values for defining the strategy. `order` The possible arguments for `standardize(order)` . `sort_free_function_type` Type of the argument to `sort_generating_pairs` . `sort_function_type` Type of the argument to `sort_generating_pairs` . `table_type` Type of the underlying table.

## Constructors¶

 `ToddCoxeter(ToddCoxeter const&)` Copy constructor. `ToddCoxeter(congruence_kind)` Construct from kind (left/right/2-sided). `ToddCoxeter(congruence_kind, T const&)` Construct from kind (left/right/2-sided) and `FroidurePin` or `FpSemigroupInterface` . `ToddCoxeter(congruence_kind, ToddCoxeter&)` Construct from kind (left/right/2-sided) and `ToddCoxeter` . `ToddCoxeter(congruence_kind, fpsemigroup::KnuthBendix&)` Construct from kind (left/right/2-sided) and `KnuthBendix` . `ToddCoxeter(congruence_kind, fpsemigroup::ToddCoxeter&)` Construct from kind (left/right/2-sided) and `ToddCoxeter` . `ToddCoxeter(congruence_kind, std::shared_ptr, options::froidure_pin)` Construct from kind (left/right/2-sided), shared pointer to `FroidurePinBase` , and options.

## Deleted constructors¶

 `ToddCoxeter() = delete` Deleted. `ToddCoxeter(ToddCoxeter&&) = delete` Deleted. `operator=(ToddCoxeter const&) = delete` Deleted. `operator=(ToddCoxeter&&) = delete` Deleted.

## Initialization¶

 `prefill(table_type const&)` Prefill the coset table.

## Settings¶

 `froidure_pin_policy() const noexcept` Get the current value of the Froidure-Pin policy. `froidure_pin_policy(options::froidure_pin) noexcept` Specify whether to use the relations or the Cayley graph. `lookahead(options::lookahead) noexcept` Set the lookahead to use in HLT. `lower_bound(size_t) noexcept` Specify minimum number of classes that may trigger early stop. `next_lookahead(size_t) noexcept` Set the threshold that will trigger a lookahead in HLT. `random_interval(T) noexcept` Set the amount of time per strategy for `options::strategy::random` . `random_interval(std::chrono::nanoseconds) noexcept` Set the amount of time per strategy for `options::strategy::random` . `random_shuffle_generating_pairs()` Randomly shuffle the generating pairs. `save(bool)` Process deductions during HLT. `sort_generating_pairs(sort_free_function_type)` Sort generating pairs. `sort_generating_pairs(sort_function_type)` Sort generating pairs. `standardize(bool) noexcept` Short-lex standardize the table during enumeration. `strategy() const noexcept` The current strategy for enumeration. `strategy(options::strategy)` Specify the strategy.

## Container-like¶

 `empty() const` Check if there are no relations or generating pairs. `reserve(size_t)` Reserve the specified capacity in the coset table. `shrink_to_fit()` Release unused memory if `finished` .

## Standardization¶

 `is_standardized() const noexcept` Check if the table has been standardized. `standardize(order)` Standardize the table according to the specified order.

## Iterators¶

 `cbegin_normal_forms()` Returns a `normal_form_iterator` pointing at the first normal form. `cend_normal_forms()` Returns a `normal_form_iterator` pointing one past the last normal form.

## Properties¶

 `compatible() const noexcept` Check if the table is compatible with the relations. `complete() const noexcept` Check if the table is complete.

## Member functions inherited from CosetManager¶

 `coset_capacity() const noexcept` Returns the capacity of the coset table. `first_free_coset() const noexcept` Returns the first free coset. `has_free_cosets() const noexcept` Check if there are any free cosets. `is_active_coset(coset_type) const` Check if the given coset is active or not. `is_valid_coset(coset_type) const noexcept` Check if the given coset is valid. `next_active_coset(coset_type) const` Returns the next active coset after the given coset. `number_of_cosets_active() const noexcept` Returns the number of active cosets. `number_of_cosets_defined() const noexcept` Returns the total number of cosets defined so far. `number_of_cosets_killed() const noexcept` Returns the total number of cosets that have been killed so far.

## Member functions inherited from CongruenceInterface¶

 `add_pair(std::initializer_list, std::initializer_list)` Add a generating pair to the congruence. `add_pair(word_type const&, word_type const&)` Add a generating pair to the congruence. `cbegin_generating_pairs() const noexcept` Returns a const iterator pointing to the first generating pair. `cbegin_ntc()` Returns a const iterator pointing to the first non-singleton class. `cend_generating_pairs() const noexcept` Returns a const iterator pointing one-after-the-end of the last generating pair. `cend_ntc()` Returns a const iterator pointing one-past-the-end of the last non-singleton class. `class_index_to_word(class_index_type)` Get a canonical representative of the `i-th` class. `class_index_type` Type for indices of congruence class indices. `const_contains(word_type const&, word_type const&) const` Check if a pair of words is known to belong to the congruence. `const_iterator` Type for a `const_iterator` to the generating pairs. `contains(word_type const&, word_type const&) override` Check if a pair of words belongs to the congruence. `has_parent_fpsemigroup() const noexcept` Check if the congruence was constructed from a `FpSemigroupInterface` instance. `has_parent_froidure_pin() const noexcept` Check if the congruence was constructed from a `FroidurePin` instance. `has_quotient_froidure_pin() const noexcept` Check if the quotient semigroup has been computed. `is_quotient_obviously_finite()` Deterministically check if the quotient is finite. `is_quotient_obviously_infinite()` Deterministically check if the quotient is infinite. `kind() const noexcept` The handedness of the congruence (left, right, or 2-sided). `less(word_type const&, word_type const&)` Compare the indices of the classes containing two words. `non_trivial_class_iterator` Type for a `const_iterator` to non-trivial classes. `non_trivial_classes()` Returns a shared pointer to the non-trivial classes. `non_trivial_classes_type` Type for non-trivial classes. `number_of_classes()` Compute the number of classes in the congruence. `number_of_generating_pairs() const noexcept` The number of generating pairs. `number_of_generators() const noexcept` The number of generators. `number_of_non_trivial_classes()` The number of non-singleton classes. `parent_fpsemigroup() const` Get the parent `FpSemigroupInterface` instance (if any). `parent_froidure_pin() const` Get the parent `FroidurePin` instance (if any). `quotient_froidure_pin()` Returns a semigroup represented as an instance of a derived class of `FroidurePinBase` that is isomorphic to the quotient of the parent semigroup of `this` by the 2-sided congruence that `this` represents. `set_number_of_generators(size_t)` Set the number of generators of the congruence. `word_to_class_index(word_type const&)` Convert a word into the index of the class containing it.

## Member functions inherited from Runner¶

 `dead() const noexcept` Check if the runner is dead. `finished() const` Check if `run` has been run to completion or not. `kill() noexcept` Stop `run` from running (thread-safe). `report() const` Check if it is time to report. `report_every(TIntType)` Set the minimum elapsed time between reports. `report_every(std::chrono::nanoseconds)` Set the minimum elapsed time between reports. `report_why_we_stopped() const` Report why `run` stopped. `run()` Run until `finished` . `run_for(TIntType)` Run for a specified amount of time. `run_for(std::chrono::nanoseconds)` Run for a specified amount of time. `run_until(T&&)` Run until a nullary predicate returns `true` or `finished` . `run_until(bool(*)())` Run until a nullary predicate returns `true` or `finished` . `running() const noexcept` Check if currently running. `started() const` Check if `run` has been called at least once before. `stopped() const` Check if the runner is stopped. `stopped_by_predicate() const` Check if the runner was, or should, stop because of the argument for `run_until` . `timed_out() const` Check if the amount of time passed to `run_for` has elapsed.