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.

See also

congruence_kind and tril.

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({0, 0}, {0});
tc.add_pair({1, 0}, {1});
tc.add_pair({0, 1}, {1});
tc.add_pair({2, 0}, {2});
tc.add_pair({0, 2}, {2});
tc.add_pair({3, 0}, {3});
tc.add_pair({0, 3}, {3});
tc.add_pair({1, 1}, {0});
tc.add_pair({2, 3}, {0});
tc.add_pair({2, 2, 2}, {0});
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)
   .lookahead(options::lookahead::partial)
   .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`
`coset_type`	Type of cosets stored in the table.
`froidure_pin_type`
`normal_form_iterator`
`options`
`options::deductions`
`options::froidure_pin`
`options::lookahead`
`options::preferred_defs`
`options::strategy`
`order`
`sort_free_function_type`
`sort_function_type`
`table_type`

Constructors¶

`ToddCoxeter(ToddCoxeter const&)`
`ToddCoxeter(congruence_kind)`
`ToddCoxeter(congruence_kind, T const&)`
`ToddCoxeter(congruence_kind, ToddCoxeter&)`
`ToddCoxeter(congruence_kind, fpsemigroup::KnuthBendix&)`
`ToddCoxeter(congruence_kind, fpsemigroup::ToddCoxeter&)`
`ToddCoxeter(congruence_kind, std::shared_ptr<FroidurePinBase>, options::froidure_pin)`

Deleted constructors¶

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

Initialization¶

prefill(table_type const&)

Settings¶

`deduction_policy() const noexcept`
`deduction_policy(options::deductions)`
`f_defs() const noexcept`
`f_defs(size_t)`
`froidure_pin_policy() const noexcept`
`froidure_pin_policy(options::froidure_pin) noexcept`
`hlt_defs() const noexcept`
`hlt_defs(size_t)`
`large_collapse() const noexcept`
`large_collapse(size_t) noexcept`
`lookahead() const noexcept`
`lookahead(options::lookahead) noexcept`
`lookahead_growth_factor() const noexcept`
`lookahead_growth_factor(float)`
`lookahead_growth_threshold() const noexcept`
`lookahead_growth_threshold(size_t) noexcept`
`lower_bound() const noexcept`
`lower_bound(size_t) noexcept`
`max_deductions() const noexcept`
`max_deductions(size_t) noexcept`
`max_preferred_defs() const noexcept`
`max_preferred_defs(size_t) noexcept`
`min_lookahead() const noexcept`
`min_lookahead(size_t) noexcept`
`next_lookahead() const noexcept`
`next_lookahead(size_t) noexcept`
`preferred_defs() const noexcept`
`preferred_defs(options::preferred_defs) noexcept`
`random_interval() const noexcept`
`random_interval(T) noexcept`
`random_interval(std::chrono::nanoseconds) noexcept`
`random_shuffle_generating_pairs()`
`remove_duplicate_generating_pairs()`
`restandardize() const noexcept`
`restandardize(bool) noexcept`
`save() const noexcept`
`save(bool)`
`settings_string() const`
`simplify(size_t)`
`sort_generating_pairs(sort_free_function_type)`
`sort_generating_pairs(sort_function_type)`
`standardize() const noexcept`
`standardize(bool) noexcept`
`strategy() const noexcept`
`strategy(options::strategy)`
`use_relations_in_extra() const noexcept`
`use_relations_in_extra(bool) noexcept`

Statistics¶

`stats() const noexcept`
`stats_string() const`

Container-like¶

`empty() const`
`reserve(size_t)`
`shrink_to_fit()`

Standardization¶

`is_standardized() const noexcept`
`standardization_order() const noexcept`
`standardize(order)`

Iterators¶

`cbegin_class(class_index_type,size_t,size_t) const`
`cbegin_class(word_type const &,size_t,size_t)`
`cbegin_extra() const noexcept`
`cbegin_normal_forms()`
`cbegin_relations() const noexcept`
`cend_class() const`
`cend_extra() const noexcept`
`cend_normal_forms()`
`cend_relations() const noexcept`

Properties¶

`compatible() const noexcept`
`complete() const noexcept`
`felsch_tree_height()`
`felsch_tree_number_of_nodes()`
`is_non_trivial(size_t, std::chrono::milliseconds, float)`
`length_of_generating_pairs()`
`number_of_words(class_index_type) const`
`number_of_words(word_type const&)`
`to_gap_string()`

Member functions inherited from CosetManager¶

`coset_capacity() const noexcept`
`first_free_coset() const noexcept`
`growth_factor() const noexcept`
`growth_factor(float)`
`has_free_cosets() const noexcept`
`is_active_coset(coset_type) const`
`is_valid_coset(coset_type) const noexcept`
`next_active_coset(coset_type) const`
`number_of_cosets_active() const noexcept`
`number_of_cosets_defined() const noexcept`
`number_of_cosets_killed() const noexcept`

Member functions inherited from CongruenceInterface¶

`add_pair(std::initializer_list<size_t>, std::initializer_list<size_t>)`
`add_pair(word_type const&, word_type const&)`
`cbegin_generating_pairs() const noexcept`
`cbegin_ntc()`
`cend_generating_pairs() const noexcept`
`cend_ntc()`
`class_index_to_word(class_index_type)`
`class_index_type`	Type for indices of congruence class indices.
`const_contains(word_type const&, word_type const&) const`
`const_iterator`
`contains(word_type const&, word_type const&) override`
`has_parent_fpsemigroup() const noexcept`
`has_parent_froidure_pin() const noexcept`
`has_quotient_froidure_pin() const noexcept`
`is_quotient_obviously_finite()`
`is_quotient_obviously_infinite()`
`kind() const noexcept`
`less(word_type const&, word_type const&)`
`non_trivial_class_iterator`
`non_trivial_classes()`
`non_trivial_classes_type`
`number_of_classes()`
`number_of_generating_pairs() const noexcept`
`number_of_generators() const noexcept`
`number_of_non_trivial_classes()`
`parent_fpsemigroup() const`
`parent_froidure_pin() const`
`quotient_froidure_pin()`
`set_number_of_generators(size_t)`
`word_to_class_index(word_type const&)`

`dead() const noexcept`
`finished() const`
`kill() noexcept`
`report() const`
`report_every() const noexcept`
`report_every(TIntType)`
`report_every(std::chrono::nanoseconds)`
`report_why_we_stopped() const`
`run()`
`run_for(TIntType)`
`run_for(std::chrono::nanoseconds)`
`run_until(T&&)`
`run_until(bool(*)())`
`running() const noexcept`
`running_for() const noexcept`
`running_until() const noexcept`
`started() const`
`stopped() const`
`stopped_by_predicate() const`
`timed_out() const`