libsemigroups  v3.1.2
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>
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 "order.hpp" // for Order
46#include "ranges.hpp" // for ??
47#include "types.hpp" // for word_type, enable_if_is_same
48
49#include "detail/containers.hpp" // for DynamicArray2
50#include "detail/int-range.hpp" // for IntRange
51#include "detail/stl.hpp" // for IsIterator
52#include "detail/uf.hpp" // for Duf
53
54#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
55#include "detail/eigen.hpp"
56#else
57#include "matrix.hpp"
58#endif
59
60namespace libsemigroups {
61
66
81 template <typename Node>
82 class WordGraph {
83 static_assert(std::is_integral<Node>(),
84 "the template parameter Node must be an integral type!");
85 static_assert(
87 "the template parameter Node must be an unsigned integral type!");
88
89 template <typename N>
90 friend class WordGraph;
91
92 public:
94 // WordGraph - typedefs - public
96
98 using node_type = Node;
99
101 using label_type = Node;
102
105
106#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
109 = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>;
110#else
113#endif
114
117 typename detail::IntRange<Node>::const_iterator;
118
121 typename detail::IntRange<Node>::const_reverse_iterator;
122
125 typename detail::DynamicArray2<Node>::const_iterator;
126
128 // WordGraph - constructors + destructor - public
130
146 // Not noexcept
147 explicit WordGraph(size_type m = 0, size_type n = 0);
148
167 WordGraph& init(size_type m = 0, size_type n = 0);
168
170 WordGraph(WordGraph const&);
171
181 template <typename OtherNode>
182 WordGraph(WordGraph<OtherNode> const& that);
183
204 template <typename OtherNode>
205 WordGraph& init(WordGraph<OtherNode> const& that);
206
208 WordGraph(WordGraph&&);
209
211 WordGraph& operator=(WordGraph const&);
212
214 WordGraph& operator=(WordGraph&&);
215
216 ~WordGraph();
217
238 static WordGraph random(size_type number_of_nodes,
240 std::mt19937 mt
242
266 // Not noexcept because DynamicArray2::add_cols isn't.
267 WordGraph& reserve(size_type m, size_type n);
268
270 // WordGraph - modifiers - public
272
291 // Not noexcept because DynamicArray2::add_rows isn't.
292 WordGraph& add_nodes(size_type nr);
293
313 // Not noexcept because DynamicArray2::add_cols isn't.
314 WordGraph& add_to_out_degree(size_type nr);
315
333 // Not noexcept because throw_if_node_out_of_bounds/label aren't
334 // return *this by reference.
335 WordGraph& target(node_type s, label_type a, node_type t);
336
355 //! No checks whatsoever on the validity of the arguments are performed.
356 inline WordGraph& target_no_checks(node_type s, label_type a, node_type t) {
357 _dynamic_array_2.set(s, a, t);
358 return *this;
359 }
360
377 //! No checks whatsoever on the validity of the arguments are performed.
378 inline WordGraph& remove_target_no_checks(node_type s, label_type a) {
379 _dynamic_array_2.set(s, a, UNDEFINED);
380 return *this;
381 }
382
396 WordGraph& remove_target(node_type s, label_type a);
397
408 WordGraph& remove_label(label_type a);
409
425
438 //! out-degree.
439 inline WordGraph& remove_all_targets() {
440 std::fill(_dynamic_array_2.begin(), _dynamic_array_2.end(), UNDEFINED);
441 return *this;
442 }
443
463 // swap m - a - > m' and n - a -> n'
465 _dynamic_array_2.swap(m, a, n, a);
466 return *this;
467 }
468
484 WordGraph& swap_targets(node_type m, node_type n, label_type a);
485
501 //! is the out-degree of the word graph.
502 [[nodiscard]] bool operator==(WordGraph const& that) const {
503 return _dynamic_array_2 == that._dynamic_array_2;
504 }
505
521 //! is the out-degree of the word graph.
522 [[nodiscard]] bool operator!=(WordGraph const& that) const {
523 return !operator==(that);
524 }
525
541 //! is the out-degree of the word graph.
542 [[nodiscard]] bool operator<(WordGraph const& that) const {
543 return _dynamic_array_2 < that._dynamic_array_2;
544 }
545
561 //! is the out-degree of the word graph.
562 [[nodiscard]] bool operator<=(WordGraph const& that) const {
563 return _dynamic_array_2 <= that._dynamic_array_2;
564 }
565
581 //! is the out-degree of the word graph.
582 [[nodiscard]] bool operator>(WordGraph const& that) const {
583 return _dynamic_array_2 > that._dynamic_array_2;
584 }
585
601 //! is the out-degree of the word graph.
602 [[nodiscard]] bool operator>=(WordGraph const& that) const {
603 return _dynamic_array_2 > that._dynamic_array_2;
604 }
605
616 // not noexcept because Hash<T>::operator() isn't
617 [[nodiscard]] size_t hash_value() const {
618 return std::hash<decltype(_dynamic_array_2)>()(_dynamic_array_2);
619 }
620
622 // WordGraph - nodes, targets, etc - public
624
642 // Not noexcept because throw_if_node_out_of_bounds/label aren't
643 [[nodiscard]] node_type target(node_type source, label_type a) const;
644
664 // Not noexcept because DynamicArray2::get is not
665 [[nodiscard]] node_type inline target_no_checks(node_type s,
666 label_type a) const {
667 return _dynamic_array_2.get(s, a);
668 }
669
698 // Not noexcept because DynamicArray2::get is not
701
732 // Not noexcept because next_label_and_target_no_checks is not
735
747 //! Constant.
748 [[nodiscard]] size_type inline number_of_nodes() const noexcept {
749 return _nr_nodes;
750 }
751
752#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
753 WordGraph& number_of_active_nodes(size_type val) {
754 _num_active_nodes = val;
755 return *this;
756 }
757
758 [[nodiscard]] size_type inline number_of_active_nodes() const noexcept {
759 return _num_active_nodes;
760 }
761#endif
762
776 // Not noexcept because std::count isn't
777 [[nodiscard]] size_type number_of_edges() const;
778
793 [[nodiscard]] size_type number_of_edges(node_type s) const;
794
810 [[nodiscard]] size_type number_of_edges_no_checks(node_type s) const;
811
823 //! Constant.
824 [[nodiscard]] size_type out_degree() const noexcept {
825 return _degree;
826 }
827
841 //! Constant.
842 const_iterator_nodes cbegin_nodes() const noexcept {
843 return detail::IntRange<node_type>(0, number_of_nodes()).cbegin();
844 }
845
859 //! Constant.
860 [[nodiscard]] const_iterator_nodes cend_nodes() const noexcept {
861 return detail::IntRange<node_type>(0, number_of_nodes()).cend();
862 }
863
881 // Not noexcept because throw_if_node_out_of_bounds isn't
882 [[nodiscard]] const_iterator_targets cbegin_targets(node_type source) const;
883
908 cbegin_targets_no_checks(node_type source) const noexcept {
909 return _dynamic_array_2.cbegin_row(source);
910 }
911
929 // Not noexcept because throw_if_node_out_of_bounds isn't
930 [[nodiscard]] const_iterator_targets cend_targets(node_type source) const;
931
956 cend_targets_no_checks(node_type source) const noexcept {
957 return _dynamic_array_2.cbegin_row(source) + _degree;
958 }
959
968 //! \noexcept
969 [[nodiscard]] auto nodes() const noexcept {
970 return rx::seq<node_type>() | rx::take(number_of_nodes());
971 }
972
982 //! \noexcept
983 [[nodiscard]] auto labels() const noexcept {
984 return rx::seq<label_type>() | rx::take(out_degree());
985 }
986
1004 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1005 targets_no_checks(node_type source) const noexcept {
1006 return rx::iterator_range(cbegin_targets_no_checks(source),
1007 cend_targets_no_checks(source));
1008 }
1009
1022 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1023 targets(node_type source) const;
1024
1042 [[nodiscard]] auto
1043 labels_and_targets_no_checks(node_type source) const noexcept {
1044 return rx::zip(rx::seq<node_type>(), targets_no_checks(source));
1045 }
1046
1058 [[nodiscard]] auto labels_and_targets(node_type source) const;
1059
1078 WordGraph& induced_subgraph_no_checks(node_type first, node_type last);
1079
1094 WordGraph& induced_subgraph(node_type first, node_type last);
1095
1118 template <typename Iterator,
1119 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1120 WordGraph& induced_subgraph_no_checks(Iterator first, Iterator last);
1121
1143 template <typename Iterator,
1144 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1145 WordGraph& induced_subgraph(Iterator first, Iterator last);
1146
1162 WordGraph& disjoint_union_inplace_no_checks(WordGraph<Node> const& that);
1163
1176 WordGraph& disjoint_union_inplace(WordGraph<Node> const& that);
1177
1178#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1179 // These are currently undocumented, because they are hard to use correctly,
1180 // shouldn't p and q be actual permutation objects?
1181
1182 // requires access to apply_row_permutation so can't be helper
1183 WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
1184 std::vector<node_type> const& q,
1185 size_t m);
1186
1187 WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
1188 std::vector<node_type> const& q) {
1189 return permute_nodes_no_checks(p, q, p.size());
1190 }
1191#endif
1192
1193 protected:
1194 // from WordGraphWithSources
1195 template <typename S>
1196 void apply_row_permutation(S const& p) {
1197 _dynamic_array_2.apply_row_permutation(p);
1198 }
1199
1200 private:
1202 // WordGraph - data members - private
1204
1205 size_type _degree;
1206 size_type _nr_nodes;
1207 // TODO(1) remove when WordGraphView is implemented
1208 size_type _num_active_nodes;
1209 mutable detail::DynamicArray2<Node> _dynamic_array_2;
1210 };
1211
1221 namespace word_graph {
1222
1224 // WordGraph - helper functions - in alphabetical order!!!
1226
1249 // TODO(1) add add_cycle with checks version.
1250 template <typename Node, typename Iterator>
1252 Iterator first,
1253 Iterator last);
1254
1270 template <typename Node>
1271 void add_cycle(WordGraph<Node>& wg, size_t N) {
1272 size_t M = wg.number_of_nodes();
1273 wg.add_nodes(N);
1274 add_cycle_no_checks(wg, wg.cbegin_nodes() + M, wg.cend_nodes());
1275 }
1276
1291 template <typename Node>
1292 [[nodiscard]] auto adjacency_matrix(WordGraph<Node> const& wg);
1293
1304 template <typename Node>
1305 [[nodiscard]] Dot dot(WordGraph<Node> const& wg);
1306
1333 template <typename Node>
1334 [[nodiscard]] bool equal_to_no_checks(WordGraph<Node> const& x,
1335 WordGraph<Node> const& y,
1336 Node first,
1337 Node last);
1338
1363 template <typename Node>
1364 [[nodiscard]] bool equal_to(WordGraph<Node> const& x,
1365 WordGraph<Node> const& y,
1366 Node first,
1367 Node last);
1368
1400 template <typename Node1, typename Node2, typename Iterator>
1401 [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
1402 Node2 source,
1403 Iterator first,
1404 Iterator last);
1405
1433 // TODO(2) example
1434 // not noexcept because WordGraph::target isn't
1435 template <typename Node1, typename Node2>
1436 [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
1437 Node2 from,
1438 word_type const& path) {
1439 static_assert(sizeof(Node2) <= sizeof(Node1));
1440 return follow_path(wg, from, path.cbegin(), path.cend());
1441 }
1442
1469 template <typename Node1, typename Node2, typename Iterator>
1470 [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
1471 Node2 from,
1472 Iterator first,
1473 Iterator last) noexcept;
1474
1501 template <typename Node1, typename Node2>
1502 [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
1503 Node2 from,
1504 word_type const& path) noexcept {
1505 static_assert(sizeof(Node2) <= sizeof(Node1));
1506 return follow_path_no_checks(wg, from, path.cbegin(), path.cend());
1507 }
1508
1541 // Not noexcept because detail::is_acyclic isn't
1542 template <typename Node>
1543 [[nodiscard]] bool is_acyclic(WordGraph<Node> const& wg);
1544
1589 // Not noexcept because detail::is_acyclic isn't
1590 template <typename Node1, typename Node2>
1591 [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg, Node2 source);
1592
1622 // Not noexcept because detail::is_acyclic isn't
1623 template <typename Node1, typename Node2>
1624 [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg,
1625 Node2 source,
1626 Node2 target);
1627
1667 template <typename Node,
1668 typename Iterator1,
1669 typename Iterator2,
1670 typename Iterator3>
1671 [[nodiscard]] bool is_compatible_no_checks(WordGraph<Node> const& wg,
1672 Iterator1 first_node,
1673 Iterator2 last_node,
1674 Iterator3 first_rule,
1675 Iterator3 last_rule);
1676
1718 template <
1719 typename Node,
1720 typename Iterator1,
1721 typename Iterator2,
1722 typename Iterator3,
1723 std::enable_if_t<!std::is_same_v<std::decay_t<Iterator3>, word_type>>>
1724 [[nodiscard]] bool is_compatible(WordGraph<Node> const& wg,
1725 Iterator1 first_node,
1726 Iterator2 last_node,
1727 Iterator3 first_rule,
1728 Iterator3 last_rule);
1729
1761 template <typename Node, typename Iterator1, typename Iterator2>
1763 Iterator1 first_node,
1764 Iterator2 last_node,
1765 word_type const& lhs,
1766 word_type const& rhs);
1767
1803 template <typename Node, typename Iterator1, typename Iterator2>
1805 Iterator1 first_node,
1806 Iterator2 last_node,
1807 word_type const& lhs,
1808 word_type const& rhs);
1809
1841 template <typename Node, typename Iterator1, typename Iterator2>
1842 [[nodiscard]] bool is_complete_no_checks(WordGraph<Node> const& wg,
1843 Iterator1 first_node,
1844 Iterator2 last_node);
1845
1875 template <typename Node, typename Iterator1, typename Iterator2>
1876 [[nodiscard]] bool is_complete(WordGraph<Node> const& wg,
1877 Iterator1 first_node,
1878 Iterator2 last_node);
1879
1897 template <typename Node>
1898 [[nodiscard]] bool is_complete(WordGraph<Node> const& wg) noexcept {
1899 return wg.number_of_edges() == wg.number_of_nodes() * wg.out_degree();
1900 }
1901
1923 template <typename Node>
1924 [[nodiscard]] bool is_connected(WordGraph<Node> const& wg);
1925
1975 template <typename Node1, typename Node2>
1976 [[nodiscard]] bool is_reachable_no_checks(WordGraph<Node1> const& wg,
1977 Node2 source,
1978 Node2 target);
1979
2011 template <typename Node1, typename Node2>
2012 [[nodiscard]] bool is_reachable(WordGraph<Node1> const& wg,
2013 Node2 source,
2014 Node2 target);
2015
2047 // TODO(1) should have a version that returns the node that everything is
2048 // reachable from
2049 template <typename Node>
2050 [[nodiscard]] bool is_strictly_cyclic(WordGraph<Node> const& wg);
2051
2078 template <typename Node1, typename Node2, typename Iterator>
2079 [[nodiscard]] std::pair<Node1, Iterator>
2081 Node2 source,
2082 Iterator first,
2083 Iterator last) noexcept;
2084
2110 template <typename Node1, typename Node2, typename Iterator>
2111 [[nodiscard]] std::pair<Node1, Iterator>
2113 Node2 source,
2114 Iterator first,
2115 Iterator last);
2116
2138 template <typename Node1, typename Node2>
2141 Node2 source,
2142 word_type const& w);
2143
2165 template <typename Node1, typename Node2>
2168 Node2 source,
2169 word_type const& w);
2170
2191 // TODO(1) tests
2192 // TODO(1) version where std::unordered_set is passed by reference, or make
2193 // this a class that stores its stack and unordered_set, not clear why we'd
2194 // single out the unordered_set to be passed by reference.
2195 // TODO(2) version which is an iterator i.e. returns an iterator or range
2196 // object that allows use to step through the nodes reachable from a given
2197 // node
2198 template <typename Node1, typename Node2>
2199 [[nodiscard]] std::unordered_set<Node1>
2200 nodes_reachable_from(WordGraph<Node1> const& wg, Node2 source);
2201
2222 template <typename Node1, typename Node2>
2223 [[nodiscard]] std::unordered_set<Node1>
2224 ancestors_of(WordGraph<Node1> const& wg, Node2 target);
2225
2247 template <typename Node1, typename Node2>
2248 [[nodiscard]] std::unordered_set<Node1>
2250
2272 template <typename Node1, typename Node2>
2273 [[nodiscard]] std::unordered_set<Node1>
2275
2296 template <typename Node1, typename Node2>
2297 [[nodiscard]] size_t
2299 return nodes_reachable_from(wg, source).size();
2300 }
2301
2320 template <typename Node1, typename Node2>
2321 [[nodiscard]] size_t
2323 Node2 source) {
2324 return nodes_reachable_from_no_checks(wg, source).size();
2325 }
2326
2348 template <typename Node>
2349 WordGraph<Node> random_acyclic(size_t number_of_nodes,
2350 size_t out_degree,
2351 std::mt19937 mt
2353
2373 template <typename Node1, typename Node2>
2375 Node2 root,
2376 Forest& f);
2377
2396 template <typename Node1, typename Node2>
2397 void spanning_tree(WordGraph<Node1> const& wg, Node2 root, Forest& f);
2398
2419 template <typename Node1, typename Node2>
2421 Node2 root);
2422
2442 template <typename Node1, typename Node2>
2443 [[nodiscard]] Forest spanning_tree(WordGraph<Node1> const& wg, Node2 root);
2444
2468 // Not nodiscard because sometimes we just don't want the output
2469 template <typename Graph>
2470 bool standardize(Graph& wg, Forest& f, Order val);
2471
2495 // Not nodiscard because sometimes we just don't want the output
2496 template <typename Graph>
2498
2515 template <typename Node>
2517 Order val = Order::shortlex);
2518
2532 template <typename Node>
2534
2556 template <typename Node, typename Iterator>
2558 Iterator first,
2559 Iterator last);
2560
2572 // not noexcept because it throws an exception!
2573 template <typename Node>
2575 typename WordGraph<Node>::label_type a);
2576
2589 template <typename Node>
2591 word_type const& word);
2592
2608 template <typename Node, typename Iterator>
2610 Iterator first,
2611 Iterator last);
2612
2625 // not noexcept because it throws an exception!
2626 template <typename Node1, typename Node2>
2628
2644 // not noexcept because it throws an exception!
2645 template <typename Node, typename Iterator1, typename Iterator2>
2647 Iterator1 first,
2648 Iterator2 last);
2649
2673 template <typename Node>
2675
2702 template <typename Node1, typename Node2>
2703 [[nodiscard]] std::vector<Node1>
2704 topological_sort(WordGraph<Node1> const& wg, Node2 source);
2705
2706 } // namespace word_graph
2707
2708 namespace detail {
2709
2710 template <typename T>
2711 struct IsWordGraphHelper : std::false_type {};
2712
2713 template <typename Node>
2714 struct IsWordGraphHelper<WordGraph<Node>> : std::true_type {};
2715 } // namespace detail
2716
2718 // WordGraph - non-member functions
2720
2728 template <typename T>
2729 static constexpr bool IsWordGraph = detail::IsWordGraphHelper<T>::value;
2730
2750 template <typename Node>
2752
2763
2791 // Passing the 2nd parameter "targets" by value disambiguates it from the
2792 // other make<WordGraph>.
2793 template <typename Return>
2794 [[nodiscard]] std::enable_if_t<IsWordGraph<Return>, Return>
2795 make(size_t num_nodes,
2797
2800 // clang-format off
2802 // clang-format on
2803 template <typename Return>
2804 [[nodiscard]] std::enable_if_t<IsWordGraph<Return>, Return>
2805 make(size_t num_nodes,
2807
2808 namespace detail {
2809 template <typename Subclass>
2810 class JoinerMeeterCommon {
2811 private:
2812 template <typename Node1, typename Node2>
2813 void throw_if_bad_args(WordGraph<Node1> const& x,
2814 Node2 xroot,
2815 WordGraph<Node1> const& y,
2816 Node2 yroot);
2817
2818 public:
2819 template <typename Node>
2820 void call_no_checks(WordGraph<Node>& xy,
2821 WordGraph<Node> const& x,
2822 Node xroot,
2823 WordGraph<Node> const& y,
2824 Node yroot);
2825
2826 template <typename Node>
2827 void call_no_checks(WordGraph<Node>& xy,
2828 WordGraph<Node> const& x,
2829 WordGraph<Node> const& y) {
2830 return call_no_checks(
2831 xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
2832 }
2833
2834 template <typename Node, typename... Args>
2835 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x,
2836 Args&&... args)
2837 -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
2838 // The versions of this function changing the 1st argument in-place
2839 // always have an odd number of arguments, so we check that it's even
2840 // here (the argument x and an odd number of further arguments).
2841 WordGraph<Node> xy;
2842 static_cast<Subclass&>(*this).call_no_checks(
2843 xy, x, std::forward<Args>(args)...);
2844 return xy;
2845 }
2846
2847 // There's no operator() with the number of nodes reachable from the
2848 // roots as arguments (7 args in total) because we'd have to check that
2849 // they were valid, and the only way to do this is to recompute them.
2850
2851 template <typename Node>
2852 void operator()(WordGraph<Node>& xy,
2853 WordGraph<Node> const& x,
2854 Node xroot,
2855 WordGraph<Node> const& y,
2856 Node yroot) {
2857 throw_if_bad_args(x, xroot, y, yroot);
2858 call_no_checks(xy, x, xroot, y, yroot);
2859 }
2860
2861 template <typename Node>
2862 void operator()(WordGraph<Node>& xy,
2863 WordGraph<Node> const& x,
2864 WordGraph<Node> const& y) {
2865 return operator()(xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
2866 }
2867
2868 template <typename Node, typename... Args>
2869 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args)
2870 -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
2871 // The versions of this function changing the 1st argument in-place
2872 // always have an odd number of arguments, so we check that it's even
2873 // here (the argument x and an odd number of further arguments).
2874 WordGraph<Node> xy;
2875 operator()(xy, x, std::forward<Args>(args)...);
2876 return xy;
2877 }
2878
2879 template <typename Node1, typename Node2>
2880 bool is_subrelation_no_checks(WordGraph<Node1> const& x,
2881 Node2 xroot,
2882 WordGraph<Node1> const& y,
2883 Node2 yroot);
2884
2885 template <typename Node>
2886 bool is_subrelation_no_checks(WordGraph<Node> const& x,
2887 WordGraph<Node> const& y) {
2888 return is_subrelation_no_checks(
2889 x, static_cast<Node>(0), y, static_cast<Node>(0));
2890 }
2891
2892 // There's no subrelation with the number of nodes reachable from the
2893 // roots as arguments (6 args in total) because we'd have to check that
2894 // they were valid, and the only way to do this is to recompute them.
2895
2896 template <typename Node1, typename Node2>
2897 bool is_subrelation(WordGraph<Node1> const& x,
2898 Node2 xroot,
2899 WordGraph<Node1> const& y,
2900 Node2 yroot) {
2901 throw_if_bad_args(x, xroot, y, yroot);
2902 return is_subrelation_no_checks(x, xroot, y, yroot);
2903 }
2904
2905 template <typename Node>
2906 bool is_subrelation(WordGraph<Node> const& x, WordGraph<Node> const& y) {
2907 return is_subrelation(x, static_cast<Node>(0), y, static_cast<Node>(0));
2908 }
2909 }; // JoinerMeeterCommon
2910 } // namespace detail
2911
2923 // This class is intentionally not a template so that we don't have to
2924 // specify the types of the nodes when constructing one of these objects.
2925 // Instead every member function has a template parameter Node, which is
2926 // deduced from the argument.
2927 class Joiner : public detail::JoinerMeeterCommon<Joiner> {
2928 private:
2929 detail::Duf<> _uf;
2931 std::vector<uint64_t> _lookup;
2932
2933 template <typename Node>
2934 [[nodiscard]] Node find(WordGraph<Node> const& x,
2935 size_t xnum_nodes_reachable_from_root,
2936 WordGraph<Node> const& y,
2937 uint64_t n,
2938 typename WordGraph<Node>::label_type a) const;
2939
2940 template <typename Node>
2941 void run(WordGraph<Node> const& x,
2942 size_t xnum_nodes_reachable_from_root,
2943 Node xroot,
2944 WordGraph<Node> const& y,
2945 size_t ynum_nodes_reachable_from_root,
2946 Node yroot);
2947
2948 public:
2953
2958
2963
2968
2973
2974 ~Joiner();
2975
3004 template <typename Node>
3006 WordGraph<Node> const& x,
3007 size_t xnum_nodes_reachable_from_root,
3008 Node xroot,
3009 WordGraph<Node> const& y,
3010 size_t ynum_nodes_reachable_from_root,
3011 Node yroot);
3012
3046 // Is x a subrelation of y?
3047 template <typename Node1, typename Node2>
3048 [[nodiscard]] bool
3050 size_t xnum_nodes_reachable_from_root,
3051 Node2 xroot,
3052 WordGraph<Node1> const& y,
3053 size_t ynum_nodes_reachable_from_root,
3054 Node2 yroot);
3055#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3079 template <typename Node>
3081 WordGraph<Node> const& x,
3082 Node xroot,
3083 WordGraph<Node> const& y,
3084 Node yroot);
3085
3105 template <typename Node>
3107 WordGraph<Node> const& x,
3108 WordGraph<Node> const& y);
3109
3129 template <typename Node, typename... Args>
3130 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);
3131
3157 template <typename Node>
3159 WordGraph<Node> const& x,
3160 Node xroot,
3161 WordGraph<Node> const& y,
3162 Node yroot);
3163
3185 template <typename Node>
3187 WordGraph<Node> const& x,
3188 WordGraph<Node> const& y);
3189
3207 template <typename Node, typename... Args>
3208 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);
3209
3239 // Is x a subrelation of y?
3240 template <typename Node1, typename Node2>
3242 Node2 xroot,
3243 WordGraph<Node1> const& y,
3244 Node2 yroot);
3245
3268 template <typename Node>
3270 WordGraph<Node> const& y);
3271
3272 // There's no subrelation with the number of nodes reachable from the
3273 // roots as arguments (6 args in total) because we'd have to check that
3274 // they were valid, and the only way to do this is to recompute them.
3275
3304 template <typename Node1, typename Node2>
3306 Node2 xroot,
3307 WordGraph<Node1> const& y,
3308 Node2 yroot);
3309
3334 template <typename Node>
3336
3337#else
3338 using detail::JoinerMeeterCommon<Joiner>::call_no_checks;
3339 using detail::JoinerMeeterCommon<Joiner>::operator();
3340 using detail::JoinerMeeterCommon<Joiner>::is_subrelation_no_checks;
3341 using detail::JoinerMeeterCommon<Joiner>::is_subrelation;
3342#endif
3343 }; // Joiner
3344
3357 // Class for forming the meet of two word graphs
3358 class Meeter : public detail::JoinerMeeterCommon<Meeter> {
3359 private:
3360 using node_type = std::pair<uint64_t, uint64_t>;
3361
3364 std::vector<node_type> _todo_new;
3365
3366 public:
3371
3376
3381
3386
3391
3392 ~Meeter();
3393
3396 template <typename Node>
3398 WordGraph<Node> const& x,
3399 size_t xnum_nodes_reachable_from_root,
3400 Node xroot,
3401 WordGraph<Node> const& y,
3402 size_t ynum_nodes_reachable_from_root,
3403 Node yroot);
3404
3407 // is x a subrelation of y
3408 template <typename Node1, typename Node2>
3409 [[nodiscard]] bool
3411 size_t xnum_nodes_reachable_from_root,
3412 Node2 xroot,
3413 WordGraph<Node1> const& y,
3414 size_t ynum_nodes_reachable_from_root,
3415 Node2 yroot);
3416
3417#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3420 template <typename Node>
3422 WordGraph<Node> const& x,
3423 Node xroot,
3424 WordGraph<Node> const& y,
3425 Node yroot);
3426
3429 template <typename Node>
3431 WordGraph<Node> const& x,
3432 WordGraph<Node> const& y);
3433
3453 template <typename Node, typename... Args>
3454 [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);
3455
3458 template <typename Node>
3460 WordGraph<Node> const& x,
3461 Node xroot,
3462 WordGraph<Node> const& y,
3463 Node yroot);
3464
3467 template <typename Node>
3469 WordGraph<Node> const& x,
3470 WordGraph<Node> const& y);
3471
3489 template <typename Node, typename... Args>
3490 [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);
3491
3494 template <typename Node1, typename Node2>
3496 Node2 xroot,
3497 WordGraph<Node1> const& y,
3498 Node2 yroot);
3499
3502 template <typename Node>
3504 WordGraph<Node> const& y);
3505
3508 template <typename Node1, typename Node2>
3510 Node2 xroot,
3511 WordGraph<Node1> const& y,
3512 Node2 yroot);
3513
3516 template <typename Node>
3518#else
3519 using detail::JoinerMeeterCommon<Meeter>::call_no_checks;
3520 using detail::JoinerMeeterCommon<Meeter>::operator();
3521 using detail::JoinerMeeterCommon<Meeter>::is_subrelation_no_checks;
3522 using detail::JoinerMeeterCommon<Meeter>::is_subrelation;
3523#endif
3524 }; // class Meeter
3525
3540 template <typename Node>
3542
3555 [[nodiscard]] static inline std::string
3557 (void) meet;
3558 return "<Meeter of word graphs>";
3559 }
3560
3573 [[nodiscard]] static inline std::string
3575 (void) join;
3576 return "<Joiner of word graphs>";
3577 }
3578
3598 template <typename Node>
3600 std::string const& prefix = "",
3601 std::string const& braces = "{}",
3602 std::string const& suffix = "");
3603} // namespace libsemigroups
3604
3605#include "word-graph.tpp"
3606
3607#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:2927
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:3358
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:82
Eigen::Matrix< double, Eigen::Dynamic, Eigen::Dynamic > adjacency_matrix_type
Definition word-graph.hpp:108
bool operator<(WordGraph const &that) const
Check if a word graph is less than another.
Definition word-graph.hpp:541
element_index_type node_type
Definition word-graph.hpp:98
auto nodes() const noexcept
Returns a range object containing all nodes in a word graph.
Definition word-graph.hpp:968
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:859
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:581
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:907
element_index_type label_type
Definition word-graph.hpp:101
bool operator<=(WordGraph const &that) const
Check if a word graph is less than or equal to another.
Definition word-graph.hpp:561
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:1042
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:1004
WordGraph & remove_all_targets()
Remove all of the edges in the word graph.
Definition word-graph.hpp:438
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:463
bool operator>=(WordGraph const &that) const
Check if a word graph is greater than or equal to another.
Definition word-graph.hpp:601
bool operator!=(WordGraph const &that) const
Check if two word graphs are inequal.
Definition word-graph.hpp:521
auto labels() const noexcept
Returns a range object containing all labels of edges in a word graph.
Definition word-graph.hpp:982
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:955
size_type out_degree() const noexcept
Definition word-graph.hpp:823
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:841
bool operator==(WordGraph const &that) const
Check if two word graphs are equal.
Definition word-graph.hpp:501
typename detail::DynamicArray2< element_index_type >::const_iterator const_iterator_targets
Definition word-graph.hpp:123
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:355
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:377
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:119
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:616
size_type number_of_nodes() const noexcept
Definition word-graph.hpp:747
typename detail::IntRange< element_index_type >::const_iterator const_iterator_nodes
Definition word-graph.hpp:115
std::size_t size_type
Definition word-graph.hpp:104
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(AhoCorasick const &ac)
Return a string representation.
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:798
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.
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:2729
Namespace containing helper functions for the WordGraph class.
Definition word-graph.hpp:1221
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:2298
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:1271
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:2322
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)