libsemigroups  v3.2.0
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
todd-coxeter-class.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2025 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// This file contains the declaration of the ToddCoxeter class. This class
20// exists mostly to wrap ToddCoxeterImpl (where the action happens) to make it
21// more user friendly. In particular, ToddCoxeter presentation()
22// and generating_pairs() return the input presentation and generating pairs,
23// whatever their type, and not the normalized Presentation<word_type> required
24// by ToddCoxeterImpl.
25
26#ifndef LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
27#define LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
28
29#include <algorithm> // for equal
30#include <cstddef> // for ptrdiff_t, size_t
31#include <iterator> // for bidirectional_iterator_tag
32#include <string> // for basic_string, string
33#include <type_traits> // for is_same_v
34#include <utility> // for move
35#include <vector> // for vector
36
37#include "presentation.hpp" // for Presentation
38#include "to-presentation.hpp" // for to<Presentation>
39#include "types.hpp" // for congruence_kind
40
41#include "detail/citow.hpp" // for detail::citow and detail::itow
42#include "detail/cong-common-class.hpp" // for detail::CongruenceCommon
43#include "detail/fmt.hpp" // for fmt
44#include "detail/todd-coxeter-impl.hpp" // for ToddCoxeterImpl
45
46namespace libsemigroups {
47
56
138 template <typename Word>
139 class ToddCoxeter : public detail::ToddCoxeterImpl {
140 private:
141 std::vector<Word> _generating_pairs;
142 Presentation<Word> _presentation;
143
144 public:
145#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
153 struct options : public FelschGraphSettings_::options {
164 enum class strategy {
169
174
184
193
203
214 };
215
232
239 enum class lookahead_style {
244
249 };
250
292
293 // NOTE: The next enum (def_version) is actually defined in FelschGraph,
294 // not in ToddCoxeter
295
316 enum class def_version : uint8_t {
321 };
322 };
323
338 [[nodiscard]] congruence_kind kind() const noexcept;
339
355 [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
356#endif
357
365 using native_word_type = Word;
366
373 using node_type = typename detail::ToddCoxeterImpl::node_type;
374
381 using word_graph_type = typename detail::ToddCoxeterImpl::word_graph_type;
382
398 using index_type = typename detail::ToddCoxeterImpl::index_type;
399
406 using label_type = typename detail::ToddCoxeterImpl::label_type;
407
413 ToddCoxeter() = default;
414
427
430 ToddCoxeter(ToddCoxeter const&) = default;
431
435
441
447
448 ~ToddCoxeter();
449
464
480
484 // call the rval ref constructor
485 : ToddCoxeter(knd, Presentation<Word>(p)) {}
486
490 // call the rval ref init
491 return init(knd, Presentation<Word>(p));
492 }
493
510 init(knd, tc);
511 }
512
530 ToddCoxeterImpl::init(knd, tc);
531 _presentation = tc.presentation();
532 _presentation.rules.insert(_presentation.rules.end(),
533 tc.generating_pairs().cbegin(),
534 tc.generating_pairs().cend());
535 // Clear generating pairs last, in case &tc == this!!!
536 _generating_pairs.clear();
537 // TODO(1) check KnuthBendix et al
538 return *this;
539 }
540
559 template <typename Node>
561 : ToddCoxeter() {
562 init(knd, wg);
563 }
564
581 template <typename Node>
583
584#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
585 // Used in Sims
586 // TODO(1) could this and the next function be removed, and replaced
587 // with something else?
588 template <typename Node>
590 Presentation<Word> const& p,
591 WordGraph<Node> const& wg) {
592 init(knd, p, wg);
593 }
594
595 // TODO(1) a "make" variant that throws if params are valid
596 template <typename Node>
597 ToddCoxeter& init(congruence_kind knd,
598 Presentation<Word> const& p,
599 WordGraph<Node> const& wg);
600#endif
601
620 template <typename Iterator1, typename Iterator2>
622 Iterator2 last) const {
623 presentation().throw_if_letter_not_in_alphabet(first, last);
624 }
625
639 [[nodiscard]] std::vector<Word> const& generating_pairs() const noexcept {
640 return _generating_pairs;
641 }
642
659 [[nodiscard]] Presentation<Word> const& presentation() const noexcept {
660 return _presentation;
661 }
662
664 // ToddCoxeter - interface requirements - add_generating_pair
666
684 template <typename Iterator1,
685 typename Iterator2,
686 typename Iterator3,
687 typename Iterator4>
689 Iterator2 last1,
690 Iterator3 first2,
691 Iterator4 last2);
692
707 template <typename Iterator1,
708 typename Iterator2,
709 typename Iterator3,
710 typename Iterator4>
712 Iterator2 last1,
713 Iterator3 first2,
714 Iterator4 last2) {
715 // Call detail::CongruenceCommon version so that we perform bound checks
716 // in ToddCoxeter and not ToddCoxeterImpl
717 return detail::CongruenceCommon::add_generating_pair<ToddCoxeter>(
718 first1, last1, first2, last2);
719 }
720
722 // ToddCoxeter - interface requirements - contains
724
745 template <typename Iterator1,
746 typename Iterator2,
747 typename Iterator3,
748 typename Iterator4>
750 Iterator2 last1,
751 Iterator3 first2,
752 Iterator4 last2) const {
753 return ToddCoxeterImpl::currently_contains_no_checks(
754 detail::citow(this, first1),
755 detail::citow(this, last1),
756 detail::citow(this, first2),
757 detail::citow(this, last2));
758 }
759
780 template <typename Iterator1,
781 typename Iterator2,
782 typename Iterator3,
783 typename Iterator4>
784 tril currently_contains(Iterator1 first1,
785 Iterator2 last1,
786 Iterator3 first2,
787 Iterator4 last2) const {
788 // Call detail::CongruenceCommon version so that we perform bound checks
789 // in ToddCoxeter and not ToddCoxeterImpl
790 return detail::CongruenceCommon::currently_contains<ToddCoxeter>(
791 first1, last1, first2, last2);
792 }
793
811 template <typename Iterator1,
812 typename Iterator2,
813 typename Iterator3,
814 typename Iterator4>
815 bool contains_no_checks(Iterator1 first1,
816 Iterator2 last1,
817 Iterator3 first2,
818 Iterator4 last2) {
819 return ToddCoxeterImpl::contains_no_checks(detail::citow(this, first1),
820 detail::citow(this, last1),
821 detail::citow(this, first2),
822 detail::citow(this, last2));
823 }
824
842 template <typename Iterator1,
843 typename Iterator2,
844 typename Iterator3,
845 typename Iterator4>
846 bool contains(Iterator1 first1,
847 Iterator2 last1,
848 Iterator3 first2,
849 Iterator4 last2);
850
852 // ToddCoxeter - interface requirements - reduce
854
876 template <typename OutputIterator,
877 typename InputIterator1,
878 typename InputIterator2>
879 OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
880 InputIterator1 first,
881 InputIterator2 last) const {
882 return ToddCoxeterImpl::reduce_no_run_no_checks(
883 detail::itow(this, d_first),
884 detail::citow(this, first),
885 detail::citow(this, last))
886 .get();
887 }
888
909 template <typename OutputIterator,
910 typename InputIterator1,
911 typename InputIterator2>
912 OutputIterator reduce_no_run(OutputIterator d_first,
913 InputIterator1 first,
914 InputIterator2 last) const {
915 return detail::CongruenceCommon::reduce_no_run<ToddCoxeter>(
916 d_first, first, last);
917 }
918
942 template <typename OutputIterator,
943 typename InputIterator1,
944 typename InputIterator2>
945 OutputIterator reduce_no_checks(OutputIterator d_first,
946 InputIterator1 first,
947 InputIterator2 last) {
948 return ToddCoxeterImpl::reduce_no_checks(detail::itow(this, d_first),
949 detail::citow(this, first),
950 detail::citow(this, last))
951 .get();
952 }
953
977 template <typename OutputIterator,
978 typename InputIterator1,
979 typename InputIterator2>
980 OutputIterator reduce(OutputIterator d_first,
981 InputIterator1 first,
982 InputIterator2 last) {
983 // Call detail::CongruenceCommon version so that we perform bound checks
984 // in ToddCoxeter and not ToddCoxeterImpl
985 return detail::CongruenceCommon::reduce<ToddCoxeter>(
986 d_first, first, last);
987 }
988
990 // ToddCoxeterImpl - word -> index
992
1007
1032 // NOTE THAT: the graph contains one more node than there are element if
1033 // the underlying presentation does not contain the empty word
1034 template <typename Iterator1, typename Iterator2>
1036 Iterator2 last) const {
1037 return ToddCoxeterImpl::current_index_of_no_checks(
1038 detail::citow(this, first), detail::citow(this, last));
1039 }
1040
1064 template <typename Iterator1, typename Iterator2>
1065 index_type current_index_of(Iterator1 first, Iterator2 last) const {
1067 return current_index_of_no_checks(first, last);
1068 }
1069
1094 template <typename Iterator1, typename Iterator2>
1095 index_type index_of_no_checks(Iterator1 first, Iterator2 last) {
1096 return ToddCoxeterImpl::index_of_no_checks(detail::citow(this, first),
1097 detail::citow(this, last));
1098 }
1099
1124 template <typename Iterator1, typename Iterator2>
1125 index_type index_of(Iterator1 first, Iterator2 last) {
1127 return index_of_no_checks(first, last);
1128 }
1129
1131
1133 // ToddCoxeter - index -> word
1135
1152
1177 // NOTE THAT: the graph contains one more node than there are element if
1178 // the underlying presentation does not contain the empty word
1179 template <typename OutputIterator>
1180 OutputIterator current_word_of_no_checks(OutputIterator d_first,
1181 index_type i) const {
1182 return ToddCoxeterImpl::current_word_of_no_checks(
1183 detail::itow(this, d_first), i)
1184 .get();
1185 }
1186
1209 template <typename OutputIterator>
1210 OutputIterator current_word_of(OutputIterator d_first, index_type i) const {
1211 return ToddCoxeterImpl::current_word_of(detail::itow(this, d_first), i)
1212 .get();
1213 }
1214
1237 template <typename Iterator>
1238 Iterator word_of_no_checks(Iterator d_first, index_type i) {
1239 return ToddCoxeterImpl::word_of_no_checks(detail::itow(this, d_first), i)
1240 .get();
1241 }
1242
1266 template <typename Iterator>
1267 Iterator word_of(Iterator d_first, index_type i) {
1268 return ToddCoxeterImpl::word_of(detail::itow(this, d_first), i).get();
1269 }
1270
1272 }; // class ToddCoxeter
1273
1275 //
1282 template <typename Word>
1283 ToddCoxeter(congruence_kind, Presentation<Word> const&) -> ToddCoxeter<Word>;
1284
1286 //
1293 template <typename Word>
1295
1297 //
1304 template <typename Word>
1305 ToddCoxeter(congruence_kind, ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;
1306
1308 //
1315 template <typename Node>
1317 -> ToddCoxeter<word_type>;
1318
1320 //
1327 template <typename Node>
1328 ToddCoxeter(congruence_kind, WordGraph<Node>&&) -> ToddCoxeter<word_type>;
1329
1331 //
1338 template <typename Word>
1339 ToddCoxeter(ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;
1340
1342 //
1349 template <typename Word>
1350 ToddCoxeter(ToddCoxeter<Word>&&) -> ToddCoxeter<Word>;
1351
1368 template <typename Word>
1369 std::string to_human_readable_repr(ToddCoxeter<Word> const& tc);
1370} // namespace libsemigroups
1371
1372#include "todd-coxeter-class.tpp"
1373#endif // LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:103
Class for representing word graphs.
Definition word-graph.hpp:83
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
Presentation(Presentation< Word > const &) -> Presentation< Word >
Deduction guide.
ToddCoxeter(congruence_kind, Presentation< Word > const &) -> ToddCoxeter< Word >
Deduction guide.
OutputIterator current_word_of(OutputIterator d_first, index_type i) const
Insert a current word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1210
Iterator word_of_no_checks(Iterator d_first, index_type i)
Insert the word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1238
Iterator word_of(Iterator d_first, index_type i)
Insert the word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1267
OutputIterator current_word_of_no_checks(OutputIterator d_first, index_type i) const
Insert a current word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1180
ToddCoxeter(congruence_kind knd, Presentation< Word > &&p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:461
ToddCoxeter & init(congruence_kind knd, Presentation< Word > &&p)
Re-initialize a ToddCoxeter instance.
ToddCoxeter & operator=(ToddCoxeter &&)=default
Move assignment operator.
ToddCoxeter()=default
Default constructor.
ToddCoxeter & init(congruence_kind knd, WordGraph< Node > const &wg)
Re-initialize a ToddCoxeter instance.
void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const
Throws if any letter in a range is out of bounds.
Definition todd-coxeter-class.hpp:621
ToddCoxeter & operator=(ToddCoxeter const &)=default
Copy assignment operator.
ToddCoxeter(ToddCoxeter const &)=default
ToddCoxeter(congruence_kind knd, WordGraph< Node > const &wg)
Construct from congruence_kind and WordGraph.
Definition todd-coxeter-class.hpp:560
ToddCoxeter(congruence_kind knd, Presentation< Word > const &p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:483
ToddCoxeter(ToddCoxeter &&)=default
ToddCoxeter & init(congruence_kind knd, Presentation< Word > const &p)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:489
ToddCoxeter & init()
Re-initialize a ToddCoxeter instance.
ToddCoxeter & init(congruence_kind knd, ToddCoxeter const &tc)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:529
ToddCoxeter(congruence_kind knd, ToddCoxeter const &tc)
Construct from congruence_kind and ToddCoxeter.
Definition todd-coxeter-class.hpp:509
OutputIterator reduce_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word with no checks.
Definition todd-coxeter-class.hpp:945
bool contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:815
tril currently_contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:784
OutputIterator reduce(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word.
Definition todd-coxeter-class.hpp:980
size_t number_of_generating_pairs() const noexcept
Returns the number of generating pairs.
ToddCoxeter & add_generating_pair(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
Definition todd-coxeter-class.hpp:711
std::vector< Word > const & generating_pairs() const noexcept
Get the generating pairs of the congruence.
Definition todd-coxeter-class.hpp:639
tril currently_contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:749
bool contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
ToddCoxeter & add_generating_pair_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
congruence_kind kind() const noexcept
The kind of the congruence (1- or 2-sided).
Presentation< Word > const & presentation() const noexcept
Get the presentation used to define a ToddCoxeter instance (if any).
Definition todd-coxeter-class.hpp:659
OutputIterator reduce_no_run_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration or checks.
Definition todd-coxeter-class.hpp:879
OutputIterator reduce_no_run(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration.
Definition todd-coxeter-class.hpp:912
typename detail::ToddCoxeterImpl::word_graph_type word_graph_type
The type of the underlying WordGraph.
Definition todd-coxeter-class.hpp:381
typename detail::ToddCoxeterImpl::node_type node_type
The type of the nodes in the word graph.
Definition todd-coxeter-class.hpp:373
typename detail::ToddCoxeterImpl::index_type index_type
The type of the index of a class.
Definition todd-coxeter-class.hpp:398
typename detail::ToddCoxeterImpl::label_type label_type
The type of the edge-labels in the word graph.
Definition todd-coxeter-class.hpp:406
Word native_word_type
Type of the letters in the relations of the presentation stored in a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:365
index_type current_index_of(Iterator1 first, Iterator2 last) const
Returns the current index of the class containing a word.
Definition todd-coxeter-class.hpp:1065
index_type current_index_of_no_checks(Iterator1 first, Iterator2 last) const
Returns the current index of the class containing a word.
Definition todd-coxeter-class.hpp:1035
index_type index_of_no_checks(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1095
index_type index_of(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1125
tril
Enum to indicate true, false or not currently knowable.
Definition types.hpp:54
congruence_kind
Enum to indicate the sided-ness of a congruence.
Definition types.hpp:67
T move(T... args)
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
Struct containing various options that can be used to control the behaviour of Todd-Coxeter.
Definition todd-coxeter-class.hpp:153
lookahead_style
Enum class for specifying the style of any lookahead performed.
Definition todd-coxeter-class.hpp:239
lookahead_extent
Enum class for specifying the extent of any lookahead performed.
Definition todd-coxeter-class.hpp:222
@ partial
Definition todd-coxeter-class.hpp:230
@ full
Definition todd-coxeter-class.hpp:226
strategy
Enum class containing various strategies.
Definition todd-coxeter-class.hpp:164
@ CR
Definition todd-coxeter-class.hpp:183
@ Cr
Definition todd-coxeter-class.hpp:202
@ hlt
Definition todd-coxeter-class.hpp:168
@ felsch
Definition todd-coxeter-class.hpp:173
@ Rc
Definition todd-coxeter-class.hpp:213
@ R_over_C
Definition todd-coxeter-class.hpp:192
def_version
Values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:316
@ two
Version 2 definition processing.
Definition todd-coxeter-class.hpp:320
@ one
Version 1 definition processing.
Definition todd-coxeter-class.hpp:318
def_policy
Enum class containing values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:270
@ discard_all_if_no_space
Definition todd-coxeter-class.hpp:287
@ unlimited
Definition todd-coxeter-class.hpp:290
@ no_stack_if_no_space
Definition todd-coxeter-class.hpp:273
@ purge_from_top
Definition todd-coxeter-class.hpp:278
@ purge_all
Definition todd-coxeter-class.hpp:283