| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/tests/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.5.2025 mit Größe 93 kB |
|
Quelle test-kambites.cpp Sprache: C |
|||||||||
|
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021 James D. Mitchell + Maria Tsalakou // // 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/>. // #include <stddef.h> // for size_t #include <algorithm> // for count_if, all_of #include <iostream> // for string, char_traits #include <iterator> // for distance #include <memory> // for allocator, shared_ptr #include <string> // for basic_string, operator==, operator!=, operator+ #include <unordered_set> // for unordered_set #include <vector> // for vector #include "catch.hpp" // for REQUIRE, REQUIRE_THROWS_AS #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE #include "libsemigroups/constants.hpp" // for UNDEFINED #include "libsemigroups/froidure-pin-base.hpp" // for FroidurePinBase #include "libsemigroups/iterator.hpp" // for ConstIteratorStateful #include "libsemigroups/kambites.hpp" // for Kambites #include "libsemigroups/knuth-bendix.hpp" // for KnuthBendix #include "libsemigroups/report.hpp" // for ReportGuard #include "libsemigroups/siso.hpp" // for const_sislo_iterator #include "libsemigroups/string.hpp" // for random_string etc #include "libsemigroups/transf.hpp" // for LeastTransf #include "libsemigroups/types.hpp" // for tril etc #include "libsemigroups/word.hpp" // for number_of_words namespace libsemigroups { struct LibsemigroupsException; // Forward decl constexpr bool REPORT = false; using detail::MultiStringView; using detail::random_string; namespace { // TODO(later) remove this, or put it in test-suffix-tree.cpp template <typename T> size_t number_of_subwords(T first, T last) { std::unordered_set<std::string> mp; for (auto it = first; it < last; ++it) { { auto& w = it->first; for (auto suffix = w.cbegin(); suffix < w.cend(); ++suffix) { for (auto prefix = suffix + 1; prefix < w.cend(); ++prefix) { mp.emplace(suffix, prefix); } } } { auto& w = it->second; for (auto suffix = w.cbegin(); suffix < w.cend(); ++suffix) { for (auto prefix = suffix + 1; prefix < w.cend(); ++prefix) { mp.emplace(suffix, prefix); } } } } return mp.size(); } // TODO(later) remove this template <typename T> size_t sum_lengths(T first, T last) { size_t result = 0; for (auto it = first; it < last; ++it) { result += it->first.size(); result += it->second.size(); } return result; } std::string random_power_string(std::string const& s, std::string const& t, std::string const& u, size_t exp) { static std::random_device rd; static std::mt19937 generator(rd()); static std::uniform_int_distribution<> distribution(0, 2); std::string result = ""; while (exp > 0) { switch (distribution(generator)) { case 0: { result += s; break; } case 1: { result += t; break; } case 2: { result += u; } default: break; } exp--; } return result; } // std::string swap_a_and_b(std::string const& w) { // std::string result; // for (auto l : w) { // if (l == 'a') { // result += "b"; // } else if (l == '#') { // result += '#'; // } else { // result += "a"; // } // } // return result; // } auto sample(std::string A, size_t R, size_t min, size_t max, size_t sample_size) { if (min < 7) { LIBSEMIGROUPS_EXCEPTION("the minimum value of // Otherwise we get lhs = rhs in many of the things below and this // skews the results. } else if (min < max && max - min <= 1) { LIBSEMIGROUPS_EXCEPTION( "the minimum and maximum values must be at least 2 apart"); } auto rg = ReportGuard(false); uint64_t total_c4 = 0; uint64_t total_confluent = 0; for (size_t j = 0; j < sample_size; ++j) { fpsemigroup::Kambites<std::string> k; k.set_alphabet(A); fpsemigroup::KnuthBendix kb1; kb1.set_alphabet(A); fpsemigroup::KnuthBendix kb2; std::reverse(A.begin(), A.end()); kb2.set_alphabet(A); std::reverse(A.begin(), A.end()); for (size_t r = 0; r < R; ++r) { auto lhs = random_string(A, min, max); std::string rhs; if (lhs.size() == min) { rhs = random_string(A, min + 1, max); } else { rhs = random_string(A, min, lhs.size()); } k.add_rule(lhs, rhs); kb1.add_rule(lhs, rhs); kb2.add_rule(lhs, rhs); } kb1.run_for(std::chrono::milliseconds(1)); kb2.run_for(std::chrono::milliseconds(1)); if (k.small_overlap_class() >= 4) { total_c4++; } if (kb1.confluent() || kb2.confluent()) { total_confluent++; } } return std::make_tuple(total_c4, total_confluent); } std::array<std::string, 5> swap_a_b_c(std::string const& w) { static std::array<std::string, 5> perms = {"bac", "acb", "cba", "bca", "cab"}; std::array<std::string, 5> result; size_t count = 0; for (auto const& p : perms) { std::string ww; for (auto l : w) { if (l == 'a') { ww += p[0]; } else if (l == 'b') { ww += p[1]; } else { ww += p[2]; } } result[count] = ww; count++; } return result; } } // namespace #ifdef false namespace { Kambites<> random_example(std::string const& alphabet) { static std::random_device rd; static std::mt19937 generator(rd()); std::uniform_int_distribution<> distribution(1, 25); Kambites<> k; k.set_alphabet(alphabet); std::vector<std::string> pieces; for (size_t i = 0; i < 13; ++i) { pieces.push_back(random_string(alphabet, distribution(generator))); } k.add_rule(pieces[0] + pieces[1] + pieces[2] + pieces[3], pieces[2] + pieces[0] + pieces[7] + pieces[4]); k.add_rule(pieces[4] + pieces[0] + pieces[5], pieces[6]); k.add_rule(pieces[7] + pieces[1] + pieces[8], pieces[9]); k.add_rule(pieces[10] + pieces[3] + pieces[11], pieces[12]); std::cout << "k.add_rule(\"" << pieces[0] + pieces[1] + pieces[2] + pieces[3] << "\", \"" << pieces[2] + pieces[0] + pieces[7] + pieces[4] << "\");\n"; std::cout << "k.add_rule(\"" << pieces[4] + pieces[0] + pieces[5] << "\", \"" << pieces[6] << "\");\n"; std::cout << "k.add_rule(\"" << pieces[7] + pieces[1] + pieces[8] << "\", \"" << pieces[9] << "\");\n"; std::cout << "k.add_rule(\"" << pieces[10] + pieces[3] + pieces[11] << "\", \"" << pieces[12] << "\");\n"; return k; } } // namespace #endif namespace fpsemigroup { //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_4() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefg"); k.add_rule("abcd", "aaaeaa"); k.add_rule("ef", "dg"); REQUIRE(k.equal_to("abcd", "aaaeaa")); REQUIRE(k.equal_to("ef", "dg")); REQUIRE(k.equal_to("aaaaaef", "aaaaadg")); REQUIRE(k.equal_to("efababa", "dgababa")); k.froidure_pin()->enumerate(100); REQUIRE(k.froidure_pin()->current_size() == 8205); } LIBSEMIGROUPS_TEST_CASE("Kambites", "000", "(fpsemi) MT test 4 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_4<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "001", "(fpsemi) MT test 4 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_4<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_no_name_1() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("aAbBcCe"); k.add_rule("aaa", "e"); k.add_rule("bbb", "e"); k.add_rule("ccc", "e"); k.add_rule("ABa", "BaB"); k.add_rule("bcB", "cBc"); k.add_rule("caC", "aCa"); k.add_rule("abcABCabcABCabcABC", "e"); k.add_rule("BcabCABcabCABcabCA", "e"); k.add_rule("cbACBacbACBacbACBa", "e"); REQUIRE(k.number_of_pieces(0) == 2); REQUIRE(k.number_of_pieces(1) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(2) == 2); REQUIRE(k.number_of_pieces(3) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(4) == 2); REQUIRE(k.number_of_pieces(5) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(6) == 2); REQUIRE(k.number_of_pieces(7) == 2); REQUIRE(k.number_of_pieces(8) == 2); REQUIRE(k.number_of_pieces(9) == 2); REQUIRE(k.number_of_pieces(10) == 2); REQUIRE(k.number_of_pieces(11) == 2); REQUIRE(k.number_of_pieces(12) == 2); REQUIRE(k.number_of_pieces(13) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(14) == 2); REQUIRE(k.number_of_pieces(15) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(16) == 2); REQUIRE(k.number_of_pieces(17) == POSITIVE_INFINITY); REQUIRE(k.small_overlap_class() == 2); } LIBSEMIGROUPS_TEST_CASE("Kambites", "002", "(fpsemi) number_of_pieces (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_no_name_1<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "003", "(fpsemi) number_of_pieces (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_no_name_1<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_no_name_2() { auto rg = ReportGuard(REPORT); for (size_t i = 4; i < 20; ++i) { std::string lhs; for (size_t b = 1; b <= i; ++b) { lhs += "a" + std::string(b, 'b'); } std::string rhs; for (size_t b = i + 1; b <= 2 * i; ++b) { rhs += "a" + std::string(b, 'b'); } Kambites<T> k; k.set_alphabet("ab"); k.add_rule(lhs, rhs); REQUIRE(k.number_of_pieces(0) == i); REQUIRE(k.number_of_pieces(1) == i + 1); REQUIRE(k.small_overlap_class() == i); } } LIBSEMIGROUPS_TEST_CASE("Kambites", "004", "(fpsemi) small_overlap_class (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_no_name_2<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "005", "(fpsemi) small_overlap_class (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_no_name_2<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_random() { auto rg = ReportGuard(REPORT); { Kambites<T> k; k.set_alphabet("abcdefghi"); k.add_rule("eiehiegiggfaigcdfdfdgiidcebacgfaf", "cgfaeiehiegiggfaigcdfdfdgigcccbddchbbhgaaedfiiahhehihcba"); k.add_rule("hihcbaeiehiegiggfaigcdfdfdgiefhbidhbdgb", "chhfgafiiddg"); k.add_rule("gcccbddchbbhgaaedfiiahheidcebacbdefegcehgffedacddiaiih", "eddfcfhbedecacheahcdeeeda"); k.add_rule("dfbiccfeagaiffcfifg", "dceibahghaedhefh"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 3762); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 254); REQUIRE(n * n == 64516); } { Kambites<T> k; k.set_alphabet("abcdefghi"); k.add_rule("feffgccdgcfbeagiifheabecdfbgebfcibeifibccahaafabeihfgfieade" "bciheddeigbaf", "ifibccahaafabeihfgfiefeffgccdgcfbeagiifheabecfeibghddfgbaia" "acghhdhggagaide"); k.add_rule("ghhdhggagaidefeffgccdgcfbeagiifheabeccbeiddgdcbcf", "ahccccffdeb"); k.add_rule("feibghddfgbaiaacdfbgebfcibeieaacdbdb", "gahdfgbghhhbcci"); k.add_rule("dgibafaahiabfgeiiibadebciheddeigbaficfbfdbfbbiddgdcifbe", "iahcfgdbggaciih"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 7197); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 327); REQUIRE(n * n == 106929); } { Kambites<T> k; k.set_alphabet("abcdefghi"); k.add_rule("adichhbhibfchbfbbibaidfibifgagcgdedfeeibhggdbchfdaefbefcbaa" "hcbhbidgaahbahhahhb", "edfeeibhggdbchfdaefbeadichhbhibfchbfbbibaiihebabeabahcgdbic" "bgiciffhfggbfadf"); k.add_rule("bgiciffhfggbfadfadichhbhibfchbfbbibaaggfdcfcebehhbdegiaeaf", "hebceeicbhidcgahhcfbb"); k.add_rule("iihebabeabahcgdbicidfibifgagcgdedehed", "ecbcgaieieicdcdfdbgagdbf"); k.add_rule("iagaadbfcbaahcbhbidgaahbahhahhbd", "ddddh"); REQUIRE(k.small_overlap_class() == 3); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 7408); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 330); REQUIRE(n * n == 108900); } { Kambites<T> k; k.set_alphabet("abcdefghi"); k.add_rule("ibddgdgddiabcahbidbedffeddciiabahbbiacbfehdfccacbhgafbgcdg", "iabahibddgdgddbdfacbafhcgfhdheieihd"); k.add_rule("hdheieihdibddgdgddebhaeaicciidebegg", "giaeehdeeec"); k.add_rule("bdfacbafhcgfiabcahbidbedffeddcifdfcdcdadhhcbcbebhei", "icaebehdff"); k.add_rule("aggiiacdbbiacbfehdfccacbhgafbgcdghiahfccdchaiagaha", "hhafbagbhghhihg"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 4560); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 265); REQUIRE(n * n == 70225); } { Kambites<T> k; k.set_alphabet("abcdefghi"); k.add_rule( "fibehffegdeggaddgfdaeaiacbhbgbbccceaibfcabbiedhecggbbdgihddd", "ceafibehffegdeggafidbaefcebegahcbhciheceaehaaehih"); k.add_rule("haaehihfibehffegdeggaecbedccaeabifeafi", "bfcccibgefiidgaih"); k.add_rule("fidbaefcebegahcbhciheceaeddgfdaeaiacbhbgbbcccgiahbibehgbgab" "efdieiggc", "abigdadaecdfdeeciggbdfdf"); k.add_rule("eeaaiicigieiabibfcabbiedhecggbbdgihdddifadgbgidbfeg", "daheebdgdiaeceeiicddg"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 6398); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 328); REQUIRE(n * n == 107584); } } LIBSEMIGROUPS_TEST_CASE("Kambites", "006", "(fpsemi) random (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_random<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "007", "(fpsemi) random (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_random<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_knuth_bendix_055() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefg"); k.add_rule("abcd", "ce"); k.add_rule("df", "dg"); REQUIRE(k.small_overlap_class() == POSITIVE_INFINITY); REQUIRE(k.is_obviously_infinite()); REQUIRE(k.equal_to("dfabcdf", "dfabcdg")); REQUIRE(k.normal_form("dfabcdg") == "dfabcdf"); REQUIRE(k.equal_to("abcdf", "ceg")); REQUIRE(k.equal_to("abcdf", "cef")); REQUIRE(k.equal_to("dfabcdf", "dfabcdg")); REQUIRE(k.equal_to("abcdf", "ceg")); REQUIRE(k.equal_to("abcdf", "cef")); REQUIRE(k.normal_form("abcdfceg") == "abcdfabcdf"); REQUIRE(k.equal_to("abcdfceg", "abcdfabcdf")); REQUIRE(k.size() == POSITIVE_INFINITY); REQUIRE(number_of_words(k.alphabet().size(), 0, 6) == 19608); REQUIRE(k.number_of_normal_forms(0, 6) == 17921); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 7); // REQUIRE(std::vector<std::string>(k.cbegin_normal_forms(0, 2), // k.cend_normal_forms()) // == std::vector<std::string>({"a", "b", "c", "d", "e", "f", // "g"})); } LIBSEMIGROUPS_TEST_CASE("Kambites", "008", "(fpsemi) KnuthBendix 055 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_knuth_bendix_055<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "009", "(fpsemi) KnuthBendix 055 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_knuth_bendix_055<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_gap_smalloverlap_85() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("cab"); k.add_rule("aabc", "acba"); REQUIRE(!k.equal_to("a", "b")); REQUIRE(k.equal_to("aabcabc", "aabccba")); REQUIRE(k.size() == POSITIVE_INFINITY); REQUIRE(number_of_words(3, 4, 16) == 21523320); REQUIRE(std::distance(cbegin_sislo("cab", "aabc", "aaabc"), cend_sislo("cab", "aabc", "aaabc")) == 162); REQUIRE(std::count_if( cbegin_sislo("cab", "cccc", "ccccc"), cend_sislo("cab", "cccc", "ccccc"), [&k](std::string const& w) { return k.equal_to(w, "acba"); }) == 2); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "010", "(fpsemi) smalloverlap/gap/test.gi:85 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_gap_smalloverlap_85<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "011", "(fpsemi) smalloverlap/gap/test.gi:85 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_gap_smalloverlap_85<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// LIBSEMIGROUPS_TEST_CASE("Kambites", "012", "(fpsemi) free semigroup", "[quick][kambites][fpsemigroup][fpsemi]") { Kambites<std::string> k; k.set_alphabet("cab"); REQUIRE(k.small_overlap_class() == POSITIVE_INFINITY); Kambites<detail::MultiStringView> kk; kk.set_alphabet("cab"); REQUIRE(kk.small_overlap_class() == POSITIVE_INFINITY); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_gap_smalloverlap_49() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefgh"); k.add_rule("abcd", "ce"); k.add_rule("df", "hd"); REQUIRE(k.is_obviously_infinite()); REQUIRE(k.equal_to("abchd", "abcdf")); REQUIRE(!k.equal_to("abchf", "abcdf")); REQUIRE(k.equal_to("abchd", "abchd")); REQUIRE(k.equal_to("abchdf", "abchhd")); // Test cases (4) and (5) REQUIRE(k.equal_to("abchd", "cef")); REQUIRE(k.equal_to("cef", "abchd")); REQUIRE(k.size() == POSITIVE_INFINITY); REQUIRE(k.number_of_normal_forms(0, 6) == 35199); REQUIRE(k.normal_form("hdfabce") == "dffababcd"); REQUIRE(k.equal_to("hdfabce", "dffababcd")); // TODO(later) include when we have cbegin_normal_forms, // cend_normal_forms // REQUIRE(std::vector<std::string>(k.cbegin_normal_forms(0, 2), // k.cend_normal_forms()) // == std::vector<std::string>( // {"a", "b", "c", "d", "e", "f", "g", "h"}));*/ } LIBSEMIGROUPS_TEST_CASE( "Kambites", "013", "(fpsemi) smalloverlap/gap/test.gi:49 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_gap_smalloverlap_49<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "014", "(fpsemi) smalloverlap/gap/test.gi:49 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_gap_smalloverlap_49<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_gap_smalloverlap_63() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefgh"); k.add_rule("afh", "bgh"); k.add_rule("hc", "d"); REQUIRE(k.is_obviously_infinite()); // Test case (6) REQUIRE(k.equal_to("afd", "bgd")); REQUIRE(k.equal_to("bghcafhbgd", "afdafhafd")); REQUIRE(k.normal_form("bghcafhbgd") == "afdafhafd"); REQUIRE(k.number_of_normal_forms(0, 6) == 34819); REQUIRE(k.size() == POSITIVE_INFINITY); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "015", "(fpsemi) smalloverlap/gap/test.gi:63 (std::string)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_gap_smalloverlap_63<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "016", "(fpsemi) smalloverlap/gap/test.gi:63 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_gap_smalloverlap_63<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_gap_smalloverlap_70() { auto rg = ReportGuard(REPORT); // The following permits a more complex test of case (6), which also // involves using the case (2) code to change the prefix being looked // for: Kambites<T> k; k.set_alphabet("abcdefghij"); k.add_rule("afh", "bgh"); k.add_rule("hc", "de"); k.add_rule("ei", "j"); REQUIRE(k.number_of_normal_forms(0, 6) == 102255); REQUIRE(k.is_obviously_infinite()); REQUIRE(k.equal_to("afdj", "bgdj")); REQUIRE(!k.equal_to("xxxxxxxxxxxxxxxxxxxxxxx", "b")); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "017", "(fpsemi) smalloverlap/gap/test.gi:70 (std::string)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_gap_smalloverlap_70<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "018", "(fpsemi) smalloverlap/gap/test.gi:70 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_gap_smalloverlap_70<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_1_million_equals() { auto rg = ReportGuard(REPORT); // A slightly more complicated presentation for testing case (6), in // which the max piece suffixes of the first two relation words no // longer agree (since fh and gh are now pieces). Kambites<T> k; k.set_alphabet("abcdefghijkl"); k.add_rule("afh", "bgh"); k.add_rule("hc", "de"); k.add_rule("ei", "j"); k.add_rule("fhk", "ghl"); REQUIRE(k.is_obviously_infinite()); REQUIRE(k.equal_to("afdj", "bgdj")); REQUIRE(k.equal_to("afdj", "afdj")); REQUIRE(k.normal_form("bfhk") == "afhl"); REQUIRE(k.equal_to("bfhk", "afhl")); REQUIRE(k.size() == POSITIVE_INFINITY); size_t N = std::distance(cbegin_sislo("abcdefghijkl", "a", "bgdk"), cend_sislo("abcdefghijkl", "a", "bgdk")); REQUIRE(N == 4522); size_t M = 0; for (auto it1 = cbegin_sislo("abcdefghijkl", "a", "bgdk"); it1 != cend_sislo("abcdefghijkl", "a", "bgdk"); ++it1) { for (auto it2 = cbegin_sislo("abcdefghijkl", "a", "bgdk"); it2 != it1; ++it2) { M++; if (k.equal_to(*it1, *it2)) { N--; break; } } } REQUIRE(M == 10052729); REQUIRE(N == 4392); REQUIRE(k.number_of_normal_forms(0, 6) == 255932); // TODO(later) include when we have cbegin_normal_forms, // cend_normal_forms // REQUIRE( // std::vector<std::string>(k.cbegin_normal_forms(0, 2), // k.cend_normal_forms()) // == std::vector<std::string>( // {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", // "l"})); } LIBSEMIGROUPS_TEST_CASE("Kambites", "019", "(fpsemi) std::string smalloverlap/gap/test.gi:77 " "(infinite) (KnuthBendix 059)", "[standard][kambites][fpsemigroup][fpsemi]") { test_case_1_million_equals<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "020", "(fpsemi) MultiStringView smalloverlap/gap/test.gi:77 " "(infinite) (KnuthBendix 059)", "[standard][kambites][fpsemigroup][fpsemi]") { test_case_1_million_equals<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_code_cov() { auto rg = ReportGuard(REPORT); // A slightly more complicated presentation for testing case (6), in // which the max piece suffixes of the first two relation words no // longer agree (since fh and gh are now pieces). Kambites<T> k; k.set_alphabet("abcde"); k.add_rule("cadeca", "baedba"); REQUIRE(!k.equal_to("cadece", "baedce")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "021", "(fpsemi) code coverage (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_code_cov<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "022", "(fpsemi) code coverage (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_code_cov<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_ex_3_13_14() { auto rg = ReportGuard(REPORT); // Example 3.13 + 3.14 Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abbba", "cdc"); std::string p = "c"; REQUIRE(k.normal_form("cdcdcabbbabbbabbcd") == "abbbadcabbbabbbabbcd"); REQUIRE(k.equal_to(k.normal_form("cdcdcabbbabbbabbcd"), "cdcdcabbbabbbabbcd")); REQUIRE(k.equal_to("abbbadcbbba", "cdabbbcdc")); REQUIRE(k.equal_to(k.normal_form("cdabbbcdc"), "cdabbbcdc")); REQUIRE(k.normal_form("cdabbbcdc") == "abbbadcbbba"); } LIBSEMIGROUPS_TEST_CASE("Kambites", "023", "(fpsemi) prefix (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_13_14<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "024", "(fpsemi) prefix (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_13_14<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_ex_3_15() { auto rg = ReportGuard(REPORT); // Example 3.15 Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("aabc", "acba"); std::string original = "cbacbaabcaabcacbacba"; std::string expected = "cbaabcabcaabcaabcabc"; REQUIRE(k.equal_to("cbaabcabcaabcaabccba", original)); REQUIRE(k.equal_to(original, expected)); REQUIRE(k.equal_to(expected, original)); REQUIRE(k.equal_to("cbaabcabcaabcaabccba", expected)); REQUIRE(k.equal_to(original, "cbaabcabcaabcaabccba")); REQUIRE(k.equal_to(expected, "cbaabcabcaabcaabccba")); REQUIRE(k.equal_to(k.normal_form(original), original)); REQUIRE(k.normal_form(original) == expected); } LIBSEMIGROUPS_TEST_CASE("Kambites", "025", "(fpsemi) normal_form (Example 3.15) (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_15<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "026", "(fpsemi) normal_form (Example 3.15) (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_15<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_ex_3_16() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abcd", "acca"); std::string original = "bbcabcdaccaccabcddd"; std::string expected = "bbcabcdabcdbcdbcddd"; REQUIRE(k.equal_to(original, expected)); REQUIRE(k.equal_to(expected, original)); REQUIRE(k.normal_form(original) == expected); REQUIRE(k.equal_to(k.normal_form(original), original)); } LIBSEMIGROUPS_TEST_CASE("Kambites", "027", "(fpsemi) normal_form (Example 3.16) (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_16<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "028", "(fpsemi) normal_form (Example 3.16) (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_ex_3_16<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_ex_3_16_again() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abcd", "acca"); REQUIRE(std::all_of( cbegin_sislo("abcd", "a", "aaaa"), cend_sislo("abcd", "a", "aaaa"), [&k](std::string const& w) { return k.normal_form(w) == w; })); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaa", "aaaaa"), cend_sislo("abcd", "aaaa", "aaaaa"), [&k](std::string const& w) { return k.normal_form(w) != w; }) == 1); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaaa", "aaaaaa"), cend_sislo("abcd", "aaaaa", "aaaaaa"), [&k](std::string const& w) { return k.normal_form(w) != w; }) == 8); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaaaa", "aaaaaaa"), cend_sislo("abcd", "aaaaaa", "aaaaaaa"), [&k](std::string const& w) { return k.normal_form(w) != w; }) == 48); { std::string w = k.normal_form("accaccabd"); REQUIRE(w == "abcdbcdbd"); REQUIRE(std::count_if(cbegin_sislo("abcd", "aaaaaaaaa", w), cend_sislo("abcd", "aaaaaaaaa", w), [&k, &w](std::string const& u) { return !k.equal_to(u, w); }) == std::distance(cbegin_sislo("abcd", "aaaaaaaaa", w), cend_sislo("abcd", "aaaaaaaaa", w))); } { std::string w = k.normal_form("accbaccad"); REQUIRE(w == "accbabcdd"); REQUIRE(std::count_if(cbegin_sislo("abcd", "aaaaaaaaa", w), cend_sislo("abcd", "aaaaaaaaa", w), [&k, &w](std::string const& u) { return !k.equal_to(u, w); }) == std::distance(cbegin_sislo("abcd", "aaaaaaaaa", w), cend_sislo("abcd", "aaaaaaaaa", w))); } { std::string w = k.normal_form("abcdbcacca"); REQUIRE(w == "abcdbcabcd"); REQUIRE(k.equal_to(w, "abcdbcacca")); REQUIRE( std::count_if( cbegin_sislo("abcd", std::string(w.size(), 'a'), w), cend_sislo("abcd", std::string(w.size(), 'a'), w), [&k, &w](std::string const& u) { return !k.equal_to(u, w); }) == std::distance( cbegin_sislo("abcd", std::string(w.size(), 'a'), w), cend_sislo("abcd", std::string(w.size(), 'a'), w))); } } LIBSEMIGROUPS_TEST_CASE( "Kambites", "029", "(fpsemi) normal_form (Example 3.16) more exhaustive (std::string)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_ex_3_16_again<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "030", "(fpsemi) normal_form (Example 3.16) more exhaustive (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_ex_3_16_again<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_small() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("ab"); REQUIRE(k.is_obviously_infinite()); REQUIRE(k.size() == POSITIVE_INFINITY); k.add_rule("aaa", "a"); k.add_rule("a", "bb"); REQUIRE(k.small_overlap_class() == 1); REQUIRE_THROWS_AS(k.size(), LibsemigroupsException); REQUIRE_THROWS_AS(k.equal_to("a", "aaa"), LibsemigroupsException); REQUIRE(!k.finished()); k.run(); REQUIRE(!k.finished()); } LIBSEMIGROUPS_TEST_CASE("Kambites", "031", "(fpsemi) small presentation (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_small<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "032", "(fpsemi) small presentation (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_small<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_non_smalloverlap() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefg"); k.add_rule("abcd", "aaaeaa"); k.add_rule("ef", "dg"); k.add_rule("a", "b"); REQUIRE(k.small_overlap_class() == 1); REQUIRE_THROWS_AS(k.size(), LibsemigroupsException); REQUIRE_THROWS_AS(k.equal_to("a", "aaa"), LibsemigroupsException); REQUIRE(!k.finished()); k.run(); REQUIRE(!k.finished()); } LIBSEMIGROUPS_TEST_CASE("Kambites", "033", "(fpsemi) non-smalloverlap (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_non_smalloverlap<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "034", "(fpsemi) non-smalloverlap (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_non_smalloverlap<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_3() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abcd", "accca"); REQUIRE(k.number_of_pieces(0) == POSITIVE_INFINITY); REQUIRE(k.number_of_pieces(1) == 4); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("bbcabcdaccaccabcddd") == "bbcabcdaccaccabcddd"); REQUIRE(k.equal_to("bbcabcdaccaccabcddd", "bbcabcdaccaccabcddd")); k.run(); REQUIRE(k.started()); REQUIRE(k.finished()); Kambites<T> l(k); REQUIRE(l.started()); REQUIRE(l.finished()); REQUIRE(l.number_of_pieces(0) == POSITIVE_INFINITY); REQUIRE(l.number_of_pieces(1) == 4); REQUIRE(l.small_overlap_class() == 4); REQUIRE(l.normal_form("bbcabcdaccaccabcddd") == "bbcabcdaccaccabcddd"); REQUIRE(l.equal_to("bbcabcdaccaccabcddd", "bbcabcdaccaccabcddd")); REQUIRE(l.number_of_normal_forms(0, 0) == 0); REQUIRE(l.number_of_normal_forms(6, 6) == 0); REQUIRE(l.number_of_normal_forms(10, 1) == 0); } LIBSEMIGROUPS_TEST_CASE("Kambites", "035", "(fpsemi) MT test 3 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_3<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "036", "(fpsemi) MT test 3 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_3<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_5() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abc"); k.add_rule("ac", "cbbbbc"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("acbbbbc") == "aac"); REQUIRE(k.equal_to("acbbbbc", "aac")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "037", "(fpsemi) MT test 5 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_5<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "038", "(fpsemi) MT test 5 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_5<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_6() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abc"); k.add_rule("ccab", "cbac"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("bacbaccabccabcbacbac") == "bacbacbaccbaccbacbac"); REQUIRE(k.equal_to("bacbaccabccabcbacbac", "bacbacbaccbaccbacbac")); REQUIRE(k.normal_form("ccabcbaccab") == "cbaccbacbac"); REQUIRE(k.equal_to("ccabcbaccab", "cbaccbacbac")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "039", "(fpsemi) MT test 6 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_6<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "040", "(fpsemi) MT test 6 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_6<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_10() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefghij"); k.add_rule("afh", "bgh"); k.add_rule("hc", "de"); k.add_rule("ei", "j"); REQUIRE(k.small_overlap_class() == POSITIVE_INFINITY); REQUIRE(k.normal_form("bgdj") == "afdei"); REQUIRE(k.equal_to("bgdj", "afdei")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "041", "(fpsemi) MT test 10 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_6<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "042", "(fpsemi) MT test 10 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_6<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_13() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abcd", "dcba"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("dcbdcba") == "abcdbcd"); REQUIRE(k.equal_to("dcbdcba", "abcdbcd")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "043", "(fpsemi) MT test 13 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_13<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "044", "(fpsemi) MT test 13 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_13<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_14() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abca", "dcbd"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("dcbabca") == "abcacbd"); REQUIRE(k.equal_to("dcbabca", "abcacbd")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "045", "(fpsemi) MT test 14 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_14<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "046", "(fpsemi) MT test 14 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_14<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_15() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("abcd", "dcba"); k.add_rule("adda", "dbbd"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("dbbabcd") == "addacba"); REQUIRE(k.equal_to("dbbabcd", "addacba")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "047", "(fpsemi) MT test 15 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_15<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "048", "(fpsemi) MT test 15 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_15<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_16() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcdefg"); k.add_rule("abcd", "acca"); k.add_rule("gf", "ge"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("accabcdgf") == "abcdbcdge"); REQUIRE(k.equal_to("accabcdgf", "abcdbcdge")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "049", "(fpsemi) MT test 16 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_16<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "050", "(fpsemi) MT test 16 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_16<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_mt_17() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("ababbabbbabbbb", "abbbbbabbbbbbabbbbbbbabbbbbbbb"); k.add_rule("cdcddcdddcdddd", "cdddddcddddddcdddddddcdddddddd"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.normal_form("abbbacdddddcddddddcdddddddcdddddddd") == "abbbacdcddcdddcdddd"); REQUIRE(k.equal_to("abbbacdddddcddddddcdddddddcdddddddd", "abbbacdcddcdddcdddd")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "051", "(fpsemi) MT test 17 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_17<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "052", "(fpsemi) MT test 17 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_mt_17<MultiStringView>(); } /////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_1() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("acba", "aabc"); k.add_rule("acba", "dbbbd"); REQUIRE(k.small_overlap_class() == 4); REQUIRE(k.equal_to("aaabc", "adbbbd")); REQUIRE(k.equal_to("adbbbd", "aaabc")); REQUIRE(number_of_words(4, 4, 6) == 1280); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaa", "aaaaaa"), cend_sislo("abcd", "aaaa", "aaaaaa"), [&k](std::string const& w) { return k.equal_to("acba", w); }) == 3); REQUIRE(k.equal_to("aaabcadbbbd", "adbbbdadbbbd")); REQUIRE(k.equal_to("aaabcaaabc", "adbbbdadbbbd")); REQUIRE(k.equal_to("acba", "dbbbd")); REQUIRE(k.equal_to("acbabbbd", "aabcbbbd")); REQUIRE(k.equal_to("aabcbbbd", "acbabbbd")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "053", "(fpsemi) weak C(4) not strong x 1 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_1<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "054", "(fpsemi) weak C(4) not strong x 1 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_1<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_2() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("acba", "aabc"); k.add_rule("acba", "adbd"); REQUIRE(k.equal_to("acbacba", "aabcabc")); REQUIRE(k.normal_form("acbacba") == "aabcabc"); REQUIRE(k.equal_to(k.normal_form("acbacba"), "aabcabc")); REQUIRE(k.equal_to("aabcabc", k.normal_form("acbacba"))); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaa", "aaaaaa"), cend_sislo("abcd", "aaaa", "aaaaaa"), [&k](std::string const& w) { return k.equal_to("acba", w); }) == 3); } LIBSEMIGROUPS_TEST_CASE("Kambites", "055", "(fpsemi) weak C(4) not strong x 2 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_2<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "056", "(fpsemi) weak C(4) not strong x 2 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_2<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_3() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcde"); k.add_rule("bceac", "aeebbc"); k.add_rule("aeebbc", "dabcd"); REQUIRE(k.normal_form("bceacdabcd") == "aeebbcaeebbc"); REQUIRE(k.equal_to(k.normal_form("bceacdabcd"), "aeebbcaeebbc")); REQUIRE(k.equal_to("aeebbcaeebbc", k.normal_form("bceacdabcd"))); REQUIRE(std::count_if( cbegin_sislo("abcd", "aaaa", "aaaaaa"), cend_sislo("abcd", "aaaa", "aaaaaa"), [&k](std::string const& w) { return k.equal_to("acba", w); }) == 1); } LIBSEMIGROUPS_TEST_CASE("Kambites", "057", "(fpsemi) weak C(4) not strong x 3 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_3<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "058", "(fpsemi) weak C(4) not strong x 3 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_3<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_4() { auto rg = ReportGuard(REPORT); Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("acba", "aabc"); k.add_rule("acba", "dbbd"); REQUIRE(k.normal_form("bbacbcaaabcbbd") == "bbacbcaaabcbbd"); REQUIRE(k.equal_to(k.normal_form("bbacbcaaabcbbd"), "bbacbcaaabcbbd")); REQUIRE(k.equal_to("bbacbcaaabcbbd", k.normal_form("bbacbcaaabcbbd"))); REQUIRE(k.normal_form("acbacba") == "aabcabc"); REQUIRE(k.equal_to(k.normal_form("acbacba"), "aabcabc")); REQUIRE(k.equal_to("aabcabc", k.normal_form("acbacba"))); } LIBSEMIGROUPS_TEST_CASE("Kambites", "059", "(fpsemi) weak C(4) not strong x 4 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_4<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "060", "(fpsemi) weak C(4) not strong x 4 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_4<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_5() { Kambites<T> k; k.set_alphabet("abcde"); k.add_rule("abcd", "aaeaaa"); REQUIRE(number_of_subwords(k.cbegin_rules(), k.cend_rules()) == 16); size_t n = sum_lengths(k.cbegin_rules(), k.cend_rules()); REQUIRE(n == 10); REQUIRE(n * n == 100); } LIBSEMIGROUPS_TEST_CASE("Kambites", "061", "(fpsemi) weak C(4) not strong x 5 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_5<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "062", "(fpsemi) weak C(4) not strong x 5 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_5<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_weak_6() { Kambites<T> k; k.set_alphabet("abcd"); k.add_rule("acba", "aabc"); k.add_rule("acba", "adbd"); REQUIRE(k.normal_form("acbacba") == "aabcabc"); REQUIRE(k.equal_to(k.normal_form("acbacba"), "aabcabc")); } LIBSEMIGROUPS_TEST_CASE("Kambites", "063", "(fpsemi) weak C(4) not strong x 6 (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_6<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "064", "(fpsemi) weak C(4) not strong x 6 (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_weak_6<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_konovalov() { Kambites<T> k; k.set_alphabet("abAB"); k.add_rule("Abba", "BB"); k.add_rule("Baab", "AA"); REQUIRE(k.small_overlap_class() == 2); } LIBSEMIGROUPS_TEST_CASE("Kambites", "065", "(fpsemi) Konovalov example (std::string)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_konovalov<std::string>(); } LIBSEMIGROUPS_TEST_CASE("Kambites", "066", "(fpsemi) Konovalov example (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi]") { test_case_konovalov<MultiStringView>(); } //////////////////////////////////////////////////////////////////////// template <typename T> void test_case_long_words() { Kambites<T> k; k.set_alphabet("abcde"); k.add_rule("bceac", "aeebbc"); k.add_rule("aeebbc", "dabcd"); REQUIRE(k.small_overlap_class() == 4); std::string w1 = "bceac"; std::string w2 = "dabcd"; std::string w3 = "aeebbc"; auto lhs = random_power_string(w1, w2, w3, 4000); auto rhs = random_power_string(w1, w2, w3, 4000); for (size_t i = 0; i < 10; ++i) { REQUIRE(k.equal_to(lhs, rhs)); } } LIBSEMIGROUPS_TEST_CASE( "Kambites", "067", "(fpsemi) long words (std::string)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_long_words<std::string>(); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "068", "(fpsemi) long words (MultiStringView)", "[quick][kambites][fpsemigroup][fpsemi][no-valgrind]") { test_case_long_words<detail::MultiStringView>(); } //////////////////////////////////////////////////////////////////////// // Some tests for exploration of the space of all 2-generator 1-relation // semigroups //////////////////////////////////////////////////////////////////////// // TODO(v3) reuse the same Kambites in-place rather than this template <typename T> auto count_2_gen_1_rel(size_t min, size_t max) { Sislo x; x.alphabet("ab"); x.first(min); x.last(max); auto last = x.cbegin(); std::advance(last, std::distance(x.cbegin(), x.cend()) - 1); uint64_t total_c4 = 0; uint64_t total = 0; for (auto it1 = x.cbegin(); it1 != last; ++it1) { for (auto it2 = it1 + 1; it2 != x.cend(); ++it2) { total++; Kambites<std::string> k; k.set_alphabet("ab"); k.add_rule(*it1, *it2); if (k.small_overlap_class() >= 4) { total_c4++; } } } return std::make_pair(total_c4, total); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "069", "(fpsemi) almost all 2-generated 1-relation monoids are C(4)", "[extreme][kambites][fpsemigroup][fpsemi]") { auto x = count_2_gen_1_rel<std::string>(1, 7); REQUIRE(x.first == 1); REQUIRE(x.second == 7875); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "070", "(fpsemi) almost all 2-generated 1-relation monoids are C(4)", "[extreme][kambites][fpsemigroup][fpsemi]") { auto x = count_2_gen_1_rel<std::string>(1, 11); REQUIRE(x.first == 18171); REQUIRE(x.second == 2092035); } // Takes approx. 31s LIBSEMIGROUPS_TEST_CASE( "Kambites", "071", "(fpsemi) almost all 2-generated 1-relation monoids are C(4)", "[extreme][kambites][fpsemigroup][fpsemi]") { auto x = count_2_gen_1_rel<std::string>(1, 12); REQUIRE(x.first == 235'629); REQUIRE(x.second == 8'378'371); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "072", "(fpsemi) almost all 2-generated 1-relation monoids are C(4)", "[fail][kambites][fpsemigroup][fpsemi]") { auto x = count_2_gen_1_rel<std::string>(1, 13); REQUIRE(x.first == 0); REQUIRE(x.second == 0); } LIBSEMIGROUPS_TEST_CASE( "Kambites", "073", "(fpsemi) almost all 2-generated 1-relation monoids are C(4)", "[extreme][kambites][fpsemigroup][fpsemi]") { std::cout.precision(10); size_t const sample_size = 1000; std::cout << "Sample size = " << sample_size << std::endl; for (size_t i = 8; i < 100; ++i) { size_t const min = 7; size_t const max = i + 1; auto x = sample("ab", 1, min, max, sample_size); std::cout << "Estimate of C(4) / non-C(4) (length " << min << " to " << max << ") = " << std::fixed << double(std::get<0>(x)) / sample_size << std::endl; std::cout << "Estimate of confluent / non-confluent (length " << min << " to " << max << ") = " << std::fixed << double(std::get<1>(x)) / sample_size << std::endl << std::endl; } } //////////////////////////////////////////////////////////////////////// // Some tests for exploration of the space of all 3-generator 1-relation // semigroups //////////////////////////////////////////////////////////////////////// LIBSEMIGROUPS_TEST_CASE("Kambites", "074", "(fpsemi) 3-generated 1-relation C(4)-semigroups", "[extreme][kambites][fpsemigroup][fpsemi]") { auto first = cbegin_sislo("abc", "a", std::string(8, 'a')); auto last = cbegin_sislo("abc", "a", std::string(8, 'a')); size_t N = std::distance(first, cend_sislo("abc", "a", std::string(8, 'a'))); REQUIRE(N == 3279); std::advance(last, N - 1); size_t total_c4 = 0; size_t total = 0; auto llast = last; ++llast; std::unordered_set<std::string> set; for (auto it1 = first; it1 != last; ++it1) { auto it2 = it1; ++it2; for (; it2 != llast; ++it2) { total++; Kambites<std::string> k; k.set_alphabet("abc"); k.add_rule(*it1, *it2); if (k.small_overlap_class() >= 4) { auto tmp = *it1 + "#" + *it2; if (set.insert(tmp).second) { auto u = swap_a_b_c(*it1); auto v = swap_a_b_c(*it2); for (size_t i = 0; i < 5; ++i) { if (shortlex_compare(u[i], v[i])) { set.insert(u[i] + "#" + v[i]); } else { set.insert(v[i] + "#" + u[i]); } } std::cout << *it1 << " = " << *it2 << std::endl; total_c4++; } } } } REQUIRE(total_c4 == 307511); REQUIRE(total == 5374281); } LIBSEMIGROUPS_TEST_CASE("Kambites", "079", "(fpsemi) normal form possible bug", "[standard][kambites][fpsemigroup][fpsemi]") { // There was a bug in MultiStringView::append, that caused this test to // fail, so we keep this test to check that the bug in // MultiStringView::append is resolved. Kambites<MultiStringView> k; k.set_alphabet("ab"); k.add_rule("aaabbab", "bbbaaba"); std::vector<std::string> words = { "bbbaabaabbbbbaabaabaaabbaabbbbbaaabaaabababbbbaaabbabababbaabbabaabb" "aaabbabbaaaabbabbbbbbaabbbbaabbabaaabaaaaabbaabababababaaaabaabbabba" "bbaaabbabababbabaabbbbbbabaabbabaaaababbababbabbabbabbbabbbabbbabbbb" "aaaaaabbabbaababbbaaababbbbababababbabaabbbbbabaaaababaaabbaaabbaaab" "babaabbbaababbbaaabbaabbbbaabbbbaaaaababbabbbaaaaaababbbbaaabbbabbba" "babbbbbbaabaabababbabbbbbaaaabbbbabbababbbaaaabbbbaabbbbbabbbbbabaab" "bbaaabaaabbababbbabbaaaaaabbbbabababbaabbabbbbabbabbaabbbaaabaaabbab" "abbbabbbbaabaaababbabbaababbbabbaababbabbbbabbbbabaabaaaabaaaabababa" "abababbaaabbabbbbbbaaaaaabbbbabbabbabaaaaabaabbaababbbbaabaaabbabaaa" "abaaabbbaaaabbabbababaaaabbbbaaabbababababaabbaaaabaabbababbabbaaaba" "bbaaabbbbbabbbaababaaabbababbbbbaabbbabaaaaabbbbabbabaaaababbabbabab" "aabbaababbaaabbabbbbabbbaaabbabbbaabbababbaabbaaaaaabaaabbbaababbaaa" "ababaabbaaabbbaabababbbbbababbbbbbbaabbbbaabababbbaabbbbbbbaabbbbaaa" "babaaaabaababbbaabaaabaaabaaaaabaabbbbabbabaaabbabbaabbaabbabaaabbbb" "baaabababbaabbbaababababaababbaabbabaaaaabaaabaaababaababaaaaaababaa" "aaaaaabaababbbbaabaabbabbabaaaaaabaabbabbbabbaabbbbbbbaaaababababbbb" "ababbbabbbaaabbabbabbaabbbbbbbababaabaabababbaaabbaabbbaabbbabbbbbab" "aaabbbababbbaabaaaabaabbaaaabbabbbabababbaaabbbbaabaabbababaaaabbbaa" "aabbbaabaa", "aaabbababbbbbaabaabaaabbaabbbbbaaabaaabababbbbaaabbabababbaabbabaabb" "bbbaababaaaabbabbbbbbaabbbbaabbabaaabaaaaabbaabababababaaaabaabbabba" "bbaaabbabababbabaabbbbbbabaabbabaaaababbababbabbabbabbbabbbabbbabbbb" "aaabbbaababaababbbaaababbbbababababbabaabbbbbabaaaababaaabbaaabbaaab" "babaabbbaababbbaaabbaabbbbaabbbbaaaaababbabbbaaaaaababbbbaaabbbabbba" "babbbbbbaabaabababbabbbbbaaaabbbbabbababbbaaaabbbbaabbbbbabbbbbabaab" "bbaaabbbbaabaabbbabbaaaaaabbbbabababbaabbabbbbabbabbaabbbaaabaaabbab" "abbbabbbbaabaaababbabbaababbbabbaababbabbbbabbbbabaabaaaabaaaabababa" "abababbaaabbabbbbbbaaaaaabbbbabbabbabaaaaabaabbaababbbbaabaaabbabaaa" "abaaabbbabbbaababababaaaabbbbaaabbababababaabbaaaabaabbababbabbaaaba" "bbaaabbbbbabbbaababaaabbababbbbbaabbbabaaaaabbbbabbabaaaababbabbabab" "aabbaababbbbbaababbbabbbaaabbabbbaabbababbaabbaaaaaabaaabbbaababbaaa" "ababaabbaaabbbaabababbbbbababbbbbbbaabbbbaabababbbaabbbbbbbaabbbbaaa" "babaaaabaabaaaabbabaabaaabaaaaabaabbbbabbabaaabbabbaabbaabbabaaabbbb" "baaabababbaaaaabbabbababaababbaabbabaaaaabaaabaaababaababaaaaaababaa" "aaaaaabaababbbbaabaabbabbabaaaaaabaabbabbbabbaabbbbbbbaaaababababbbb" --> -------------------- --> maximum size reached --> -------------------- ¤ Dauer der Verarbeitung: 0.32 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28