22#ifndef LIBSEMIGROUPS_WORD_GRAPH_HPP_
23#define LIBSEMIGROUPS_WORD_GRAPH_HPP_
35#include <unordered_set>
40#include "constants.hpp"
43#include "exception.hpp"
45#include "is_specialization_of.hpp"
50#include "detail/containers.hpp"
51#include "detail/int-range.hpp"
52#include "detail/stl.hpp"
53#include "detail/uf.hpp"
55#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
56#include "detail/eigen.hpp"
82 template <
typename Node>
85 "the template parameter Node must be an integral type!");
88 "the template parameter Node must be an unsigned integral type!");
91 friend class WordGraph;
107#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
110 = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>;
118 typename detail::IntRange<Node>::const_iterator;
122 typename detail::IntRange<Node>::const_reverse_iterator;
126 typename detail::DynamicArray2<Node>::const_iterator;
171 WordGraph(WordGraph
const&);
182 template <
typename OtherNode>
183 WordGraph(WordGraph<OtherNode>
const& that);
205 template <
typename OtherNode>
206 WordGraph&
init(WordGraph<OtherNode>
const& that);
209 WordGraph(WordGraph&&);
358 _dynamic_array_2.set(s, a, t);
466 _dynamic_array_2.swap(m, a, n, a);
503 [[nodiscard]]
bool operator==(WordGraph
const& that)
const {
504 return _dynamic_array_2 == that._dynamic_array_2;
523 [[nodiscard]]
bool operator!=(WordGraph
const& that)
const {
543 [[nodiscard]]
bool operator<(WordGraph
const& that)
const {
544 return _dynamic_array_2 < that._dynamic_array_2;
563 [[nodiscard]]
bool operator<=(WordGraph
const& that)
const {
564 return _dynamic_array_2 <= that._dynamic_array_2;
583 [[nodiscard]]
bool operator>(WordGraph
const& that)
const {
584 return _dynamic_array_2 > that._dynamic_array_2;
603 [[nodiscard]]
bool operator>=(WordGraph
const& that)
const {
604 return _dynamic_array_2 > that._dynamic_array_2;
668 return _dynamic_array_2.get(s, a);
753#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
755 _num_active_nodes = val;
759 [[nodiscard]]
size_type inline number_of_active_nodes() const noexcept {
760 return _num_active_nodes;
910 return _dynamic_array_2.cbegin_row(source);
958 return _dynamic_array_2.cbegin_row(source) + _degree;
970 [[nodiscard]]
auto nodes() const noexcept {
984 [[nodiscard]]
auto labels() const noexcept {
985 return rx::seq<label_type>() | rx::take(
out_degree());
1005 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1023 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1119 template <
typename Iterator,
1120 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1144 template <
typename Iterator,
1145 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1179#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1190 return permute_nodes_no_checks(p, q, p.
size());
1196 template <
typename S>
1197 void apply_row_permutation(S
const& p) {
1198 _dynamic_array_2.apply_row_permutation(p);
1210 mutable detail::DynamicArray2<Node> _dynamic_array_2;
1251 template <
typename Node,
typename Iterator>
1271 template <
typename Node>
1292 template <
typename Node>
1305 template <
typename Node>
1334 template <
typename Node>
1364 template <
typename Node>
1401 template <
typename Node1,
typename Node2,
typename Iterator>
1436 template <
typename Node1,
typename Node2>
1440 static_assert(
sizeof(Node2) <=
sizeof(Node1));
1470 template <
typename Node1,
typename Node2,
typename Iterator>
1474 Iterator last)
noexcept;
1502 template <
typename Node1,
typename Node2>
1506 static_assert(
sizeof(Node2) <=
sizeof(Node1));
1543 template <
typename Node>
1591 template <
typename Node1,
typename Node2>
1624 template <
typename Node1,
typename Node2>
1668 template <
typename Node,
1673 Iterator1 first_node,
1674 Iterator2 last_node,
1675 Iterator3 first_rule,
1676 Iterator3 last_rule);
1724 std::enable_if_t<!std::is_same_v<std::decay_t<Iterator3>,
word_type>>>
1726 Iterator1 first_node,
1727 Iterator2 last_node,
1728 Iterator3 first_rule,
1729 Iterator3 last_rule);
1762 template <
typename Node,
typename Iterator1,
typename Iterator2>
1764 Iterator1 first_node,
1765 Iterator2 last_node,
1804 template <
typename Node,
typename Iterator1,
typename Iterator2>
1806 Iterator1 first_node,
1807 Iterator2 last_node,
1842 template <
typename Node,
typename Iterator1,
typename Iterator2>
1844 Iterator1 first_node,
1845 Iterator2 last_node);
1876 template <
typename Node,
typename Iterator1,
typename Iterator2>
1878 Iterator1 first_node,
1879 Iterator2 last_node);
1898 template <
typename Node>
1900 return wg.number_of_edges() == wg.number_of_nodes() * wg.out_degree();
1924 template <
typename Node>
1976 template <
typename Node1,
typename Node2>
2012 template <
typename Node1,
typename Node2>
2050 template <
typename Node>
2079 template <
typename Node1,
typename Node2,
typename Iterator>
2084 Iterator last)
noexcept;
2111 template <
typename Node1,
typename Node2,
typename Iterator>
2139 template <
typename Node1,
typename Node2>
2166 template <
typename Node1,
typename Node2>
2199 template <
typename Node1,
typename Node2>
2223 template <
typename Node1,
typename Node2>
2248 template <
typename Node1,
typename Node2>
2273 template <
typename Node1,
typename Node2>
2297 template <
typename Node1,
typename Node2>
2298 [[nodiscard]]
size_t
2321 template <
typename Node1,
typename Node2>
2322 [[nodiscard]]
size_t
2349 template <
typename Node>
2374 template <
typename Node1,
typename Node2>
2397 template <
typename Node1,
typename Node2>
2420 template <
typename Node1,
typename Node2>
2443 template <
typename Node1,
typename Node2>
2470 template <
typename Graph>
2497 template <
typename Graph>
2516 template <
typename Node>
2533 template <
typename Node>
2557 template <
typename Node,
typename Iterator>
2574 template <
typename Node>
2590 template <
typename Node>
2609 template <
typename Node,
typename Iterator>
2627 template <
typename Node1,
typename Node2>
2646 template <
typename Node,
typename Iterator1,
typename Iterator2>
2674 template <
typename Node>
2703 template <
typename Node1,
typename Node2>
2722 template <
typename Thing>
2745 template <
typename Node>
2789 template <
typename Return>
2790 [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
2800 template <
typename Return>
2801 [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
2807 template <
typename Sub
class>
2808 class JoinerMeeterCommon {
2810 template <
typename Node1,
typename Node2>
2817 template <
typename Node>
2824 template <
typename Node>
2828 return call_no_checks(
2829 xy, x,
static_cast<Node
>(0), y,
static_cast<Node
>(0));
2832 template <
typename Node,
typename... Args>
2833 [[nodiscard]]
auto call_no_checks(WordGraph<Node>
const& x,
2835 -> std::enable_if_t<
sizeof...(Args) % 2 == 1, WordGraph<Node>> {
2840 static_cast<Subclass&
>(*this).call_no_checks(
2849 template <
typename Node>
2850 void operator()(WordGraph<Node>& xy,
2851 WordGraph<Node>
const& x,
2853 WordGraph<Node>
const& y,
2855 throw_if_bad_args(x, xroot, y, yroot);
2856 call_no_checks(xy, x, xroot, y, yroot);
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));
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>> {
2877 template <
typename Node1,
typename Node2>
2878 bool is_subrelation_no_checks(WordGraph<Node1>
const& x,
2880 WordGraph<Node1>
const& y,
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));
2894 template <
typename Node1,
typename Node2>
2895 bool is_subrelation(WordGraph<Node1>
const& x,
2897 WordGraph<Node1>
const& y,
2899 throw_if_bad_args(x, xroot, y, yroot);
2900 return is_subrelation_no_checks(x, xroot, y, yroot);
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));
2925 class Joiner :
public detail::JoinerMeeterCommon<Joiner> {
2931 template <
typename Node>
2933 size_t xnum_nodes_reachable_from_root,
2938 template <
typename Node>
2940 size_t xnum_nodes_reachable_from_root,
2943 size_t ynum_nodes_reachable_from_root,
3002 template <
typename Node>
3005 size_t xnum_nodes_reachable_from_root,
3008 size_t ynum_nodes_reachable_from_root,
3045 template <
typename Node1,
typename Node2>
3048 size_t xnum_nodes_reachable_from_root,
3051 size_t ynum_nodes_reachable_from_root,
3053#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3077 template <
typename Node>
3103 template <
typename Node>
3127 template <
typename Node,
typename... Args>
3155 template <
typename Node>
3183 template <
typename Node>
3205 template <
typename Node,
typename... Args>
3238 template <
typename Node1,
typename Node2>
3266 template <
typename Node>
3302 template <
typename Node1,
typename Node2>
3332 template <
typename Node>
3337 using detail::JoinerMeeterCommon<
Joiner>::operator();
3356 class Meeter :
public detail::JoinerMeeterCommon<Meeter> {
3394 template <
typename Node>
3397 size_t xnum_nodes_reachable_from_root,
3400 size_t ynum_nodes_reachable_from_root,
3406 template <
typename Node1,
typename Node2>
3409 size_t xnum_nodes_reachable_from_root,
3412 size_t ynum_nodes_reachable_from_root,
3415#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3418 template <
typename Node>
3427 template <
typename Node>
3451 template <
typename Node,
typename... Args>
3456 template <
typename Node>
3465 template <
typename Node>
3487 template <
typename Node,
typename... Args>
3492 template <
typename Node1,
typename Node2>
3500 template <
typename Node>
3506 template <
typename Node1,
typename Node2>
3514 template <
typename Node>
3518 using detail::JoinerMeeterCommon<
Meeter>::operator();
3538 template <
typename Node>
3556 return "<Meeter of word graphs>";
3574 return "<Joiner of word graphs>";
3596 template <
typename Node>
3603#include "word-graph.tpp"
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.
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