libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
action.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2019-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 a generic implementation of a class Action which
20// represents the action of a semigroup on a set.
21
22#ifndef LIBSEMIGROUPS_ACTION_HPP_
23#define LIBSEMIGROUPS_ACTION_HPP_
24
25#include <cstddef> // for size_t
26#include <stack> // for stack
27#include <type_traits> // for is_trivially_default_construc...
28#include <unordered_map> // for unordered_map
29#include <utility> // for pair
30#include <vector> // for vector
31
32#include "adapters.hpp" // for One
33#include "constants.hpp" // for UNDEFINED
34#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
35#include "exception.hpp" // for LIBSEMIGROUPS_EXCEPTION
36#include "forest.hpp" // for Forest
37#include "gabow.hpp" // for Gabow
38#include "runner.hpp" // for Runner
39#include "word-graph.hpp" // for WordGraph
40
41#include "detail/bruidhinn-traits.hpp" // for detail::BruidhinnTraits
42#include "detail/report.hpp" // for report_default
43
44namespace libsemigroups {
82
91 enum class side {
98 };
99
171 template <typename Element,
172 typename Point,
173 typename Func,
174 typename Traits,
175 side LeftOrRight>
176 class Action : public Runner, private detail::BruidhinnTraits<Point> {
178 // Action - typedefs - private
180
181 using internal_point_type =
182 typename detail::BruidhinnTraits<Point>::internal_value_type;
183 using internal_const_point_type =
184 typename detail::BruidhinnTraits<Point>::internal_const_value_type;
185 using internal_const_reference =
186 typename detail::BruidhinnTraits<Point>::internal_const_reference;
187
188 struct InternalEqualTo : private detail::BruidhinnTraits<Point> {
189 using EqualTo = typename Traits::EqualTo;
190 bool operator()(internal_const_point_type x,
191 internal_const_point_type y) const {
192 return EqualTo()(this->to_external_const(x),
193 this->to_external_const(y));
194 }
195 };
196
197 struct InternalHash : private detail::BruidhinnTraits<Point> {
198 using Hash = typename Traits::Hash;
199 size_t operator()(internal_const_point_type x) const {
200 return Hash()(this->to_external_const(x));
201 }
202 };
203
204 using Degree = typename Traits::Degree;
205
206 // Forward decls
207 class MultiplierCache;
208 struct Options;
209
210 static_assert(
213 internal_const_point_type>::type>::value,
214 "internal_const_element_type must be const or pointer to const");
215
216 public:
218 // Action - typedefs - public
220
225 using element_type = Element;
226
231 using point_type = Point;
232
238 using index_type = size_t;
239
250 using action_type = Func;
251
256 template <typename Elment,
257 typename Pint,
258 typename Fnc,
259 typename Trits,
260 side LftOrRight>
264
269 friend std::ostream& operator<<(std::ostream& os, Action const& action) {
270 os << detail::to_string(action);
271 return os;
272 }
273
275 // Action - iterators - public
277
283 = detail::BruidhinnConstIterator<point_type,
285
291 typename detail::BruidhinnTraits<Point>::const_reference;
292
298 typename detail::BruidhinnTraits<Point>::const_pointer;
299
300 private:
302 // Action - internal types with call operators - private
304
305 using ActionOp = Func;
306 using One = typename Traits::One;
307 using Product = typename Traits::Product;
308 using Swap = typename Traits::Swap;
309
311 "the 3rd template parameter Func is not trivially "
312 "default constructible");
313 // TODO(2) more static assertions
314
316 // Action - product functions for left/right multiplication - private
318
319 auto internal_product(element_type& xy,
320 element_type const& x,
321 element_type const& y) {
322 if constexpr (LeftOrRight == side::right) {
323 Product()(xy, x, y);
324 } else {
325 Product()(xy, y, x);
326 }
327 }
328
330 // Action - data members - private
332
333 // TODO(1) change size_t -> uint32_t
335 WordGraph<uint32_t> _graph;
336 std::unordered_map<internal_const_point_type,
337 size_t,
338 InternalHash,
339 InternalEqualTo>
340 _map;
341 Options _options;
343 MultiplierCache _multipliers_from_scc_root;
344 MultiplierCache _multipliers_to_scc_root;
345 size_t _pos;
346 Gabow<uint32_t> _scc;
347 internal_point_type _tmp_point;
348 bool _tmp_point_init;
349
350 public:
352 // Action - constructor + destructor - public
354
365 Action();
366
376 Action& init();
377
378 //! Default copy constructor.
379 Action(Action const& that) : Action() {
380 *this = that;
381 }
382
383 //! Default move constructor.
384 Action(Action&& that) : Action() {
385 *this = std::move(that);
386 }
387
389 Action& operator=(Action const&);
390
393
394 ~Action();
395
397 // Action - modifiers - public
399
413 Action& reserve(size_t val);
414
431
445 //! Constant.
446 Action& add_generator(element_type const& gen) {
447 throw_if_bad_degree(gen);
448 return add_generator_no_checks(gen);
449 }
450
464 //! Constant.
466 _gens.push_back(gen);
467 return *this;
468 }
469
471 // Action - member functions: position, empty, size, etc - public
473
482 //! Constant.
483 [[nodiscard]] size_t number_of_generators() const noexcept {
484 return _gens.size();
485 }
486
495 //! Constant.
496 [[nodiscard]] std::vector<Element> const& generators() const noexcept {
497 return _gens;
498 }
499
515 [[nodiscard]] index_type position(const_reference_point_type pt) const;
516
526 //! Constant.
527 [[nodiscard]] bool empty() const noexcept {
528 return _orb.empty();
529 }
530
544 [[nodiscard]] inline const_reference_point_type
545 operator[](index_type pos) const noexcept {
546 LIBSEMIGROUPS_ASSERT(pos < _orb.size());
547 return this->to_external_const(_orb[pos]);
548 }
549
562 //! Constant.
563 [[nodiscard]] inline const_reference_point_type at(index_type pos) const {
564 return this->to_external_const(_orb.at(pos));
565 }
566
578 //! points in the orbit and \f$n\f$ is the number of generators.
579 [[nodiscard]] size_t size() {
580 run();
581 return _orb.size();
582 }
583
595 //! Constant.
596 [[nodiscard]] size_t current_size() const noexcept {
597 return _orb.size();
598 }
599
613 //! Constant.
614 [[nodiscard]] const_iterator cbegin() const noexcept {
615 return const_iterator(_orb.cbegin());
616 }
617
618 //! \copydoc cbegin
619 [[nodiscard]] const_iterator begin() const noexcept {
620 return cbegin();
621 }
622
636 // TODO(1) add a reference to the ranges page when it exists
637 [[nodiscard]] auto range() const noexcept {
638 return rx::iterator_range(_orb.cbegin(), _orb.cend())
639 | rx::transform([this](auto const& pt) {
640 return this->to_external_const(pt);
641 });
642 }
643
658 //! Constant.
659 [[nodiscard]] const_iterator cend() const noexcept {
660 return const_iterator(_orb.cend());
661 }
662
663 //! \copydoc cend
664 [[nodiscard]] const_iterator end() const noexcept {
665 return cend();
666 }
667
669 // Action - member functions: strongly connected components - public
671
685 //! Constant.
686 [[nodiscard]] bool cache_scc_multipliers() const noexcept {
687 return _options._cache_scc_multipliers;
688 }
689
705 //! Constant.
706 Action& cache_scc_multipliers(bool val) noexcept {
707 _options._cache_scc_multipliers = val;
708 return *this;
709 }
710
728 //! enumerated orbit.
730 return multiplier_private<true>(
731 _multipliers_from_scc_root, _scc.spanning_forest(), pos);
732 }
733
751 //! enumerated orbit.
753 return multiplier_private<false>(
754 _multipliers_to_scc_root, _scc.reverse_spanning_forest(), pos);
755 }
756
776 // TODO(2) this could be a helper
777 return root_of_scc(position(x));
778 }
779
796 //! enumerated orbit.
798 return this->to_external_const(_orb[_scc.root_of(pos)]);
799 }
800
811 //! enumerated orbit.
812 [[nodiscard]] WordGraph<uint32_t> const& word_graph() {
813 run();
814 return _graph;
815 }
816
831 //! enumerated orbit.
832 [[nodiscard]] Gabow<uint32_t> const& scc() {
833 run();
834 return _scc;
835 }
836
849 // These functions allow the action operation (defined by Func) to be called
850 // on an instance of Action. This isn't very helpful in C++ code, but is in
851 // the python bindings, where figuring out the type of Func is a bit fiddly.
852 static void apply(point_type& result,
853 point_type const& pt,
854 element_type const& x) {
855 ActionOp()(result, pt, x);
856 }
857
868 //! \no_libsemigroups_except
869 [[nodiscard]] static point_type apply(point_type const& pt,
870 element_type const& x) {
871 point_type result;
872 apply(result, pt, x);
873 return result;
874 }
875
876 private:
878 // Runner - pure virtual member functions - private
880
881 [[nodiscard]] bool finished_impl() const override {
882 return (_pos == _orb.size()) && (_graph.out_degree() == _gens.size());
883 }
884
885 void run_impl() override;
886
888 // Action - member functions - private
890
891 template <bool Forward>
892 element_type multiplier_private(MultiplierCache& mults,
893 Forest const& f,
894 index_type pos);
895
896 void throw_if_index_out_of_range(index_type i) const;
897 void throw_if_no_generators() const;
898 void throw_if_bad_degree(element_type const&) const;
899 };
900
909 template <typename Element, typename Point>
924
929 template <typename Element,
930 typename Point,
931 typename Func = ImageRightAction<Element, Point>,
932 typename Traits = ActionTraits<Element, Point>>
934
939 template <typename Element,
940 typename Point,
941 typename Func = ImageLeftAction<Element, Point>,
942 typename Traits = ActionTraits<Element, Point>>
944} // namespace libsemigroups
945
946#include "action.tpp"
947#endif // LIBSEMIGROUPS_ACTION_HPP_
Class for generating the action of a semigroup.
Definition action.hpp:176
index_type position(const_reference_point_type pt) const
Returns the position of a point in the so far discovered points.
size_t size()
Returns the size of the fully enumerated action.
Definition action.hpp:578
auto range() const noexcept
Returns a range object containing the current points in the action.
Definition action.hpp:636
Action & init()
Initialize an existing Action object.
Action & operator=(Action const &)
Default copy assignment operator.
typename detail::BruidhinnTraits< Point >::const_reference const_reference_point_type
The type of a const reference to a point_type.
Definition action.hpp:289
const_iterator begin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first point.
Definition action.hpp:618
friend std::ostringstream & operator<<(std::ostringstream &os, Action< Elment, Pint, Fnc, Trits, LftOrRight > const &action)
Insertion operator.
Action & add_generator_no_checks(element_type const &gen)
Add a generator to the action.
Definition action.hpp:464
bool empty() const noexcept
Checks if the Action contains any points.
Definition action.hpp:526
Func action_type
Type of the action of element_type on point_type.
Definition action.hpp:250
Element element_type
The template parameter Element.
Definition action.hpp:225
typename detail::BruidhinnTraits< Point >::const_pointer const_pointer_point_type
The type of a const pointer to a point_type.
Definition action.hpp:296
element_type multiplier_from_scc_root(index_type pos)
Returns a multiplier from a scc root to a given index.
Definition action.hpp:728
const_iterator end() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last point.
Definition action.hpp:663
Action & add_generator(element_type const &gen)
Add a generator to the action.
Definition action.hpp:445
element_type multiplier_to_scc_root(index_type pos)
Returns a multiplier from a given index to a scc root.
Definition action.hpp:751
size_t number_of_generators() const noexcept
Returns the number of generators.
Definition action.hpp:482
Action & reserve(size_t val)
Increase the capacity to a value that is greater or equal to val.
size_t index_type
The type of the index of a point.
Definition action.hpp:238
Point point_type
The template parameter Point.
Definition action.hpp:231
static void apply(point_type &result, point_type const &pt, element_type const &x)
Apply the template parameter Func in-place.
Definition action.hpp:851
detail::BruidhinnConstIterator< point_type, std::vector< internal_point_type > > const_iterator
The type of a const iterator pointing to a point_type.
Definition action.hpp:282
const_iterator cend() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last point.
Definition action.hpp:658
Action()
Default constructor.
Gabow< uint32_t > const & scc()
Returns a reference to a Gabow object for strongly connected components.
Definition action.hpp:831
size_t current_size() const noexcept
Returns the number of points found so far.
Definition action.hpp:595
std::vector< Element > const & generators() const noexcept
Returns a const reference to the vector of generators.
Definition action.hpp:495
const_reference_point_type root_of_scc(const_reference_point_type x)
Returns a const reference to the root point of a strongly connected component.
Definition action.hpp:774
const_iterator cbegin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first point.
Definition action.hpp:613
Action & add_seed(const_reference_point_type seed)
Add a seed to the action.
WordGraph< uint32_t > const & word_graph()
Definition action.hpp:811
friend std::ostream & operator<<(std::ostream &os, Action const &action)
Definition action.hpp:269
bool cache_scc_multipliers() const noexcept
Returns whether or not we are caching scc multipliers.
Definition action.hpp:685
const_reference_point_type at(index_type pos) const
Returns a const reference to the point in a given position.
Definition action.hpp:562
const_reference_point_type operator[](index_type pos) const noexcept
Returns a const reference to the point in a given position.
Definition action.hpp:544
Class implementing Gabow's algorithm for computing strongly connected components of a WordGraph.
Definition gabow.hpp:61
void run()
Run until finished.
Runner()
Default constructor.
Class for representing word graphs.
Definition word-graph.hpp:82
size_type out_degree() const noexcept
Returns the out-degree.
Definition word-graph.hpp:823
Action< Element, Point, Func, Traits, side::right > RightAction
Definition action.hpp:933
Action< Element, Point, Func, Traits, side::left > LeftAction
Definition action.hpp:943
side
Enum class indicating the handedness or side of an action.
Definition action.hpp:91
@ right
Definition action.hpp:97
@ left
Definition action.hpp:94
T move(T... args)
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T size(T... args)
Definition action.hpp:910
::libsemigroups::Hash< Point > Hash
Adapter for hashing.
Definition action.hpp:914
::libsemigroups::Swap< Element > Swap
Adapter for swapping.
Definition action.hpp:918
::libsemigroups::Degree< Element > Degree
Adapter for the degree of an element.
Definition action.hpp:912
::libsemigroups::EqualTo< Point > EqualTo
Adapter for testing equality.
Definition action.hpp:916
::libsemigroups::Product< Element > Product
Adapter for the product of two elements.
Definition action.hpp:922
::libsemigroups::One< Element > One
Adapter for the identity element of the given type.
Definition action.hpp:920
Adapter for the degree of an element.
Definition adapters.hpp:159
Adapter for testing equality.
Definition adapters.hpp:413
Adapter for hashing.
Definition adapters.hpp:446
Adapter for the value of a left action.
Definition adapters.hpp:350
Adapter for the value of a right action.
Definition adapters.hpp:392
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284
Adapter for swapping.
Definition adapters.hpp:666