//
// 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
