# 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.

Some of the features of this class were inspired by similar features in ACE by George Havas and Colin Ramsay.

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();
tc.contains({0, 0, 0, 0}, {0, 0});
equal tc.word_to_class_index({0, 0, 0, 0});
tc.standardize(order::lex);
```

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¶

 `class_iterator` The type of a const iterator pointing to a word belonging to a particular class. `coset_type` Type of cosets stored in the table. `froidure_pin_type` The type of the return value of `quotient_froidure_pin()` . `normal_form_iterator` The type of a const iterator pointing to a normal form. `options` Holds values of various options. `options::deductions` Values for specifying how to handle deductions. `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::preferred_defs` Values for specifying how to handle preferred definitions. `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¶

 `deduction_policy() const noexcept` The current value of the deduction policy setting. `deduction_policy(options::deductions)` Specify how to handle deductions. `f_defs() const noexcept` The current value of the f_defs setting. `f_defs(size_t)` The approx number of Felsch style definitions in ACE strategies. `froidure_pin_policy() const noexcept` The current value of the Froidure-Pin policy setting. `froidure_pin_policy(options::froidure_pin) noexcept` Specify whether to use the relations or the Cayley graph. `hlt_defs() const noexcept` The current value of the hlt_defs setting. `hlt_defs(size_t)` The approx number of HLT style definitions in ACE strategies. `large_collapse() const noexcept` The current value of the large collapse setting. `large_collapse(size_t) noexcept` Specify what should be considered a large collapse. `lookahead() const noexcept` The current value of the setting for lookaheads. `lookahead(options::lookahead) noexcept` Set the style of lookahead to use in HLT. `lookahead_growth_factor() const noexcept` The current value of the lookahead growth factor. `lookahead_growth_factor(float)` Set the lookahead growth factor. `lookahead_growth_threshold() const noexcept` The current value of the lookahead growth threshold. `lookahead_growth_threshold(size_t) noexcept` Set the lookahead growth threshold. `lower_bound() const noexcept` The current value of the lower bound setting. `lower_bound(size_t) noexcept` Specify minimum number of classes that may trigger early stop. `max_deductions() const noexcept` The current value of the setting for the maximum number of deductions. `max_deductions(size_t) noexcept` The maximum number of deductions in the stack. `max_preferred_defs() const noexcept` The current value of the maximum preferred definitions setting. `max_preferred_defs(size_t) noexcept` Specify the maximum number of preferred definitions. `min_lookahead() const noexcept` The current value of the minimum lookahead setting. `min_lookahead(size_t) noexcept` Set the minimum value of `next_lookahead()` . `next_lookahead() const noexcept` The current value of the next lookahead setting. `next_lookahead(size_t) noexcept` Set the threshold that will trigger a lookahead in HLT. `preferred_defs() const noexcept` The current value of the preferred definitions setting. `preferred_defs(options::preferred_defs) noexcept` Specify how to handle preferred definitions. `random_interval() const noexcept` The current value of the random interval setting. `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. `remove_duplicate_generating_pairs()` Remove duplicate generating pairs. `restandardize() const noexcept` The current value of the restandardize setting. `restandardize(bool) noexcept` Specify whether to standardize between HLT and Felsch. `save() const noexcept` The current value of save setting. `save(bool)` Process deductions during HLT. `settings_string() const` Returns a string containing a tabularized summary of all the settings. `simplify(size_t)` Simplify defining relations and/or generating pairs. `sort_generating_pairs(sort_free_function_type)` Sort generating pairs. `sort_generating_pairs(sort_function_type)` Sort generating pairs. `standardize() const noexcept` The current value of the standardize setting. `standardize(bool) noexcept` Partially short-lex standardize the table during enumeration. `strategy() const noexcept` The current strategy for enumeration. `strategy(options::strategy)` Specify the strategy. `use_relations_in_extra() const noexcept` The current value of the setting for using relations. `use_relations_in_extra(bool) noexcept` Perform an HLT-style push of the defining relations at the identity.

## Statistics¶

 `stats() const noexcept` Returns a const reference to a statistics object. `stats_string() const` Returns a string containing a tabularized summary of the statistics.

## 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. `standardization_order() const noexcept` Returns the current order in which the table is standardized. `standardize(order)` Standardize the table according to the specified order.

## Iterators¶

 `cbegin_class(class_index_type,size_t,size_t) const` Returns a `class_iterator` pointing at the shortlex least word in an class. `cbegin_class(word_type const &,size_t,size_t)` Returns a `class_iterator` pointing at the shortlex least word in a class. `cbegin_extra() const noexcept` Returns a const iterator pointing at the first word in a generating pair. `cbegin_normal_forms()` Returns a `normal_form_iterator` pointing at the first normal form. `cbegin_relations() const noexcept` Returns a const iterator pointing at the first word in the first defining relation (if any). `cend_class() const` Returns a `class_iterator` pointing one past the last word in a class. `cend_extra() const noexcept` Returns a const iterator pointing one after the last word in any generating pair. `cend_normal_forms()` Returns a `normal_form_iterator` pointing one past the last normal form. `cend_relations() const noexcept` Returns a const iterator pointing one after the last word in the last defining relation (if any).

## Properties¶

 `compatible() const noexcept` Check if the table is compatible with the relations. `complete() const noexcept` Check if the table is complete. `felsch_tree_height()` Returns the height of the Felsch tree. `felsch_tree_number_of_nodes()` Returns the number of nodes of the Felsch tree. `is_non_trivial(size_t, std::chrono::milliseconds, float)` Check if the congruence has more than one class. `length_of_generating_pairs()` Returns the total length of the generating pairs. `number_of_words(class_index_type) const` Returns the size of the specified class. `number_of_words(word_type const&)` Returns the size of the specified class. `to_gap_string()` Returns a string containing a GAP definition of the finitely presented semigroup represented by a `ToddCoxeter` instance.

## 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. `growth_factor() const noexcept` The current value of the growth factor setting. `growth_factor(float)` Set the value of the growth factor setting. `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() const noexcept` Get the minimum elapsed time between reports. `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. `running_for() const noexcept` Check if the runner is currently running for a particular length of time. `running_until() const noexcept` Check if the runner is currently running until a nullary predicate returns `true`. `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.