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 19 #include "cong-intf.hpp" 20 21 #include "constants.hpp" // for UNDEFINED 22 #include "froidure-pin-base.hpp" // for FroidurePinBase 23 #include "libsemigroups-debug.hpp" // for LIBSEMIGROUPS_ASSERT 24 #include "libsemigroups-exception.hpp" // for LIBSEMIGROUPS_EXCEPTION 25 #include "report.hpp" // for REPORT_VERBOSE_DEFAULT 26 #include "stl.hpp" // for detail::to_string 27 28 namespace libsemigroups { 29 30 class CongruenceInterface::LazyFroidurePin { 31 public: 32 LazyFroidurePin() = default; 33 set(std::shared_ptr<FroidurePinBase> ptr)34 void set(std::shared_ptr<FroidurePinBase> ptr) { 35 LIBSEMIGROUPS_ASSERT(_froidure_pin == nullptr); 36 LIBSEMIGROUPS_ASSERT(_fp_semigroup == nullptr); 37 _froidure_pin = ptr; 38 } 39 set(std::shared_ptr<FpSemigroupInterface> ptr)40 void set(std::shared_ptr<FpSemigroupInterface> ptr) { 41 LIBSEMIGROUPS_ASSERT(_froidure_pin == nullptr); 42 LIBSEMIGROUPS_ASSERT(_fp_semigroup == nullptr); 43 _fp_semigroup = ptr; 44 } 45 has_froidure_pin() const46 bool has_froidure_pin() const noexcept { 47 return _froidure_pin != nullptr; 48 } 49 can_compute_froidure_pin() const50 bool can_compute_froidure_pin() const noexcept { 51 return _froidure_pin != nullptr || _fp_semigroup != nullptr; 52 } 53 froidure_pin() const54 std::shared_ptr<FroidurePinBase> froidure_pin() const { 55 if (!has_froidure_pin()) { 56 if (_fp_semigroup != nullptr 57 && !_fp_semigroup->is_obviously_infinite()) { 58 _froidure_pin = _fp_semigroup->froidure_pin(); 59 } else { 60 // This can be the case if a CongruenceInterface is default 61 // constructed, i.e. constructed neither from a FroidurePinBase 62 // nor an FpSemigroupInterface, or the _fp_semigroup is obviously 63 // infinite 64 LIBSEMIGROUPS_EXCEPTION("no parent FroidurePin can be determined!"); 65 } 66 } 67 return _froidure_pin; 68 } 69 70 private: 71 mutable std::shared_ptr<FroidurePinBase> _froidure_pin; 72 mutable std::shared_ptr<FpSemigroupInterface> _fp_semigroup; 73 }; 74 75 //////////////////////////////////////////////////////////////////////////// 76 // CongruenceInterface - constructors + destructor - public 77 //////////////////////////////////////////////////////////////////////////// 78 CongruenceInterface(congruence_type type)79 CongruenceInterface::CongruenceInterface(congruence_type type) 80 : Runner(), 81 // Non-mutable 82 _gen_pairs(), 83 _nr_gens(UNDEFINED), 84 _parent(std::make_shared<LazyFroidurePin>()), 85 _type(type), 86 // Mutable 87 _init_ntc_done(), 88 _is_obviously_finite(false), 89 _is_obviously_infinite(false), 90 _quotient(nullptr), 91 _non_trivial_classes() { 92 reset(); 93 } 94 95 CongruenceInterface::~CongruenceInterface() = default; 96 97 //////////////////////////////////////////////////////////////////////////// 98 // Runner - non-pure virtual overridden function - public 99 //////////////////////////////////////////////////////////////////////////// 100 before_run()101 void CongruenceInterface::before_run() { 102 if (nr_generators() == UNDEFINED) { 103 LIBSEMIGROUPS_EXCEPTION("no generators have been set!"); 104 } 105 } 106 107 //////////////////////////////////////////////////////////////////////////// 108 // CongruenceInterface - non-pure virtual methods - public 109 //////////////////////////////////////////////////////////////////////////// 110 const_contains(word_type const & u,word_type const & v) const111 tril CongruenceInterface::const_contains(word_type const& u, 112 word_type const& v) const { 113 validate_word(u); 114 validate_word(v); 115 if (u == v) { 116 return tril::TRUE; 117 } 118 class_index_type uu, vv; 119 try { 120 uu = const_word_to_class_index(u); 121 vv = const_word_to_class_index(v); 122 } catch (LibsemigroupsException const& e) { 123 REPORT_VERBOSE_DEFAULT("ignoring exception:\n%s", e.what()); 124 return tril::unknown; 125 } 126 if (uu == UNDEFINED || vv == UNDEFINED) { 127 return tril::unknown; 128 } else if (uu == vv) { 129 return tril::TRUE; 130 } else if (finished()) { 131 return tril::FALSE; 132 } else { 133 return tril::unknown; 134 } 135 } 136 set_nr_generators(size_t n)137 void CongruenceInterface::set_nr_generators(size_t n) { 138 if (nr_generators() != UNDEFINED) { 139 if (nr_generators() != n) { 140 LIBSEMIGROUPS_EXCEPTION("cannot change the number of generators"); 141 } else { 142 return; // do nothing 143 } 144 } else if (n == 0) { 145 LIBSEMIGROUPS_EXCEPTION("the number of generators must be non-zero!"); 146 } else if (started()) { 147 LIBSEMIGROUPS_EXCEPTION( 148 "cannot set the number of generator at this stage"); 149 } 150 _nr_gens = n; 151 set_nr_generators_impl(n); 152 reset(); 153 } 154 155 ///////////////////////////////////////////////////////////////////////// 156 // CongruenceInterface - non-virtual methods - public 157 ///////////////////////////////////////////////////////////////////////// 158 add_pair(word_type const & u,word_type const & v)159 void CongruenceInterface::add_pair(word_type const& u, word_type const& v) { 160 if (started()) { 161 LIBSEMIGROUPS_EXCEPTION( 162 "cannot add further generating pairs at this stage"); 163 } 164 validate_word(u); 165 validate_word(v); 166 if (u == v) { 167 return; 168 } else if (has_parent_froidure_pin() 169 && parent_froidure_pin()->equal_to(u, v)) { 170 return; 171 } 172 // Note that _gen_pairs might contain pairs of distinct words that 173 // represent the same element of the parent semigroup (if any). 174 _gen_pairs.emplace_back(u, v); 175 add_pair_impl(u, v); 176 reset(); 177 } 178 class_index_to_word(class_index_type i)179 word_type CongruenceInterface::class_index_to_word(class_index_type i) { 180 if (nr_generators() == UNDEFINED) { 181 LIBSEMIGROUPS_EXCEPTION("no generators have been defined"); 182 } else if (i >= nr_classes()) { 183 LIBSEMIGROUPS_EXCEPTION("invalid class index, expected a value in the " 184 "range [0, %d), found %d", 185 nr_classes(), 186 i); 187 } 188 return class_index_to_word_impl(i); 189 } 190 191 // Basic exception guarantee (since is_quotient_obviously_infinite() may 192 // change the object). 193 std::shared_ptr<FroidurePinBase> quotient_froidure_pin()194 CongruenceInterface::quotient_froidure_pin() { 195 if (_quotient != nullptr) { 196 LIBSEMIGROUPS_ASSERT(kind() == congruence_type::twosided); 197 return _quotient; 198 } else if (kind() != congruence_type::twosided) { 199 LIBSEMIGROUPS_EXCEPTION("the congruence must be two-sided"); 200 } else if (is_quotient_obviously_infinite()) { 201 LIBSEMIGROUPS_EXCEPTION( 202 "cannot find the quotient semigroup, it is infinite"); 203 } 204 _quotient = quotient_impl(); 205 _quotient->immutable(true); 206 return _quotient; 207 } 208 is_quotient_obviously_infinite()209 bool CongruenceInterface::is_quotient_obviously_infinite() { 210 // If has_parent_froidure_pin(), then that is either finite (and so this 211 // is not obviously infinite), or infinite, which is undecidable in 212 // general, so we leave the answer to this question to 213 // is_quotient_obviously_infinite_impl in the derived class. 214 if (nr_generators() == UNDEFINED) { 215 // If nr_generators() is undefined, then there is no quotient yet, 216 // and so it is not obviously infinite, or anything! 217 REPORT_VERBOSE("not obviously infinite (no generators yet defined)"); 218 return false; 219 } else if (has_quotient_froidure_pin() 220 && quotient_froidure_pin()->finished()) { 221 // If the quotient FroidurePin is fully enumerated, it must be 222 // finite, and hence this is not (obviously) infinite. 223 REPORT_VERBOSE("not obviously infinite (finite)"); 224 return false; 225 } else if (has_parent_froidure_pin() && parent_froidure_pin()->finished()) { 226 REPORT_VERBOSE("not obviously infinite (parent finite)"); 227 return false; 228 } else if (is_quotient_obviously_infinite_impl()) { 229 // The derived class of CongruenceInterface knows the quotient is 230 // infinite 231 return true; 232 } 233 REPORT_VERBOSE("the quotient is not obviously infinite . . ."); 234 return false; 235 } 236 is_quotient_obviously_finite()237 bool CongruenceInterface::is_quotient_obviously_finite() { 238 if ((has_quotient_froidure_pin() && quotient_froidure_pin()->finished()) 239 || (has_parent_froidure_pin() && parent_froidure_pin()->finished()) 240 || is_quotient_obviously_finite_impl()) { 241 return true; 242 } 243 return false; 244 } 245 nr_classes()246 size_t CongruenceInterface::nr_classes() { 247 if (nr_generators() == UNDEFINED) { 248 return UNDEFINED; 249 } else if (!finished() && is_quotient_obviously_infinite()) { 250 return POSITIVE_INFINITY; 251 } 252 return nr_classes_impl(); 253 } 254 255 CongruenceInterface::class_index_type word_to_class_index(word_type const & word)256 CongruenceInterface::word_to_class_index(word_type const& word) { 257 // validate_word throws if nr_generators is undefined. 258 validate_word(word); 259 return word_to_class_index_impl(word); 260 } 261 262 ///////////////////////////////////////////////////////////////////////// 263 // CongruenceInterface - non-virtual methods - protected 264 ///////////////////////////////////////////////////////////////////////// 265 set_parent_froidure_pin(std::shared_ptr<FroidurePinBase> prnt)266 void CongruenceInterface::set_parent_froidure_pin( 267 std::shared_ptr<FroidurePinBase> prnt) { 268 LIBSEMIGROUPS_ASSERT(!_parent->has_froidure_pin()); 269 LIBSEMIGROUPS_ASSERT(nr_generators() == UNDEFINED 270 || prnt->nr_generators() == nr_generators()); 271 LIBSEMIGROUPS_ASSERT(!finished()); 272 if (nr_generators() == UNDEFINED) { 273 set_nr_generators(prnt->nr_generators()); 274 } 275 _parent->set(prnt); 276 reset(); 277 } 278 set_parent_froidure_pin(std::shared_ptr<FpSemigroupInterface> prnt)279 void CongruenceInterface::set_parent_froidure_pin( 280 std::shared_ptr<FpSemigroupInterface> prnt) { 281 LIBSEMIGROUPS_ASSERT(!_parent->has_froidure_pin()); 282 LIBSEMIGROUPS_ASSERT(nr_generators() == UNDEFINED 283 || prnt->alphabet().size() == nr_generators()); 284 LIBSEMIGROUPS_ASSERT(!finished()); 285 if (nr_generators() == UNDEFINED && !prnt->alphabet().empty()) { 286 set_nr_generators(prnt->alphabet().size()); 287 } 288 _parent->set(prnt); 289 reset(); 290 } 291 292 ///////////////////////////////////////////////////////////////////////// 293 // CongruenceInterface - non-pure virtual methods - private 294 ///////////////////////////////////////////////////////////////////////// 295 add_pair_impl(word_type const &,word_type const &)296 void CongruenceInterface::add_pair_impl(word_type const&, word_type const&) {} 297 298 CongruenceInterface::class_index_type const_word_to_class_index(word_type const &) const299 CongruenceInterface::const_word_to_class_index(word_type const&) const { 300 return UNDEFINED; 301 } 302 set_nr_generators_impl(size_t)303 void CongruenceInterface::set_nr_generators_impl(size_t) { 304 // do nothing 305 } 306 307 std::shared_ptr<CongruenceInterface::non_trivial_classes_type const> non_trivial_classes_impl()308 CongruenceInterface::non_trivial_classes_impl() { 309 if (!_parent->can_compute_froidure_pin()) { 310 LIBSEMIGROUPS_EXCEPTION("Cannot determine the parent FroidurePin and so " 311 "cannot compute non-trivial classes!"); 312 } 313 // The next line may trigger an infinite computation 314 auto fp = _parent->froidure_pin(); 315 auto ntc = non_trivial_classes_type(nr_classes(), std::vector<word_type>()); 316 317 word_type w; 318 for (size_t pos = 0; pos < fp->size(); ++pos) { 319 fp->factorisation(w, pos); 320 LIBSEMIGROUPS_ASSERT(word_to_class_index(w) < ntc.size()); 321 ntc[word_to_class_index(w)].push_back(w); 322 } 323 ntc.erase(std::remove_if(ntc.begin(), 324 ntc.end(), 325 [](std::vector<word_type> const& klass) -> bool { 326 return klass.size() <= 1; 327 }), 328 ntc.end()); 329 return std::make_shared<non_trivial_classes_type>(ntc); 330 } 331 332 ///////////////////////////////////////////////////////////////////////// 333 // CongruenceInterface - non-virtual methods - private 334 ///////////////////////////////////////////////////////////////////////// 335 init_non_trivial_classes()336 void CongruenceInterface::init_non_trivial_classes() { 337 if (!_init_ntc_done) { 338 _non_trivial_classes = non_trivial_classes_impl(); 339 _init_ntc_done = true; 340 } 341 } 342 reset()343 void CongruenceInterface::reset() noexcept { 344 // set_finished(false); 345 _non_trivial_classes.reset(); 346 _init_ntc_done = false; 347 _quotient.reset(); 348 _is_obviously_finite = false; 349 _is_obviously_infinite = false; 350 } 351 352 std::shared_ptr<FroidurePinBase> parent_froidure_pin() const353 CongruenceInterface::parent_froidure_pin() const { 354 return _parent->froidure_pin(); 355 } 356 has_parent_froidure_pin() const357 bool CongruenceInterface::has_parent_froidure_pin() const noexcept { 358 return _parent->has_froidure_pin(); 359 } 360 361 ///////////////////////////////////////////////////////////////////////// 362 // CongruenceInterface - non-virtual methods - protected 363 ///////////////////////////////////////////////////////////////////////// 364 validate_letter(letter_type c) const365 bool CongruenceInterface::validate_letter(letter_type c) const { 366 if (nr_generators() == UNDEFINED) { 367 LIBSEMIGROUPS_EXCEPTION("no generators have been defined"); 368 } 369 return c < _nr_gens; 370 } 371 validate_word(word_type const & w) const372 void CongruenceInterface::validate_word(word_type const& w) const { 373 for (auto l : w) { 374 // validate_letter throws if no generators are defined 375 if (!validate_letter(l)) { 376 LIBSEMIGROUPS_EXCEPTION( 377 "letter index out of bounds in word %s, expected " 378 "value in [0, %d), got %d", 379 detail::to_string(w), 380 l, 381 _nr_gens); 382 } 383 } 384 } 385 386 ///////////////////////////////////////////////////////////////////////// 387 // CongruenceInterface - non-virtual static methods - protected 388 ///////////////////////////////////////////////////////////////////////// 389 390 std::string const& congruence_type_to_string(congruence_type typ)391 CongruenceInterface::congruence_type_to_string(congruence_type typ) { 392 switch (typ) { 393 case congruence_type::twosided: 394 return STRING_TWOSIDED; 395 case congruence_type::left: 396 return STRING_LEFT; 397 case congruence_type::right: 398 return STRING_RIGHT; 399 default: 400 LIBSEMIGROUPS_EXCEPTION("incorrect type"); 401 } 402 } 403 404 ///////////////////////////////////////////////////////////////////////// 405 // CongruenceInterface - static data members - private 406 ///////////////////////////////////////////////////////////////////////// 407 408 const std::string CongruenceInterface::STRING_TWOSIDED = "two-sided"; 409 const std::string CongruenceInterface::STRING_LEFT = "left"; 410 const std::string CongruenceInterface::STRING_RIGHT = "right"; 411 } // namespace libsemigroups 412