libsemigroups  v3.1.2
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
135 template <typename Word>
136 class ToddCoxeter : public detail::ToddCoxeterImpl {
137 private:
138 std::vector<Word> _generating_pairs;
139 Presentation<Word> _presentation;
140
141 public:
142#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
150 struct options : public FelschGraphSettings_::options {
161 enum class strategy {
166
171
181
190
200
211 };
212
229
236 enum class lookahead_style {
241
246 };
247
289
290 // NOTE: The next enum (def_version) is actually defined in FelschGraph,
291 // not in ToddCoxeter
292
313 enum class def_version : uint8_t {
318 };
319 };
320
335 [[nodiscard]] congruence_kind kind() const noexcept;
336
352 [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
353#endif
354
362 using native_word_type = Word;
363
370 using node_type = typename detail::ToddCoxeterImpl::node_type;
371
378 using word_graph_type = typename detail::ToddCoxeterImpl::word_graph_type;
379
395 using index_type = typename detail::ToddCoxeterImpl::index_type;
396
403 using label_type = typename detail::ToddCoxeterImpl::label_type;
404
410 ToddCoxeter() = default;
411
424
427 ToddCoxeter(ToddCoxeter const&) = default;
428
432
438
444
445 ~ToddCoxeter();
446
461
477
481 // call the rval ref constructor
482 : ToddCoxeter(knd, Presentation<Word>(p)) {}
483
487 // call the rval ref init
488 return init(knd, Presentation<Word>(p));
489 }
490
507 init(knd, tc);
508 }
509
527 ToddCoxeterImpl::init(knd, tc);
528 _presentation = tc.presentation();
529 _presentation.rules.insert(_presentation.rules.end(),
530 tc.generating_pairs().cbegin(),
531 tc.generating_pairs().cend());
532 // Clear generating pairs last, in case &tc == this!!!
533 _generating_pairs.clear();
534 // TODO(1) check KnuthBendix et al
535 return *this;
536 }
537
556 template <typename Node>
558 : ToddCoxeter() {
559 init(knd, wg);
560 }
561
578 template <typename Node>
580
581#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
582 // Used in Sims
583 // TODO(1) could this and the next function be removed, and replaced
584 // with something else?
585 template <typename Node>
587 Presentation<Word> const& p,
588 WordGraph<Node> const& wg) {
589 init(knd, p, wg);
590 }
591
592 // TODO(1) a "make" variant that throws if params are valid
593 template <typename Node>
594 ToddCoxeter& init(congruence_kind knd,
595 Presentation<Word> const& p,
596 WordGraph<Node> const& wg);
597#endif
598
617 template <typename Iterator1, typename Iterator2>
619 Iterator2 last) const {
620 presentation().throw_if_letter_not_in_alphabet(first, last);
621 }
622
636 [[nodiscard]] std::vector<Word> const& generating_pairs() const noexcept {
637 return _generating_pairs;
638 }
639
656 [[nodiscard]] Presentation<Word> const& presentation() const noexcept {
657 return _presentation;
658 }
659
661 // ToddCoxeter - interface requirements - add_generating_pair
663
681 template <typename Iterator1,
682 typename Iterator2,
683 typename Iterator3,
684 typename Iterator4>
686 Iterator2 last1,
687 Iterator3 first2,
688 Iterator4 last2);
689
704 template <typename Iterator1,
705 typename Iterator2,
706 typename Iterator3,
707 typename Iterator4>
709 Iterator2 last1,
710 Iterator3 first2,
711 Iterator4 last2) {
712 // Call detail::CongruenceCommon version so that we perform bound checks
713 // in ToddCoxeter and not ToddCoxeterImpl
714 return detail::CongruenceCommon::add_generating_pair<ToddCoxeter>(
715 first1, last1, first2, last2);
716 }
717
719 // ToddCoxeter - interface requirements - contains
721
742 template <typename Iterator1,
743 typename Iterator2,
744 typename Iterator3,
745 typename Iterator4>
747 Iterator2 last1,
748 Iterator3 first2,
749 Iterator4 last2) const {
750 return ToddCoxeterImpl::currently_contains_no_checks(
751 detail::citow(this, first1),
752 detail::citow(this, last1),
753 detail::citow(this, first2),
754 detail::citow(this, last2));
755 }
756
777 template <typename Iterator1,
778 typename Iterator2,
779 typename Iterator3,
780 typename Iterator4>
781 tril currently_contains(Iterator1 first1,
782 Iterator2 last1,
783 Iterator3 first2,
784 Iterator4 last2) const {
785 // Call detail::CongruenceCommon version so that we perform bound checks
786 // in ToddCoxeter and not ToddCoxeterImpl
787 return detail::CongruenceCommon::currently_contains<ToddCoxeter>(
788 first1, last1, first2, last2);
789 }
790
808 template <typename Iterator1,
809 typename Iterator2,
810 typename Iterator3,
811 typename Iterator4>
812 bool contains_no_checks(Iterator1 first1,
813 Iterator2 last1,
814 Iterator3 first2,
815 Iterator4 last2) {
816 return ToddCoxeterImpl::contains_no_checks(detail::citow(this, first1),
817 detail::citow(this, last1),
818 detail::citow(this, first2),
819 detail::citow(this, last2));
820 }
821
839 template <typename Iterator1,
840 typename Iterator2,
841 typename Iterator3,
842 typename Iterator4>
843 bool contains(Iterator1 first1,
844 Iterator2 last1,
845 Iterator3 first2,
846 Iterator4 last2);
847
849 // ToddCoxeter - interface requirements - reduce
851
873 template <typename OutputIterator,
874 typename InputIterator1,
875 typename InputIterator2>
876 OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
877 InputIterator1 first,
878 InputIterator2 last) const {
879 return ToddCoxeterImpl::reduce_no_run_no_checks(
880 detail::itow(this, d_first),
881 detail::citow(this, first),
882 detail::citow(this, last))
883 .get();
884 }
885
906 template <typename OutputIterator,
907 typename InputIterator1,
908 typename InputIterator2>
909 OutputIterator reduce_no_run(OutputIterator d_first,
910 InputIterator1 first,
911 InputIterator2 last) const {
912 return detail::CongruenceCommon::reduce_no_run<ToddCoxeter>(
913 d_first, first, last);
914 }
915
939 template <typename OutputIterator,
940 typename InputIterator1,
941 typename InputIterator2>
942 OutputIterator reduce_no_checks(OutputIterator d_first,
943 InputIterator1 first,
944 InputIterator2 last) {
945 return ToddCoxeterImpl::reduce_no_checks(detail::itow(this, d_first),
946 detail::citow(this, first),
947 detail::citow(this, last))
948 .get();
949 }
950
974 template <typename OutputIterator,
975 typename InputIterator1,
976 typename InputIterator2>
977 OutputIterator reduce(OutputIterator d_first,
978 InputIterator1 first,
979 InputIterator2 last) {
980 // Call detail::CongruenceCommon version so that we perform bound checks
981 // in ToddCoxeter and not ToddCoxeterImpl
982 return detail::CongruenceCommon::reduce<ToddCoxeter>(
983 d_first, first, last);
984 }
985
987 // ToddCoxeterImpl - word -> index
989
1004
1029 // NOTE THAT: the graph contains one more node than there are element if
1030 // the underlying presentation does not contain the empty word
1031 template <typename Iterator1, typename Iterator2>
1033 Iterator2 last) const {
1034 return ToddCoxeterImpl::current_index_of_no_checks(
1035 detail::citow(this, first), detail::citow(this, last));
1036 }
1037
1061 template <typename Iterator1, typename Iterator2>
1062 index_type current_index_of(Iterator1 first, Iterator2 last) const {
1064 return current_index_of_no_checks(first, last);
1065 }
1066
1091 template <typename Iterator1, typename Iterator2>
1092 index_type index_of_no_checks(Iterator1 first, Iterator2 last) {
1093 return ToddCoxeterImpl::index_of_no_checks(detail::citow(this, first),
1094 detail::citow(this, last));
1095 }
1096
1121 template <typename Iterator1, typename Iterator2>
1122 index_type index_of(Iterator1 first, Iterator2 last) {
1124 return index_of_no_checks(first, last);
1125 }
1126
1128
1130 // ToddCoxeter - index -> word
1132
1149
1174 // NOTE THAT: the graph contains one more node than there are element if
1175 // the underlying presentation does not contain the empty word
1176 template <typename OutputIterator>
1177 OutputIterator current_word_of_no_checks(OutputIterator d_first,
1178 index_type i) const {
1179 return ToddCoxeterImpl::current_word_of_no_checks(
1180 detail::itow(this, d_first), i)
1181 .get();
1182 }
1183
1206 template <typename OutputIterator>
1207 OutputIterator current_word_of(OutputIterator d_first, index_type i) const {
1208 return ToddCoxeterImpl::current_word_of(detail::itow(this, d_first), i)
1209 .get();
1210 }
1211
1234 template <typename Iterator>
1235 Iterator word_of_no_checks(Iterator d_first, index_type i) {
1236 return ToddCoxeterImpl::word_of_no_checks(detail::itow(this, d_first), i)
1237 .get();
1238 }
1239
1263 template <typename Iterator>
1264 Iterator word_of(Iterator d_first, index_type i) {
1265 return ToddCoxeterImpl::word_of(detail::itow(this, d_first), i).get();
1266 }
1267
1269 }; // class ToddCoxeter
1270
1272 //
1279 template <typename Word>
1280 ToddCoxeter(congruence_kind, Presentation<Word> const&) -> ToddCoxeter<Word>;
1281
1283 //
1290 template <typename Word>
1292
1294 //
1301 template <typename Word>
1302 ToddCoxeter(congruence_kind, ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;
1303
1305 //
1312 template <typename Node>
1314 -> ToddCoxeter<word_type>;
1315
1317 //
1324 template <typename Node>
1325 ToddCoxeter(congruence_kind, WordGraph<Node>&&) -> ToddCoxeter<word_type>;
1326
1328 //
1335 template <typename Word>
1336 ToddCoxeter(ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;
1337
1339 //
1346 template <typename Word>
1347 ToddCoxeter(ToddCoxeter<Word>&&) -> ToddCoxeter<Word>;
1348
1365 template <typename Word>
1366 std::string to_human_readable_repr(ToddCoxeter<Word> const& tc);
1367} // namespace libsemigroups
1368
1369#include "todd-coxeter-class.tpp"
1370#endif // LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
Class for representing word graphs.
Definition word-graph.hpp:82
std::string to_human_readable_repr(AhoCorasick const &ac)
Return a string representation.
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:1207
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:1235
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:1264
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:1177
ToddCoxeter(congruence_kind knd, Presentation< Word > &&p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:458
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:618
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:557
ToddCoxeter(congruence_kind knd, Presentation< Word > const &p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:480
ToddCoxeter(ToddCoxeter &&)=default
ToddCoxeter & init(congruence_kind knd, Presentation< Word > const &p)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:486
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:526
ToddCoxeter(congruence_kind knd, ToddCoxeter const &tc)
Construct from congruence_kind and ToddCoxeter.
Definition todd-coxeter-class.hpp:506
OutputIterator reduce_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word with no checks.
Definition todd-coxeter-class.hpp:942
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:812
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:781
OutputIterator reduce(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word.
Definition todd-coxeter-class.hpp:977
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:708
std::vector< Word > const & generating_pairs() const noexcept
Get the generating pairs of the congruence.
Definition todd-coxeter-class.hpp:636
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:746
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:656
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:876
OutputIterator reduce_no_run(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration.
Definition todd-coxeter-class.hpp:909
typename detail::ToddCoxeterImpl::word_graph_type word_graph_type
The type of the underlying WordGraph.
Definition todd-coxeter-class.hpp:378
typename detail::ToddCoxeterImpl::node_type node_type
The type of the nodes in the word graph.
Definition todd-coxeter-class.hpp:370
typename detail::ToddCoxeterImpl::index_type index_type
The type of the index of a class.
Definition todd-coxeter-class.hpp:395
typename detail::ToddCoxeterImpl::label_type label_type
The type of the edge-labels in the word graph.
Definition todd-coxeter-class.hpp:403
Word native_word_type
Type of the letters in the relations of the presentation stored in a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:362
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:1062
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:1032
index_type index_of_no_checks(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1092
index_type index_of(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1122
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:150
lookahead_style
Enum class for specifying the style of any lookahead performed.
Definition todd-coxeter-class.hpp:236
lookahead_extent
Enum class for specifying the extent of any lookahead performed.
Definition todd-coxeter-class.hpp:219
@ partial
Definition todd-coxeter-class.hpp:227
@ full
Definition todd-coxeter-class.hpp:223
strategy
Enum class containing various strategies.
Definition todd-coxeter-class.hpp:161
@ CR
Definition todd-coxeter-class.hpp:180
@ Cr
Definition todd-coxeter-class.hpp:199
@ hlt
Definition todd-coxeter-class.hpp:165
@ felsch
Definition todd-coxeter-class.hpp:170
@ Rc
Definition todd-coxeter-class.hpp:210
@ R_over_C
Definition todd-coxeter-class.hpp:189
def_version
Values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:313
@ two
Version 2 definition processing.
Definition todd-coxeter-class.hpp:317
@ one
Version 1 definition processing.
Definition todd-coxeter-class.hpp:315
def_policy
Enum class containing values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:267
@ discard_all_if_no_space
Definition todd-coxeter-class.hpp:284
@ unlimited
Definition todd-coxeter-class.hpp:287
@ no_stack_if_no_space
Definition todd-coxeter-class.hpp:270
@ purge_from_top
Definition todd-coxeter-class.hpp:275
@ purge_all
Definition todd-coxeter-class.hpp:280