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;
133 mutable detail::DynamicArray2<Node> _dynamic_array_2;
189 WordGraph(WordGraph
const&);
200 template <
typename OtherNode>
201 WordGraph(WordGraph<OtherNode>
const& that);
223 template <
typename OtherNode>
224 WordGraph&
init(WordGraph<OtherNode>
const& that);
227 WordGraph(WordGraph&&);
376 _dynamic_array_2.set(s, a, t);
484 _dynamic_array_2.swap(m, a, n, a);
521 [[nodiscard]]
bool operator==(WordGraph
const& that)
const {
522 return _dynamic_array_2 == that._dynamic_array_2;
541 [[nodiscard]]
bool operator!=(WordGraph
const& that)
const {
561 [[nodiscard]]
bool operator<(WordGraph
const& that)
const {
562 return _dynamic_array_2 < that._dynamic_array_2;
581 [[nodiscard]]
bool operator<=(WordGraph
const& that)
const {
582 return _dynamic_array_2 <= that._dynamic_array_2;
601 [[nodiscard]]
bool operator>(WordGraph
const& that)
const {
602 return _dynamic_array_2 > that._dynamic_array_2;
621 [[nodiscard]]
bool operator>=(WordGraph
const& that)
const {
622 return _dynamic_array_2 > that._dynamic_array_2;
686 return _dynamic_array_2.get(s, a);
771#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
773 _num_active_nodes = val;
777 [[nodiscard]]
size_type inline number_of_active_nodes() const noexcept {
778 return _num_active_nodes;
928 return _dynamic_array_2.cbegin_row(source);
976 return _dynamic_array_2.cbegin_row(source) + _degree;
988 [[nodiscard]]
auto nodes() const noexcept {
1002 [[nodiscard]]
auto labels() const noexcept {
1003 return rx::seq<label_type>() | rx::take(
out_degree());
1023 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1041 [[nodiscard]] rx::iterator_range<const_iterator_targets>
1137 template <
typename Iterator,
1138 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1162 template <
typename Iterator,
1163 typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
1197#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1208 return permute_nodes_no_checks(p, q, p.
size());
1213 return permute_nodes_no_checks(p, q, p.
size());
1258 template <
typename Node,
typename Iterator>
1280 template <
typename Node>
1303 template <
typename Node>
1304 [[deprecated]] [[nodiscard]]
auto
1319 template <
typename Node>
1351 template <
typename Node>
1352 [[deprecated]] [[nodiscard]]
bool
1388 template <
typename Node>
1430 template <
typename Node1,
typename Node2,
typename Iterator>
1470 template <
typename Node1,
typename Node2>
1474 static_assert(
sizeof(Node2) <=
sizeof(Node1));
1509 template <
typename Node1,
typename Node2,
typename Iterator>
1510 [[deprecated]] [[nodiscard]] Node1
1514 Iterator last)
noexcept;
1547 template <
typename Node1,
typename Node2>
1548 [[deprecated]] [[nodiscard]] Node1
1552 static_assert(
sizeof(Node2) <=
sizeof(Node1));
1594 template <
typename Node>
1647 template <
typename Node1,
typename Node2>
1686 template <
typename Node1,
typename Node2>
1739 template <
typename Node,
1743 [[deprecated]] [[nodiscard]]
bool
1745 Iterator1 first_node,
1746 Iterator2 last_node,
1747 Iterator3 first_rule,
1748 Iterator3 last_rule);
1801 std::enable_if_t<!std::is_same_v<std::decay_t<Iterator3>,
word_type>>>
1803 Iterator1 first_node,
1804 Iterator2 last_node,
1805 Iterator3 first_rule,
1806 Iterator3 last_rule);
1844 template <
typename Node,
typename Iterator1,
typename Iterator2>
1846 Iterator1 first_node,
1847 Iterator2 last_node,
1889 template <
typename Node,
typename Iterator1,
typename Iterator2>
1891 Iterator1 first_node,
1892 Iterator2 last_node,
1930 template <
typename Node,
typename Iterator1,
typename Iterator2>
1931 [[deprecated]] [[nodiscard]]
bool
1933 Iterator1 first_node,
1934 Iterator2 last_node);
1968 template <
typename Node,
typename Iterator1,
typename Iterator2>
1970 Iterator1 first_node,
1971 Iterator2 last_node);
1993 template <
typename Node>
1994 [[deprecated]] [[nodiscard]]
bool
1996 return wg.number_of_edges() == wg.number_of_nodes() * wg.out_degree();
2023 template <
typename Node>
2078 template <
typename Node1,
typename Node2>
2079 [[deprecated]] [[nodiscard]]
bool
2118 template <
typename Node1,
typename Node2>
2159 template <
typename Node>
2160 [[deprecated]] [[nodiscard]]
bool
2192 template <
typename Node1,
typename Node2,
typename Iterator>
2197 Iterator last)
noexcept;
2227 template <
typename Node1,
typename Node2,
typename Iterator>
2258 template <
typename Node1,
typename Node2>
2288 template <
typename Node1,
typename Node2>
2324 template <
typename Node1,
typename Node2>
2351 template <
typename Node1,
typename Node2>
2379 template <
typename Node1,
typename Node2>
2407 template <
typename Node1,
typename Node2>
2434 template <
typename Node1,
typename Node2>
2435 [[deprecated]] [[nodiscard]]
size_t
2461 template <
typename Node1,
typename Node2>
2462 [[deprecated]] [[nodiscard]]
size_t
2492 template <
typename Node>
2520 template <
typename Node1,
typename Node2>
2546 template <
typename Node1,
typename Node2>
2574 template <
typename Node1,
typename Node2>
2575 [[deprecated]] [[nodiscard]]
Forest
2600 template <
typename Node1,
typename Node2>
2601 [[deprecated]] [[nodiscard]]
Forest
2631 template <
typename Graph>
2661 template <
typename Graph>
2685 template <
typename Node>
2702 template <
typename Node>
2726 template <
typename Node,
typename Iterator>
2743 template <
typename Node>
2759 template <
typename Node>
2778 template <
typename Node,
typename Iterator>
2796 template <
typename Node1,
typename Node2>
2815 template <
typename Node,
typename Iterator1,
typename Iterator2>
2846 template <
typename Node>
2879 template <
typename Node1,
typename Node2>
2898 template <
typename Thing>
2924 template <
typename Node>
2972 template <
typename Return>
2973 [[deprecated]] [[nodiscard]] std::enable_if_t<
2985 template <
typename Return>
2986 [[deprecated]] [[nodiscard]] std::
2987 enable_if_t<is_specialization_of_v<Return, WordGraph>, Return>
2992 template <
typename Sub
class>
2995 template <
typename Node1,
typename Node2>
3002 template <
typename Node>
3009 template <
typename Node>
3013 return call_no_checks(
3014 xy, x,
static_cast<Node
>(0), y,
static_cast<Node
>(0));
3017 template <
typename Node,
typename... Args>
3025 static_cast<Subclass&
>(*this).call_no_checks(
3034 template <
typename Node>
3040 throw_if_bad_args(x, xroot, y, yroot);
3041 call_no_checks(xy, x, xroot, y, yroot);
3044 template <
typename Node>
3048 return operator()(xy, x,
static_cast<Node
>(0), y,
static_cast<Node
>(0));
3051 template <
typename Node,
typename... Args>
3052 [[nodiscard]]
auto operator()(
WordGraph<Node> const& x, Args&&... args)
3062 template <
typename Node1,
typename Node2>
3068 template <
typename Node>
3071 return is_subrelation_no_checks(
3072 x,
static_cast<Node
>(0), y,
static_cast<Node
>(0));
3079 template <
typename Node1,
typename Node2>
3084 throw_if_bad_args(x, xroot, y, yroot);
3085 return is_subrelation_no_checks(x, xroot, y, yroot);
3088 template <
typename Node>
3090 return is_subrelation(x,
static_cast<Node
>(0), y,
static_cast<Node
>(0));
3113#pragma GCC diagnostic push
3114#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
3116#pragma GCC diagnostic pop
3122 template <
typename Node>
3124 size_t xnum_nodes_reachable_from_root,
3129 template <
typename Node>
3131 size_t xnum_nodes_reachable_from_root,
3134 size_t ynum_nodes_reachable_from_root,
3193 template <
typename Node>
3196 size_t xnum_nodes_reachable_from_root,
3199 size_t ynum_nodes_reachable_from_root,
3236 template <
typename Node1,
typename Node2>
3239 size_t xnum_nodes_reachable_from_root,
3242 size_t ynum_nodes_reachable_from_root,
3244#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3268 template <
typename Node>
3294 template <
typename Node>
3318 template <
typename Node,
typename... Args>
3346 template <
typename Node>
3374 template <
typename Node>
3396 template <
typename Node,
typename... Args>
3429 template <
typename Node1,
typename Node2>
3457 template <
typename Node>
3493 template <
typename Node1,
typename Node2>
3523 template <
typename Node>
3527#pragma GCC diagnostic push
3528#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
3533#pragma GCC diagnostic pop
3553#pragma GCC diagnostic push
3554#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
3556#pragma GCC diagnostic pop
3594 template <
typename Node>
3597 size_t xnum_nodes_reachable_from_root,
3600 size_t ynum_nodes_reachable_from_root,
3606 template <
typename Node1,
typename Node2>
3609 size_t xnum_nodes_reachable_from_root,
3612 size_t ynum_nodes_reachable_from_root,
3615#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3618 template <
typename Node>
3627 template <
typename Node>
3651 template <
typename Node,
typename... Args>
3656 template <
typename Node>
3665 template <
typename Node>
3687 template <
typename Node,
typename... Args>
3692 template <
typename Node1,
typename Node2>
3700 template <
typename Node>
3706 template <
typename Node1,
typename Node2>
3714 template <
typename Node>
3717#pragma GCC diagnostic push
3718#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
3723#pragma GCC diagnostic pop
3744 template <
typename Node>
3763 [[deprecated]] [[nodiscard]]
static inline std::string
3766 return "<Meeter of word graphs>";
3784 [[deprecated]] [[nodiscard]]
static inline std::string
3787 return "<Joiner of word graphs>";
3812 template <
typename Node>
3820#include "word-graph.tpp"
A representation of a graph in the DOT language of Graphviz.
Definition dot.hpp:116
Class representing a collection of spanning trees of a word graph.
Definition forest.hpp:46
Class for taking joins of word graphs.
Definition word-graph.hpp:3115
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:3555
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
Definition word-graph.hpp:560
node_type node_type
Definition word-graph.hpp:99
auto nodes() const noexcept
Definition word-graph.hpp:987
auto labels_and_targets(node_type source) const
const_iterator_nodes cend_nodes() const noexcept
Definition word-graph.hpp:878
WordGraph & disjoint_union_inplace(WordGraph< node_type > const &that)
std::pair< label_type, node_type > next_label_and_target_no_checks(node_type s, label_type a) const
WordGraph & remove_label(label_type a)
WordGraph & swap_targets(node_type m, node_type n, label_type a)
size_type number_of_edges() const
bool operator>(WordGraph const &that) const
Definition word-graph.hpp:600
const_iterator_targets cbegin_targets_no_checks(node_type source) const noexcept
Definition word-graph.hpp:926
typename detail::IntRange< node_type >::const_iterator const_iterator_nodes
Definition word-graph.hpp:116
node_type label_type
Definition word-graph.hpp:102
bool operator<=(WordGraph const &that) const
Definition word-graph.hpp:580
auto labels_and_targets_no_checks(node_type source) const noexcept
Definition word-graph.hpp:1061
WordGraph & induced_subgraph(node_type first, node_type last)
rx::iterator_range< const_iterator_targets > targets_no_checks(node_type source) const noexcept
Definition word-graph.hpp:1023
WordGraph & remove_all_targets()
Definition word-graph.hpp:457
const_iterator_targets cbegin_targets(node_type source) const
WordGraph & disjoint_union_inplace_no_checks(WordGraph< node_type > const &that)
WordGraph & remove_target(node_type s, label_type a)
WordGraph & swap_targets_no_checks(node_type m, node_type n, label_type a)
Definition word-graph.hpp:482
typename detail::IntRange< node_type >::const_reverse_iterator const_reverse_iterator_nodes
Definition word-graph.hpp:120
bool operator>=(WordGraph const &that) const
Definition word-graph.hpp:620
bool operator!=(WordGraph const &that) const
Definition word-graph.hpp:540
auto labels() const noexcept
Definition word-graph.hpp:1001
WordGraph & reserve(size_type m, size_type n)
const_iterator_targets cend_targets_no_checks(node_type source) const noexcept
Definition word-graph.hpp:974
size_type out_degree() const noexcept
Definition word-graph.hpp:842
const_iterator_nodes cbegin_nodes() const noexcept
Definition word-graph.hpp:860
bool operator==(WordGraph const &that) const
Definition word-graph.hpp:520
rx::iterator_range< const_iterator_targets > targets(node_type source) const
WordGraph & operator=(WordGraph const &)
WordGraph & target(node_type s, label_type a, node_type t)
WordGraph & add_nodes(size_type nr)
typename detail::DynamicArray2< node_type >::const_iterator const_iterator_targets
Definition word-graph.hpp:124
WordGraph & target_no_checks(node_type s, label_type a, node_type t)
Definition word-graph.hpp:374
const_iterator_targets cend_targets(node_type source) const
WordGraph & init(size_type m=0, size_type n=0)
WordGraph & remove_target_no_checks(node_type s, label_type a)
Definition word-graph.hpp:396
std::pair< label_type, node_type > next_label_and_target(node_type s, label_type a) const
WordGraph & remove_label_no_checks(label_type a)
WordGraph & add_to_out_degree(size_type nr)
static WordGraph random(size_type number_of_nodes, size_type out_degree, std::mt19937 mt=std::mt19937(std::random_device()()))
size_t hash_value() const
Definition word-graph.hpp:635
size_type number_of_nodes() const noexcept
Definition word-graph.hpp:766
std::size_t size_type
Definition word-graph.hpp:105
WordGraph & induced_subgraph_no_checks(node_type first, node_type last)
size_type number_of_edges_no_checks(node_type s) const
Definition word-graph.hpp:2993
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
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-class.hpp:2380
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:856
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:84
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:54
@ shortlex
Definition order.hpp:60
static constexpr bool IsWordGraph
Helper variable template.
Definition word-graph.hpp:2900
Namespace containing helper functions for the WordGraph class.
Definition word-graph.hpp:1227
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:2436
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:1281
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:2463
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