libsemigroups  v3.1.3
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
word-graph.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2019-2025 Finn Smith + 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 declarations related to word graphs (which are basically
20// deterministic automata without initial or accept states).
21
22#ifndef LIBSEMIGROUPS_WORD_GRAPH_HPP_
23#define LIBSEMIGROUPS_WORD_GRAPH_HPP_
24
25#include <algorithm> // for uniform_int_distribution
26#include <cstddef> // for size_t
27#include <cstdint> // for uint32_t
28#include <ostream> // for operator<<
29#include <queue> // for queue
30#include <random> // for mt19937
31#include <stack> // for stack
32#include <string> // for to_string
33#include <tuple> // for tie
34#include <type_traits> // for is_integral, is_unsigned
35#include <unordered_set> // for unordered_set
36#include <utility> // for pair
37#include <vector> // for vector
38
39#include "config.hpp" // for LIBSEMIGROUPS_EIGEN_EN...
40#include "constants.hpp" // for UNDEFINED
41#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
42#include "dot.hpp" // for Dot
43#include "exception.hpp" // for LIBSEMIGROUPS_EXCEPTION
44#include "forest.hpp" // for Forest
45#include "is_specialization_of.hpp" // for is_specialization_of_v
46#include "order.hpp" // for Order
47#include "ranges.hpp" // for ??
48#include "types.hpp" // for word_type, enable_if_is_same
49
50#include "detail/containers.hpp" // for DynamicArray2
51#include "detail/int-range.hpp" // for IntRange
52#include "detail/stl.hpp" // for IsIterator
53#include "detail/uf.hpp" // for Duf
54
55#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
56#include "detail/eigen.hpp"
57#else
58#include "matrix.hpp"
59#endif
60
61namespace libsemigroups {
62
67
82 template <typename Node>
83 class WordGraph {
84 static_assert(std::is_integral<Node>(),
85 "the template parameter Node must be an integral type!");
86 static_assert(
88 "the template parameter Node must be an unsigned integral type!");
89
90 template <typename N>
91 friend class WordGraph;
92
93 public:
95 // WordGraph - typedefs - public
97
99 using node_type = Node;
100
102 using label_type = Node;
103
106
107#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
110 = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>;
111#else
114#endif
115
118 typename detail::IntRange<Node>::const_iterator;
119
122 typename detail::IntRange<Node>::const_reverse_iterator;
123
126 typename detail::DynamicArray2<Node>::const_iterator;
127
129 // WordGraph - constructors + destructor - public
131
147 // Not noexcept
148 explicit WordGraph(size_type m = 0, size_type n = 0);
149
168 WordGraph& init(size_type m = 0, size_type n = 0);
169
171 WordGraph(WordGraph const&);
172
182 template <typename OtherNode>
183 WordGraph(WordGraph<OtherNode> const& that);
184
205 template <typename OtherNode>
206 WordGraph& init(WordGraph<OtherNode> const& that);
207
209 WordGraph(WordGraph&&);
210
212 WordGraph& operator=(WordGraph const&);
213
215 WordGraph& operator=(WordGraph&&);
216
217 ~WordGraph();
218
239 static WordGraph random(size_type number_of_nodes,
241 std::mt19937 mt
243
267 // Not noexcept because DynamicArray2::add_cols isn't.
268 WordGraph& reserve(size_type m, size_type n);
269
271 // WordGraph - modifiers - public
273
292 // Not noexcept because DynamicArray2::add_rows isn't.
293 WordGraph& add_nodes(size_type nr);
294
314 // Not noexcept because DynamicArray2::add_cols isn't.
315 WordGraph& add_to_out_degree(size_type nr);
316
334 // Not noexcept because throw_if_node_out_of_bounds/label aren't
335 // return *this by reference.
336 WordGraph& target(node_type s, label_type a, node_type t);
337
356 //! No checks whatsoever on the validity of the arguments are performed.
357 inline WordGraph& target_no_checks(node_type s, label_type a, node_type t) {
358 _dynamic_array_2.set(s, a, t);
359 return *this;
360 }
361
378 //! No checks whatsoever on the validity of the arguments are performed.
379 inline WordGraph& remove_target_no_checks(node_type s, label_type a) {
380 _dynamic_array_2.set(s, a, UNDEFINED);
381 return *this;
382 }
383
397 WordGraph& remove_target(node_type s, label_type a);
398
409 WordGraph& remove_label(label_type a);
410
426
439 //! out-degree.
440 inline WordGraph& remove_all_targets() {
441 std::fill(_dynamic_array_2.begin(), _dynamic_array_2.end(), UNDEFINED);
442 return *this;
443 }
444
464 // swap m - a - > m' and n - a -> n'
466 _dynamic_array_2.swap(m, a, n, a);
467 return *this;
468 }
469
485 WordGraph& swap_targets(node_type m, node_type n, label_type a);
486
502 //! is the out-degree of the word graph.
503 [[nodiscard]] bool operator==(WordGraph const& that) const {
504 return _dynamic_array_2 == that._dynamic_array_2;
505 }
506
522 //! is the out-degree of the word graph.
523 [[nodiscard]] bool operator!=(WordGraph const& that) const {
524 return !operator==(that);
525 }
526
542 //! is the out-degree of the word graph.
543 [[nodiscard]] bool operator<(WordGraph const& that) const {
544 return _dynamic_array_2 < that._dynamic_array_2;
545 }
546
562 //! is the out-degree of the word graph.
563 [[nodiscard]] bool operator<=(WordGraph const& that) const {
564 return _dynamic_array_2 <= that._dynamic_array_2;
565 }
566
582 //! is the out-degree of the word graph.
583 [[nodiscard]] bool operator>(WordGraph const& that) const {
584 return _dynamic_array_2 > that._dynamic_array_2;
585 }
586
602 //! is the out-degree of the word graph.
603 [[nodiscard]] bool operator>=(WordGraph const& that) const {
604 return _dynamic_array_2 > that._dynamic_array_2;
605 }
606
617 // not noexcept because Hash<T>::operator() isn't
618 [[nodiscard]] size_t hash_value() const {
619 return std::hash<decltype(_dynamic_array_2)>()(_dynamic_array_2);
620 }
621
623 // WordGraph - nodes, targets, etc - public
625
643 // Not noexcept because throw_if_node_out_of_bounds/label aren't
644 [[nodiscard]] node_type target(node_type source, label_type a) const;
645
665 // Not noexcept because DynamicArray2::get is not
666 [[nodiscard]] node_type inline target_no_checks(node_type s,
667 label_type a) const {
668 return _dynamic_array_2.get(s, a);
669 }
670
699 // Not noexcept because DynamicArray2::get is not
702
733 // Not noexcept because next_label_and_target_no_checks is not
736
748 //! Constant.
749 [[nodiscard]] size_type inline number_of_nodes() const noexcept {
750 return _nr_nodes;
751 }
752
753#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
754 WordGraph& number_of_active_nodes(size_type val) {
755 _num_active_nodes = val;
756 return *this;
757 }
758
759 [[nodiscard]] size_type inline number_of_active_nodes() const noexcept {
760 return _num_active_nodes;
761 }
762#endif
763
777 // Not noexcept because std::count isn't
778 [[nodiscard]] size_type number_of_edges() const;
779
794 [[nodiscard]] size_type number_of_edges(node_type s) const;
795
811 [[nodiscard]] size_type number_of_edges_no_checks(node_type s) const;
812
824 //! Constant.
825 [[nodiscard]] size_type out_degree() const noexcept {
826 return _degree;
827 }
828
842 //! Constant.
843 const_iterator_nodes cbegin_nodes() const noexcept {
844 return detail::IntRange<node_type>(0, number_of_nodes()).cbegin();
845 }
846
860 //! Constant.
861 [[nodiscard]] const_iterator_nodes cend_nodes() const noexcept {
862 return detail::IntRange<node_type>(0, number_of_nodes()).cend();
863 }
864
882 // Not noexcept because throw_if_node_out_of_bounds isn't
883 [[nodiscard]] const_iterator_targets cbegin_targets(node_type source) const;
884
909 cbegin_targets_no_checks(node_type source) const noexcept {
910 return _dynamic_array_2.cbegin_row(source);
911 }
912
930 // Not noexcept because throw_if_node_out_of_bounds isn't
931 [[nodiscard]] const_iterator_targets cend_targets(node_type source) const;
932
957 cend_targets_no_checks(node_type source) const noexcept {
958 return _dynamic_array_2.cbegin_row(source) + _degree;
959 }
960
969 //! \noexcept
970 [[nodiscard]] auto nodes() const noexcept {
971 return rx::seq<node_type>() | rx::take(number_of_nodes());
972 }
973
983 //! \noexcept
984 [[nodiscard]] auto labels() const noexcept {
985 return rx::seq<label_type>() | rx::take(out_degree());
986 }
987
1005 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1006 targets_no_checks(node_type source) const noexcept {
1007 return rx::iterator_range(cbegin_targets_no_checks(source),
1008 cend_targets_no_checks(source));
1009 }
1010
1023 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1024 targets(node_type source) const;
1025
1043 [[nodiscard]] auto
1044 labels_and_targets_no_checks(node_type source) const noexcept {
1045 return rx::zip(rx::seq<node_type>(), targets_no_checks(source));
1046 }
1047
1059 [[nodiscard]] auto labels_and_targets(node_type source) const;
1060
1079 WordGraph& induced_subgraph_no_checks(node_type first, node_type last);
1080
1095 WordGraph& induced_subgraph(node_type first, node_type last);
1096
1119 template <typename Iterator,
1120 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1121 WordGraph& induced_subgraph_no_checks(Iterator first, Iterator last);
1122
1144 template <typename Iterator,
1145 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1146 WordGraph& induced_subgraph(Iterator first, Iterator last);
1147
1163 WordGraph& disjoint_union_inplace_no_checks(WordGraph<Node> const& that);
1164
1177 WordGraph& disjoint_union_inplace(WordGraph<Node> const& that);
1178
1179#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1180 // These are currently undocumented, because they are hard to use correctly,
1181 // shouldn't p and q be actual permutation objects?
1182
1183 // requires access to apply_row_permutation so can't be helper
1184 WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
1185 std::vector<node_type> const& q,
1186 size_t m);
1187
1188 WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
1189 std::vector<node_type> const& q) {
1190 return permute_nodes_no_checks(p, q, p.size());
1191 }
1192#endif
1193
1194 protected:
1195 // from WordGraphWithSources
1196 template <typename S>
1197 void apply_row_permutation(S const& p) {
1198 _dynamic_array_2.apply_row_permutation(p);
1199 }
1200
1201 private:
1203 // WordGraph - data members - private
1205
1206 size_type _degree;
1207 size_type _nr_nodes;
1208 // TODO(1) remove when WordGraphView is implemented
1209 size_type _num_active_nodes;
1210 mutable detail::DynamicArray2<Node> _dynamic_array_2;
1211 };
1212
1222 namespace word_graph {
1223
1225 // WordGraph - helper functions - in alphabetical order!!!
1227
1250 // TODO(1) add add_cycle with checks version.
1251 template <typename Node, typename Iterator>
1253 Iterator first,
1254 Iterator last);
1255
1271 template <typename Node>
1272 void add_cycle(WordGraph<Node>& wg, size_t N) {
1273 size_t M = wg.number_of_nodes();
1274 wg.add_nodes(N);
1275 add_cycle_no_checks(wg, wg.cbegin_nodes() + M, wg.cend_nodes());
1276 }
1277
1292 template <typename Node>
1293 [[nodiscard]] auto adjacency_matrix(WordGraph<Node> const& wg);
1294
1305 template <typename Node>
1306 [[nodiscard]] Dot dot(WordGraph<Node> const& wg);
1307
1334 template <typename Node>
1335 [[nodiscard]] bool equal_to_no_checks(WordGraph<Node> const& x,
1336 WordGraph<Node> const& y,
1337 Node first,
1338 Node last);
1339
1364 template <typename Node>
1365 [[nodiscard]] bool equal_to(WordGraph<Node> const& x,
1366 WordGraph<Node> const& y,
1367 Node first,
1368 Node last);
1369
1401 template <typename Node1, typename Node2, typename Iterator>
1402 [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
1403 Node2 source,
1404 Iterator first,
1405 Iterator last);
1406
1434 // TODO(2) example
1435 // not noexcept because WordGraph::target isn't
1436 template <typename Node1, typename Node2>
1437 [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
1438 Node2 from,
1439 word_type const& path) {
1440 static_assert(sizeof(Node2) <= sizeof(Node1));
1441 return follow_path(wg, from, path.cbegin(), path.cend());
1442 }
1443
1470 template <typename Node1, typename Node2, typename Iterator>
1471 [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
1472 Node2 from,
1473 Iterator first,
1474 Iterator last) noexcept;
1475
1502 template <typename Node1, typename Node2>
1503 [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
1504 Node2 from,
1505 word_type const& path) noexcept {
1506 static_assert(sizeof(Node2) <= sizeof(Node1));
1507 return follow_path_no_checks(wg, from, path.cbegin(), path.cend());
1508 }
1509
1542 // Not noexcept because detail::is_acyclic isn't
1543 template <typename Node>
1544 [[nodiscard]] bool is_acyclic(WordGraph<Node> const& wg);
1545
1590 // Not noexcept because detail::is_acyclic isn't
1591 template <typename Node1, typename Node2>
1592 [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg, Node2 source);
1593
1623 // Not noexcept because detail::is_acyclic isn't
1624 template <typename Node1, typename Node2>
1625 [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg,
1626 Node2 source,
1627 Node2 target);
1628
1668 template <typename Node,
1669 typename Iterator1,
1670 typename Iterator2,
1671 typename Iterator3>
1672 [[nodiscard]] bool is_compatible_no_checks(WordGraph<Node> const& wg,
1673 Iterator1 first_node,
1674 Iterator2 last_node,
1675 Iterator3 first_rule,
1676 Iterator3 last_rule);
1677
1719 template <
1720 typename Node,
1721 typename Iterator1,
1722 typename Iterator2,
1723 typename Iterator3,
1724 std::enable_if_t<!std::is_same_v<std::decay_t<Iterator3>, word_type>>>
1725 [[nodiscard]] bool is_compatible(WordGraph<Node> const& wg,
1726 Iterator1 first_node,
1727 Iterator2 last_node,
1728 Iterator3 first_rule,
1729 Iterator3 last_rule);
1730
1762 template <typename Node, typename Iterator1, typename Iterator2>
1764 Iterator1 first_node,
1765 Iterator2 last_node,
1766 word_type const& lhs,
1767 word_type const& rhs);
1768
1804 template <typename Node, typename Iterator1, typename Iterator2>
1806 Iterator1 first_node,
1807 Iterator2 last_node,
1808 word_type const& lhs,
1809 word_type const& rhs);
1810
1842 template <typename Node, typename Iterator1, typename Iterator2>
1843 [[nodiscard]] bool is_complete_no_checks(WordGraph<Node> const& wg,
1844 Iterator1 first_node,
1845 Iterator2 last_node);
1846
1876 template <typename Node, typename Iterator1, typename Iterator2>
1877 [[nodiscard]] bool is_complete(WordGraph<Node> const& wg,
1878 Iterator1 first_node,
1879 Iterator2 last_node);
1880
1898 template <typename Node>
1899 [[nodiscard]] bool is_complete(WordGraph<Node> const& wg) noexcept {
1900 return wg.number_of_edges() == wg.number_of_nodes() * wg.out_degree();
1901 }
1902
1924 template <typename Node>
1925 [[nodiscard]] bool is_connected(WordGraph<Node> const& wg);
1926
1976 template <typename Node1, typename Node2>
1977 [[nodiscard]] bool is_reachable_no_checks(WordGraph<Node1> const& wg,
1978 Node2 source,
1979 Node2 target);
1980
2012 template <typename Node1, typename Node2>
2013 [[nodiscard]] bool is_reachable(WordGraph<Node1> const& wg,
2014 Node2 source,
2015 Node2 target);
2016
2048 // TODO(1) should have a version that returns the node that everything is
2049 // reachable from
2050 template <typename Node>
2051 [[nodiscard]] bool is_strictly_cyclic(WordGraph<Node> const& wg);
2052
2079 template <typename Node1, typename Node2, typename Iterator>
2080 [[nodiscard]] std::pair<Node1, Iterator>
2082 Node2 source,
2083 Iterator first,
2084 Iterator last) noexcept;
2085
2111 template <typename Node1, typename Node2, typename Iterator>
2112 [[nodiscard]] std::pair<Node1, Iterator>
2114 Node2 source,
2115 Iterator first,
2116 Iterator last);
2117
2139 template <typename Node1, typename Node2>
2142 Node2 source,
2143 word_type const& w);
2144
2166 template <typename Node1, typename Node2>
2169 Node2 source,
2170 word_type const& w);
2171
2192 // TODO(1) tests
2193 // TODO(1) version where std::unordered_set is passed by reference, or make
2194 // this a class that stores its stack and unordered_set, not clear why we'd
2195 // single out the unordered_set to be passed by reference.
2196 // TODO(2) version which is an iterator i.e. returns an iterator or range
2197 // object that allows use to step through the nodes reachable from a given
2198 // node
2199 template <typename Node1, typename Node2>
2200 [[nodiscard]] std::unordered_set<Node1>
2201 nodes_reachable_from(WordGraph<Node1> const& wg, Node2 source);
2202
2223 template <typename Node1, typename Node2>
2224 [[nodiscard]] std::unordered_set<Node1>
2225 ancestors_of(WordGraph<Node1> const& wg, Node2 target);
2226
2248 template <typename Node1, typename Node2>
2249 [[nodiscard]] std::unordered_set<Node1>
2251
2273 template <typename Node1, typename Node2>
2274 [[nodiscard]] std::unordered_set<Node1>
2276
2297 template <typename Node1, typename Node2>
2298 [[nodiscard]] size_t
2300 return nodes_reachable_from(wg, source).size();
2301 }
2302
2321 template <typename Node1, typename Node2>
2322 [[nodiscard]] size_t
2324 Node2 source) {
2325 return nodes_reachable_from_no_checks(wg, source).size();
2326 }
2327
2349 template <typename Node>
2350 WordGraph<Node> random_acyclic(size_t number_of_nodes,
2351 size_t out_degree,
2352 std::mt19937 mt
2354
2374 template <typename Node1, typename Node2>
2376 Node2 root,
2377 Forest& f);
2378
2397 template <typename Node1, typename Node2>
2398 void spanning_tree(WordGraph<Node1> const& wg, Node2 root, Forest& f);
2399
2420 template <typename Node1, typename Node2>
2422 Node2 root);
2423
2443 template <typename Node1, typename Node2>
2444 [[nodiscard]] Forest spanning_tree(WordGraph<Node1> const& wg, Node2 root);
2445
2469 // Not nodiscard because sometimes we just don't want the output
2470 template <typename Graph>
2471 bool standardize(Graph& wg, Forest& f, Order val);
2472
2496 // Not nodiscard because sometimes we just don't want the output
2497 template <typename Graph>
2499
2516 template <typename Node>
2518 Order val = Order::shortlex);
2519
2533 template <typename Node>
2535
2557 template <typename Node, typename Iterator>
2559 Iterator first,
2560 Iterator last);
2561
2573 // not noexcept because it throws an exception!
2574 template <typename Node>
2576 typename WordGraph<Node>::label_type a);
2577
2590 template <typename Node>
2592 word_type const& word);
2593
2609 template <typename Node, typename Iterator>
2611 Iterator first,
2612 Iterator last);
2613
2626 // not noexcept because it throws an exception!
2627 template <typename Node1, typename Node2>
2629
2645 // not noexcept because it throws an exception!
2646 template <typename Node, typename Iterator1, typename Iterator2>
2648 Iterator1 first,
2649 Iterator2 last);
2650
2674 template <typename Node>
2676
2703 template <typename Node1, typename Node2>
2704 [[nodiscard]] std::vector<Node1>
2705 topological_sort(WordGraph<Node1> const& wg, Node2 source);
2706
2707 } // namespace word_graph
2708
2710 // WordGraph - non-member functions
2712
2722 template <typename Thing>
2723 static constexpr bool IsWordGraph [[deprecated]]
2725
2745 template <typename Node>
2747
2758
2787 // Passing the 2nd parameter "targets" by value disambiguates it from the
2788 // other make<WordGraph>.
2789 template <typename Return>
2790 [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
2791 Return>
2792 make(size_t num_nodes,
2794
2797 // clang-format off
2799 // clang-format on
2800 template <typename Return>
2801 [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
2802 Return>
2803 make(size_t num_nodes,
2805
2806 namespace detail {
2807 template <typename Subclass>
2808 class JoinerMeeterCommon {
2809 private:
2810 template <typename Node1, typename Node2>
2811 void throw_if_bad_args(WordGraph<Node1> const& x,
2812 Node2 xroot,
2813 WordGraph<Node1> const& y,
2814 Node2 yroot);
2815
2816 public:
2817 template <typename Node>
2818 void call_no_checks(WordGraph<Node>& xy,
2819 WordGraph<Node> const& x,
2820 Node xroot,
2821 WordGraph<Node> const& y,
2822 Node yroot);
2823
2824 template <typename Node>
2825 void call_no_checks(WordGraph<Node>& xy,
2826 WordGraph<Node> const& x,
2827 WordGraph<Node> const& y) {
2828 return call_no_checks(
2829 xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
2830 }
2831
2832 template <typename Node, typename... Args>
2833 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x,
2834 Args&&... args)
2835 -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
2836 // The versions of this function changing the 1st argument in-place
2837 // always have an odd number of arguments, so we check that it's even
2838 // here (the argument x and an odd number of further arguments).
2839 WordGraph<Node> xy;
2840 static_cast<Subclass&>(*this).call_no_checks(
2841 xy, x, std::forward<Args>(args)...);
2842 return xy;
2843 }
2844
2845 // There's no operator() with the number of nodes reachable from the
2846 // roots as arguments (7 args in total) because we'd have to check that
2847 // they were valid, and the only way to do this is to recompute them.
2848
2849 template <typename Node>
2850 void operator()(WordGraph<Node>& xy,
2851 WordGraph<Node> const& x,
2852 Node xroot,
2853 WordGraph<Node> const& y,
2854 Node yroot) {
2855 throw_if_bad_args(x, xroot, y, yroot);
2856 call_no_checks(xy, x, xroot, y, yroot);
2857 }
2858
2859 template <typename Node>
2860 void operator()(WordGraph<Node>& xy,
2861 WordGraph<Node> const& x,
2862 WordGraph<Node> const& y) {
2863 return operator()(xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
2864 }
2865
2866 template <typename Node, typename... Args>
2867 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args)
2868 -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
2869 // The versions of this function changing the 1st argument in-place
2870 // always have an odd number of arguments, so we check that it's even
2871 // here (the argument x and an odd number of further arguments).
2872 WordGraph<Node> xy;
2873 operator()(xy, x, std::forward<Args>(args)...);
2874 return xy;
2875 }
2876
2877 template <typename Node1, typename Node2>
2878 bool is_subrelation_no_checks(WordGraph<Node1> const& x,
2879 Node2 xroot,
2880 WordGraph<Node1> const& y,
2881 Node2 yroot);
2882
2883 template <typename Node>
2884 bool is_subrelation_no_checks(WordGraph<Node> const& x,
2885 WordGraph<Node> const& y) {
2886 return is_subrelation_no_checks(
2887 x, static_cast<Node>(0), y, static_cast<Node>(0));
2888 }
2889
2890 // There's no subrelation with the number of nodes reachable from the
2891 // roots as arguments (6 args in total) because we'd have to check that
2892 // they were valid, and the only way to do this is to recompute them.
2893
2894 template <typename Node1, typename Node2>
2895 bool is_subrelation(WordGraph<Node1> const& x,
2896 Node2 xroot,
2897 WordGraph<Node1> const& y,
2898 Node2 yroot) {
2899 throw_if_bad_args(x, xroot, y, yroot);
2900 return is_subrelation_no_checks(x, xroot, y, yroot);
2901 }
2902
2903 template <typename Node>
2904 bool is_subrelation(WordGraph<Node> const& x, WordGraph<Node> const& y) {
2905 return is_subrelation(x, static_cast<Node>(0), y, static_cast<Node>(0));
2906 }
2907 }; // JoinerMeeterCommon
2908 } // namespace detail
2909
2921 // This class is intentionally not a template so that we don't have to
2922 // specify the types of the nodes when constructing one of these objects.
2923 // Instead every member function has a template parameter Node, which is
2924 // deduced from the argument.
2925 class Joiner : public detail::JoinerMeeterCommon<Joiner> {
2926 private:
2927 detail::Duf<> _uf;
2929 std::vector<uint64_t> _lookup;
2930
2931 template <typename Node>
2932 [[nodiscard]] Node find(WordGraph<Node> const& x,
2933 size_t xnum_nodes_reachable_from_root,
2934 WordGraph<Node> const& y,
2935 uint64_t n,
2936 typename WordGraph<Node>::label_type a) const;
2937
2938 template <typename Node>
2939 void run(WordGraph<Node> const& x,
2940 size_t xnum_nodes_reachable_from_root,
2941 Node xroot,
2942 WordGraph<Node> const& y,
2943 size_t ynum_nodes_reachable_from_root,
2944 Node yroot);
2945
2946 public:
2951
2956
2961
2966
2971
2972 ~Joiner();
2973
3002 template <typename Node>
3004 WordGraph<Node> const& x,
3005 size_t xnum_nodes_reachable_from_root,
3006 Node xroot,
3007 WordGraph<Node> const& y,
3008 size_t ynum_nodes_reachable_from_root,
3009 Node yroot);
3010
3044 // Is x a subrelation of y?
3045 template <typename Node1, typename Node2>
3046 [[nodiscard]] bool
3048 size_t xnum_nodes_reachable_from_root,
3049 Node2 xroot,
3050 WordGraph<Node1> const& y,
3051 size_t ynum_nodes_reachable_from_root,
3052 Node2 yroot);
3053#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3077 template <typename Node>
3079 WordGraph<Node> const& x,
3080 Node xroot,
3081 WordGraph<Node> const& y,
3082 Node yroot);
3083
3103 template <typename Node>
3105 WordGraph<Node> const& x,
3106 WordGraph<Node> const& y);
3107
3127 template <typename Node, typename... Args>
3128 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);
3129
3155 template <typename Node>
3157 WordGraph<Node> const& x,
3158 Node xroot,
3159 WordGraph<Node> const& y,
3160 Node yroot);
3161
3183 template <typename Node>
3185 WordGraph<Node> const& x,
3186 WordGraph<Node> const& y);
3187
3205 template <typename Node, typename... Args>
3206 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);
3207
3237 // Is x a subrelation of y?
3238 template <typename Node1, typename Node2>
3240 Node2 xroot,
3241 WordGraph<Node1> const& y,
3242 Node2 yroot);
3243
3266 template <typename Node>
3268 WordGraph<Node> const& y);
3269
3270 // There's no subrelation with the number of nodes reachable from the
3271 // roots as arguments (6 args in total) because we'd have to check that
3272 // they were valid, and the only way to do this is to recompute them.
3273
3302 template <typename Node1, typename Node2>
3304 Node2 xroot,
3305 WordGraph<Node1> const& y,
3306 Node2 yroot);
3307
3332 template <typename Node>
3334
3335#else
3336 using detail::JoinerMeeterCommon<Joiner>::call_no_checks;
3337 using detail::JoinerMeeterCommon<Joiner>::operator();
3338 using detail::JoinerMeeterCommon<Joiner>::is_subrelation_no_checks;
3339 using detail::JoinerMeeterCommon<Joiner>::is_subrelation;
3340#endif
3341 }; // Joiner
3342
3355 // Class for forming the meet of two word graphs
3356 class Meeter : public detail::JoinerMeeterCommon<Meeter> {
3357 private:
3358 using node_type = std::pair<uint64_t, uint64_t>;
3359
3362 std::vector<node_type> _todo_new;
3363
3364 public:
3369
3374
3379
3384
3389
3390 ~Meeter();
3391
3394 template <typename Node>
3396 WordGraph<Node> const& x,
3397 size_t xnum_nodes_reachable_from_root,
3398 Node xroot,
3399 WordGraph<Node> const& y,
3400 size_t ynum_nodes_reachable_from_root,
3401 Node yroot);
3402
3405 // is x a subrelation of y
3406 template <typename Node1, typename Node2>
3407 [[nodiscard]] bool
3409 size_t xnum_nodes_reachable_from_root,
3410 Node2 xroot,
3411 WordGraph<Node1> const& y,
3412 size_t ynum_nodes_reachable_from_root,
3413 Node2 yroot);
3414
3415#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3418 template <typename Node>
3420 WordGraph<Node> const& x,
3421 Node xroot,
3422 WordGraph<Node> const& y,
3423 Node yroot);
3424
3427 template <typename Node>
3429 WordGraph<Node> const& x,
3430 WordGraph<Node> const& y);
3431
3451 template <typename Node, typename... Args>
3452 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);
3453
3456 template <typename Node>
3458 WordGraph<Node> const& x,
3459 Node xroot,
3460 WordGraph<Node> const& y,
3461 Node yroot);
3462
3465 template <typename Node>
3467 WordGraph<Node> const& x,
3468 WordGraph<Node> const& y);
3469
3487 template <typename Node, typename... Args>
3488 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);
3489
3492 template <typename Node1, typename Node2>
3494 Node2 xroot,
3495 WordGraph<Node1> const& y,
3496 Node2 yroot);
3497
3500 template <typename Node>
3502 WordGraph<Node> const& y);
3503
3506 template <typename Node1, typename Node2>
3508 Node2 xroot,
3509 WordGraph<Node1> const& y,
3510 Node2 yroot);
3511
3514 template <typename Node>
3516#else
3517 using detail::JoinerMeeterCommon<Meeter>::call_no_checks;
3518 using detail::JoinerMeeterCommon<Meeter>::operator();
3519 using detail::JoinerMeeterCommon<Meeter>::is_subrelation_no_checks;
3520 using detail::JoinerMeeterCommon<Meeter>::is_subrelation;
3521#endif
3522 }; // class Meeter
3523
3538 template <typename Node>
3540
3553 [[nodiscard]] static inline std::string
3555 (void) meet;
3556 return "<Meeter of word graphs>";
3557 }
3558
3571 [[nodiscard]] static inline std::string
3573 (void) join;
3574 return "<Joiner of word graphs>";
3575 }
3576
3596 template <typename Node>
3598 std::string const& prefix = "",
3599 std::string const& braces = "{}",
3600 std::string const& suffix = "");
3601} // namespace libsemigroups
3602
3603#include "word-graph.tpp"
3604
3605#endif // LIBSEMIGROUPS_WORD_GRAPH_HPP_
T cbegin(T... args)
A representation of a graph in the DOT language of Graphviz.
Definition dot.hpp:115
Class representing a collection of spanning trees of a word graph.
Definition forest.hpp:42
Class for taking joins of word graphs.
Definition word-graph.hpp:2925
bool is_subrelation_no_checks(WordGraph< Node > const &x, WordGraph< Node > const &y)
Check if the language accepted by one word graph is contained in that defined by another word graph.
auto call_no_checks(WordGraph< Node > const &x, Args &&... args)
Returns a word graph containing the join/meet of two given word graphs.
auto operator()(WordGraph< Node > const &x, Args &&... args)
Returns a word graph containing the join/meet of two given word graphs.
Joiner(Joiner const &)
Default copy constructor.
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
bool is_subrelation(WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
Check if the language accepted by one word graph is contained in that defined by another word graph.
Joiner(Joiner &&)
Default move constructor.
bool is_subrelation_no_checks(WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
Check if the language accepted by one word graph is contained in that defined by another word graph.
Joiner()
Default constructor.
Joiner & operator=(Joiner const &)
Default copy assignment operator.
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Joiner & operator=(Joiner &&)
Default move assignment operator.
bool is_subrelation(WordGraph< Node > const &x, WordGraph< Node > const &y)
Check if the language accepted by one word graph is contained in that defined by another word graph.
void operator()(WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, size_t xnum_nodes_reachable_from_root, Node xroot, WordGraph< Node > const &y, size_t ynum_nodes_reachable_from_root, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
bool is_subrelation_no_checks(WordGraph< Node1 > const &x, size_t xnum_nodes_reachable_from_root, Node2 xroot, WordGraph< Node1 > const &y, size_t ynum_nodes_reachable_from_root, Node2 yroot)
Check if the language accepted by one word graph is contained in that accepted by another word graph.
void operator()(WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Class for taking meets of word graphs.
Definition word-graph.hpp:3356
bool is_subrelation_no_checks(WordGraph< Node > const &x, WordGraph< Node > const &y)
Check if the language accepted by one word graph is contained in that defined by another word graph.
auto call_no_checks(WordGraph< Node > const &x, Args &&... args)
Returns a word graph containing the join/meet of two given word graphs.
auto operator()(WordGraph< Node > const &x, Args &&... args)
Returns a word graph containing the join/meet of two given word graphs.
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
bool is_subrelation(WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
Check if the language accepted by one word graph is contained in that defined by another word graph.
bool is_subrelation_no_checks(WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
Check if the language accepted by one word graph is contained in that defined by another word graph.
Meeter & operator=(Meeter const &)
Default copy assignment operator.
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Meeter()
Default constructor.
Meeter & operator=(Meeter &&)
Default move assignment operator.
bool is_subrelation(WordGraph< Node > const &x, WordGraph< Node > const &y)
Check if the language accepted by one word graph is contained in that defined by another word graph.
void operator()(WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Meeter(Meeter &&)
Default move constructor.
void call_no_checks(WordGraph< Node > &xy, WordGraph< Node > const &x, size_t xnum_nodes_reachable_from_root, Node xroot, WordGraph< Node > const &y, size_t ynum_nodes_reachable_from_root, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Meeter(Meeter const &)
Default copy constructor.
bool is_subrelation_no_checks(WordGraph< Node1 > const &x, size_t xnum_nodes_reachable_from_root, Node2 xroot, WordGraph< Node1 > const &y, size_t ynum_nodes_reachable_from_root, Node2 yroot)
Check if the language accepted by one word graph is contained in that accepted by another word graph.
void operator()(WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
Replace the contents of a word graph with the join/meet of two given word graphs with respect to give...
Class for representing word graphs.
Definition word-graph.hpp:83
Eigen::Matrix< double, Eigen::Dynamic, Eigen::Dynamic > adjacency_matrix_type
Definition word-graph.hpp:109
bool operator<(WordGraph const &that) const
Check if a word graph is less than another.
Definition word-graph.hpp:542
element_index_type node_type
Definition word-graph.hpp:99
auto nodes() const noexcept
Returns a range object containing all nodes in a word graph.
Definition word-graph.hpp:969
auto labels_and_targets(node_type source) const
Returns a range object containing pairs consisting of edge labels and target nodes.
const_iterator_nodes cend_nodes() const noexcept
Returns a random access iterator pointing one-past-the-last node of the word graph.
Definition word-graph.hpp:860
WordGraph & disjoint_union_inplace(WordGraph< Node > const &that)
Unites a word graph in-place.
std::pair< label_type, node_type > next_label_and_target_no_checks(node_type s, label_type a) const
Get the next target of an edge incident to a given node that doesn't equal UNDEFINED.
WordGraph & remove_label(label_type a)
Removes a given label from the word graph.
WordGraph & swap_targets(node_type m, node_type n, label_type a)
Swaps the edge with specified label from one node with another.
size_type number_of_edges() const
Returns the number of edges.
bool operator>(WordGraph const &that) const
Check if a word graph is greater than another.
Definition word-graph.hpp:582
const_iterator_targets cbegin_targets_no_checks(node_type source) const noexcept
Returns a random access iterator pointing at the target of the edge with label 0 incident to a given ...
Definition word-graph.hpp:908
element_index_type label_type
Definition word-graph.hpp:102
bool operator<=(WordGraph const &that) const
Check if a word graph is less than or equal to another.
Definition word-graph.hpp:562
auto labels_and_targets_no_checks(node_type source) const noexcept
Returns a range object containing pairs consisting of edge labels and target nodes.
Definition word-graph.hpp:1043
WordGraph & induced_subgraph(node_type first, node_type last)
Modify in-place to contain the subgraph induced by a range of nodes.
rx::iterator_range< const_iterator_targets > targets_no_checks(node_type source) const noexcept
Returns a range object containing all the targets of edges with a given source.
Definition word-graph.hpp:1005
WordGraph & remove_all_targets()
Remove all of the edges in the word graph.
Definition word-graph.hpp:439
const_iterator_targets cbegin_targets(node_type source) const
Returns a random access iterator pointing at the target of the edge with label 0 incident to a given ...
WordGraph & disjoint_union_inplace_no_checks(WordGraph< Node > const &that)
Unites a word graph in-place.
WordGraph & remove_target(node_type s, label_type a)
Remove an edge from a node with a given label.
WordGraph & swap_targets_no_checks(node_type m, node_type n, label_type a)
Swaps the edge with specified label from one node with another.
Definition word-graph.hpp:464
bool operator>=(WordGraph const &that) const
Check if a word graph is greater than or equal to another.
Definition word-graph.hpp:602
bool operator!=(WordGraph const &that) const
Check if two word graphs are inequal.
Definition word-graph.hpp:522
auto labels() const noexcept
Returns a range object containing all labels of edges in a word graph.
Definition word-graph.hpp:983
WordGraph & reserve(size_type m, size_type n)
Ensures that the word graph has capacity for a given number of nodes, and out-degree.
const_iterator_targets cend_targets_no_checks(node_type source) const noexcept
Returns a random access iterator pointing one beyond the target of the edge with label out_degree() -...
Definition word-graph.hpp:956
size_type out_degree() const noexcept
Definition word-graph.hpp:824
const_iterator_nodes cbegin_nodes() const noexcept
Returns a random access iterator pointing at the first node of the word graph.
Definition word-graph.hpp:842
bool operator==(WordGraph const &that) const
Check if two word graphs are equal.
Definition word-graph.hpp:502
typename detail::DynamicArray2< element_index_type >::const_iterator const_iterator_targets
Definition word-graph.hpp:124
rx::iterator_range< const_iterator_targets > targets(node_type source) const
Returns a range object containing all the targets of edges with a given source.
WordGraph & operator=(WordGraph const &)
Default copy assignment constructor.
WordGraph & target(node_type s, label_type a, node_type t)
Add an edge from one node to another with a given label.
WordGraph & add_nodes(size_type nr)
Add a number of new nodes.
WordGraph & target_no_checks(node_type s, label_type a, node_type t)
Add an edge from one node to another with a given label.
Definition word-graph.hpp:356
const_iterator_targets cend_targets(node_type source) const
Returns a random access iterator pointing one beyond the target of the edge with label out_degree() -...
WordGraph & init(size_type m=0, size_type n=0)
Re-initialize the word graph to have m nodes and out-degree n.
WordGraph & remove_target_no_checks(node_type s, label_type a)
Remove an edge from a node with a given label.
Definition word-graph.hpp:378
std::pair< label_type, node_type > next_label_and_target(node_type s, label_type a) const
Get the next target of an edge incident to a given node that doesn't equal UNDEFINED.
typename detail::IntRange< element_index_type >::const_reverse_iterator const_reverse_iterator_nodes
Definition word-graph.hpp:120
WordGraph & remove_label_no_checks(label_type a)
Removes a given label from the word graph.
WordGraph & add_to_out_degree(size_type nr)
Add to the out-degree of every node.
static WordGraph random(size_type number_of_nodes, size_type out_degree, std::mt19937 mt=std::mt19937(std::random_device()()))
Construct a random word graph from number of nodes and out-degree.
size_t hash_value() const
Returns a hash value.
Definition word-graph.hpp:617
size_type number_of_nodes() const noexcept
Definition word-graph.hpp:748
typename detail::IntRange< element_index_type >::const_iterator const_iterator_nodes
Definition word-graph.hpp:116
std::size_t size_type
Definition word-graph.hpp:105
WordGraph & induced_subgraph_no_checks(node_type first, node_type last)
Modify in-place to contain the subgraph induced by a range of nodes.
size_type number_of_edges_no_checks(node_type s) const
Returns the number of edges with given source node.
T cend(T... args)
T fill(T... args)
T forward(T... args)
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
std::ostringstream & operator<<(std::ostringstream &os, BMat8 const &x)
Insertion operator.
Undefined const UNDEFINED
Value for something undefined.
std::conditional_t< R==0||C==0, DynamicIntMat< Scalar >, StaticIntMat< R, C, Scalar > > IntMat
Alias template for integer matrices.
Definition matrix.hpp:4290
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:790
std::string to_input_string(Transf< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}")
Return a string that can be used to recreate a transformation.
constexpr bool is_specialization_of_v
Helper variable template for is_specialization_of.
Definition is_specialization_of.hpp:83
std::vector< letter_type > word_type
Type for a word over the generators of a semigroup.
Definition types.hpp:99
Order
The possible orderings of words and strings.
Definition order.hpp:45
@ shortlex
Definition order.hpp:51
static constexpr bool IsWordGraph
Helper variable template.
Definition word-graph.hpp:2724
Namespace containing helper functions for the WordGraph class.
Definition word-graph.hpp:1222
auto adjacency_matrix(WordGraph< Node > const &wg)
Returns the adjacency matrix of a word graph.
void spanning_tree_no_checks(WordGraph< Node1 > const &wg, Node2 root, Forest &f)
Replace the contents of a Forest by a spanning tree of the nodes reachable from a given node in a wor...
void throw_if_any_target_out_of_bounds(WordGraph< Node > const &wg)
Throws if the target of any edge is out of bounds.
std::unordered_set< Node1 > ancestors_of_no_checks(WordGraph< Node1 > const &wg, Node2 target)
Returns the std::unordered_set of nodes that can reach a given node in a word graph.
void throw_if_node_out_of_bounds(WordGraph< Node1 > const &wg, Node2 n)
Throws if a node is out of bounds.
std::pair< Node1, Iterator > last_node_on_path(WordGraph< Node1 > const &wg, Node2 source, Iterator first, Iterator last)
Returns the last node on the path labelled by a word and an iterator to the position in the word reac...
bool is_strictly_cyclic(WordGraph< Node > const &wg)
Check if every node is reachable from some node.
std::unordered_set< Node1 > nodes_reachable_from(WordGraph< Node1 > const &wg, Node2 source)
Returns the std::unordered_set of nodes reachable from a given node in a word graph.
bool is_connected(WordGraph< Node > const &wg)
Check if a word graph is connected.
bool equal_to_no_checks(WordGraph< Node > const &x, WordGraph< Node > const &y, Node first, Node last)
Compares two word graphs on a range of nodes.
bool equal_to(WordGraph< Node > const &x, WordGraph< Node > const &y, Node first, Node last)
Compares two word graphs on a range of nodes.
size_t number_of_nodes_reachable_from(WordGraph< Node1 > const &wg, Node2 source)
Returns the number of nodes reachable from a given node in a word graph.
Definition word-graph.hpp:2299
bool is_reachable(WordGraph< Node1 > const &wg, Node2 source, Node2 target)
Check if there is a path from one node to another.
bool is_compatible(WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node, Iterator3 first_rule, Iterator3 last_rule)
Check if a word graph is compatible with some relations at a range of nodes.
std::vector< Node > topological_sort(WordGraph< Node > const &wg)
Returns the nodes of the word graph in topological order (see below) if possible.
bool is_complete(WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node)
Check if every node in a range has exactly WordGraph::out_degree out-edges.
std::pair< Node1, Iterator > last_node_on_path_no_checks(WordGraph< Node1 > const &wg, Node2 source, Iterator first, Iterator last) noexcept
Returns the last node on the path labelled by a word and an iterator to the position in the word reac...
std::unordered_set< Node1 > nodes_reachable_from_no_checks(WordGraph< Node1 > const &wg, Node2 source)
Returns the std::unordered_set of nodes reachable from a given node in a word graph.
std::unordered_set< Node1 > ancestors_of(WordGraph< Node1 > const &wg, Node2 target)
Returns the std::unordered_set of nodes that can reach a given node in a word graph.
WordGraph< Node > random_acyclic(size_t number_of_nodes, size_t out_degree, std::mt19937 mt=std::mt19937(std::random_device()()))
Construct a random connected acyclic word graph with given number of nodes, and out-degree.
void throw_if_label_out_of_bounds(WordGraph< Node > const &wg, typename WordGraph< Node >::label_type a)
Throws if a label is out of bounds.
void add_cycle(WordGraph< Node > &wg, size_t N)
Adds a cycle consisting of N new nodes.
Definition word-graph.hpp:1272
bool is_compatible_no_checks(WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node, Iterator3 first_rule, Iterator3 last_rule)
Check if a word graph is compatible with some relations at a range of nodes.
bool is_reachable_no_checks(WordGraph< Node1 > const &wg, Node2 source, Node2 target)
Check if there is a path from one node to another.
bool standardize(Graph &wg, Forest &f, Order val)
Standardizes a word graph in-place.
size_t number_of_nodes_reachable_from_no_checks(WordGraph< Node1 > const &wg, Node2 source)
Returns the number of nodes reachable from a given node in a word graph.
Definition word-graph.hpp:2323
bool is_complete_no_checks(WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node)
Check if every node in a range has exactly WordGraph::out_degree out-edges.
Node1 follow_path_no_checks(WordGraph< Node1 > const &wg, Node2 from, Iterator first, Iterator last) noexcept
Follow the path from a specified node labelled by a word.
bool is_standardized(WordGraph< Node > const &wg, Order val=Order::shortlex)
Check if a word graph is standardized.
bool is_acyclic(WordGraph< Node > const &wg)
Check if a word graph is acyclic.
void spanning_tree(WordGraph< Node1 > const &wg, Node2 root, Forest &f)
Replace the contents of a Forest by a spanning tree of the nodes reachable from a given node in a wor...
Node1 follow_path(WordGraph< Node1 > const &wg, Node2 source, Iterator first, Iterator last)
Find the node that a path starting at a given node leads to (if any).
void add_cycle_no_checks(WordGraph< Node > &wg, Iterator first, Iterator last)
Adds a cycle involving the specified range of nodes to a word graph.
Dot dot(WordGraph< Node > const &wg)
Returns a Dot object representing a word graph.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T size(T... args)