//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2021 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/>.
// The purpose of this file is to test the ToddCoxeter classes.
#include <algorithm>
// for is_sorted, copy, all_of
#include <array>
// for array
#include <chrono>
// for duration, milliseconds
#include <cstddef>
// for size_t
#include <fstream>
// for ofstream
#include <functional>
// for mem_fn
#include <iostream>
// for string, operator<<, ostream
#include <memory>
// for unique_ptr, shared_ptr
#include <string>
// for basic_string, operator==
#include <unordered_map>
// for operator!=, operator==
#include <unordered_set>
// for unordered_set
#include <utility>
// for pair
#include <vector>
// for vector, operator==, swap
#define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER
#include "catch.hpp" // for TEST_CASE
#include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE
#include "libsemigroups/bmat8.hpp" // for BMat8
#include "libsemigroups/cong-intf.hpp" // for CongruenceInterface::class...
#include "libsemigroups/cong-wrap.hpp" // for CongruenceWrapper...
#include "libsemigroups/constants.hpp" // for operator==, operator!=
#include "libsemigroups/containers.hpp" // for DynamicArray2, DynamicArra...
#include "libsemigroups/fpsemi-examples.hpp" // for setup, RennerTypeDMonoid
#include "libsemigroups/fpsemi-intf.hpp" // for FpSemigroupInterface::rule...
#include "libsemigroups/fpsemi.hpp" // for FpSemigroup
#include "libsemigroups/froidure-pin-base.hpp" // for FroidurePinBase
#include "libsemigroups/froidure-pin.hpp" // for FroidurePin, FroidurePin<>...
#include "libsemigroups/iterator.hpp" // for ConstIteratorStateful, ope...
#include "libsemigroups/knuth-bendix.hpp" // for KnuthBendix
#include "libsemigroups/order.hpp" // for RecursivePathCompare, Lexi...
#include "libsemigroups/report.hpp" // for ReportGuard
#include "libsemigroups/string.hpp" // for operator<<, to_string
#include "libsemigroups/tce.hpp" // for TCE, operator<<, IncreaseD...
#include "libsemigroups/todd-coxeter.hpp" // for ToddCoxeter, operator|
#include "libsemigroups/transf.hpp" // for Transf, LeastTransf
#include "libsemigroups/types.hpp" // for word_type, relation_type
#include "libsemigroups/wislo.hpp" // for const_wislo_iterator, cbeg...
namespace libsemigroups {
struct LibsemigroupsException;
// Forward declaration
constexpr
bool REPORT =
false;
congruence_kind constexpr twosided = congruence_kind::twosided;
congruence_kind constexpr left = congruence_kind::left;
congruence_kind constexpr right = congruence_kind::right;
using KnuthBendix = fpsemigroup::KnuthBendix;
using tc_order = congruence::ToddCoxeter::order;
using options = congruence::ToddCoxeter::options;
using fpsemigroup::author;
using fpsemigroup::make;
using fpsemigroup::setup;
using fpsemigroup::brauer_monoid;
using fpsemigroup::dual_symmetric_inverse_monoid;
using fpsemigroup::fibonacci_semigroup;
using fpsemigroup::full_transformation_monoid;
using fpsemigroup::orientation_preserving_monoid;
using fpsemigroup::orientation_reversing_monoid;
using fpsemigroup::partial_transformation_monoid;
using fpsemigroup::partition_monoid;
using fpsemigroup::rook_monoid;
using fpsemigroup::singular_brauer_monoid;
using fpsemigroup::stellar_monoid;
using fpsemigroup::stylic_monoid;
using fpsemigroup::symmetric_group;
using fpsemigroup::symmetric_inverse_monoid;
using fpsemigroup::temperley_lieb_monoid;
using fpsemigroup::uniform_block_bijection_monoid;
namespace {
// Test functions
void check_felsch(congruence::ToddCoxeter& var) {
SECTION(
"Felsch + no standardisation") {
var.strategy(options::strategy::felsch).standardize(
false);
}
SECTION(
"Felsch + standardisation") {
var.strategy(options::strategy::felsch).standardize(
true);
}
}
void check_felsch(fpsemigroup::ToddCoxeter& var) {
check_felsch(var.congruence());
}
void check_felsch_throws(congruence::ToddCoxeter& var) {
SECTION(
"Felsch (throws)") {
REQUIRE_THROWS_AS(var.strategy(options::strategy::felsch),
LibsemigroupsException);
}
}
void check_felsch_throws(fpsemigroup::ToddCoxeter& var) {
check_felsch_throws(var.congruence());
}
void check_hlt_no_save(congruence::ToddCoxeter& var) {
SECTION(
"HLT + no standardise + full lookahead + no save") {
var.strategy(options::strategy::hlt);
var.standardize(
false).lookahead(options::lookahead::full).save(
false);
}
SECTION(
"HLT + standardise + full lookahead + no save") {
var.strategy(options::strategy::hlt);
var.standardize(
true).lookahead(options::lookahead::full).save(
false);
}
SECTION(
"HLT + no standardise + partial lookahead + no save") {
var.strategy(options::strategy::hlt);
var.standardize(
false)
.lookahead(options::lookahead::partial)
.save(
false);
}
SECTION(
"HLT + standardise + partial lookahead + no save") {
var.strategy(options::strategy::hlt);
var.standardize(
true)
.lookahead(options::lookahead::partial)
.save(
false);
}
}
void check_hlt_no_save(fpsemigroup::ToddCoxeter& var) {
check_hlt_no_save(var.congruence());
}
void check_hlt_save(congruence::ToddCoxeter& var) {
SECTION(
"HLT + no standardise + full lookahead + save") {
var.strategy(options::strategy::hlt);
var.standardize(
false).lookahead(options::lookahead::full).save(
true);
}
SECTION(
"HLT + standardise + full lookahead + save") {
var.strategy(options::strategy::hlt);
var.standardize(
true).lookahead(options::lookahead::full).save(
true);
}
SECTION(
"HLT + no standardise + partial lookahead + save") {
var.strategy(options::strategy::hlt);
var.standardize(
false)
.lookahead(options::lookahead::partial)
.save(
true);
}
SECTION(
"HLT + standardise + partial lookahead + save") {
var.strategy(options::strategy::hlt);
var.standardize(
true).lookahead(options::lookahead::partial).save(
true);
}
}
void check_hlt_save_throws(congruence::ToddCoxeter& var) {
SECTION(
"HLT + save (throws)") {
REQUIRE_THROWS_AS(var.strategy(options::strategy::hlt).save(
true),
LibsemigroupsException);
}
}
void check_hlt_save_throws(fpsemigroup::ToddCoxeter& var) {
check_hlt_save_throws(var.congruence());
}
void check_hlt(congruence::ToddCoxeter& var) {
check_hlt_no_save(var);
check_hlt_save(var);
}
void check_hlt(fpsemigroup::ToddCoxeter& var) {
check_hlt(var.congruence());
}
void check_random(congruence::ToddCoxeter& var) {
SECTION(
"random strategy") {
var.strategy(options::strategy::random);
}
}
void check_random(fpsemigroup::ToddCoxeter& var) {
check_random(var.congruence());
}
void check_Rc_style(congruence::ToddCoxeter& tc) {
SECTION(
"Rc style + full lookahead") {
tc.strategy(options::strategy::Rc).lookahead(options::lookahead::full);
tc.run();
}
SECTION(
"Rc style + partial lookahead") {
tc.strategy(options::strategy::Rc)
.lookahead(options::lookahead::partial);
tc.run();
}
}
void check_Rc_style(fpsemigroup::ToddCoxeter& tc) {
check_Rc_style(tc.congruence());
}
void check_Cr_style(congruence::ToddCoxeter& tc) {
SECTION(
"Cr style") {
tc.strategy(options::strategy::Cr);
tc.run();
}
}
void check_Cr_style(fpsemigroup::ToddCoxeter& tc) {
check_Cr_style(tc.congruence());
}
void check_R_over_C_style(congruence::ToddCoxeter& tc) {
SECTION(
"R/C style") {
tc.strategy(options::strategy::R_over_C);
tc.run();
}
}
void check_R_over_C_style(fpsemigroup::ToddCoxeter& tc) {
check_R_over_C_style(tc.congruence());
}
void check_CR_style(congruence::ToddCoxeter& tc) {
SECTION(
"CR style") {
tc.strategy(options::strategy::CR);
tc.run();
}
}
void check_CR_style(fpsemigroup::ToddCoxeter& tc) {
check_CR_style(tc.congruence());
}
// This is how the recursive words up to a given length M, and on an
// arbitrary finite alphabet are generated. On a single letter alphabet,
// this order is just increasing powers of the only generator:
//
// a < aa < aaa < aaaa < ... < aa...a (M times)
//
// With an n-letter alphabet A = {a_1, a_2, ..., a_n}, suppose we have
// already obtained all of the words W_{n - 1} containing {a_1, ..., a_{n
// - 1}}. Every word in W_{n - 1} is less than any word containing a_n,
// and the least word greater than every word in W_{n - 1} is a_n. Words
// greater than a_n are obtain in the follow way, where:
//
// x: is the maximum word in W_{n - 1}, this is constant, in the
// description
// that follows.
// u: the first word obtained in point (1), the first time it is applied
// after (2) has been applied, starting with u = a_{n - 1}.
// v: a word with one fewer letters than u, starting with the empty word.
// w: a word such that w < u, also starting with the empty word.
//
// 1. If v < x, then v is replaced by the next word in the order. If |uv|
// <=
// M, then the next word is uv. Otherwise, goto 1.
//
// 2. If v = x, then and there exists a word w' in the set of words
// obtained
// so far such that w' > w and |w'| <= M - 1, then replace w with w',
// replace u by wa_n, replace v by the empty word, and the next word is
// wa_n.
//
// If no such word w' exists, then we have enumerated all the required
// words, and we can stop.
//
// For example, if A = {a, b} and M = 4, then the initial elements in the
// order are:
//
// e < a < aa < aaa < aaaa (e is the empty word)
//
// Set b > aaaa. At this point, x = aaaa, u = b, v = e, w = e, and so
// (1) applies, v <- a, and since |uv| = ba <= 4 = M, the next word is
// ba. Repeatedly applying (1), until it fails to hold, we obtain the
// following:
//
// aaaa < b < ba < baa < baaa
//
// After defining baa < baaa, x = aaaa, u = b, v = aaaa, and w = e. Hence
// v = x, and so (2) applies. The next w' in the set of words so far
// enumerated is a, and |a| = 1 <= 3 = M - 1, and so w <- a, u <- ab, v <-
// e, and the next word is ab. We repeatedly apply (1), until it fails, to
// obtain
//
// baaa < ab < aba < abaa
//
// At which point u = b, v = aaaa = x, and w = a. Hence (2) applies, w <-
// aa, v <- e, u <- aab, and the next word is: aab. And so on ...
//
// The next function implements this order, returning the words on an
// n-letter alphabet of length up to M.
std::vector<word_type> recursive_path_words(size_t n, size_t M) {
std::vector<word_type> out;
size_t a =
0;
for (size_t i =
0; i < M; ++i) {
out.push_back(word_type(i +
1, a));
}
a++;
int x = out.size();
int u = out.size();
int v = -
1;
// -1 is the empty word
int w = -
1;
// -1 is the empty word
out.push_back({a});
while (a < n) {
if (v < x -
1) {
do {
v++;
}
while (v < x && out[u].size() + out[v].size() > M);
if (v < x && out[u].size() + out[v].size() <= M) {
word_type nxt = out[u];
nxt.insert(nxt.end(), out[v].begin(), out[v].end());
out.push_back(nxt);
}
}
else {
do {
w++;
}
while (
static_cast<size_t>(w) < out.size()
&& out[w].size() +
1 > M);
if (
static_cast<size_t>(w) < out.size()) {
word_type nxt = out[w];
u = out.size();
v = -
1;
nxt.push_back(a);
out.push_back(nxt);
}
else {
a++;
if (a < n) {
x = out.size();
u = out.size();
v = -
1;
w = -
1;
out.push_back({a});
}
}
}
}
return out;
}
void output_gap_benchmark_file(std::string
const& fname,
congruence::ToddCoxeter& tc) {
std::ofstream file;
file.open(fname);
file <<
"local free, rules, R, S, T;\n";
file << tc.to_gap_string();
file <<
"R := RightMagmaCongruenceByGeneratingPairs(S, []);\n";
file <<
"T := CosetTableOfFpSemigroup(R);;\n";
file <<
"Assert(0, Length(T) = Size(GeneratorsOfSemigroup(S)));\n";
file <<
"Assert(0, Length(T[1]) - 1 = "
<< std::to_string(tc.number_of_classes()) <<
");\n";
file.close();
}
}
// namespace
namespace congruence {
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"000",
"small 2-sided congruence",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
1,
1,
1,
1}, {
1});
tc.add_pair({
0,
1,
0,
1}, {
0,
0});
REQUIRE(!tc.finished());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
27);
tc.shrink_to_fit();
auto words
= std::vector<word_type>(tc.cbegin_class(
1,
0,
10), tc.cend_class());
REQUIRE(words
== std::vector<word_type>({word_type({
1}),
word_type({
1,
1,
1,
1}),
word_type({
1,
1,
1,
1,
1,
1,
1})}));
words = std::vector<word_type>(
tc.cbegin_class(word_type({
1,
1,
1,
1}),
0,
10), tc.cend_class());
REQUIRE(words
== std::vector<word_type>({word_type({
1}),
word_type({
1,
1,
1,
1}),
word_type({
1,
1,
1,
1,
1,
1,
1})}));
REQUIRE(tc.number_of_words(
1) == POSITIVE_INFINITY);
std::vector<size_t> class_sizes;
for (size_t i =
0; i < tc.number_of_classes(); ++i) {
class_sizes.push_back(tc.number_of_words(i));
}
REQUIRE(class_sizes
== std::vector<size_t>(tc.number_of_classes(),
size_t(POSITIVE_INFINITY)));
REQUIRE(tc.word_to_class_index(words[
0]) ==
1);
REQUIRE(
std::all_of(words.cbegin(), words.cend(), [&tc](word_type
const& w) {
return tc.word_to_class_index(w) ==
1;
}));
// Too small for lookahead to kick in...
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"001",
"small 2-sided congruence",
"[no-valgrind][todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
// (a^3, a)
tc.add_pair({
0}, {
1,
1});
// (a, b^2)
REQUIRE(!tc.finished());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
5);
REQUIRE(tc.finished());
REQUIRE(!tc.is_standardized());
REQUIRE(tc.word_to_class_index({
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
0,
1,
1,
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
0,
0,
0}) != tc.word_to_class_index({
1}));
tc.standardize(tc_order::lex);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
0,
0}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
0,
0,
1}));
REQUIRE(tc.class_index_to_word(
3) == word_type({
0,
0,
1,
0}));
REQUIRE(tc.word_to_class_index(word_type({
0,
0,
0,
1})) ==
3);
REQUIRE(tc.class_index_to_word(
4) == word_type({
1}));
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
0)) ==
0);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
1)) ==
1);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
2)) ==
2);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
3)) ==
3);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
4)) ==
4);
REQUIRE(tc.word_to_class_index({
0,
1}) ==
3);
REQUIRE(LexicographicalCompare<word_type>{}({
0,
0,
1}, {
0,
1}));
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
LexicographicalCompare<word_type>{}));
tc.standardize(tc_order::shortlex);
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cend_normal_forms())
== std::vector<word_type>({{
0}, {
1}, {
0,
0}, {
0,
1}, {
0,
0,
1}}));
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
0)) ==
0);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
1)) ==
1);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
2)) ==
2);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
3)) ==
3);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
4)) ==
4);
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
ShortLexCompare<word_type>{}));
auto nf = std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cend_normal_forms());
REQUIRE(nf
== std::vector<word_type>({{
0}, {
1}, {
0,
0}, {
0,
1}, {
0,
0,
1}}));
REQUIRE(std::all_of(nf.begin(), nf.end(), [&tc](word_type& w) {
return w == *tc.cbegin_class(w,
0, w.size() +
1);
}));
for (size_t i =
2; i <
6; ++i) {
for (size_t j =
2; j <
10 - i; ++j) {
auto v = std::vector<word_type>(
cbegin_wislo(i, {
0}, word_type(j +
1,
0)),
cend_wislo(i, {
0}, word_type(j +
1,
0)));
std::sort(v.begin(), v.end(), RecursivePathCompare<word_type>{});
REQUIRE(v == recursive_path_words(i, j));
}
}
tc.standardize(tc_order::recursive);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
0,
0}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
1}));
REQUIRE(tc.class_index_to_word(
3) == word_type({
1,
0}));
REQUIRE(tc.class_index_to_word(
4) == word_type({
1,
0,
0}));
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
RecursivePathCompare<word_type>{}));
}
// Felsch is actually faster here!
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"002",
"Example 6.6 in Sims (see also KnuthBendix 013)",
"[todd-coxeter][standard]") {
using TCE = detail::TCE;
using FroidurePinTCE
= FroidurePin<TCE, FroidurePinTraits<TCE, TCE::Table>>;
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(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});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
10'752);
REQUIRE(tc.complete());
REQUIRE(tc.compatible());
// Take a copy to test copy constructor
auto& S =
static_cast<FroidurePinTCE&>(*tc.quotient_froidure_pin());
auto T = S.copy_closure({S.generator(
0)});
REQUIRE(T.size() == S.size());
REQUIRE(T.number_of_generators() == S.number_of_generators());
REQUIRE(S.size() ==
10'752);
REQUIRE(S.number_of_idempotents() ==
1);
for (size_t c =
0; c < tc.number_of_classes(); ++c) {
REQUIRE(tc.class_index_to_word(c) == S.factorisation(c));
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
}
REQUIRE(tc.finished());
tc.standardize(tc_order::recursive);
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
RecursivePathCompare<word_type>{}));
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cbegin_normal_forms() +
10)
== std::vector<word_type>({{{
0},
{
1},
{
2},
{
2,
1},
{
1,
2},
{
1,
2,
1},
{
2,
2},
{
2,
2,
1},
{
2,
1,
2},
{
2,
1,
2,
1}}}));
tc.standardize(tc_order::lex);
for (size_t c =
0; c < tc.number_of_classes(); ++c) {
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
}
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
LexicographicalCompare<word_type>{}));
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cbegin_normal_forms() +
10)
== std::vector<word_type>({{
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}}));
tc.standardize(tc_order::shortlex);
for (size_t c =
0; c < tc.number_of_classes(); ++c) {
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
}
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
ShortLexCompare<word_type>{}));
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cbegin_normal_forms() +
10)
== std::vector<word_type>({{
0},
{
1},
{
2},
{
3},
{
1,
2},
{
1,
3},
{
2,
1},
{
3,
1},
{
1,
2,
1},
{
1,
3,
1}}));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"003",
"constructed from FroidurePin",
"[no-valgrind][todd-coxeter][quick][no-coverage]") {
auto rg = ReportGuard(REPORT);
FroidurePin<BMat8> S(
{BMat8({{
0,
1,
0,
0}, {
1,
0,
0,
0}, {
0,
0,
1,
0}, {
0,
0,
0,
1}}),
BMat8({{
0,
1,
0,
0}, {
0,
0,
1,
0}, {
0,
0,
0,
1}, {
1,
0,
0,
0}}),
BMat8({{
1,
0,
0,
0}, {
0,
1,
0,
0}, {
0,
0,
1,
0}, {
1,
0,
0,
1}}),
BMat8({{
1,
0,
0,
0}, {
0,
1,
0,
0}, {
0,
0,
1,
0}, {
0,
0,
0,
0}})});
ToddCoxeter tc(twosided, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair({
0}, {
1});
check_felsch(tc);
check_hlt(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
tc.random_interval(std::chrono::milliseconds(
100));
tc.lower_bound(
3);
tc.run();
REQUIRE(tc.complete());
REQUIRE(tc.compatible());
REQUIRE(tc.number_of_classes() ==
3);
// REQUIRE(tc.number_of_generators() == 4);
REQUIRE(tc.contains({
0}, {
1}));
tc.standardize(tc_order::shortlex);
REQUIRE(tc.contains({
0}, {
1}));
tc.shrink_to_fit();
REQUIRE(tc.contains({
0}, {
1}));
auto& T = *tc.quotient_froidure_pin();
REQUIRE(T.size() ==
3);
REQUIRE(tc.class_index_to_word(
0) == T.factorisation(
0));
REQUIRE(tc.class_index_to_word(
1) == T.factorisation(
1));
REQUIRE(tc.class_index_to_word(
2) == T.factorisation(
2));
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
2}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
0,
0}));
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
0)) ==
0);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
1)) ==
1);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
2)) ==
2);
tc.standardize(tc_order::lex);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
0,
0}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
0,
0,
2}));
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
0)) ==
0);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
1)) ==
1);
REQUIRE(tc.word_to_class_index(tc.class_index_to_word(
2)) ==
2);
tc.standardize(tc_order::shortlex);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
2}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
0,
0}));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"004",
"2-sided congruence from FroidurePin",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
using Transf = LeastTransf<
5>;
FroidurePin<Transf> S({Transf({
1,
3,
4,
2,
3}), Transf({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
ToddCoxeter tc(twosided, S);
tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
tc.add_pair(S.factorisation(Transf({
3,
4,
4,
4,
4})),
S.factorisation(Transf({
3,
1,
3,
3,
3})));
REQUIRE(!tc.finished());
tc.shrink_to_fit();
// does nothing
REQUIRE(!tc.finished());
tc.standardize(tc_order::none);
// does nothing
REQUIRE(!tc.finished());
check_hlt_no_save(tc);
check_hlt_save_throws(tc);
check_felsch_throws(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() ==
21);
tc.shrink_to_fit();
REQUIRE(tc.number_of_classes() ==
21);
tc.standardize(tc_order::recursive);
auto w = std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cend_normal_forms());
REQUIRE(w.size() ==
21);
REQUIRE(w
== std::vector<word_type>({{
0},
{
0,
0},
{
0,
0,
0},
{
0,
0,
0,
0},
{
1},
{
1,
0},
{
1,
0,
0},
{
1,
0,
0,
0},
{
0,
1},
{
0,
1,
0},
{
0,
1,
0,
0},
{
0,
1,
0,
0,
0},
{
0,
0,
1},
{
1,
1},
{
1,
1,
0},
{
1,
1,
0,
0},
{
1,
1,
0,
0,
0},
{
0,
1,
1},
{
0,
1,
1,
0},
{
0,
1,
1,
0,
0},
{
0,
1,
1,
0,
0,
0}}));
REQUIRE(std::unique(w.begin(), w.end()) == w.end());
REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
RecursivePathCompare<word_type>{}));
REQUIRE(std::all_of(
tc.cbegin_normal_forms(),
tc.cend_normal_forms(),
[&tc](word_type
const& ww) ->
bool {
return tc.class_index_to_word(tc.word_to_class_index(ww)) == ww;
}));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"005",
"non-trivial two-sided from relations",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
3);
tc.add_pair({
0,
1}, {
1,
0});
tc.add_pair({
0,
2}, {
2,
2});
tc.add_pair({
0,
2}, {
0});
tc.add_pair({
2,
2}, {
0});
tc.add_pair({
1,
2}, {
1,
2});
tc.add_pair({
1,
2}, {
2,
2});
tc.add_pair({
1,
2,
2}, {
1});
tc.add_pair({
1,
2}, {
1});
tc.add_pair({
2,
2}, {
1});
tc.add_pair({
0}, {
1});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
2);
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"006",
"small right cong. on free semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(right);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0}, {
1,
1});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
5);
REQUIRE(tc.finished());
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"007",
"left cong. on free semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
ToddCoxeter tc(left);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0}, {
1,
1});
tc.growth_factor(
1.
5);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(!tc.is_standardized());
REQUIRE(tc.word_to_class_index({
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
0,
1,
1,
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
1})
!= tc.word_to_class_index({
0,
0,
0,
0}));
REQUIRE(tc.word_to_class_index({
0,
0,
0})
!= tc.word_to_class_index({
0,
0,
0,
0}));
tc.standardize(tc_order::shortlex);
REQUIRE(tc.is_standardized());
}
{
ToddCoxeter tc(left);
REQUIRE_NOTHROW(ToddCoxeter(left, tc));
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"008",
"for small fp semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
// (a^3, a)
tc.add_pair({
0}, {
1,
1});
// (a, b^2)
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.word_to_class_index({
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
0,
1,
1,
0,
0,
1})
== tc.word_to_class_index({
0,
0,
0,
0,
1}));
REQUIRE(tc.word_to_class_index({
0,
0,
0}) != tc.word_to_class_index({
1}));
REQUIRE(tc.word_to_class_index({
0,
0,
0,
0}) < tc.number_of_classes());
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"009",
"2-sided cong. trans. semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
auto S = FroidurePin<Transf<>>(
{Transf<>({
1,
3,
4,
2,
3}), Transf<>({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
ToddCoxeter tc(twosided, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair(S.factorisation(Transf<>({
3,
4,
4,
4,
4})),
S.factorisation(Transf<>({
3,
1,
3,
3,
3})));
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
21);
REQUIRE(tc.number_of_classes() ==
21);
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
1,
3,
1,
3,
3})))
== tc.word_to_class_index(
S.factorisation(Transf<>({
4,
2,
4,
4,
2}))));
tc.standardize(tc_order::shortlex);
REQUIRE(tc.number_of_non_trivial_classes() ==
1);
REQUIRE(tc.cbegin_ntc()->size() ==
68);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"010",
"left congruence on transformation semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
auto S = FroidurePin<Transf<>>(
{Transf<>({
1,
3,
4,
2,
3}), Transf<>({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
ToddCoxeter tc(left, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair(S.factorisation(Transf<>({
3,
4,
4,
4,
4})),
S.factorisation(Transf<>({
3,
1,
3,
3,
3})));
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
69);
REQUIRE(tc.number_of_classes() ==
69);
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
1,
3,
1,
3,
3})))
!= tc.word_to_class_index(
S.factorisation(Transf<>({
4,
2,
4,
4,
2}))));
tc.standardize(tc_order::shortlex);
REQUIRE(tc.number_of_non_trivial_classes() ==
1);
REQUIRE(tc.cbegin_ntc()->size() ==
20);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"011",
"right cong. trans. semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
auto S = FroidurePin<Transf<>>(
{Transf<>({
1,
3,
4,
2,
3}), Transf<>({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
ToddCoxeter tc(right, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair(S.factorisation(Transf<>({
3,
4,
4,
4,
4})),
S.factorisation(Transf<>({
3,
1,
3,
3,
3})));
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
72);
REQUIRE(tc.number_of_classes() ==
72);
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
1,
3,
1,
3,
3})))
!= tc.word_to_class_index(
S.factorisation(Transf<>({
4,
2,
4,
4,
2}))));
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
1,
3,
3,
3,
3})))
!= tc.word_to_class_index(
S.factorisation(Transf<>({
4,
2,
4,
4,
2}))));
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
2,
4,
2,
2,
2})))
== tc.word_to_class_index(
S.factorisation(Transf<>({
2,
3,
3,
3,
3}))));
REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({
1,
3,
3,
3,
3})))
!= tc.word_to_class_index(
S.factorisation(Transf<>({
2,
3,
3,
3,
3}))));
tc.standardize(tc_order::shortlex);
REQUIRE(tc.number_of_non_trivial_classes() ==
4);
std::vector<size_t> v(tc.number_of_non_trivial_classes(),
0);
std::transform(tc.cbegin_ntc(),
tc.cend_ntc(),
v.begin(),
std::mem_fn(&std::vector<word_type>::size));
REQUIRE(std::count(v.cbegin(), v.cend(),
3) ==
1);
REQUIRE(std::count(v.cbegin(), v.cend(),
5) ==
2);
REQUIRE(std::count(v.cbegin(), v.cend(),
7) ==
1);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"012",
"trans. semigroup (size 88)",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
FroidurePin<Transf<>> S;
S.add_generator(Transf<>({
1,
3,
4,
2,
3}));
S.add_generator(Transf<>({
3,
2,
1,
3,
3}));
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
REQUIRE(S.degree() ==
5);
ToddCoxeter tc(twosided, S);
tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
word_type w1, w2;
S.factorisation(w1, S.position(Transf<>({
3,
4,
4,
4,
4})));
S.factorisation(w2, S.position(Transf<>({
3,
1,
3,
3,
3})));
tc.add_pair(w1, w2);
check_hlt_no_save(tc);
check_hlt_save_throws(tc);
check_felsch_throws(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() ==
21);
REQUIRE(tc.number_of_classes() ==
21);
word_type w3, w4;
S.factorisation(w3, S.position(Transf<>({
1,
3,
1,
3,
3})));
S.factorisation(w4, S.position(Transf<>({
4,
2,
4,
4,
2})));
REQUIRE(tc.word_to_class_index(w3) == tc.word_to_class_index(w4));
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"013",
"left cong. on trans. semigroup (size 88)",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
FroidurePin<Transf<>> S;
S.add_generator(Transf<>({
1,
3,
4,
2,
3}));
S.add_generator(Transf<>({
3,
2,
1,
3,
3}));
REQUIRE(S.size() ==
88);
REQUIRE(S.degree() ==
5);
word_type w1, w2;
S.factorisation(w1, S.position(Transf<>({
3,
4,
4,
4,
4})));
S.factorisation(w2, S.position(Transf<>({
3,
1,
3,
3,
3})));
ToddCoxeter tc(left, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair(w1, w2);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
69);
REQUIRE(tc.number_of_classes() ==
69);
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"014",
"right cong. on trans. semigroup (size 88)",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
FroidurePin<Transf<>> S;
S.add_generator(Transf<>({
1,
3,
4,
2,
3}));
S.add_generator(Transf<>({
3,
2,
1,
3,
3}));
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
REQUIRE(S.degree() ==
5);
word_type w1, w2;
S.factorisation(w1, S.position(Transf<>({
3,
4,
4,
4,
4})));
S.factorisation(w2, S.position(Transf<>({
3,
1,
3,
3,
3})));
ToddCoxeter tc(right, S);
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.add_pair(w1, w2);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
72);
REQUIRE(tc.number_of_classes() ==
72);
word_type w3, w4, w5, w6;
S.factorisation(w3, S.position(Transf<>({
1,
3,
3,
3,
3})));
S.factorisation(w4, S.position(Transf<>({
4,
2,
4,
4,
2})));
S.factorisation(w5, S.position(Transf<>({
2,
4,
2,
2,
2})));
S.factorisation(w6, S.position(Transf<>({
2,
3,
3,
3,
3})));
REQUIRE(tc.word_to_class_index(w3) != tc.word_to_class_index(w4));
REQUIRE(tc.word_to_class_index(w5) == tc.word_to_class_index(w6));
REQUIRE(tc.word_to_class_index(w3) != tc.word_to_class_index(w6));
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"015",
"finite fp-semigroup, dihedral group of order 6",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
5);
tc.add_pair({
0,
0}, {
0});
tc.add_pair({
0,
1}, {
1});
tc.add_pair({
1,
0}, {
1});
tc.add_pair({
0,
2}, {
2});
tc.add_pair({
2,
0}, {
2});
tc.add_pair({
0,
3}, {
3});
tc.add_pair({
3,
0}, {
3});
tc.add_pair({
0,
4}, {
4});
tc.add_pair({
4,
0}, {
4});
tc.add_pair({
1,
2}, {
0});
tc.add_pair({
2,
1}, {
0});
tc.add_pair({
3,
4}, {
0});
tc.add_pair({
4,
3}, {
0});
tc.add_pair({
2,
2}, {
0});
tc.add_pair({
1,
4,
2,
3,
3}, {
0});
tc.add_pair({
4,
4,
4}, {
0});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
6);
REQUIRE(tc.word_to_class_index({
1}) == tc.word_to_class_index({
2}));
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"016",
"finite fp-semigroup, size 16",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
4);
tc.add_pair({
3}, {
2});
tc.add_pair({
0,
3}, {
0,
2});
tc.add_pair({
1,
1}, {
1});
tc.add_pair({
1,
3}, {
1,
2});
tc.add_pair({
2,
1}, {
2});
tc.add_pair({
2,
2}, {
2});
tc.add_pair({
2,
3}, {
2});
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0,
0,
1}, {
1});
tc.add_pair({
0,
0,
2}, {
2});
tc.add_pair({
0,
1,
2}, {
1,
2});
tc.add_pair({
1,
0,
0}, {
1});
tc.add_pair({
1,
0,
2}, {
0,
2});
tc.add_pair({
2,
0,
0}, {
2});
tc.add_pair({
0,
1,
0,
1}, {
1,
0,
1});
tc.add_pair({
0,
2,
0,
2}, {
2,
0,
2});
tc.add_pair({
1,
0,
1,
0}, {
1,
0,
1});
tc.add_pair({
1,
2,
0,
1}, {
1,
0,
1});
tc.add_pair({
1,
2,
0,
2}, {
2,
0,
2});
tc.add_pair({
2,
0,
1,
0}, {
2,
0,
1});
tc.add_pair({
2,
0,
2,
0}, {
2,
0,
2});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
16);
REQUIRE(tc.word_to_class_index({
2}) == tc.word_to_class_index({
3}));
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"017",
"finite fp-semigroup, size 16",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
11);
tc.add_pair({
2}, {
1});
tc.add_pair({
4}, {
3});
tc.add_pair({
5}, {
0});
tc.add_pair({
6}, {
3});
tc.add_pair({
7}, {
1});
tc.add_pair({
8}, {
3});
tc.add_pair({
9}, {
3});
tc.add_pair({
10}, {
0});
tc.add_pair({
0,
2}, {
0,
1});
tc.add_pair({
0,
4}, {
0,
3});
tc.add_pair({
0,
5}, {
0,
0});
tc.add_pair({
0,
6}, {
0,
3});
tc.add_pair({
0,
7}, {
0,
1});
tc.add_pair({
0,
8}, {
0,
3});
tc.add_pair({
0,
9}, {
0,
3});
tc.add_pair({
0,
10}, {
0,
0});
tc.add_pair({
1,
1}, {
1});
tc.add_pair({
1,
2}, {
1});
tc.add_pair({
1,
4}, {
1,
3});
tc.add_pair({
1,
5}, {
1,
0});
tc.add_pair({
1,
6}, {
1,
3});
tc.add_pair({
1,
7}, {
1});
tc.add_pair({
1,
8}, {
1,
3});
tc.add_pair({
1,
9}, {
1,
3});
tc.add_pair({
1,
10}, {
1,
0});
tc.add_pair({
3,
1}, {
3});
tc.add_pair({
3,
2}, {
3});
tc.add_pair({
3,
3}, {
3});
tc.add_pair({
3,
4}, {
3});
tc.add_pair({
3,
5}, {
3,
0});
tc.add_pair({
3,
6}, {
3});
tc.add_pair({
3,
7}, {
3});
tc.add_pair({
3,
8}, {
3});
tc.add_pair({
3,
9}, {
3});
tc.add_pair({
3,
10}, {
3,
0});
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0,
0,
1}, {
1});
tc.add_pair({
0,
0,
3}, {
3});
tc.add_pair({
0,
1,
3}, {
1,
3});
tc.add_pair({
1,
0,
0}, {
1});
tc.add_pair({
1,
0,
3}, {
0,
3});
tc.add_pair({
3,
0,
0}, {
3});
tc.add_pair({
0,
1,
0,
1}, {
1,
0,
1});
tc.add_pair({
0,
3,
0,
3}, {
3,
0,
3});
tc.add_pair({
1,
0,
1,
0}, {
1,
0,
1});
tc.add_pair({
1,
3,
0,
1}, {
1,
0,
1});
tc.add_pair({
1,
3,
0,
3}, {
3,
0,
3});
tc.add_pair({
3,
0,
1,
0}, {
3,
0,
1});
tc.add_pair({
3,
0,
3,
0}, {
3,
0,
3});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
16);
REQUIRE(tc.word_to_class_index({
0}) == tc.word_to_class_index({
5}));
REQUIRE(tc.word_to_class_index({
0}) == tc.word_to_class_index({
10}));
REQUIRE(tc.word_to_class_index({
1}) == tc.word_to_class_index({
2}));
REQUIRE(tc.word_to_class_index({
1}) == tc.word_to_class_index({
7}));
REQUIRE(tc.word_to_class_index({
3}) == tc.word_to_class_index({
4}));
REQUIRE(tc.word_to_class_index({
3}) == tc.word_to_class_index({
6}));
REQUIRE(tc.word_to_class_index({
3}) == tc.word_to_class_index({
8}));
REQUIRE(tc.word_to_class_index({
3}) == tc.word_to_class_index({
9}));
tc.standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"018",
"test lookahead",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.next_lookahead(
10);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
1,
0,
0}, {
1,
0});
tc.add_pair({
1,
0,
1,
1,
1}, {
1,
0});
tc.add_pair({
1,
1,
1,
1,
1}, {
1,
1});
tc.add_pair({
1,
1,
0,
1,
1,
0}, {
1,
0,
1,
0,
1,
1});
tc.add_pair({
0,
0,
1,
0,
1,
1,
0}, {
0,
1,
0,
1,
1,
0});
tc.add_pair({
0,
0,
1,
1,
0,
1,
0}, {
0,
1,
1,
0,
1,
0});
tc.add_pair({
0,
1,
0,
1,
0,
1,
0}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
0,
1,
0,
1,
0,
1}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
0,
1,
0,
1,
1,
0}, {
1,
0,
1,
0,
1,
1});
tc.add_pair({
1,
0,
1,
1,
0,
1,
0}, {
1,
0,
1,
1,
0,
1});
tc.add_pair({
1,
1,
0,
1,
0,
1,
0}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
1,
1,
1,
0,
1,
0}, {
1,
0,
1,
0});
tc.add_pair({
0,
0,
1,
1,
1,
0,
1,
0}, {
1,
1,
1,
0,
1,
0});
check_hlt(tc);
REQUIRE(tc.number_of_classes() ==
78);
tc.standardize(tc_order::shortlex);
}
{
ToddCoxeter tc(left);
tc.set_number_of_generators(
2);
tc.next_lookahead(
10);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
1,
0,
0}, {
1,
0});
tc.add_pair({
1,
0,
1,
1,
1}, {
1,
0});
tc.add_pair({
1,
1,
1,
1,
1}, {
1,
1});
tc.add_pair({
1,
1,
0,
1,
1,
0}, {
1,
0,
1,
0,
1,
1});
tc.add_pair({
0,
0,
1,
0,
1,
1,
0}, {
0,
1,
0,
1,
1,
0});
tc.add_pair({
0,
0,
1,
1,
0,
1,
0}, {
0,
1,
1,
0,
1,
0});
tc.add_pair({
0,
1,
0,
1,
0,
1,
0}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
0,
1,
0,
1,
0,
1}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
0,
1,
0,
1,
1,
0}, {
1,
0,
1,
0,
1,
1});
tc.add_pair({
1,
0,
1,
1,
0,
1,
0}, {
1,
0,
1,
1,
0,
1});
tc.add_pair({
1,
1,
0,
1,
0,
1,
0}, {
1,
0,
1,
0,
1,
0});
tc.add_pair({
1,
1,
1,
1,
0,
1,
0}, {
1,
0,
1,
0});
tc.add_pair({
0,
0,
1,
1,
1,
0,
1,
0}, {
1,
1,
1,
0,
1,
0});
check_hlt(tc);
REQUIRE(tc.number_of_classes() ==
78);
tc.standardize(tc_order::shortlex);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"019",
"non-trivial left cong. from semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
FroidurePin<Transf<>> S;
S.add_generator(Transf<>({
1,
3,
4,
2,
3}));
S.add_generator(Transf<>({
3,
2,
1,
3,
3}));
REQUIRE(S.size() ==
88);
REQUIRE(S.degree() ==
5);
word_type w1, w2;
S.factorisation(w1, S.position(Transf<>({
3,
4,
4,
4,
4})));
S.factorisation(w2, S.position(Transf<>({
3,
1,
3,
3,
3})));
ToddCoxeter tc(left, S);
tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
tc.add_pair(w1, w2);
check_hlt_no_save(tc);
check_hlt_save_throws(tc);
check_felsch_throws(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() ==
69);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"020",
"2-sided cong. on free semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
1);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
REQUIRE(tc.contains({
0,
0}, {
0,
0}));
REQUIRE(!tc.contains({
0,
0}, {
0}));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"021",
"calling run when obviously infinite",
"[todd-coxeter][quick]") {
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
5);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
REQUIRE_THROWS_AS(tc.run(), LibsemigroupsException);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"022",
"stellar_monoid S3",
"[todd-coxeter][quick][hivert]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
4);
tc.add_pair({
3,
3}, {
3});
tc.add_pair({
0,
3}, {
0});
tc.add_pair({
3,
0}, {
0});
tc.add_pair({
1,
3}, {
1});
tc.add_pair({
3,
1}, {
1});
tc.add_pair({
2,
3}, {
2});
tc.add_pair({
3,
2}, {
2});
tc.add_pair({
0,
0}, {
0});
tc.add_pair({
1,
1}, {
1});
tc.add_pair({
2,
2}, {
2});
tc.add_pair({
0,
2}, {
2,
0});
tc.add_pair({
2,
0}, {
0,
2});
tc.add_pair({
1,
2,
1}, {
2,
1,
2});
tc.add_pair({
1,
0,
1,
0}, {
0,
1,
0,
1});
tc.add_pair({
1,
0,
1,
0}, {
0,
1,
0});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
34);
REQUIRE(tc.quotient_froidure_pin()->size() ==
34);
using froidure_pin_type =
typename ToddCoxeter::froidure_pin_type;
using detail::TCE;
auto& S =
static_cast<froidure_pin_type&>(*tc.quotient_froidure_pin());
S.run();
std::vector<TCE> v(S.cbegin(), S.cend());
std::sort(v.begin(), v.end());
REQUIRE(v
== std::vector<TCE>({TCE(
1), TCE(
2), TCE(
3), TCE(
4), TCE(
5),
TCE(
6), TCE(
7), TCE(
8), TCE(
9), TCE(
10),
TCE(
11), TCE(
12), TCE(
13), TCE(
14), TCE(
15),
TCE(
16), TCE(
17), TCE(
18), TCE(
19), TCE(
20),
TCE(
21), TCE(
22), TCE(
23), TCE(
24), TCE(
25),
TCE(
26), TCE(
27), TCE(
28), TCE(
29), TCE(
30),
TCE(
31), TCE(
32), TCE(
33), TCE(
34)}));
REQUIRE(std::vector<TCE>(S.cbegin_sorted(), S.cend_sorted())
== std::vector<TCE>({TCE(
1), TCE(
2), TCE(
3), TCE(
4), TCE(
5),
TCE(
6), TCE(
7), TCE(
8), TCE(
9), TCE(
10),
TCE(
11), TCE(
12), TCE(
13), TCE(
14), TCE(
15),
TCE(
16), TCE(
17), TCE(
18), TCE(
19), TCE(
20),
TCE(
21), TCE(
22), TCE(
23), TCE(
24), TCE(
25),
TCE(
26), TCE(
27), TCE(
28), TCE(
29), TCE(
30),
TCE(
31), TCE(
32), TCE(
33), TCE(
34)}));
REQUIRE(detail::to_string(TCE(
1)) ==
"1");
REQUIRE_NOTHROW(IncreaseDegree<TCE>()(TCE(
1),
10));
std::ostringstream oss;
oss << TCE(
10);
// Does not do anything visible
std::stringbuf buf;
std::ostream os(&buf);
os << TCE(
32);
// Does not do anything visible
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"023",
"finite semigroup (size 5)",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
congruence::ToddCoxeter tc(left);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
// (a^3, a)
tc.add_pair({
0}, {
1,
1});
// (a, b^2)
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
5);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"024",
"exceptions",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
congruence::ToddCoxeter tc1(left);
tc1.set_number_of_generators(
2);
tc1.add_pair({
0,
0,
0}, {
0});
tc1.add_pair({
0}, {
1,
1});
REQUIRE(tc1.number_of_classes() ==
5);
REQUIRE_THROWS_AS(ToddCoxeter(right, tc1), LibsemigroupsException);
REQUIRE_THROWS_AS(ToddCoxeter(twosided, tc1), LibsemigroupsException);
ToddCoxeter tc2(left, tc1);
REQUIRE(!tc1.contains({
0}, {
1}));
tc2.add_pair({
0}, {
1});
check_hlt(tc2);
check_felsch(tc2);
check_random(tc2);
check_Rc_style(tc2);
check_R_over_C_style(tc2);
check_CR_style(tc2);
check_Cr_style(tc2);
REQUIRE(tc2.number_of_classes() ==
1);
ToddCoxeter tc3(left);
tc3.set_number_of_generators(
2);
tc3.add_pair({
0,
0,
0}, {
0});
tc3.add_pair({
0}, {
1,
1});
tc3.add_pair({
0}, {
1});
REQUIRE(tc3.number_of_classes() ==
1);
}
{
congruence::ToddCoxeter tc1(right);
tc1.set_number_of_generators(
2);
tc1.add_pair({
0,
0,
0}, {
0});
tc1.add_pair({
0}, {
1,
1});
REQUIRE(tc1.number_of_classes() ==
5);
REQUIRE_THROWS_AS(ToddCoxeter(left, tc1), LibsemigroupsException);
REQUIRE_THROWS_AS(ToddCoxeter(twosided, tc1), LibsemigroupsException);
ToddCoxeter tc2(right, tc1);
REQUIRE(!tc1.contains({
0}, {
1}));
tc2.add_pair({
0}, {
1});
check_hlt(tc2);
check_felsch(tc2);
check_random(tc2);
check_Rc_style(tc2);
check_R_over_C_style(tc2);
check_CR_style(tc2);
check_Cr_style(tc2);
REQUIRE(tc2.number_of_classes() ==
1);
ToddCoxeter tc3(right);
tc3.set_number_of_generators(
2);
tc3.add_pair({
0,
0,
0}, {
0});
tc3.add_pair({
0}, {
1,
1});
tc3.add_pair({
0}, {
1});
REQUIRE(tc3.number_of_classes() ==
1);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"025",
"obviously infinite",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
congruence::ToddCoxeter tc(left);
tc.set_number_of_generators(
3);
tc.add_pair({
0,
0,
0}, {
0});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
REQUIRE(!tc.is_quotient_obviously_finite());
}
{
congruence::ToddCoxeter tc(right);
tc.set_number_of_generators(
3);
tc.add_pair({
0,
0,
0}, {
0});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
REQUIRE(!tc.is_quotient_obviously_finite());
}
{
congruence::ToddCoxeter tc(twosided);
tc.set_number_of_generators(
3);
tc.add_pair({
0,
0,
0}, {
0});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
REQUIRE(!tc.is_quotient_obviously_finite());
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"026",
"exceptions",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
congruence::ToddCoxeter tc(right);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0}, {
1,
1});
check_hlt(tc);
check_felsch(tc);
REQUIRE(tc.number_of_classes() ==
5);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
// This next one should throw
REQUIRE_THROWS_AS(tc.quotient_froidure_pin(), LibsemigroupsException);
}
{
congruence::ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0,
0}, {
0});
tc.add_pair({
0}, {
1,
1});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
5);
REQUIRE(tc.class_index_to_word(
0) == word_type({
0}));
REQUIRE(tc.class_index_to_word(
1) == word_type({
1}));
REQUIRE(tc.class_index_to_word(
2) == word_type({
0,
0}));
REQUIRE(tc.class_index_to_word(
3) == word_type({
0,
1}));
REQUIRE(tc.class_index_to_word(
4) == word_type({
0,
0,
1}));
REQUIRE_THROWS_AS(tc.class_index_to_word(
5), LibsemigroupsException);
REQUIRE_THROWS_AS(tc.class_index_to_word(
100), LibsemigroupsException);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"027",
"empty",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
congruence::ToddCoxeter tc(left);
REQUIRE(tc.empty());
tc.set_number_of_generators(
3);
REQUIRE(tc.empty());
tc.add_pair({
0}, {
2});
REQUIRE(tc.empty());
tc.reserve(
100);
tc.reserve(
200);
REQUIRE(tc.empty());
}
{
FroidurePin<BMat8> S(
{BMat8({{
0,
1,
0,
0}, {
1,
0,
0,
0}, {
0,
0,
1,
0}, {
0,
0,
0,
1}})});
ToddCoxeter tc(twosided, S);
REQUIRE(tc.empty());
tc.add_pair({
0}, {
0,
0});
REQUIRE(tc.empty());
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"028",
"congruence of fpsemigroup::ToddCoxeter",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
fpsemigroup::ToddCoxeter tc1;
tc1.set_alphabet(
"ab");
tc1.add_rule(
"aaa",
"a");
tc1.add_rule(
"a",
"bb");
REQUIRE(tc1.size() ==
5);
congruence::ToddCoxeter tc2(left, tc1);
REQUIRE(tc2.empty());
tc2.add_pair({
0}, {
1});
REQUIRE_THROWS_AS(tc2.add_pair({
0}, {
2}), LibsemigroupsException);
check_hlt_no_save(tc2);
check_hlt_save_throws(tc2);
check_felsch_throws(tc2);
check_random(tc2);
REQUIRE(tc2.number_of_classes() ==
1);
}
{
fpsemigroup::ToddCoxeter tc1;
tc1.set_alphabet(
"ab");
tc1.add_rule(
"aaa",
"a");
tc1.add_rule(
"a",
"bb");
congruence::ToddCoxeter tc2(left, tc1);
tc2.add_pair({
0}, {
1});
check_hlt(tc2);
check_felsch(tc2);
check_random(tc2);
check_Rc_style(tc2);
check_R_over_C_style(tc2);
check_CR_style(tc2);
check_Cr_style(tc2);
REQUIRE(!tc2.empty());
REQUIRE_THROWS_AS(tc2.add_pair({
0}, {
2}), LibsemigroupsException);
REQUIRE(tc2.number_of_classes() ==
1);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"029",
"!KnuthBendix.started()",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
fpsemigroup::KnuthBendix kb;
kb.set_alphabet(
"abB");
kb.add_rule(
"bb",
"B");
kb.add_rule(
"BaB",
"aba");
REQUIRE(!kb.confluent());
REQUIRE(!kb.started());
std::unique_ptr<ToddCoxeter> tc = nullptr;
SECTION(
"2-sided") {
tc = std::make_unique<ToddCoxeter>(twosided, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
SECTION(
"left") {
tc = std::make_unique<ToddCoxeter>(left, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
SECTION(
"right") {
tc = std::make_unique<ToddCoxeter>(left, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
REQUIRE(!tc->has_parent_froidure_pin());
tc->add_pair({
1}, {
2});
REQUIRE(tc->is_quotient_obviously_infinite());
REQUIRE(tc->number_of_classes() == POSITIVE_INFINITY);
REQUIRE(std::vector<relation_type>(tc->cbegin_generating_pairs(),
tc->cend_generating_pairs())
== std::vector<relation_type>(
{{{
1,
1}, {
2}}, {{
2,
0,
2}, {
0,
1,
0}}, {{
1}, {
2}}}));
REQUIRE(!tc->finished());
REQUIRE(!tc->started());
tc->add_pair({
1}, {
0});
REQUIRE(!tc->is_quotient_obviously_infinite());
REQUIRE(tc->number_of_classes() ==
1);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"030",
"KnuthBendix.finished()",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
fpsemigroup::KnuthBendix kb;
kb.set_alphabet(
"abB");
kb.add_rule(
"bb",
"B");
kb.add_rule(
"BaB",
"aba");
REQUIRE(!kb.confluent());
kb.run();
REQUIRE(kb.confluent());
REQUIRE(kb.number_of_active_rules() ==
6);
REQUIRE(kb.finished());
std::unique_ptr<ToddCoxeter> tc = nullptr;
SECTION(
"2-sided") {
tc = std::make_unique<ToddCoxeter>(twosided, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
SECTION(
"left") {
tc = std::make_unique<ToddCoxeter>(left, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
SECTION(
"right") {
tc = std::make_unique<ToddCoxeter>(right, kb);
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
// Don't use the other check_* functions because they run to avoid an
// issue with fpsemigroup::ToddCoxeter.
}
REQUIRE(tc->has_parent_froidure_pin());
tc->add_pair({
1}, {
2});
REQUIRE(tc->is_quotient_obviously_infinite());
REQUIRE(tc->number_of_classes() == POSITIVE_INFINITY);
REQUIRE(std::vector<relation_type>(tc->cbegin_generating_pairs(),
tc->cend_generating_pairs())
== std::vector<relation_type>(
{{{
1,
1}, {
2}}, {{
2,
0,
2}, {
0,
1,
0}}, {{
1}, {
2}}}));
tc->add_pair({
1}, {
0});
REQUIRE(!tc->is_quotient_obviously_infinite());
REQUIRE(tc->number_of_classes() ==
1);
if (tc->kind() == twosided) {
REQUIRE(tc->quotient_froidure_pin()->size() ==
1);
}
else {
REQUIRE_THROWS_AS(tc->quotient_froidure_pin(), LibsemigroupsException);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"031",
"KnuthBendix.finished()",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
fpsemigroup::KnuthBendix kb;
kb.set_alphabet(
"abB");
kb.add_rule(
"bb",
"B");
kb.add_rule(
"BaB",
"aba");
kb.add_rule(
"a",
"b");
kb.add_rule(
"b",
"B");
REQUIRE(kb.confluent());
kb.run();
REQUIRE(kb.confluent());
REQUIRE(kb.number_of_active_rules() ==
3);
REQUIRE(kb.size() ==
1);
REQUIRE(kb.is_obviously_finite());
REQUIRE(kb.finished());
std::unique_ptr<ToddCoxeter> tc = nullptr;
SECTION(
"2-sided") {
tc = std::make_unique<ToddCoxeter>(twosided, kb);
tc->add_pair({
1}, {
2});
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
check_Rc_style(*tc);
check_R_over_C_style(*tc);
check_CR_style(*tc);
check_Cr_style(*tc);
}
SECTION(
"left") {
tc = std::make_unique<ToddCoxeter>(left, kb);
tc->add_pair({
1}, {
2});
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
check_Rc_style(*tc);
check_R_over_C_style(*tc);
check_CR_style(*tc);
check_Cr_style(*tc);
}
SECTION(
"right") {
tc = std::make_unique<ToddCoxeter>(left, kb);
tc->add_pair({
1}, {
2});
check_hlt(*tc);
check_felsch(*tc);
check_random(*tc);
check_Rc_style(*tc);
check_R_over_C_style(*tc);
check_CR_style(*tc);
check_Cr_style(*tc);
}
REQUIRE(tc->has_parent_froidure_pin());
REQUIRE(tc->number_of_classes() ==
1);
if (tc->kind() == twosided) {
REQUIRE(tc->quotient_froidure_pin()->size() ==
1);
}
else {
REQUIRE_THROWS_AS(tc->quotient_froidure_pin(), LibsemigroupsException);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"032",
"prefill",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
detail::DynamicArray2<ToddCoxeter::class_index_type> rv(
2,
1);
REQUIRE(rv.number_of_cols() ==
2);
REQUIRE(rv.number_of_rows() ==
1);
{
ToddCoxeter tc(twosided);
// prefill before number_of_generators are set
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
tc.set_number_of_generators(
3);
// prefill where number_of_generators != number_of_cols of rv
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
}
{
ToddCoxeter tc(left);
tc.set_number_of_generators(
2);
rv.set(
0,
0,
0);
rv.set(
0,
1,
1);
// prefill with too few rows
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
rv.add_rows(
1);
REQUIRE(rv.number_of_rows() ==
2);
rv.set(
1,
0, UNDEFINED);
rv.set(
1,
1, UNDEFINED);
// prefill with bad value (0, 0)
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
rv.set(
0,
0,
2);
// prefill with bad value (0, 0)
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
rv.set(
0,
0,
1);
// UNDEFINED is not allowed
REQUIRE_THROWS_AS(tc.prefill(rv), LibsemigroupsException);
rv.set(
1,
0,
1);
rv.set(
1,
1,
1);
tc.prefill(rv);
}
{
detail::DynamicArray2<ToddCoxeter::class_index_type> rv2(
2,
0);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
REQUIRE_THROWS_AS(tc.prefill(rv2), LibsemigroupsException);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"033",
"congruence of ToddCoxeter",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc1(twosided);
tc1.set_number_of_generators(
2);
tc1.add_pair({
0,
0,
0}, {
0});
tc1.add_pair({
0}, {
1,
1});
REQUIRE(tc1.number_of_classes() ==
5);
ToddCoxeter tc2(left, tc1);
tc2.next_lookahead(
1);
tc2.report_every(
1);
REQUIRE(!tc2.empty());
check_hlt(tc2);
check_random(tc2);
tc2.add_pair({
0}, {
0,
0});
REQUIRE(tc2.number_of_classes() ==
3);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"034",
"congruence of ToddCoxeter",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
using Transf = LeastTransf<
5>;
FroidurePin<Transf> S({Transf({
1,
3,
4,
2,
3}), Transf({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
ToddCoxeter tc(twosided, S);
tc.froidure_pin_policy(options::froidure_pin::none);
tc.set_number_of_generators(
2);
check_hlt_no_save(tc);
check_hlt_save_throws(tc);
check_felsch_throws(tc);
check_random(tc);
tc.add_pair({
0}, {
1,
1});
REQUIRE(tc.number_of_classes() ==
1);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"035",
"congruence on FpSemigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
FpSemigroup S;
S.set_alphabet(
"abe");
S.set_identity(
"e");
S.add_rule(
"abb",
"bb");
S.add_rule(
"bbb",
"bb");
S.add_rule(
"aaaa",
"a");
S.add_rule(
"baab",
"bb");
S.add_rule(
"baaab",
"b");
S.add_rule(
"babab",
"b");
S.add_rule(
"bbaaa",
"bb");
S.add_rule(
"bbaba",
"bbaa");
REQUIRE(S.knuth_bendix()->confluent());
REQUIRE(S.knuth_bendix()->number_of_rules() ==
13);
ToddCoxeter tc(left, *S.knuth_bendix());
tc.add_pair({
0}, {
1,
1,
1});
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
2);
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cend_normal_forms())
== std::vector<word_type>({{
0}, {
2}}));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"036",
"exceptions",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
using Transf = LeastTransf<
5>;
FroidurePin<Transf> S({Transf({
1,
3,
4,
2,
3}), Transf({
3,
2,
1,
3,
3})});
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0}, {
1});
tc.add_pair({
0,
0}, {
0});
REQUIRE(tc.number_of_classes() ==
1);
REQUIRE_THROWS_AS(tc.prefill(S.right_cayley_graph()),
LibsemigroupsException);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"037",
"copy constructor",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0}, {
1});
tc.add_pair({
0,
0}, {
0});
tc.strategy(options::strategy::felsch);
REQUIRE(tc.strategy() == options::strategy::felsch);
REQUIRE(!tc.complete());
REQUIRE(tc.compatible());
REQUIRE(tc.number_of_classes() ==
1);
REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
tc.cend_normal_forms())
== std::vector<word_type>(
1, {
0}));
REQUIRE(tc.complete());
REQUIRE(tc.compatible());
ToddCoxeter copy(tc);
REQUIRE(copy.number_of_generators() ==
2);
REQUIRE(copy.number_of_generating_pairs() ==
2);
REQUIRE(copy.finished());
REQUIRE(copy.number_of_classes() ==
1);
REQUIRE(copy.froidure_pin_policy() == options::froidure_pin::none);
REQUIRE(copy.complete());
REQUIRE(copy.compatible());
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"038",
"simplify",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
2);
tc.add_pair({
0,
0}, {
1});
tc.add_pair({
0,
0}, {
0});
tc.add_pair({
0,
1,
0}, {
0,
0});
tc.add_pair({
0,
1,
0,
1}, {
0,
1,
0});
tc.simplify();
REQUIRE(tc.number_of_generating_pairs() ==
4);
REQUIRE(tc.number_of_classes() ==
1);
std::vector<word_type> result(tc.cbegin_relations(), tc.cend_relations());
std::sort(result.begin(), result.end());
REQUIRE(result
== std::vector<word_type>(
{{
0}, {
0}, {
0}, {
0}, {
0,
0}, {
0,
1,
0}, {
0,
1,
0,
1}, {
1}}));
ToddCoxeter tc2(right, tc);
tc2.add_pair({
0,
0}, {
1});
tc2.add_pair({
0,
0}, {
0});
tc2.add_pair({
0,
1,
0}, {
0,
0});
tc2.add_pair({
0,
1,
0,
1}, {
0,
1,
0});
REQUIRE(tc2.felsch_tree_height() ==
4);
REQUIRE(std::equal(tc.cbegin_relations(),
tc.cend_relations(),
tc2.cbegin_relations(),
tc2.cend_relations()));
REQUIRE(std::vector<word_type>(tc2.cbegin_extra(), tc2.cend_extra())
== std::vector<word_type>({{
0,
0},
{
1},
{
0,
0},
{
0},
{
0,
1,
0},
{
0,
0},
{
0,
1,
0,
1},
{
0,
1,
0}}));
tc2.simplify();
REQUIRE(
std::vector<word_type>(tc2.cbegin_extra(), tc2.cend_extra()).empty());
REQUIRE(tc2.felsch_tree_height() ==
4);
REQUIRE(tc2.number_of_classes() ==
1);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"039",
"stylic_monoid",
"[todd-coxeter][quick][no-coverage][no-valgrind]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
9);
for (
auto const& w : stylic_monoid(
9)) {
tc.add_pair(w.first, w.second);
}
tc.strategy(options::strategy::random);
REQUIRE_THROWS_AS(tc.run_for(std::chrono::milliseconds(
100)),
LibsemigroupsException);
tc.remove_duplicate_generating_pairs()
.sort_generating_pairs()
.strategy(options::strategy::hlt)
.lookahead(options::lookahead::partial | options::lookahead::hlt);
REQUIRE(tc.number_of_classes() ==
115'974);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"040",
"fibonacci_semigroup(4, 6)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard();
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
6);
for (
auto const& w : fibonacci_semigroup(
4,
6)) {
tc.add_pair(w.first, w.second);
}
tc.strategy(options::strategy::felsch);
REQUIRE(tc.number_of_classes() ==
0);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"041",
"some finite classes",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
1);
REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
tc.add_pair({
0,
0,
0,
0,
0,
0}, {
0,
0,
0,
0});
tc.add_pair({
0,
0,
0,
0,
0,
0}, {
0,
0,
0,
0});
tc.add_pair({
0,
0,
0,
0,
0,
0}, {
0,
0,
0,
0});
tc.strategy(options::strategy::random)
.remove_duplicate_generating_pairs()
.standardize(
true);
REQUIRE(!tc.compatible());
REQUIRE_THROWS_AS(tc.run_for(std::chrono::microseconds(
1)),
LibsemigroupsException);
tc.strategy(options::strategy::CR);
size_t x =
0;
REQUIRE_THROWS_AS(tc.run_until([&x] {
return x >
4; }),
LibsemigroupsException);
tc.lower_bound(
100)
.use_relations_in_extra(
true)
.deduction_policy(options::deductions::v1
| options::deductions::unlimited)
.restandardize(
true)
.max_preferred_defs(
0);
REQUIRE_THROWS_AS(tc.hlt_defs(
0), LibsemigroupsException);
REQUIRE_THROWS_AS(tc.f_defs(
0), LibsemigroupsException);
tc.hlt_defs(
10)
.f_defs(
10)
.lookahead_growth_factor(
3.
0)
.lookahead_growth_threshold(
100'000)
.large_collapse(
1);
REQUIRE_THROWS_AS(tc.lookahead_growth_factor(
0.
1),
LibsemigroupsException);
REQUIRE(tc.random_interval() == std::chrono::milliseconds(
200));
REQUIRE(tc.felsch_tree_height() ==
6);
REQUIRE(tc.number_of_classes() ==
5);
REQUIRE(tc.number_of_words(
0) ==
1);
REQUIRE(tc.number_of_words(
1) ==
1);
REQUIRE(tc.number_of_words(
2) ==
1);
REQUIRE(tc.number_of_words(
3) == POSITIVE_INFINITY);
REQUIRE(tc.number_of_words(
4) == POSITIVE_INFINITY);
REQUIRE(tc.standardization_order() == ToddCoxeter::order::none);
REQUIRE(tc.felsch_tree_number_of_nodes() ==
7);
REQUIRE_THROWS_AS(tc.remove_duplicate_generating_pairs(),
LibsemigroupsException);
ToddCoxeter tc2(left, tc);
tc2.add_pair({
0,
0}, {
0});
tc2.add_pair({
0,
0}, {
0});
tc2.remove_duplicate_generating_pairs();
// Uses CongruenceInterface's generating pairs
REQUIRE(tc2.number_of_generating_pairs() ==
2);
ToddCoxeter tc3(twosided);
tc3.set_number_of_generators(
1);
REQUIRE(tc3.is_non_trivial() == tril::
TRUE);
tc3.add_pair({
0,
0}, {
0});
REQUIRE(tc3.is_non_trivial() == tril::unknown);
REQUIRE(tc3.number_of_classes() ==
1);
REQUIRE(tc3.is_non_trivial() == tril::
FALSE);
REQUIRE(!tc.settings_string().empty());
REQUIRE(!tc3.settings_string().empty());
REQUIRE(!tc.stats_string().empty());
}
// Takes about 6m
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"042",
"symmetric_group(10, Moore)",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard(
true);
auto s = symmetric_group(
10, author::Moore);
for (
auto& rel : s) {
if (rel.first.empty()) {
rel.first = {
2};
}
if (rel.second.empty()) {
rel.second = {
2};
}
}
auto p = make<Presentation<word_type>>(s);
p.alphabet(
3);
presentation::add_identity_rules(p,
2);
p.validate();
ToddCoxeter tc(twosided);
tc.set_number_of_generators(
3);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
REQUIRE(tc.number_of_classes() ==
3'628'800);
std::cout << tc.stats_string();
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"043",
"symmetric_group(7, Coxeter + Moser)",
"[todd-coxeter][quick][no-valgrind]") {
auto rg = ReportGuard(REPORT);
size_t n =
7;
auto s = symmetric_group(n, author::Coxeter + author::Moser);
for (
auto& rel : s) {
if (rel.first.empty()) {
rel.first = {n -
1};
}
if (rel.second.empty()) {
rel.second = {n -
1};
}
}
auto p = make<Presentation<word_type>>(s);
p.alphabet(n);
presentation::add_identity_rules(p, n -
1);
p.validate();
ToddCoxeter tc(twosided);
tc.set_number_of_generators(n);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
tc.run_for(std::chrono::microseconds(
1));
REQUIRE(tc.is_non_trivial() == tril::
TRUE);
REQUIRE(!tc.finished());
tc.standardize(ToddCoxeter::order::shortlex);
tc.standardize(ToddCoxeter::order::none);
tc.strategy(options::strategy::CR).f_defs(
100);
REQUIRE(tc.number_of_classes() ==
5'040);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"116",
"symmetric_group(7, Burnside + Miller)",
"[todd-coxeter][quick][no-valgrind]") {
auto rg = ReportGuard(REPORT);
size_t n =
7;
auto s = symmetric_group(n, author::Burnside + author::Miller);
for (
auto& rel : s) {
if (rel.first.empty()) {
rel.first = {n -
1};
}
if (rel.second.empty()) {
rel.second = {n -
1};
}
}
auto p = make<Presentation<word_type>>(s);
p.alphabet(n);
presentation::add_identity_rules(p, n -
1);
p.validate();
ToddCoxeter tc(twosided);
tc.set_number_of_generators(n);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
REQUIRE(tc.number_of_classes() ==
5'040);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"044",
"Option exceptions",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
REQUIRE_THROWS_AS(options::deductions::unlimited
| options::deductions::unlimited,
LibsemigroupsException);
REQUIRE_THROWS_AS(options::deductions::v1 | options::deductions::v2,
LibsemigroupsException);
REQUIRE_THROWS_AS(options::lookahead::hlt | options::lookahead::hlt,
LibsemigroupsException);
REQUIRE_THROWS_AS(options::lookahead::hlt | options::lookahead::felsch,
LibsemigroupsException);
REQUIRE_THROWS_AS(options::lookahead::full | options::lookahead::partial,
LibsemigroupsException);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"045",
"Options operator<<",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
ToddCoxeter tc(twosided);
tc.strategy(options::strategy::hlt);
tc.settings_string();
tc.strategy(options::strategy::felsch);
tc.settings_string();
tc.strategy(options::strategy::random);
tc.settings_string();
tc.strategy(options::strategy::CR);
tc.settings_string();
tc.strategy(options::strategy::R_over_C);
tc.settings_string();
tc.strategy(options::strategy::Cr);
tc.settings_string();
tc.strategy(options::strategy::Rc);
tc.settings_string();
}
{
ToddCoxeter tc(twosided);
tc.lookahead(options::lookahead::full | options::lookahead::felsch);
tc.settings_string();
tc.lookahead(options::lookahead::full | options::lookahead::hlt);
tc.settings_string();
tc.lookahead(options::lookahead::partial | options::lookahead::felsch);
tc.settings_string();
tc.lookahead(options::lookahead::partial | options::lookahead::hlt);
tc.settings_string();
}
{
ToddCoxeter tc(twosided);
tc.deduction_policy(options::deductions::v1
| options::deductions::no_stack_if_no_space);
tc.settings_string();
tc.deduction_policy(options::deductions::v1
| options::deductions::purge_all);
tc.settings_string();
tc.deduction_policy(options::deductions::v1
| options::deductions::purge_from_top);
tc.settings_string();
tc.deduction_policy(options::deductions::v1
| options::deductions::discard_all_if_no_space);
tc.settings_string();
tc.deduction_policy(options::deductions::v1
| options::deductions::unlimited);
tc.settings_string();
tc.deduction_policy(options::deductions::v2
| options::deductions::no_stack_if_no_space);
tc.settings_string();
tc.deduction_policy(options::deductions::v2
| options::deductions::purge_all);
tc.settings_string();
tc.deduction_policy(options::deductions::v2
| options::deductions::purge_from_top);
tc.deduction_policy(options::deductions::v2
| options::deductions::discard_all_if_no_space);
tc.settings_string();
tc.deduction_policy(options::deductions::v2
| options::deductions::unlimited);
tc.settings_string();
}
{
ToddCoxeter tc(twosided);
tc.froidure_pin_policy(options::froidure_pin::none);
tc.settings_string();
tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
tc.settings_string();
tc.froidure_pin_policy(options::froidure_pin::use_relations);
tc.settings_string();
}
{
ToddCoxeter tc(twosided);
tc.preferred_defs(options::preferred_defs::none);
tc.settings_string();
tc.preferred_defs(options::preferred_defs::immediate_no_stack);
tc.settings_string();
tc.preferred_defs(options::preferred_defs::immediate_yes_stack);
tc.settings_string();
tc.preferred_defs(options::preferred_defs::deferred);
tc.settings_string();
}
}
// Takes about 9m3s (2021 - MacBook Air M1 - 8GB RAM)
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"046",
"Easdown-East-FitzGerald DualSymInv(5)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
auto const n =
5;
ToddCoxeter tc(twosided);
setup(tc,
n +
1,
dual_symmetric_inverse_monoid,
n,
author::Easdown + author::East + author::FitzGerald);
// tc.strategy(options::strategy::Rc)
// .max_deductions(10'000)
// .max_preferred_defs(512)
// .random_interval(std::chrono::seconds(10));
check_hlt(tc);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_R_over_C_style(tc);
check_Rc_style(tc);
REQUIRE(tc.number_of_classes() ==
6'721);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"047",
"uniform_block_bijection_monoid(3) (FitzGerald)",
"[todd-coxeter][quick]") {
// 16, 131, 1496, 22482, 426833, 9934563, 9934563
auto rg = ReportGuard(REPORT);
auto const n =
3;
ToddCoxeter tc(twosided);
setup(tc, n +
1, uniform_block_bijection_monoid, n, author::FitzGerald);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_R_over_C_style(tc);
check_Rc_style(tc);
REQUIRE(tc.number_of_classes() ==
16);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"048",
"stellar_monoid(7) (Gay-Hivert)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(
false);
size_t
const n =
7;
ToddCoxeter tc1(congruence_kind::twosided);
setup(tc1, n +
1, rook_monoid, n,
0);
ToddCoxeter tc2(congruence_kind::twosided, tc1);
setup(tc2, n +
1, stellar_monoid, n);
tc2.strategy(options::strategy::felsch);
REQUIRE(tc2.number_of_classes() ==
13'700);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"049",
"partition_monoid(4) (East)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
4;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
5, partition_monoid, n, author::East);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_R_over_C_style(tc);
check_Rc_style(tc);
REQUIRE(tc.number_of_classes() ==
4'140);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"050",
"singular_brauer_monoid(6) (Maltcev + Mazorchuk)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
6;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n * n - n, singular_brauer_monoid, n);
tc.sort_generating_pairs().remove_duplicate_generating_pairs();
REQUIRE(tc.number_of_classes() ==
9'675);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"051",
"orientation_preserving_monoid(6) (Ruskuc + Arthur)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
6;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
3, orientation_preserving_monoid, n);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_R_over_C_style(tc);
check_Rc_style(tc);
REQUIRE(tc.number_of_classes() ==
2'742);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"052",
"orientation_reversing_monoid(5) (Ruskuc + Arthur)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
5;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
4, orientation_reversing_monoid, n);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.number_of_classes() ==
1'015);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"053",
"temperley_lieb_monoid(10) (East)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
10;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n -
1, temperley_lieb_monoid, n);
REQUIRE(tc.number_of_classes() ==
16'795);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"054",
"Generate GAP benchmarks for stellar_monoid(n) (Gay-Hivert)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
9; ++n) {
ToddCoxeter tc1(congruence_kind::twosided);
setup(tc1, n +
1, rook_monoid, n,
0);
ToddCoxeter tc2(congruence_kind::twosided, tc1);
setup(tc2, n +
1, stellar_monoid, n);
output_gap_benchmark_file(
"stellar-" + std::to_string(n) +
".g", tc2);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"055",
"Generate GAP benchmarks for partition_monoid(n) (East)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
4; n <=
6; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
5, partition_monoid, n, author::East);
tc.save(
true);
output_gap_benchmark_file(
"partition-" + std::to_string(n) +
".g", tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"056",
"Generate GAP benchmarks for dual symmetric inverse monoid (East)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
6; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
n +
1,
dual_symmetric_inverse_monoid,
n,
author::Easdown + author::East + author::FitzGerald);
output_gap_benchmark_file(
"dual-sym-inv-" + std::to_string(n) +
".g",
tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"057",
"Generate GAP benchmarks for "
"uniform_block_bijection_monoid (FitzGerald)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
7; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n +
1, uniform_block_bijection_monoid, n, author::FitzGerald);
output_gap_benchmark_file(
"uniform-block-bijection-" + std::to_string(n) +
".g", tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"058",
"Generate GAP benchmarks for stylic monoids",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
9; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n, stylic_monoid, n);
output_gap_benchmark_file(
"stylic-" + std::to_string(n) +
".g", tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"059",
"Generate GAP benchmarks for OP_n",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
9; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
3, orientation_preserving_monoid, n);
output_gap_benchmark_file(
"orient-" + std::to_string(n) +
".g", tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"060",
"Generate GAP benchmarks for OR_n",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
8; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
4, orientation_reversing_monoid, n);
output_gap_benchmark_file(
"orient-reverse-" + std::to_string(n) +
".g",
tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"061",
"Generate GAP benchmarks for temperley_lieb_monoid(n)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
13; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n -
1, temperley_lieb_monoid, n);
output_gap_benchmark_file(
"temperley-lieb-" + std::to_string(n) +
".g",
tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"062",
"Generate GAP benchmarks for singular_brauer_monoid(n)",
"[todd-coxeter][fail]") {
auto rg = ReportGuard(
false);
for (size_t n =
3; n <=
7; ++n) {
ToddCoxeter tc(congruence_kind::twosided);
setup(tc, n * n - n, singular_brauer_monoid, n);
output_gap_benchmark_file(
"singular-brauer-" + std::to_string(n) +
".g",
tc);
}
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"111",
"partition_monoid(2)",
"[todd-coxeter][quick]") {
ToddCoxeter p(congruence_kind::twosided);
p.set_number_of_generators(
4);
p.add_pair({
0,
1}, {
1});
p.add_pair({
1,
0}, {
1});
p.add_pair({
0,
2}, {
2});
p.add_pair({
2,
0}, {
2});
p.add_pair({
0,
3}, {
3});
p.add_pair({
3,
0}, {
3});
p.add_pair({
1,
1}, {
0});
p.add_pair({
1,
3}, {
3});
p.add_pair({
2,
2}, {
2});
p.add_pair({
3,
1}, {
3});
p.add_pair({
3,
3}, {
3});
p.add_pair({
2,
3,
2}, {
2});
p.add_pair({
3,
2,
3}, {
3});
p.add_pair({
1,
2,
1,
2}, {
2,
1,
2});
p.add_pair({
2,
1,
2,
1}, {
2,
1,
2});
auto rg = ReportGuard(
false);
REQUIRE(p.number_of_classes() ==
15);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"112",
"brauer_monoid(4) (Kudryavtseva + Mazorchuk)",
"[todd-coxeter][quick][no-valgrind][no-coverage]") {
auto rg = ReportGuard(REPORT);
size_t
const n =
4;
ToddCoxeter tc(congruence_kind::twosided);
setup(tc,
2 * n -
1, brauer_monoid, n);
tc.sort_generating_pairs().remove_duplicate_generating_pairs();
REQUIRE(tc.number_of_classes() ==
105);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"113",
"symmetric_inverse_monoid",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
size_t n =
5;
auto s = symmetric_inverse_monoid(n, author::Sutov);
auto p = make<Presentation<word_type>>(s);
p.alphabet(n +
1);
presentation::replace_word(p, word_type({}), {n});
presentation::add_identity_rules(p, n);
p.validate();
ToddCoxeter tc(congruence_kind::twosided);
tc.set_number_of_generators(n +
1);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
REQUIRE(tc.number_of_classes() ==
1546);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"114",
"partial_transformation_monoid(5)",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
size_t n =
5;
auto s = partial_transformation_monoid(n, author::Sutov);
auto p = make<Presentation<word_type>>(s);
p.alphabet(n +
2);
presentation::replace_word(p, word_type({}), {n +
1});
presentation::add_identity_rules(p, n +
1);
p.validate();
ToddCoxeter tc(congruence_kind::twosided);
tc.set_number_of_generators(n +
2);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
REQUIRE(tc.number_of_classes() ==
7776);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"115",
"full_transformation_monoid(5)",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard(REPORT);
size_t n =
7;
auto s = full_transformation_monoid(n, author::Iwahori);
auto p = make<Presentation<word_type>>(s);
p.alphabet(n +
1);
presentation::replace_word(p, word_type({}), {n});
presentation::add_identity_rules(p, n);
p.validate();
ToddCoxeter tc(congruence_kind::twosided);
tc.set_number_of_generators(n +
1);
for (size_t i =
0; i < p.rules.size() -
1; i +=
2) {
tc.add_pair(p.rules[i], p.rules[i +
1]);
}
REQUIRE(tc.number_of_classes() ==
823543);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"110",
"to_gap_string",
"[todd-coxeter][quick]") {
ToddCoxeter tc1(congruence_kind::right);
tc1.set_number_of_generators(
2);
tc1.add_pair({
0,
1}, {
1,
0});
REQUIRE_THROWS_AS(tc1.to_gap_string(), LibsemigroupsException);
ToddCoxeter tc2(congruence_kind::left);
tc2.set_number_of_generators(
2);
tc2.add_pair({
0,
1}, {
1,
0});
REQUIRE_THROWS_AS(tc2.to_gap_string(), LibsemigroupsException);
ToddCoxeter tc3(congruence_kind::twosided);
tc3.set_number_of_generators(
2);
tc3.add_pair({
0,
1}, {
1,
0});
REQUIRE(tc3.to_gap_string().size() >
0);
}
}
// namespace congruence
namespace fpsemigroup {
constexpr
bool REPORT =
false;
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"063",
"add_rule",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
{
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"a",
"bb");
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
SECTION(
"R/C + Felsch lookahead") {
tc.congruence()
.strategy(options::strategy::R_over_C)
.lookahead(options::lookahead::felsch | options::lookahead::full);
tc.congruence().run();
}
SECTION(
"HLT + Felsch lookahead + save") {
tc.congruence()
.strategy(options::strategy::hlt)
.save(
true)
.lookahead(options::lookahead::felsch | options::lookahead::full)
.next_lookahead(
2);
tc.congruence().run();
}
SECTION(
"Cr + small number of f_defs") {
tc.congruence().strategy(options::strategy::Cr).f_defs(
3);
tc.congruence().run();
}
SECTION(
"Rc + small number of deductions") {
tc.congruence().strategy(options::strategy::Rc).max_deductions(
0);
tc.congruence().run();
}
SECTION(
"Felsch + v2 + no preferred defs") {
tc.congruence()
.strategy(options::strategy::felsch)
.deduction_policy(options::deductions::v2
| options::deductions::purge_all)
.preferred_defs(options::preferred_defs::none);
}
SECTION(
"Felsch + v2 + immediate no stack") {
tc.congruence()
.strategy(options::strategy::felsch)
.deduction_policy(options::deductions::v2
| options::deductions::purge_from_top)
.preferred_defs(options::preferred_defs::immediate_no_stack);
}
SECTION(
"Felsch + v1 + immediate no stack") {
tc.congruence()
.strategy(options::strategy::felsch)
.deduction_policy(options::deductions::v1
| options::deductions::discard_all_if_no_space)
.preferred_defs(options::preferred_defs::immediate_no_stack);
}
SECTION(
"Felsch + v1 + immediate yes stack") {
tc.congruence()
.strategy(options::strategy::felsch)
.deduction_policy(options::deductions::v1
| options::deductions::no_stack_if_no_space)
.preferred_defs(options::preferred_defs::immediate_yes_stack);
}
SECTION(
"large collapse") {
tc.congruence().large_collapse(
0);
}
REQUIRE(tc.size() ==
5);
}
{
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"a",
"bb");
tc.congruence().next_lookahead(
1);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
5);
}
}
// KnuthBendix methods fail for this one
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"064",
"(from kbmag/standalone/kb_data/s4) (KnuthBendix 49)",
"[todd-coxeter][quick][kbmag]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"abcd");
tc.add_rule(
"bb",
"c");
tc.add_rule(
"caca",
"abab");
tc.add_rule(
"bc",
"d");
tc.add_rule(
"cb",
"d");
tc.add_rule(
"aa",
"d");
tc.add_rule(
"ad",
"a");
tc.add_rule(
"da",
"a");
tc.add_rule(
"bd",
"b");
tc.add_rule(
"db",
"b");
tc.add_rule(
"cd",
"c");
tc.add_rule(
"dc",
"c");
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
24);
REQUIRE(tc.froidure_pin()->size() ==
24);
REQUIRE(tc.normal_form(
"aaaaaaaaaaaaaaaaaaa") ==
"a");
REQUIRE(KnuthBendix(tc.froidure_pin()).confluent());
}
// Second of BHN's series of increasingly complicated presentations
// of 1. Doesn't terminate
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"065",
"(from kbmag/standalone/kb_data/degen4b) "
"(KnuthBendix 065)",
"[fail][todd-coxeter][kbmag][shortlex]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet(
"abcdefg");
tc.set_identity(
"g");
tc.set_inverses(
"defabcg");
tc.add_rule(
"bbdeaecbffdbaeeccefbccefb",
"g");
tc.add_rule(
"ccefbfacddecbffaafdcaafdc",
"g");
tc.add_rule(
"aafdcdbaeefacddbbdeabbdea",
"g");
tc.congruence().lookahead(options::lookahead::full
| options::lookahead::felsch);
REQUIRE(!tc.is_obviously_infinite());
REQUIRE(tc.size() ==
1);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"066",
"test validate",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"a",
"b");
tc.add_rule(
"bb",
"b");
REQUIRE_THROWS_AS(tc.add_rule(
"b",
"c"), LibsemigroupsException);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"067",
"add_rules after construct. from semigroup",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
using Transf = LeastTransf<
5>;
FroidurePin<Transf> S({Transf({
1,
3,
4,
2,
3}), Transf({
3,
2,
1,
3,
3})});
REQUIRE(S.size() ==
88);
REQUIRE(S.number_of_rules() ==
18);
word_type w1, w2, w3, w4;
S.factorisation(w1, S.position(Transf({
3,
4,
4,
4,
4})));
S.factorisation(w2, S.position(Transf({
3,
1,
3,
3,
3})));
S.factorisation(w3, S.position(Transf({
1,
3,
1,
3,
3})));
S.factorisation(w4, S.position(Transf({
4,
2,
4,
4,
2})));
ToddCoxeter tc1(S);
tc1.add_rule(w1, w2);
check_hlt_no_save(tc1);
check_hlt_save_throws(tc1);
check_felsch_throws(tc1);
check_random(tc1);
REQUIRE(tc1.size() ==
21);
REQUIRE(tc1.size() == tc1.froidure_pin()->size());
REQUIRE(tc1.equal_to(w3, w4));
REQUIRE(tc1.normal_form(w3) == tc1.normal_form(w4));
ToddCoxeter tc2(S);
tc2.add_rule(w1, w2);
check_hlt_no_save(tc2);
check_hlt_save_throws(tc2);
check_felsch_throws(tc2);
REQUIRE(tc2.size() ==
21);
REQUIRE(tc2.size() == tc2.froidure_pin()->size());
REQUIRE(tc2.equal_to(w3, w4));
REQUIRE(tc2.normal_form(w3) == tc2.normal_form(w4));
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"068",
"Sym(5) from Chapter 3, Proposition 1.1 in NR",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ABabe");
tc.set_identity(
"e");
tc.add_rule(
"aa",
"e");
tc.add_rule(
"bbbbb",
"e");
tc.add_rule(
"babababa",
"e");
tc.add_rule(
"bB",
"e");
tc.add_rule(
"Bb",
"e");
tc.add_rule(
"BabBab",
"e");
tc.add_rule(
"aBBabbaBBabb",
"e");
tc.add_rule(
"aBBBabbbaBBBabbb",
"e");
tc.add_rule(
"aA",
"e");
tc.add_rule(
"Aa",
"e");
SECTION(
"Deduction policy == purge_from_top") {
tc.congruence()
.max_deductions(
2)
.strategy(options::strategy::felsch)
.max_preferred_defs(
3);
REQUIRE_THROWS_AS(tc.congruence().deduction_policy(
options::deductions::purge_from_top),
LibsemigroupsException);
tc.congruence().deduction_policy(options::deductions::v1
| options::deductions::purge_from_top);
}
SECTION(
"Deduction policy == purge_all") {
tc.congruence().max_deductions(
2).strategy(options::strategy::felsch);
tc.congruence().deduction_policy(options::deductions::v1
| options::deductions::purge_all);
}
SECTION(
"Deduction policy == discard_all_if_no_space") {
tc.congruence().max_deductions(
2).strategy(options::strategy::felsch);
tc.congruence().deduction_policy(
options::deductions::v2
| options::deductions::discard_all_if_no_space);
}
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
120);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"069",
"Chapter 7, Theorem 3.6 in NR (size 243)",
"[no-valgrind][todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbb",
"b");
tc.add_rule(
"ababababab",
"aa");
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
243);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"070",
"finite semigroup (size 99)",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbb",
"b");
tc.add_rule(
"abababab",
"aa");
REQUIRE(!tc.is_obviously_finite());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
99);
REQUIRE(tc.finished());
REQUIRE(tc.is_obviously_finite());
}
// The following 8 examples are from Trevor Walker's Thesis: Semigroup
// enumeration - computer implementation and applications, p41.
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"071",
"Walker 1",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"abcABCDEFGHIXYZ");
tc.add_rule(
"A",
"aaaaaaaaaaaaaa");
tc.add_rule(
"B",
"bbbbbbbbbbbbbb");
tc.add_rule(
"C",
"cccccccccccccc");
tc.add_rule(
"D",
"aaaaba");
tc.add_rule(
"E",
"bbbbab");
tc.add_rule(
"F",
"aaaaca");
tc.add_rule(
"G",
"ccccac");
tc.add_rule(
"H",
"bbbbcb");
tc.add_rule(
"I",
"ccccbc");
tc.add_rule(
"X",
"aaa");
tc.add_rule(
"Y",
"bbb");
tc.add_rule(
"Z",
"ccc");
tc.add_rule(
"A",
"a");
tc.add_rule(
"B",
"b");
tc.add_rule(
"C",
"c");
tc.add_rule(
"D",
"Y");
tc.add_rule(
"E",
"X");
tc.add_rule(
"F",
"Z");
tc.add_rule(
"G",
"X");
tc.add_rule(
"H",
"Z");
tc.add_rule(
"I",
"Y");
tc.congruence()
.sort_generating_pairs(shortlex_compare)
.next_lookahead(
500'000)
.run_until([&tc]() ->
bool {
return tc.congruence().coset_capacity() >=
10'000;
});
REQUIRE(!tc.finished());
REQUIRE(!tc.is_obviously_finite());
tc.congruence().standardize(tc_order::shortlex);
REQUIRE(!tc.finished());
tc.congruence().standardize(tc_order::lex);
REQUIRE(!tc.finished());
tc.congruence().standardize(tc_order::recursive);
REQUIRE(!tc.finished());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
// This takes approx 1 seconds with Felsch . . .
REQUIRE(tc.size() ==
1);
tc.congruence().standardize(tc_order::shortlex);
REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms(),
ShortLexCompare<word_type>{}));
tc.congruence().standardize(tc_order::lex);
REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms(),
LexicographicalCompare<word_type>{}));
tc.congruence().standardize(tc_order::recursive);
REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms(),
RecursivePathCompare<word_type>{}));
}
// The following example is a good one for using the lookahead.
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"072",
"Walker 2",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"a");
tc.add_rule(
"bbb",
"b");
tc.add_rule(
"ababa",
"b");
tc.add_rule(
"aaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaabaaaa",
"b");
REQUIRE(!tc.is_obviously_finite());
SECTION(
"custom HLT") {
tc.congruence()
.sort_generating_pairs()
.next_lookahead(
1'000'000)
.max_deductions(
2'000)
.use_relations_in_extra(
true)
.strategy(options::strategy::hlt)
.lookahead(options::lookahead::partial | options::lookahead::felsch)
.deduction_policy(options::deductions::v2
| options::deductions::no_stack_if_no_space);
}
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
14'911);
tc.congruence().standardize(tc_order::shortlex);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"073",
"Walker 3",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaaaaaaaaaaaaaaa",
"a");
tc.add_rule(
"bbbbbbbbbbbbbbbb",
"b");
tc.add_rule(
"abb",
"baa");
tc.congruence().next_lookahead(
2'000'000);
tc.congruence().simplify();
REQUIRE(!tc.is_obviously_finite());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
// check_Rc_style(tc); // Rc_style + partial lookahead works very badly
// 2m30s
check_R_over_C_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
20'490);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"074",
"Walker 4",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbbbb",
"b");
tc.add_rule(
"ababbbbababbbbababbbbababbbbababbbbababbbbababbbbabba",
"bb");
tc.congruence().next_lookahead(
3'000'000);
REQUIRE(!tc.is_obviously_finite());
check_hlt(tc);
// Felsch very slow
check_random(tc);
SECTION(
"custom R/C") {
tc.congruence()
.next_lookahead(
3'000'000)
.strategy(options::strategy::R_over_C)
.max_deductions(
100'000);
}
tc.congruence().run();
REQUIRE(tc.size() ==
36'412);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"075",
"Walker 5",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbbbb",
"b");
tc.add_rule(
"ababbbbababbbbababbbbababbbbababbbbababbbbababbbbabbabbbbbaa",
"bb");
tc.congruence().next_lookahead(
5'000'000);
REQUIRE(!tc.is_obviously_finite());
// This example is extremely slow with Felsch
check_hlt(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
tc.congruence().run();
REQUIRE(tc.congruence().complete());
REQUIRE(tc.congruence().compatible());
REQUIRE(tc.size() ==
72'822);
std::cout << tc.congruence().stats_string();
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"076",
"not Walker 6",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbbbbbbb",
"b");
tc.add_rule(
"ababbbbababbbbababbbbababbbbababbbbababbbbababbbbabbabbbbbbbb",
"bb");
tc.congruence().next_lookahead(
5'000'000);
REQUIRE(!tc.is_obviously_finite());
// This example is extremely slow with Felsch, the random strategy
// strategy is typically fastest
check_hlt(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
8);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"077",
"Walker 6",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbbbbbbb",
"b");
std::string lng(
"ababbbbbbb");
lng += lng;
lng +=
"abbabbbbbbbb";
tc.add_rule(lng,
"bb");
REQUIRE(!tc.is_obviously_finite());
// This example is extremely slow with Felsch
check_hlt(tc);
check_random(tc);
// check_Rc_style(tc); // partial lookahead is too slow
// check_Cr_style(tc); // very slow
check_R_over_C_style(tc);
REQUIRE(tc.size() ==
78'722);
}
// Felsch is faster here too!
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"078",
"Walker 7",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"abcde");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbb",
"b");
tc.add_rule(
"ccc",
"c");
tc.add_rule(
"ddd",
"d");
tc.add_rule(
"eee",
"e");
tc.add_rule(
"ababab",
"aa");
tc.add_rule(
"bcbcbc",
"bb");
tc.add_rule(
"cdcdcd",
"cc");
tc.add_rule(
"dedede",
"dd");
tc.add_rule(
"ac",
"ca");
tc.add_rule(
"ad",
"da");
tc.add_rule(
"ae",
"ea");
tc.add_rule(
"bd",
"db");
tc.add_rule(
"be",
"eb");
tc.add_rule(
"ce",
"ec");
REQUIRE(!tc.is_obviously_finite());
check_hlt(tc);
check_felsch(tc);
check_random(tc);
// check_Rc_style(tc); // partial lookahead very slow ~8s
check_R_over_C_style(tc);
check_Cr_style(tc);
tc.congruence()
.deduction_policy(options::deductions::v1
| options::deductions::no_stack_if_no_space)
.preferred_defs(options::preferred_defs::none);
REQUIRE(tc.size() ==
153'500);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"079",
"Walker 8",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"ab");
tc.add_rule(
"aaa",
"a");
tc.add_rule(
"bbbbbbbbbbbbbbbbbbbbbbb",
"b");
tc.add_rule(
"abbbbbbbbbbbabb",
"bba");
REQUIRE(tc.congruence().length_of_generating_pairs() ==
46);
REQUIRE(!tc.is_obviously_finite());
tc.congruence().next_lookahead(
500'000);
// This example is extremely slow with Felsch
check_hlt(tc);
check_random(tc);
// check_Rc_style(tc); + partial lookahead too slow
// check_Cr_style(tc); // too slow
check_R_over_C_style(tc);
REQUIRE(tc.congruence().number_of_classes() ==
270'272);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"080",
"KnuthBendix 098",
"[todd-coxeter][quick][no-valgrind]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
"aAbBcCdDyYfFgGe");
tc.set_identity(
"e");
tc.set_inverses(
"AaBbCcDdYyFfGge");
tc.add_rule(
"ab",
"c");
tc.add_rule(
"bc",
"d");
tc.add_rule(
"cd",
"y");
tc.add_rule(
"dy",
"f");
tc.add_rule(
"yf",
"g");
tc.add_rule(
"fg",
"a");
tc.add_rule(
"ga",
"b");
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
29);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"081",
"Holt 2 - SL(2, p)",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet(
"xXyYe");
tc.set_identity(
"e");
tc.set_inverses(
"XxYye");
tc.add_rule(
"xxYXYXYX",
"e");
auto second = [](size_t p) -> std::string {
std::string s =
"xyyyyx";
s += std::string((p +
1) /
2,
'y');
s += s;
s += std::string(p,
'y');
s += std::string(
2 * (p /
3),
'x');
return s;
};
REQUIRE(second(
3) ==
"xyyyyxyyxyyyyxyyyyyxx");
SECTION(
"p = 3") {
tc.add_rule(second(
3),
"e");
check_hlt(tc);
check_felsch(tc);
REQUIRE(tc.size() ==
24);
}
SECTION(
"p = 5") {
tc.add_rule(second(
5),
"e");
check_hlt(tc);
check_felsch(tc);
REQUIRE(tc.size() ==
120);
}
SECTION(
"p = 7") {
tc.add_rule(second(
7),
"e");
check_hlt(tc);
check_felsch(tc);
REQUIRE(tc.size() ==
336);
}
SECTION("p =
11") {
tc.add_rule(second(
11), "e");
check_hlt(tc);
check_random(tc);
REQUIRE(tc.size() ==
1'
320);
}
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
082",
"Holt
3",
"[todd-coxeter][standard]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet("aAbBcCe");
tc.set_identity("e");
tc.set_inverses("AaBbCce");
tc.add_rule("bbCbc", "e");
tc.add_rule("aaBab", "e");
tc.add_rule("cABcabc", "e");
REQUIRE(tc.congruence().is_non_trivial() == tril::TRUE);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
6'
561);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
083",
"Holt
3",
"[todd-coxeter][fail]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet("aAbBcCe");
tc.set_identity("e");
tc.set_inverses("AaBbCce");
tc.add_rule("aaCac", "e");
tc.add_rule("acbbACb", "e");
tc.add_rule("ABabccc", "e");
REQUIRE(!tc.is_obviously_infinite());
REQUIRE(tc.congruence().number_of_generating_pairs() ==
22);
tc.congruence().strategy(options::strategy::R_over_C);
tc.congruence()
.sort_generating_pairs()
.remove_duplicate_generating_pairs();
REQUIRE(tc.congruence().number_of_generating_pairs() ==
22);
tc.congruence()
.lookahead(options::lookahead::partial | options::lookahead::hlt)
.lookahead_growth_factor(
1.
01)
.lookahead_growth_threshold(
10)
.f_defs(
250'
000)
.hlt_defs(
20'
000'
000);
// REQUIRE(tc.congruence().is_non_trivial() == tril::TRUE);
tc.congruence().run();
REQUIRE(tc.size() ==
6'
561);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
084",
"Campbell-Reza
1",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet("ab");
tc.add_rule("aa", "bb");
tc.add_rule("ba", "aaaaaab");
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
REQUIRE(tc.size() ==
14);
tc.congruence().standardize(tc_order::shortlex);
REQUIRE(std::vector<word_type>(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms())
== std::vector<word_type>({{
0},
{
1},
{
0,
0},
{
0,
1},
{
1,
0},
{
0,
0,
0},
{
0,
0,
1},
{
0,
0,
0,
0},
{
0,
0,
0,
1},
{
0,
0,
0,
0,
0},
{
0,
0,
0,
0,
1},
{
0,
0,
0,
0,
0,
0},
{
0,
0,
0,
0,
0,
1},
{
0,
0,
0,
0,
0,
0,
0}}));
REQUIRE(tc.froidure_pin()->number_of_rules() ==
6);
REQUIRE(tc.normal_form("aaaaaaab") == "aab");
REQUIRE(tc.normal_form("bab") == "aaa");
}
// The next example demonstrates why we require deferred standardization
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
085",
"Renner monoid type D4 (Gay-Hivert), q =
1",
"[no-valgrind][quick][todd-coxeter][no-coverage]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet(
11);
for (relation_type const& rl : RennerTypeDMonoid(
4,
1)) {
tc.add_rule(rl);
}
REQUIRE(tc.number_of_rules() ==
121);
REQUIRE(!tc.is_obviously_infinite());
REQUIRE(tc.size() ==
10'
625);
check_hlt(tc);
check_felsch(tc);
check_random(tc);
check_Rc_style(tc);
check_R_over_C_style(tc);
check_CR_style(tc);
check_Cr_style(tc);
tc.congruence().standardize(tc_order::shortlex);
REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms(),
ShortLexCompare<word_type>{}));
tc.congruence().standardize(tc_order::lex);
REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
tc.congruence().cend_normal_forms(),
LexicographicalCompare<word_type>{}));
// The next section is very slow
// SECTION("standardizing with recursive order") {
// tc.congruence().standardize(tc_order::recursive);
// REQUIRE(std::is_sorted(tc.congruence().cbegin_normal_forms(),
// tc.congruence().cend_normal_forms(),
// RecursivePathCompare<word_type>{}));
// }
}
// Felsch very slow here
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
086",
"trivial semigroup",
"[no-valgrind][todd-coxeter][quick][no-coverage]") {
auto rg = ReportGuard(REPORT);
for (size_t N =
2; N <
1000; N +=
199) {
ToddCoxeter tc;
tc.set_alphabet("eab");
tc.set_identity("e");
std::string lhs = "a" + std::string(N, 'b');
std::string rhs = "e";
tc.add_rule(lhs, rhs);
lhs = std::string(N, 'a');
rhs = std::string(N +
1, 'b');
tc.add_rule(lhs, rhs);
lhs = "ba";
rhs = std::string(N, 'b') + "a";
tc.add_rule(lhs, rhs);
tc.run();
if (N %
3 ==
1) {
REQUIRE(tc.size() ==
3);
} else {
REQUIRE(tc.size() ==
1);
}
}
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
087",
"ACE ---
2p17-
2p14 - HLT",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(false);
ToddCoxeter G;
G.set_alphabet("abcABCe");
G.set_identity("e");
G.set_inverses("ABCabce");
G.add_rule("aBCbac", "e");
G.add_rule("bACbaacA", "e");
G.add_rule("accAABab", "e");
congruence::ToddCoxeter H(right, G.congruence());
H.add_pair({
1,
2}, {
6});
H.next_lookahead(
1'
000'
000);
REQUIRE(H.number_of_classes() ==
16'
384);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
088",
"ACE ---
2p17-
2p3 - HLT",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abcABCe");
G.set_identity("e");
G.set_inverses("ABCabce");
G.add_rule("aBCbac", "e");
G.add_rule("bACbaacA", "e");
G.add_rule("accAABab", "e");
letter_type a =
0;
letter_type b =
1;
letter_type c =
2;
letter_type A =
3;
letter_type B =
4;
letter_type C =
5;
letter_type e =
6;
congruence::ToddCoxeter H(right, G.congruence());
H.add_pair({b, c}, {e});
H.add_pair({b, c}, {A, B, A, A, b, c, a, b, C});
H.strategy(options::strategy::hlt)
.save(true)
.lookahead(options::lookahead::partial);
REQUIRE(H.number_of_classes() ==
8);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
089",
"ACE ---
2p17-
1a - HLT",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abcABCe");
G.set_identity("e");
G.set_inverses("ABCabce");
G.add_rule("aBCbac", "e");
G.add_rule("bACbaacA", "e");
G.add_rule("accAABab", "e");
letter_type a =
0;
letter_type b =
1;
letter_type c =
2;
letter_type A =
3;
letter_type B =
4;
letter_type C =
5;
letter_type e =
6;
congruence::ToddCoxeter H(right, G.congruence());
H.add_pair({b, c}, {e});
H.add_pair({A, B, A, A, b, c, a, b, C}, {e});
H.add_pair({A, c, c, c, a, c, B, c, A}, {e});
H.large_collapse(
10'
000);
H.strategy(options::strategy::hlt)
.save(true)
.lookahead(options::lookahead::partial);
REQUIRE(H.number_of_classes() ==
1);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
090",
"ACE --- F27",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abcdxyzABCDXYZe");
G.set_identity("e");
G.set_inverses("ABCDXYZabcdxyze");
G.add_rule("abC", "e");
G.add_rule("bcD", "e");
G.add_rule("cdX", "e");
G.add_rule("dxY", "e");
G.add_rule("xyZ", "e");
G.add_rule("yzA", "e");
G.add_rule("zaB", "e");
congruence::ToddCoxeter H(twosided, G);
check_felsch(H);
check_hlt(H);
check_random(H);
REQUIRE(H.number_of_classes() ==
29);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
091",
"ACE --- SL219 - HLT",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abABe");
G.set_identity("e");
G.set_inverses("ABabe");
G.add_rule("aBABAB", "e");
G.add_rule("BAAbaa", "e");
G.add_rule(
"abbbbabbbbbbbbbbabbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaa",
"e");
letter_type b =
1;
letter_type e =
4;
congruence::ToddCoxeter H(right, G);
H.add_pair({b}, {e});
H.strategy(options::strategy::hlt)
.save(false)
.lookahead(options::lookahead::partial);
REQUIRE(H.number_of_classes() ==
180);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
092",
"ACE --- perf602p5 - HLT",
"[no-valgrind][todd-coxeter][quick][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abstuvdABSTUVDe");
G.set_identity("e");
G.set_inverses("ABSTUVDabstuvde");
G.add_rule("aaD", "e");
G.add_rule("bbb", "e");
G.add_rule("ababababab", "e");
G.add_rule("ss", "e");
G.add_rule("tt", "e");
G.add_rule("uu", "e");
G.add_rule("vv", "e");
G.add_rule("dd", "e");
G.add_rule("STst", "e");
G.add_rule("UVuv", "e");
G.add_rule("SUsu", "e");
G.add_rule("SVsv", "e");
G.add_rule("TUtu", "e");
G.add_rule("TVtv", "e");
G.add_rule("AsaU", "e");
G.add_rule("AtaV", "e");
G.add_rule("AuaS", "e");
G.add_rule("AvaT", "e");
G.add_rule("BsbDVT", "e");
G.add_rule("BtbVUTS", "e");
G.add_rule("BubVU", "e");
G.add_rule("BvbU", "e");
G.add_rule("DAda", "e");
G.add_rule("DBdb", "e");
G.add_rule("DSds", "e");
G.add_rule("DTdt", "e");
G.add_rule("DUdu", "e");
G.add_rule("DVdv", "e");
congruence::ToddCoxeter H(right, G);
letter_type a =
0;
letter_type e =
14;
H.add_pair({a}, {e});
check_hlt(H);
check_random(H);
check_felsch(H);
REQUIRE(H.number_of_classes() ==
480);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
093",
"ACE --- M12",
"[todd-coxeter][standard][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abcABCe");
G.set_identity("e");
G.set_inverses("ABCabce");
G.add_rule("aaaaaaaaaaa", "e");
G.add_rule("bb", "e");
G.add_rule("cc", "e");
G.add_rule("ababab", "e");
G.add_rule("acacac", "e");
G.add_rule("bcbcbcbcbcbcbcbcbcbc", "e");
G.add_rule("cbcbabcbcAAAAA", "e");
congruence::ToddCoxeter H(twosided, G);
SECTION("HLT + save + partial lookahead") {
H.strategy(options::strategy::hlt)
.save(true)
.lookahead(options::lookahead::partial);
}
SECTION("random") {
H.strategy(options::strategy::random)
.random_interval(std::chrono::milliseconds(
100));
}
check_felsch(H);
REQUIRE(H.number_of_classes() ==
95'
040);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
094",
"ACE --- C5 - HLT",
"[todd-coxeter][quick][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abABe");
G.set_identity("e");
G.set_inverses("ABabe");
G.add_rule("aaaaa", "e");
G.add_rule("b", "e");
congruence::ToddCoxeter H(twosided, G);
check_hlt(H);
check_random(H);
check_felsch(H);
REQUIRE(H.number_of_classes() ==
5);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
095",
"ACE --- A5-C5",
"[todd-coxeter][quick][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abABe");
G.set_identity("e");
G.set_inverses("ABabe");
G.add_rule("aa", "e");
G.add_rule("bbb", "e");
G.add_rule("ababababab", "e");
congruence::ToddCoxeter H(right, G);
letter_type const a =
0, b =
1, e =
4;
H.add_pair({a, b}, {e});
check_hlt(H);
check_random(H);
check_felsch(H);
REQUIRE(H.number_of_classes() ==
12);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
096",
"ACE --- A5",
"[todd-coxeter][quick][ace]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter G;
G.set_alphabet("abABe");
G.set_identity("e");
G.set_inverses("ABabe");
G.add_rule("aa", "e");
G.add_rule("bbb", "e");
G.add_rule("ababababab", "e");
congruence::ToddCoxeter H(twosided, G);
check_hlt(H);
check_random(H);
check_felsch(H);
H.random_shuffle_generating_pairs();
REQUIRE(H.number_of_classes() ==
60);
REQUIRE_THROWS_AS(H.random_shuffle_generating_pairs(),
LibsemigroupsException);
}
// Felsch is much much better here
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
097",
"relation ordering",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet(
13);
for (relation_type const& rl : RennerTypeDMonoid(
5,
1)) {
tc.add_rule(rl);
}
REQUIRE(tc.number_of_rules() ==
173);
REQUIRE(!tc.is_obviously_infinite());
tc.congruence()
.sort_generating_pairs(&shortlex_compare)
.sort_generating_pairs(recursive_path_compare)
.remove_duplicate_generating_pairs();
REQUIRE(tc.number_of_rules() ==
173);
tc.congruence().strategy(options::strategy::felsch).f_defs(
100'
000).run();
REQUIRE(tc.size() ==
258'
661);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
098",
"relation ordering",
"[todd-coxeter][quick]") {
ToddCoxeter tc;
tc.set_alphabet(
10);
tc.add_rule({
0,
1}, {
0});
tc.add_rule({
0,
2}, {
0});
tc.add_rule({
0,
3}, {
0});
tc.add_rule({
0,
4}, {
0});
tc.add_rule({
0,
5}, {
0});
tc.add_rule({
0,
6}, {
0});
tc.add_rule({
0,
7}, {
0});
tc.add_rule({
0,
8}, {
0});
tc.add_rule({
0,
9}, {
0});
tc.add_rule({
1,
0}, {
1});
tc.add_rule({
1,
1}, {
1});
tc.add_rule({
1,
2}, {
1});
tc.add_rule({
1,
3}, {
1});
tc.add_rule({
1,
4}, {
1});
tc.add_rule({
1,
5}, {
1});
tc.add_rule({
1,
6}, {
1});
tc.add_rule({
1,
7}, {
1});
tc.add_rule({
1,
8}, {
1});
tc.add_rule({
1,
9}, {
1});
tc.add_rule({
2,
0}, {
2});
tc.add_rule({
2,
1}, {
2});
tc.add_rule({
2,
2}, {
2});
tc.add_rule({
2,
3}, {
2});
tc.add_rule({
2,
4}, {
2});
tc.add_rule({
2,
5}, {
2});
tc.add_rule({
2,
6}, {
2});
tc.add_rule({
2,
7}, {
2});
tc.add_rule({
2,
8}, {
2});
tc.add_rule({
2,
9}, {
2});
tc.add_rule({
3,
0}, {
3});
tc.add_rule({
3,
1}, {
3});
tc.add_rule({
3,
2}, {
3});
tc.add_rule({
3,
3}, {
3});
tc.add_rule({
3,
4}, {
3});
tc.add_rule({
3,
5}, {
3});
tc.add_rule({
3,
6}, {
3});
tc.add_rule({
3,
7}, {
3});
tc.add_rule({
3,
8}, {
3});
tc.add_rule({
3,
9}, {
3});
tc.add_rule({
4,
0}, {
4});
tc.add_rule({
4,
1}, {
4});
tc.add_rule({
4,
2}, {
4});
tc.add_rule({
4,
3}, {
4});
tc.add_rule({
4,
4}, {
4});
tc.add_rule({
4,
5}, {
4});
tc.add_rule({
4,
6}, {
4});
tc.add_rule({
4,
7}, {
4});
tc.add_rule({
4,
8}, {
4});
tc.add_rule({
4,
9}, {
4});
tc.add_rule({
5,
0}, {
5});
tc.add_rule({
5,
1}, {
5});
tc.add_rule({
5,
2}, {
5});
tc.add_rule({
5,
3}, {
5});
tc.add_rule({
5,
4}, {
5});
tc.add_rule({
5,
5}, {
5});
tc.add_rule({
5,
6}, {
5});
tc.add_rule({
5,
7}, {
5});
tc.add_rule({
5,
8}, {
5});
tc.add_rule({
5,
9}, {
5});
tc.add_rule({
6,
0}, {
6});
tc.add_rule({
6,
1}, {
6});
tc.add_rule({
6,
2}, {
6});
tc.add_rule({
6,
3}, {
6});
tc.add_rule({
6,
4}, {
6});
tc.add_rule({
6,
5}, {
6});
tc.add_rule({
6,
6}, {
6});
tc.add_rule({
6,
7}, {
6});
tc.add_rule({
6,
8}, {
6});
tc.add_rule({
6,
9}, {
6});
tc.add_rule({
7,
0}, {
7});
tc.add_rule({
7,
1}, {
7});
tc.add_rule({
7}, {
7,
2});
tc.add_rule({
7,
3}, {
7});
tc.add_rule({
7,
4}, {
7});
tc.add_rule({
7,
5}, {
7});
tc.add_rule({
7,
6}, {
7});
tc.add_rule({
7,
7}, {
7});
tc.add_rule({
7,
8}, {
7});
tc.add_rule({
7,
9}, {
7});
tc.add_rule({
8,
0}, {
8});
tc.add_rule({
8,
1}, {
8});
tc.add_rule({
8,
2}, {
8});
tc.add_rule({
8,
3}, {
8});
tc.add_rule({
8,
4}, {
8});
tc.add_rule({
8,
5}, {
8});
tc.add_rule({
8,
6}, {
8});
tc.add_rule({
8,
7}, {
8});
tc.add_rule({
8,
8}, {
8});
tc.add_rule({
8,
9}, {
8});
tc.add_rule({
9,
0}, {
9});
tc.add_rule({
9,
0,
1,
2,
3,
4,
5,
5,
1,
5,
6,
9,
8,
8,
8,
8,
8,
0}, {
9});
tc.congruence().sort_generating_pairs(recursive_path_compare);
check_felsch(tc);
check_hlt(tc);
check_random(tc);
REQUIRE(tc.size() ==
10);
REQUIRE_THROWS_AS(tc.congruence().sort_generating_pairs(shortlex_compare),
LibsemigroupsException);
}
LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
"
099",
"short circuit size in obviously infinite",
"[todd-coxeter][quick]") {
auto rg = ReportGuard(REPORT);
ToddCoxeter tc;
tc.set_alphabet("abc");
tc.add_rule("aaaa", "a");
REQUIRE(tc.size() == POSITIVE_INFINITY);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
100",
"
http://brauer.maths.qmul.ac.uk/Atlas/misc/24A8/mag/
24A8G1-P1.M",
"[todd-coxeter][standard]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "X");
tc.add_rule("yyyyyy", "Y");
tc.add_rule("YXyx", "XYxy");
tc.add_rule("xYYYxYYYxYY", "yyXyyyXyyyX");
tc.add_rule("xyxyyXyxYYxyyyx", "yyyXyyy");
tc.congruence()
.next_lookahead(
2'
000'
000)
.strategy(options::strategy::hlt)
.sort_generating_pairs()
.lookahead(options::lookahead::partial)
.standardize(true);
tc.congruence().run();
REQUIRE(tc.size() ==
322'
560);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
101",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/M11/mag/M11G1-P1.M",
"[todd-coxeter][quick][no-coverage][no-valgrind]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyyxyy", "e");
tc.add_rule("xyxyxYxyxyyxYxyxYxY", "e");
REQUIRE(tc.size() ==
7'
920);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
102",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/M12/mag/M12G1-P1.M",
"[todd-coxeter][standard]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("xyxyxYxyxyxYxyxyxYxyxyxYxyxyxYxyxyxY", "e");
tc.add_rule("XYXYxyxyXYXYxyxyXYXYxyxyXYXYxyxyXYXYxyxy", "e");
REQUIRE(tc.size() ==
95'
040);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
103",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/M22/mag/M22G1-P1.M",
"[todd-coxeter][extreme]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("XYXYxyxyXYXYxyxyXYXYxyxy", "e");
tc.add_rule("xyxyxYxyxyxYxyxyxYxyxyxYxyxyxY", "e");
REQUIRE(tc.size() ==
443'
520);
}
// Takes about
4 minutes (
2021 - MacBook Air M1 -
8GB RAM)
// with Felsch (
3.
5mins or
2.
5mins with lowerbound) or HLT (
4.
5mins)
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
104",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/M23/mag/M23G1-P1.M",
"[todd-coxeter][extreme]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyyxyy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("xyxYxyyxyxYxyyxyxYxyyxyxYxyy", "e");
tc.add_rule("xyxyxyxYxyyxyxYxyxYxyxyxyxYxYxY", "e");
tc.add_rule("xyxyyxyyxyxyyxyyxyxyyxyyxyxyyxyyxyxyyxyyxyxyyxyy", "e");
tc.add_rule("xyxyyxyxyyxyxyyxyyxYxyyxYxyxyyxyxYxyy", "e");
tc.congruence()
.sort_generating_pairs()
.strategy(options::strategy::felsch)
.use_relations_in_extra(true)
.lower_bound(
10'
200'
960)
.deduction_policy(options::deductions::v2
| options::deductions::no_stack_if_no_space)
.reserve(
50'
000'
000);
std::cout << tc.congruence().settings_string();
tc.congruence().run();
REQUIRE(tc.size() ==
10'
200'
960);
}
// Takes about
3 minutes
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
105",
"
http://brauer.maths.qmul.ac.uk/Atlas/clas/S62/mag/S62G1-P1.M",
"[todd-coxeter][extreme]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxyXYxyXYxyXYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("XYXYxyxyXYXYxyxyXYXYxyxyXYXYxyxyXYXYxyxy", "e");
tc.add_rule("xyxyxYxyxyxYxyxyxYxyxYxYxyxYxYxyxYxY", "e");
tc.add_rule("xyxyxYxyxYxyxYxyxyxYxyxYxyxYxyxyxYxyxYxyxYxyxyxYxyxYxyxY",
"e");
congruence::ToddCoxeter tc2(congruence_kind::right, tc);
tc2.add_pair(tc.string_to_word("xy"), tc.string_to_word("e"));
REQUIRE(tc2.number_of_classes() ==
10'
644'
480);
}
// Approx.
32 minutes (
2021 - MacBook Air M1 -
8GB RAM)
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
106",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/HS/mag/HSG1-P1.M",
"[todd-coxeter][extreme]") {
auto rg = ReportGuard();
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyyxyyxyyxyyxyyxyy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("XYXYxyxyXYXYxyxyXYXYxyxy", "e");
tc.add_rule("XYYxyyXYYxyyXYYxyyXYYxyyXYYxyyXYYxyy", "e");
tc.add_rule("xyxyxyyxYxYYxYxyyxyxyxYYxYYxYYxYY", "e");
tc.add_rule("xyxyyxYYxYYxyyxYYxYYxyyxyxyyxYxyyxYxyy", "e");
tc.add_rule("xyxyxyyxyyxyxYxYxyxyyxyyxyxyxYYxYxYY", "e");
tc.add_rule("xyxyxyyxYxYYxyxyxYxyxyxyyxYxYYxyxyxY", "e");
tc.add_rule("xyxyxyyxyxyxyyxyxyxYxyxyxyyxyyxyyxyxyxY", "e");
tc.add_rule("xyxyxyyxyxyyxyxyyxyxyxyyxYxyxYYxyxYxyy", "e");
congruence::ToddCoxeter tc2(congruence_kind::right, tc);
tc2.add_pair(tc.string_to_word("xy"), tc.string_to_word("e"));
tc2.sort_generating_pairs()
.use_relations_in_extra(true)
.strategy(options::strategy::hlt)
.lookahead(options::lookahead::felsch | options::lookahead::partial);
REQUIRE(tc2.number_of_classes() ==
4'
032'
000);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
107",
"
http://brauer.maths.qmul.ac.uk/Atlas/spor/J1/mag/J1G1-P1.M",
"[todd-coxeter][standard]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyy", "e");
tc.add_rule("xyxyxyxyxyxyxy", "e");
tc.add_rule("xyxyxYxyxYxyxYxyxyxYxyxYxyxYxyxyxYxyxYxyxYxyxyxYxyxYxyxYxyxy"
"xYxyxYxyxY",
"e");
tc.add_rule("xyxyxYxyxYxyxYxyxYxyxYxyxYxyxyxYxYxyxyxYxyxYxyxYxyxYxyxYxyxY"
"xyxyxYxY",
"e");
REQUIRE(tc.size() ==
175'
560);
}
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
108",
"
http://brauer.maths.qmul.ac.uk/Atlas/lin/L34/mag/L34G1-P1.M",
"[todd-coxeter][quick][no-coverage][no-valgrind]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyy", "e");
tc.add_rule("xyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyy", "e");
tc.add_rule("XYxyXYxyXYxyXYxyXYxy", "e");
tc.add_rule("xyxyxYxyxyxYxyxyxYxyxyxYxyxyxY", "e");
tc.add_rule("xyxyxyyxYxyxyxyyxYxyxyxyyxYxyxyxyyxYxyxyxyyxY", "e");
REQUIRE(tc.size() ==
20'
160);
}
// Takes about
10 seconds (
2021 - MacBook Air M1 -
8GB RAM)
LIBSEMIGROUPS_TEST_CASE(
"ToddCoxeter",
"
109",
"
http://brauer.maths.qmul.ac.uk/Atlas/clas/S62/mag/S62G1-P1.M",
"[todd-coxeter][extreme]") {
ToddCoxeter tc;
tc.set_alphabet("xyXYe");
tc.set_identity("e");
tc.set_inverses("XYxye");
tc.add_rule("xx", "e");
tc.add_rule("yyyyyyy", "e");
tc.add_rule("xyxyxyxyxyxyxyxyxy", "e");
tc.add_rule("xyyxyyxyyxyyxyyxyyxyyxyyxyyxyyxyyxyy", "e");
tc.add_rule("XYXYXYxyxyxyXYXYXYxyxyxy", "e");
tc.add_rule("XYxyXYxyXYxy", "e");
tc.add_rule("XYYxyyXYYxyy", "e");
REQUIRE(tc.size() ==
1'
451'
520);
std::cout << tc.congruence().stats_string();
}
} // namespace fpsemigroup
} // namespace libsemigroups
