1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2019 James D. Mitchell 4 // 5 // This program is free software: you can redistribute it and/or modify 6 // it under the terms of the GNU General Public License as published by 7 // the Free Software Foundation, either version 3 of the License, or 8 // (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program. If not, see <http://www.gnu.org/licenses/>. 17 18 // The purpose of this file is to test the CongruenceInterface class. 19 20 #include <cstddef> 21 22 #include "catch.hpp" // for REQUIRE, SECTION, ... 23 #include "cong-pair.hpp" // for FpSemigroupByPairs 24 #include "element-helper.hpp" // for FpSemigroupByPairs 25 #include "fpsemi-intf.hpp" // for FpSemigroupInterface 26 #include "fpsemi.hpp" // for FpSemigroup 27 #include "knuth-bendix.hpp" // for fpsemigroup::KnuthBendix 28 #include "order.hpp" // for shortlex_words 29 #include "string.hpp" // for to_string of rule_type for debugging 30 #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE 31 #include "todd-coxeter.hpp" // for fpsemigroup::ToddCoxeter 32 33 // The following is required to get catch to print rules 34 namespace std { 35 using rule_type = libsemigroups::FpSemigroupInterface::rule_type; operator <<(std::ostream & os,rule_type const & value)36 std::ostream& operator<<(std::ostream& os, rule_type const& value) { 37 os << "{ " << value.first << ", " << value.second << " }"; 38 return os; 39 } 40 } // namespace std 41 42 namespace libsemigroups { 43 struct LibsemigroupsException; // Forward declaration 44 45 constexpr bool REPORT = false; 46 47 namespace fpsemigroup { 48 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 49 "000", 50 "run with no alphabet", 51 "[quick]") { 52 auto rg = ReportGuard(REPORT); 53 54 std::unique_ptr<FpSemigroupInterface> fp; 55 SECTION("ToddCoxeter") { 56 fp = detail::make_unique<ToddCoxeter>(); 57 } 58 SECTION("KnuthBendix") { 59 fp = detail::make_unique<KnuthBendix>(); 60 } 61 SECTION("FpSemigroup") { 62 fp = detail::make_unique<FpSemigroup>(); 63 } 64 REQUIRE_THROWS_AS(fp->run(), LibsemigroupsException); 65 } 66 67 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 68 "001", 69 "equal_to", 70 "[quick][no-valgrind]") { 71 auto rg = ReportGuard(REPORT); 72 73 std::unique_ptr<FpSemigroupInterface> fp; 74 size_t nr_words = 0; 75 SECTION("human readable alphabet") { 76 SECTION("ToddCoxeter") { 77 fp = detail::make_unique<ToddCoxeter>(); 78 } 79 SECTION("KnuthBendix") { 80 fp = detail::make_unique<KnuthBendix>(); 81 } 82 SECTION("FpSemigroup") { 83 fp = detail::make_unique<FpSemigroup>(); 84 } 85 fp->set_alphabet("ab"); 86 fp->add_rule("aaa", "a"); 87 fp->add_rule("bbbb", "b"); 88 fp->add_rule("abab", "aa"); 89 REQUIRE(!fp->finished()); 90 REQUIRE(fp->size() == 27); 91 nr_words = 171; 92 } 93 SECTION("FpSemigroupByPairs") { 94 using Transf = typename TransfHelper<5>::type; 95 FroidurePin<Transf> S( 96 {Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 97 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 98 fp->add_rule({0, 0, 0}, {0}); 99 fp->add_rule({1, 1, 1, 1}, {1}); 100 fp->add_rule({0, 1, 0, 1}, {1, 1}); 101 REQUIRE(!fp->finished()); 102 REQUIRE(fp->size() == 2); 103 nr_words = 10; 104 } 105 REQUIRE(fp->equal_to({0, 0, 0}, {0})); 106 REQUIRE(!fp->equal_to({1, 1, 1, 1, 1, 1}, {0})); 107 auto words = shortlex_words(2, 10); 108 REQUIRE(words.size() == 2046); 109 REQUIRE(std::count_if(words.cbegin(), 110 words.cend(), __anonef1cada50102(word_type const& w) 111 [&fp](word_type const& w) -> bool { 112 return fp->equal_to(w, {0}); 113 }) 114 == nr_words); 115 } 116 117 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 118 "002", 119 "normal_form", 120 "[quick]") { 121 std::unique_ptr<FpSemigroupInterface> fp; 122 SECTION("ToddCoxeter") { 123 fp = detail::make_unique<ToddCoxeter>(); 124 } 125 SECTION("KnuthBendix") { 126 fp = detail::make_unique<KnuthBendix>(); 127 } 128 SECTION("FpSemigroup") { 129 fp = detail::make_unique<FpSemigroup>(); 130 } 131 fp->set_alphabet("ab"); 132 fp->add_rule("aaa", "a"); 133 fp->add_rule("bbbb", "b"); 134 fp->add_rule("abab", "aa"); 135 REQUIRE(!fp->finished()); 136 REQUIRE(fp->size() == 27); 137 // Not yet implemented 138 // SECTION("FpSemigroupByPairs") { 139 // } 140 REQUIRE(fp->normal_form({0, 0, 0}) == word_type({0})); 141 REQUIRE(fp->normal_form({1, 1, 1, 1, 1, 1}) == word_type({1, 1, 1})); 142 auto words = shortlex_words(2, 5); 143 REQUIRE(words.size() == 62); 144 std::transform(words.cbegin(), 145 words.cend(), 146 words.begin(), __anonef1cada50202(word_type const& w) 147 [&fp](word_type const& w) { return fp->normal_form(w); }); 148 REQUIRE(words 149 == std::vector<word_type>({{0}, 150 {1}, 151 {0, 0}, 152 {0, 1}, 153 {1, 0}, 154 {1, 1}, 155 {0}, 156 {0, 0, 1}, 157 {0, 1, 0}, 158 {0, 1, 1}, 159 {1, 0, 0}, 160 {1, 0, 1}, 161 {1, 1, 0}, 162 {1, 1, 1}, 163 {0, 0}, 164 {0, 1}, 165 {0, 1, 1}, 166 {0, 1, 0}, 167 {0, 1}, 168 {0, 0}, 169 {0, 0, 1}, 170 {0}, 171 {1, 0}, 172 {1, 0, 0, 1}, 173 {1, 0, 1, 0}, 174 {1, 0, 1, 1}, 175 {1, 1, 0, 0}, 176 {1, 1, 0, 1}, 177 {1, 1, 1, 0}, 178 {1}, 179 {0}, 180 {0, 0, 1}, 181 {0, 1, 0}, 182 {0, 1, 1}, 183 {0, 0, 1}, 184 {0}, 185 {0, 1}, 186 {0, 0}, 187 {0, 1, 0}, 188 {0, 1, 1}, 189 {0}, 190 {0, 0, 1}, 191 {0, 1, 1}, 192 {0, 1, 0}, 193 {0, 0}, 194 {0, 1}, 195 {1, 0, 0}, 196 {1, 0, 1}, 197 {1, 0, 1, 1}, 198 {1, 0, 1, 0}, 199 {1, 0, 1}, 200 {1, 0, 0}, 201 {1, 0, 0, 1}, 202 {1, 0}, 203 {1, 1, 0}, 204 {1, 1, 0, 0, 1}, 205 {1, 1, 0, 1, 0}, 206 {1, 1, 0, 1, 1}, 207 {1, 1, 1, 0, 0}, 208 {1, 1, 1, 0, 1}, 209 {1, 0}, 210 {1, 1}})); 211 } 212 213 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 214 "003", 215 "set_alphabet (1/2)", 216 "[quick]") { 217 auto rg = ReportGuard(REPORT); 218 std::unique_ptr<FpSemigroupInterface> fp; 219 SECTION("ToddCoxeter") { 220 fp = detail::make_unique<ToddCoxeter>(); 221 } 222 SECTION("KnuthBendix") { 223 fp = detail::make_unique<KnuthBendix>(); 224 } 225 SECTION("FpSemigroup") { 226 fp = detail::make_unique<FpSemigroup>(); 227 } 228 // Duplicates 229 REQUIRE_THROWS_AS(fp->set_alphabet("aa"), LibsemigroupsException); 230 231 // Empty 232 REQUIRE_THROWS_AS(fp->set_alphabet(""), LibsemigroupsException); 233 REQUIRE_THROWS_AS(fp->set_alphabet(0), LibsemigroupsException); 234 235 // Too many 236 REQUIRE_THROWS_AS(fp->set_alphabet(300), LibsemigroupsException); 237 238 fp->set_alphabet("ab"); 239 // Set more than once 240 REQUIRE_THROWS_AS(fp->set_alphabet("ab"), LibsemigroupsException); 241 REQUIRE_THROWS_AS(fp->set_alphabet(2), LibsemigroupsException); 242 } 243 244 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 245 "004", 246 "set_alphabet (2/2)", 247 "[quick]") { 248 auto rg = ReportGuard(REPORT); 249 std::unique_ptr<FpSemigroupInterface> fp; 250 using Transf = typename TransfHelper<5>::type; 251 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 252 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 253 fp->add_rule({0, 0, 0}, {0}); 254 fp->add_rule({1, 1, 1, 1}, {1}); 255 fp->add_rule({0, 1, 0, 1}, {1, 1}); 256 REQUIRE(!fp->finished()); 257 REQUIRE(fp->size() == 2); 258 259 // Duplicates 260 REQUIRE_THROWS_AS(fp->set_alphabet("aa"), LibsemigroupsException); 261 262 // Empty 263 REQUIRE_THROWS_AS(fp->set_alphabet(""), LibsemigroupsException); 264 REQUIRE_THROWS_AS(fp->set_alphabet(0), LibsemigroupsException); 265 266 // Too many 267 REQUIRE_THROWS_AS(fp->set_alphabet(300), LibsemigroupsException); 268 269 // Set more than once 270 REQUIRE_THROWS_AS(fp->set_alphabet("ab"), LibsemigroupsException); 271 REQUIRE_THROWS_AS(fp->set_alphabet(2), LibsemigroupsException); 272 } 273 274 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 275 "005", 276 "add_rule after finished", 277 "[quick]") { 278 auto rg = ReportGuard(REPORT); 279 280 std::unique_ptr<FpSemigroupInterface> fp; 281 SECTION("human readable alphabet") { 282 SECTION("ToddCoxeter") { 283 fp = detail::make_unique<ToddCoxeter>(); 284 } 285 SECTION("KnuthBendix") { 286 fp = detail::make_unique<KnuthBendix>(); 287 } 288 SECTION("FpSemigroup") { 289 fp = detail::make_unique<FpSemigroup>(); 290 } 291 fp->set_alphabet("ab"); 292 fp->add_rule("aaa", "a"); 293 fp->add_rule("bbbb", "b"); 294 fp->add_rule("abab", "aa"); 295 REQUIRE(!fp->finished()); 296 REQUIRE(fp->size() == 27); 297 } 298 SECTION("FpSemigroupByPairs") { 299 using Transf = typename TransfHelper<5>::type; 300 FroidurePin<Transf> S( 301 {Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 302 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 303 fp->add_rule({0, 0, 0}, {0}); 304 fp->add_rule({1, 1, 1, 1}, {1}); 305 fp->add_rule({0, 1, 0, 1}, {1, 1}); 306 REQUIRE(!fp->finished()); 307 REQUIRE(fp->size() == 2); 308 } 309 310 REQUIRE(fp->finished()); 311 REQUIRE(fp->started()); 312 // Add rule after finished 313 REQUIRE_THROWS_AS(fp->add_rule({0}, {1}), LibsemigroupsException); 314 REQUIRE_THROWS_AS(fp->add_rule({"a"}, {"b"}), LibsemigroupsException); 315 } 316 317 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 318 "006", 319 "add_rule with equal words (1/2)", 320 "[quick]") { 321 auto rg = ReportGuard(REPORT); 322 323 std::unique_ptr<FpSemigroupInterface> fp; 324 using Transf = typename TransfHelper<5>::type; 325 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 326 SECTION("human readable alphabet") { 327 SECTION("ToddCoxeter") { 328 fp = detail::make_unique<ToddCoxeter>(S); 329 } 330 SECTION("KnuthBendix") { 331 fp = detail::make_unique<KnuthBendix>(S); 332 } 333 SECTION("FpSemigroup") { 334 fp = detail::make_unique<FpSemigroup>(S); 335 } 336 } 337 SECTION("FpSemigroupByPairs") { 338 using Transf = typename TransfHelper<5>::type; 339 FroidurePin<Transf> S( 340 {Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 341 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 342 } 343 size_t expected = fp->nr_rules(); 344 REQUIRE_NOTHROW(fp->add_rule({0}, {0})); 345 REQUIRE(fp->nr_rules() == expected); 346 REQUIRE_NOTHROW(fp->add_rule(std::pair<word_type, word_type>({0}, {0}))); 347 REQUIRE_NOTHROW( 348 fp->add_rule(std::pair<word_type, word_type>({{1, 1}, {0, 1}}))); 349 REQUIRE(fp->nr_rules() == expected + 1); 350 } 351 352 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 353 "007", 354 "add_rule with equal words (2/2)", 355 "[quick]") { 356 auto rg = ReportGuard(REPORT); 357 358 std::unique_ptr<FpSemigroupInterface> fp; 359 SECTION("ToddCoxeter") { 360 fp = detail::make_unique<ToddCoxeter>(); 361 } 362 SECTION("KnuthBendix") { 363 fp = detail::make_unique<KnuthBendix>(); 364 } 365 SECTION("FpSemigroup") { 366 fp = detail::make_unique<FpSemigroup>(); 367 } 368 fp->set_alphabet("ab"); 369 size_t expected = fp->nr_rules(); 370 REQUIRE_NOTHROW(fp->add_rule("a", "a")); 371 REQUIRE_NOTHROW(fp->add_rule("ab", "ab")); 372 REQUIRE_NOTHROW(fp->add_rule("abaaaaaaaa", "abaaaaaaaa")); 373 REQUIRE(fp->nr_rules() == expected); 374 REQUIRE_NOTHROW(fp->add_rule(std::make_pair("a", "a"))); 375 REQUIRE_NOTHROW(fp->add_rule(std::make_pair("ab", "ab"))); 376 REQUIRE(fp->nr_rules() == expected); 377 } 378 379 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 380 "008", 381 "add_rule with word_type", 382 "[quick]") { 383 auto rg = ReportGuard(REPORT); 384 385 std::unique_ptr<FpSemigroupInterface> fp; 386 SECTION("ToddCoxeter") { 387 fp = detail::make_unique<ToddCoxeter>(); 388 } 389 SECTION("KnuthBendix") { 390 fp = detail::make_unique<KnuthBendix>(); 391 } 392 SECTION("FpSemigroup") { 393 fp = detail::make_unique<FpSemigroup>(); 394 } 395 fp->set_alphabet(2); 396 size_t expected = fp->nr_rules(); 397 REQUIRE_NOTHROW(fp->add_rule({0}, {0})); 398 REQUIRE_NOTHROW(fp->add_rule({0, 1}, {0, 1})); 399 REQUIRE(fp->nr_rules() == expected); 400 REQUIRE_NOTHROW(fp->add_rule({0, 0, 0}, {0})); 401 REQUIRE_NOTHROW(fp->add_rule({0, 1, 0}, {0, 1})); 402 REQUIRE(fp->nr_rules() == expected + 2); 403 REQUIRE_THROWS_AS(fp->add_rule({0, 1, 0}, {}), LibsemigroupsException); 404 } 405 406 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 407 "009", 408 "add_rule with empty word (1/2)", 409 "[quick]") { 410 auto rg = ReportGuard(REPORT); 411 412 std::unique_ptr<FpSemigroupInterface> fp; 413 SECTION("ToddCoxeter") { 414 fp = detail::make_unique<ToddCoxeter>(); 415 } 416 SECTION("FpSemigroup") { 417 fp = detail::make_unique<FpSemigroup>(); 418 } 419 fp->set_alphabet("ab"); 420 REQUIRE_THROWS_AS(fp->add_rule("abaaaaaaaa", ""), LibsemigroupsException); 421 } 422 423 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 424 "010", 425 "add_rule with empty word (1/2)", 426 "[quick]") { 427 auto rg = ReportGuard(REPORT); 428 429 std::unique_ptr<FpSemigroupInterface> fp; 430 fp = detail::make_unique<KnuthBendix>(); 431 fp->set_alphabet("ab"); 432 REQUIRE_NOTHROW(fp->add_rule("abaaaaaaaa", "")); 433 } 434 435 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 436 "011", 437 "add_rules (1/3)", 438 "[quick]") { 439 auto rg = ReportGuard(REPORT); 440 441 std::unique_ptr<FpSemigroupInterface> fp; 442 443 SECTION("ToddCoxeter") { 444 fp = detail::make_unique<ToddCoxeter>(); 445 } 446 SECTION("KnuthBendix") { 447 fp = detail::make_unique<KnuthBendix>(); 448 } 449 SECTION("FpSemigroup") { 450 fp = detail::make_unique<FpSemigroup>(); 451 } 452 fp->set_alphabet("a"); 453 using Transf = typename TransfHelper<5>::type; 454 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 455 REQUIRE_THROWS_AS(fp->add_rules(S), LibsemigroupsException); 456 } 457 458 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 459 "012", 460 "add_rules (2/3)", 461 "[quick]") { 462 auto rg = ReportGuard(REPORT); 463 464 using Transf = typename TransfHelper<5>::type; 465 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 466 FpSemigroupByPairs<Transf> fp(S); 467 REQUIRE(fp.nr_rules() == 18); 468 REQUIRE(fp.congruence().nr_generating_pairs() == 0); 469 // Generating pairs are the extra generating pairs added, whereas 470 // the nr_rules is the number of rules of defining the semigroup over 471 // which the congruence is defined. 472 REQUIRE(fp.congruence().nr_generating_pairs() == 0); 473 474 using Transf = typename TransfHelper<5>::type; 475 FroidurePin<Transf> T({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 476 REQUIRE_NOTHROW(fp.add_rules(T)); 477 REQUIRE(fp.nr_rules() == 36); 478 REQUIRE(fp.size() == S.size()); 479 REQUIRE(fp.congruence().nr_generating_pairs() == 0); 480 } 481 482 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 483 "013", 484 "add_rules (3/3)", 485 "[quick]") { 486 auto rg = ReportGuard(REPORT); 487 std::unique_ptr<FpSemigroupInterface> fp; 488 SECTION("ToddCoxeter") { 489 fp = detail::make_unique<ToddCoxeter>(); 490 } 491 SECTION("KnuthBendix") { 492 fp = detail::make_unique<KnuthBendix>(); 493 } 494 SECTION("FpSemigroup") { 495 fp = detail::make_unique<FpSemigroup>(); 496 } 497 REQUIRE_NOTHROW(fp->set_alphabet("ab")); 498 size_t const expected = fp->nr_rules() + 3; 499 std::vector<std::pair<std::string, std::string>> v 500 = {{"aaa", "a"}, {"ab", "ba"}, {"bbbb", "b"}}; 501 REQUIRE_NOTHROW(fp->add_rules(v)); 502 REQUIRE(fp->nr_rules() == expected); 503 } 504 505 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 506 "014", 507 "set_identity (1/3)", 508 "[quick]") { 509 using rule_type = typename FpSemigroupInterface::rule_type; 510 auto rg = ReportGuard(REPORT); 511 std::unique_ptr<FpSemigroupInterface> fp; 512 SECTION("ToddCoxeter") { 513 fp = detail::make_unique<ToddCoxeter>(); 514 } 515 SECTION("KnuthBendix") { 516 fp = detail::make_unique<KnuthBendix>(); 517 } 518 SECTION("FpSemigroup") { 519 fp = detail::make_unique<FpSemigroup>(); 520 } 521 522 // No alphabet 523 REQUIRE_THROWS_AS(fp->set_identity("a"), LibsemigroupsException); 524 // Too long 525 REQUIRE_THROWS_AS(fp->set_identity("aa"), LibsemigroupsException); 526 527 REQUIRE_NOTHROW(fp->set_alphabet("ab")); 528 529 // Letter out of range 530 REQUIRE_THROWS_AS(fp->set_identity("x"), LibsemigroupsException); 531 // Too long 532 REQUIRE_THROWS_AS(fp->set_identity("aa"), LibsemigroupsException); 533 534 REQUIRE_NOTHROW(fp->set_identity("a")); 535 REQUIRE(fp->identity() == "a"); 536 537 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 538 == std::vector<rule_type>({rule_type({"aa", "a"}), 539 rule_type({"ba", "b"}), 540 rule_type({"ab", "b"})})); 541 REQUIRE_NOTHROW(fp->set_identity("b")); 542 REQUIRE(fp->identity() == "b"); 543 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 544 == std::vector<rule_type>({rule_type({"aa", "a"}), 545 rule_type({"ba", "b"}), 546 rule_type({"ab", "b"}), 547 rule_type({"ab", "a"}), 548 rule_type({"ba", "a"}), 549 rule_type({"bb", "b"})})); 550 } 551 552 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 553 "015", 554 "set_identity (2/3)", 555 "[quick]") { 556 using rule_type = typename FpSemigroupInterface::rule_type; 557 auto rg = ReportGuard(REPORT); 558 std::unique_ptr<FpSemigroupInterface> fp; 559 using Transf = typename TransfHelper<5>::type; 560 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 561 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 562 563 auto a = std::string(1, fp->alphabet()[0]); 564 auto b = std::string(1, fp->alphabet()[1]); 565 REQUIRE_NOTHROW(fp->set_identity(0)); 566 REQUIRE(fp->identity() == a); 567 568 // Letter out of range 569 REQUIRE_THROWS_AS(fp->set_identity(letter_type(10)), 570 LibsemigroupsException); 571 REQUIRE(fp->identity() == a); 572 573 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 574 == std::vector<rule_type>( 575 {rule_type({b + b + b, b}), 576 rule_type({b + b + a + b, b + a + b}), 577 rule_type({a + a + a + a + a, a + a}), 578 rule_type({a + b + a + a + b, a + a + a + a + b}), 579 rule_type({b + a + a + a + a, b + a}), 580 rule_type({b + b + a + a + b, b + a + a + a + b}), 581 rule_type({a + a + b + a + b + a, a + a + b + b}), 582 rule_type({a + a + b + a + b + b, a + a + b + a}), 583 rule_type({b + a + b + a + b + a, b + a + b + b}), 584 rule_type({b + a + b + a + b + b, b + a + b + a}), 585 rule_type({b + b + a + a + a + b, b + a + a + b}), 586 rule_type({a + a + b + b + a + a + a, a + a + b + b}), 587 rule_type( 588 {b + a + b + a + a + a + b, a + a + b + a + a + a + b}), 589 rule_type({b + a + b + b + a + a + a, b + a + b + b}), 590 rule_type({a + a + a + b + a + a + a + b, 591 a + a + b + a + a + a + b}), 592 rule_type({a + a + b + a + a + a + b + b, 593 a + a + b + a + a + a + b}), 594 rule_type({b + a + a + b + a + a + a + b, 595 a + a + b + a + a + a + b}), 596 rule_type({a + a + b + a + a + a + b + a + a + a, 597 a + a + b + a + a + a + b}), 598 rule_type({a + a, a}), 599 rule_type({b + a, b}), 600 rule_type({a + b, b})})); 601 } 602 603 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 604 "016", 605 "set_identity (3/3)", 606 "[quick]") { 607 using rule_type = typename FpSemigroupInterface::rule_type; 608 auto rg = ReportGuard(REPORT); 609 std::unique_ptr<FpSemigroupInterface> fp; 610 SECTION("ToddCoxeter") { 611 fp = detail::make_unique<ToddCoxeter>(); 612 } 613 SECTION("KnuthBendix") { 614 fp = detail::make_unique<KnuthBendix>(); 615 } 616 SECTION("FpSemigroup") { 617 fp = detail::make_unique<FpSemigroup>(); 618 } 619 // No alphabet 620 REQUIRE_THROWS_AS(fp->set_identity(0), LibsemigroupsException); 621 622 REQUIRE_NOTHROW(fp->set_alphabet("ab")); 623 624 // Letter out of range 625 REQUIRE_THROWS_AS(fp->set_identity(10), LibsemigroupsException); 626 627 REQUIRE_NOTHROW(fp->set_identity(0)); 628 REQUIRE(fp->identity() == "a"); 629 630 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 631 == std::vector<rule_type>({rule_type({"aa", "a"}), 632 rule_type({"ba", "b"}), 633 rule_type({"ab", "b"})})); 634 REQUIRE_NOTHROW(fp->set_identity(1)); 635 REQUIRE(fp->identity() == "b"); 636 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 637 == std::vector<rule_type>({rule_type({"aa", "a"}), 638 rule_type({"ba", "b"}), 639 rule_type({"ab", "b"}), 640 rule_type({"ab", "a"}), 641 rule_type({"ba", "a"}), 642 rule_type({"bb", "b"})})); 643 } 644 645 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 646 "017", 647 "identity", 648 "[quick]") { 649 auto rg = ReportGuard(REPORT); 650 std::unique_ptr<FpSemigroupInterface> fp; 651 SECTION("ToddCoxeter") { 652 fp = detail::make_unique<ToddCoxeter>(); 653 } 654 SECTION("KnuthBendix") { 655 fp = detail::make_unique<KnuthBendix>(); 656 } 657 SECTION("FpSemigroup") { 658 fp = detail::make_unique<FpSemigroup>(); 659 } 660 REQUIRE_THROWS_AS(fp->identity(), LibsemigroupsException); 661 } 662 663 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 664 "018", 665 "set_inverses + inverses (1/2)", 666 "[quick]") { 667 using rule_type = typename FpSemigroupInterface::rule_type; 668 auto rg = ReportGuard(REPORT); 669 std::unique_ptr<FpSemigroupInterface> fp; 670 SECTION("ToddCoxeter") { 671 fp = detail::make_unique<ToddCoxeter>(); 672 } 673 SECTION("KnuthBendix") { 674 fp = detail::make_unique<KnuthBendix>(); 675 } 676 SECTION("FpSemigroup") { 677 fp = detail::make_unique<FpSemigroup>(); 678 } 679 // No alphabet 680 REQUIRE_THROWS_AS(fp->set_inverses("bac"), LibsemigroupsException); 681 // Not set 682 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 683 684 // No identity 685 fp->set_alphabet("abc"); 686 REQUIRE_THROWS_AS(fp->set_inverses("bac"), LibsemigroupsException); 687 // Not set 688 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 689 690 fp->set_identity("c"); 691 // Duplicates 692 REQUIRE_THROWS_AS(fp->set_inverses("bbc"), LibsemigroupsException); 693 // Not set 694 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 695 // Wrong size 696 REQUIRE_THROWS_AS(fp->set_inverses("bc"), LibsemigroupsException); 697 // Not set 698 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 699 700 fp->set_inverses("bac"); 701 // Can't set inverses more than once 702 REQUIRE_THROWS_AS(fp->set_inverses("abc"), LibsemigroupsException); 703 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 704 == std::vector<rule_type>({rule_type({"ac", "a"}), 705 rule_type({"ca", "a"}), 706 rule_type({"bc", "b"}), 707 rule_type({"cb", "b"}), 708 rule_type({"cc", "c"}), 709 rule_type({"ab", "c"}), 710 rule_type({"ba", "c"}), 711 rule_type({"ba", "c"}), 712 rule_type({"ab", "c"}), 713 rule_type({"cc", "c"}), 714 rule_type({"cc", "c"})})); 715 REQUIRE(fp->inverses() == "bac"); 716 } 717 718 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 719 "019", 720 "set_inverses + inverses (2/2)", 721 "[quick]") { 722 using rule_type = typename FpSemigroupInterface::rule_type; 723 auto rg = ReportGuard(REPORT); 724 std::unique_ptr<FpSemigroupInterface> fp; 725 using Transf = typename TransfHelper<5>::type; 726 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 727 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 728 729 auto a = std::string(1, fp->alphabet()[0]); 730 auto b = std::string(1, fp->alphabet()[1]); 731 732 // Not set 733 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 734 735 // No identity 736 REQUIRE_THROWS_AS(fp->set_inverses(b + a), LibsemigroupsException); 737 // Not set 738 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 739 740 fp->set_identity(a); 741 // Duplicates 742 REQUIRE_THROWS_AS(fp->set_inverses(b + b), LibsemigroupsException); 743 // Not set 744 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 745 // Wrong size 746 REQUIRE_THROWS_AS(fp->set_inverses(a), LibsemigroupsException); 747 // Not set 748 REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException); 749 750 fp->set_inverses(b + a); 751 752 // Can't set inverses more than once 753 REQUIRE_THROWS_AS(fp->set_inverses(b + a), LibsemigroupsException); 754 755 REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules()) 756 == std::vector<rule_type>( 757 {rule_type({b + b + b, b}), 758 rule_type({b + b + a + b, b + a + b}), 759 rule_type({a + a + a + a + a, a + a}), 760 rule_type({a + b + a + a + b, a + a + a + a + b}), 761 rule_type({b + a + a + a + a, b + a}), 762 rule_type({b + b + a + a + b, b + a + a + a + b}), 763 rule_type({a + a + b + a + b + a, a + a + b + b}), 764 rule_type({a + a + b + a + b + b, a + a + b + a}), 765 rule_type({b + a + b + a + b + a, b + a + b + b}), 766 rule_type({b + a + b + a + b + b, b + a + b + a}), 767 rule_type({b + b + a + a + a + b, b + a + a + b}), 768 rule_type({a + a + b + b + a + a + a, a + a + b + b}), 769 rule_type( 770 {b + a + b + a + a + a + b, a + a + b + a + a + a + b}), 771 rule_type({b + a + b + b + a + a + a, b + a + b + b}), 772 rule_type({a + a + a + b + a + a + a + b, 773 a + a + b + a + a + a + b}), 774 rule_type({a + a + b + a + a + a + b + b, 775 a + a + b + a + a + a + b}), 776 rule_type({b + a + a + b + a + a + a + b, 777 a + a + b + a + a + a + b}), 778 rule_type({a + a + b + a + a + a + b + a + a + a, 779 a + a + b + a + a + a + b}), 780 rule_type({a + a, a}), 781 rule_type({b + a, b}), 782 rule_type({a + b, b}), 783 rule_type({a + b, a}), 784 rule_type({b + a, a}), 785 rule_type({b + a, a}), 786 rule_type({a + b, a})})); 787 } 788 789 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 790 "020", 791 "is_obviously_infinite (1/2)", 792 "[quick]") { 793 auto rg = ReportGuard(REPORT); 794 std::unique_ptr<FpSemigroupInterface> fp; 795 SECTION("ToddCoxeter") { 796 fp = detail::make_unique<ToddCoxeter>(); 797 } 798 SECTION("KnuthBendix") { 799 fp = detail::make_unique<KnuthBendix>(); 800 } 801 SECTION("FpSemigroup") { 802 fp = detail::make_unique<FpSemigroup>(); 803 } 804 // No alphabet 805 REQUIRE(!fp->is_obviously_infinite()); 806 fp->set_alphabet("ab"); 807 808 // More generators than rules 809 REQUIRE(fp->is_obviously_infinite()); 810 fp->add_rule("aaa", "a"); 811 REQUIRE(fp->is_obviously_infinite()); 812 813 fp->add_rule("bbbb", "b"); 814 fp->add_rule("abab", "aa"); 815 REQUIRE(!fp->is_obviously_infinite()); 816 817 REQUIRE(fp->froidure_pin()->size() == 27); 818 REQUIRE(!fp->is_obviously_infinite()); 819 } 820 821 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 822 "021", 823 "is_obviously_infinite (2/2)", 824 "[quick]") { 825 auto rg = ReportGuard(REPORT); 826 std::unique_ptr<FpSemigroupInterface> fp; 827 using Transf = typename TransfHelper<1>::type; 828 FroidurePin<Transf> S({Transf({0})}); 829 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 830 831 REQUIRE(!fp->is_obviously_infinite()); 832 REQUIRE(!fp->is_obviously_infinite()); 833 fp->add_rule({0, 0, 0}, {0}); 834 REQUIRE(!fp->is_obviously_infinite()); 835 836 REQUIRE(!fp->is_obviously_infinite()); 837 } 838 839 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 840 "022", 841 "is_obviously_finite (1/2)", 842 "[quick]") { 843 auto rg = ReportGuard(REPORT); 844 std::unique_ptr<FpSemigroupInterface> fp; 845 SECTION("ToddCoxeter") { 846 fp = detail::make_unique<ToddCoxeter>(); 847 } 848 SECTION("KnuthBendix") { 849 fp = detail::make_unique<KnuthBendix>(); 850 } 851 SECTION("FpSemigroup") { 852 fp = detail::make_unique<FpSemigroup>(); 853 } 854 // No alphabet 855 REQUIRE(fp->is_obviously_finite()); 856 fp->set_alphabet("ab"); 857 858 // More generators than rules 859 REQUIRE(!fp->is_obviously_finite()); 860 fp->add_rule("aaa", "a"); 861 REQUIRE(!fp->is_obviously_finite()); 862 863 fp->add_rule("bbbb", "b"); 864 fp->add_rule("abab", "aa"); 865 REQUIRE(!fp->is_obviously_finite()); 866 867 REQUIRE(fp->froidure_pin()->size() == 27); 868 REQUIRE(fp->is_obviously_finite()); 869 } 870 871 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 872 "023", 873 "is_obviously_finite (2/2)", 874 "[quick]") { 875 auto rg = ReportGuard(REPORT); 876 std::unique_ptr<FpSemigroupInterface> fp; 877 using Transf = typename TransfHelper<1>::type; 878 FroidurePin<Transf> S({Transf({0})}); 879 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 880 REQUIRE(fp->is_obviously_finite()); 881 REQUIRE(fp->is_obviously_finite()); 882 fp->add_rule({0, 0, 0}, {0}); 883 REQUIRE(fp->is_obviously_finite()); 884 REQUIRE(fp->is_obviously_finite()); 885 } 886 887 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 888 "024", 889 "to_gap_string (1/3)", 890 "[quick]") { 891 auto rg = ReportGuard(REPORT); 892 std::unique_ptr<FpSemigroupInterface> fp; 893 SECTION("ToddCoxeter") { 894 fp = detail::make_unique<ToddCoxeter>(); 895 } 896 SECTION("KnuthBendix") { 897 fp = detail::make_unique<KnuthBendix>(); 898 } 899 SECTION("FpSemigroup") { 900 fp = detail::make_unique<FpSemigroup>(); 901 } 902 fp->set_alphabet("ab"); 903 fp->add_rule("aaa", "a"); 904 fp->add_rule("bbbb", "b"); 905 fp->add_rule("abab", "aa"); 906 907 REQUIRE(fp->to_gap_string() 908 == "free := FreeMonoid(\"a\", \"b\");\n" 909 "AssignGeneratorVariables(free);\n" 910 "rules := [\n" 911 " [a * a * a, a],\n" 912 " [b * b * b * b, b],\n" 913 " [a * b * a * b, a * a]\n" 914 " ];\n" 915 "S := free / rules;\n"); 916 } 917 918 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 919 "025", 920 "to_gap_string (2/3)", 921 "[quick]") { 922 auto rg = ReportGuard(REPORT); 923 std::unique_ptr<FpSemigroupInterface> fp; 924 fp = detail::make_unique<KnuthBendix>(); 925 fp->set_alphabet("ab"); 926 fp->add_rule("abab", ""); 927 928 REQUIRE(fp->to_gap_string() 929 == "free := FreeMonoid(\"a\", \"b\");\n" 930 "AssignGeneratorVariables(free);\n" 931 "rules := [\n" 932 " [a * b * a * b, One(free)]\n" 933 " ];\n" 934 "S := free / rules;\n"); 935 } 936 937 LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface", 938 "026", 939 "to_gap_string (3/3)", 940 "[quick]") { 941 auto rg = ReportGuard(REPORT); 942 std::unique_ptr<FpSemigroupInterface> fp; 943 using Transf = typename TransfHelper<1>::type; 944 FroidurePin<Transf> S({Transf({0})}); 945 fp = detail::make_unique<FpSemigroupByPairs<Transf>>(S); 946 947 REQUIRE(fp->to_gap_string() 948 == "free := FreeMonoid(\"a\");\n" 949 "AssignGeneratorVariables(free);\n" 950 "rules := [\n" 951 " [a * a, a]\n" 952 " ];\n" 953 "S := free / rules;\n"); 954 } 955 956 } // namespace fpsemigroup 957 } // namespace libsemigroups 958