Defined in word-graph.hpp.

This namespace contains helper functions for the WordGraph class.

Functions
template<typename Node>
void	add_cycle (WordGraph< Node > &wg, size_t N)
	Adds a cycle consisting of `N` new nodes.

template<typename Node, typename Iterator>
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.

template<typename Node>
auto	adjacency_matrix (WordGraph< Node > const &wg)
	Returns the adjacency matrix of a word graph.

template<typename Node1, typename Node2>
std::unordered_set< Node1 >	ancestors_of (WordGraph< Node1 > const &wg, Node2 source)

template<typename Node1, typename Node2>
std::unordered_set< Node1 >	ancestors_of_no_checks (WordGraph< Node1 > const &wg, Node2 source)

template<typename Node>
Dot	dot (WordGraph< Node > const &wg)
	Returns a Dot object representing a word graph.

template<typename Node>
bool	equal_to (WordGraph< Node > const &x, WordGraph< Node > const &y, Node first, Node last)
	Compares two word graphs on a range of nodes.

template<typename Node>
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.

template<typename Node1, typename Node2>
Node1	follow_path (WordGraph< Node1 > const &wg, Node2 from, word_type const &path)
	Find the node that a path starting at a given node leads to (if any).

template<typename Node1, typename Node2, typename Iterator>
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).

template<typename Node1, typename Node2, typename Iterator>
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.

template<typename Node1, typename Node2>
Node1	follow_path_no_checks (WordGraph< Node1 > const &wg, Node2 from, word_type const &path) noexcept
	Follow the path from a specified node labelled by a word.

template<typename Node>
bool	is_acyclic (WordGraph< Node > const &wg)
	Check if a word graph is acyclic.

template<typename Node1, typename Node2>
bool	is_acyclic (WordGraph< Node1 > const &wg, Node2 source)
	Check if the word graph induced by the nodes reachable from a source node is acyclic.

template<typename Node1, typename Node2>
bool	is_acyclic (WordGraph< Node1 > const &wg, Node2 source, Node2 target)
	Check if the word graph induced by the nodes reachable from a source node and from which a target node can be reached is acyclic.

template<typename Node, typename Iterator1, typename Iterator2, typename Iterator3, std::enable_if_t<!std::is_same_v< std::decay_t< Iterator3 >, word_type > >>
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.

template<typename Node, typename Iterator1, typename Iterator2>
bool	is_compatible (WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node, word_type const &lhs, word_type const &rhs)
	Check if a word graph is compatible with a pair of words for a range of nodes.

template<typename Node, typename Iterator1, typename Iterator2, typename Iterator3>
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.

template<typename Node, typename Iterator1, typename Iterator2>
bool	is_compatible_no_checks (WordGraph< Node > const &wg, Iterator1 first_node, Iterator2 last_node, word_type const &lhs, word_type const &rhs)
	Check if a word graph is compatible with a pair of words for a range of nodes.

template<typename Node>
bool	is_complete (WordGraph< Node > const &wg) noexcept
	Check if every node has exactly WordGraph::out_degree out-edges.

template<typename Node, typename Iterator1, typename Iterator2>
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.

template<typename Node, typename Iterator1, typename Iterator2>
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.

template<typename Node>
bool	is_connected (WordGraph< Node > const &wg)
	Check if a word graph is connected.

template<typename Node1, typename Node2>
bool	is_reachable (WordGraph< Node1 > const &wg, Node2 source, Node2 target)
	Check if there is a path from one node to another.

template<typename Node1, typename Node2>
bool	is_reachable_no_checks (WordGraph< Node1 > const &wg, Node2 source, Node2 target)
	Check if there is a path from one node to another.

template<typename Node>
bool	is_standardized (WordGraph< Node > const &wg, Order val=Order::shortlex)
	Check if a word graph is standardized.

template<typename Node>
bool	is_strictly_cyclic (WordGraph< Node > const &wg)
	Check if every node is reachable from some node.

template<typename Node1, typename Node2, typename Iterator>
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 reached.

template<typename Node1, typename Node2>
std::pair< Node1, word_type::const_iterator >	last_node_on_path (WordGraph< Node1 > const &wg, Node2 source, word_type const &w)
	Returns the last node on the path labelled by a word and an iterator to the position in the word reached.

template<typename Node1, typename Node2, typename Iterator>
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 reached.

template<typename Node1, typename Node2>
std::pair< Node1, word_type::const_iterator >	last_node_on_path_no_checks (WordGraph< Node1 > const &wg, Node2 source, word_type const &w)
	Returns the last node on the path labelled by a word and an iterator to the position in the word reached.

template<typename Node1, typename Node2>
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.

template<typename Node1, typename Node2>
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.

template<typename Node1, typename Node2>
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.

template<typename Node1, typename Node2>
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.

template<typename Node>
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.

template<typename Node1, typename Node2>
Forest	spanning_tree (WordGraph< Node1 > const &wg, Node2 root)
	Returns a Forest containing a spanning tree of the nodes reachable from a given node in a word graph.

template<typename Node1, typename Node2>
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 word graph.

template<typename Node1, typename Node2>
Forest	spanning_tree_no_checks (WordGraph< Node1 > const &wg, Node2 root)
	Returns a Forest containing a spanning tree of the nodes reachable from a given node in a word graph.

template<typename Node1, typename Node2>
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 word graph.

template<typename Graph>
bool	standardize (Graph &wg, Forest &f, Order val)
	Standardizes a word graph in-place.

template<typename Graph>
std::pair< bool, Forest >	standardize (Graph &wg, Order val=Order::shortlex)
	Standardizes a word graph in-place.

template<typename Node>
void	throw_if_any_target_out_of_bounds (WordGraph< Node > const &wg)
	Throws if the target of any edge is out of bounds.

template<typename Node, typename Iterator>
void	throw_if_any_target_out_of_bounds (WordGraph< Node > const &wg, Iterator first, Iterator last)
	Throws if the target of any edge with source in a given range is out of bounds.

template<typename Node, typename Iterator>
void	throw_if_label_out_of_bounds (WordGraph< Node > const &wg, Iterator first, Iterator last)
	Throws if a label is out of bounds.

template<typename Node>
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.

template<typename Node>
void	throw_if_label_out_of_bounds (WordGraph< Node > const &wg, word_type const &word)
	Throws if a label is out of bounds.

template<typename Node, typename Iterator1, typename Iterator2>
void	throw_if_node_out_of_bounds (WordGraph< Node > const &wg, Iterator1 first, Iterator2 last)
	Throws if any node in a range is out of bounds.

template<typename Node1, typename Node2>
void	throw_if_node_out_of_bounds (WordGraph< Node1 > const &wg, Node2 n)
	Throws if a node is out of bounds.

template<typename Node>
std::vector< Node >	topological_sort (WordGraph< Node > const &wg)
	Returns the nodes of the word graph in topological order (see below) if possible.

template<typename Node1, typename Node2>
std::vector< Node1 >	topological_sort (WordGraph< Node1 > const &wg, Node2 source)

Function Documentation

◆ add_cycle()

template<typename Node>

void add_cycle	(	WordGraph< Node > &	wg,
		size_t	N )

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the WordGraph object to add a cycle to.
N	the length of the cycle and number of new nodes to add.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(N)\) where \(N\) is the second parameter.

Note: The edges added by this function are all labelled 0.

◆ add_cycle_no_checks()

template<typename Node, typename Iterator>

void add_cycle_no_checks	(	WordGraph< Node > &	wg,
		Iterator	first,
		Iterator	last )

This function adds a cycle involving the specified range of nodes.

Template Parameters

Node	the type of the nodes of the WordGraph.
Iterator	the type of an iterator pointing to nodes of a word graph.

Parameters

wg	the WordGraph object to add a cycle to.
first	an iterator to nodes of `wg`.
last	an iterator to nodes of `wg`.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m)\) where \(m\) is the distance between first and last.

Note: The edges added by this function are all labelled 0.

◆ adjacency_matrix()

template<typename Node>

auto adjacency_matrix ( WordGraph< Node > const & wg )

nodiscard

This function returns the adjacency matrix of the word graph wg. The type of the returned matrix depends on whether or not libsemigroups is compiled with eigen enabled. The returned matrix has the number of edges with source s and target t in the (s, t)-entry.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the word graph.

Returns: The adjacency matrix.

◆ dot()

template<typename Node>

Dot dot ( WordGraph< Node > const & wg )

nodiscard

This function returns a Dot object representing the word graph wg.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the word graph.

Returns: A Dot object.

◆ equal_to()

template<typename Node>

bool equal_to	(	WordGraph< Node > const &	x,
		WordGraph< Node > const &	y,
		Node	first,
		Node	last )

nodiscard

This function returns true if the word graphs x and y are equal on the range of nodes from first to last; and false otherwise. The word graphs x and y are equal at a node s if:

the out-degrees of x and y coincide;
the edges with source s and label a have equal targets in x and y for every label a.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

x	the first word graph for comparison.
y	the second word graph for comparison.
first	the first node in the range.
last	the last node in the range plus `1`.

Returns: Whether or not the word graphs are equal at the specified range of nodes.

Exceptions

LibsemigroupsException if first is not a node in x or not a node in y; or if last - 1 is not a node in or not a node in y.

See also: WordGraph::operator== for a comparison of two entire word graphs.

◆ equal_to_no_checks()

template<typename Node>

bool equal_to_no_checks	(	WordGraph< Node > const &	x,
		WordGraph< Node > const &	y,
		Node	first,
		Node	last )

nodiscard

This function returns true if the word graphs x and y are equal on the range of nodes from first to last; and false otherwise. The word graphs x and y are equal at a node s if:

the out-degrees of x and y coincide;
the edges with source s and label a have equal targets in x and y for every label a.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

x	the first word graph for comparison.
y	the second word graph for comparison.
first	the first node in the range.
last	the last node in the range plus `1`.

Returns: Whether or not the word graphs are equal at the specified range of nodes.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks are performed to ensure that the arguments are valid.

See also: WordGraph::operator== for a comparison of two entire word graphs.

◆ follow_path() [1/2]

template<typename Node1, typename Node2>

Node1 follow_path	(	WordGraph< Node1 > const &	wg,
		Node2	from,
		word_type const &	path )

nodiscard

This function attempts to follow the path in the word graph wg starting at the node from labelled by the word path. If this path exists, then the last node on that path is returned. If this path does not exist, then UNDEFINED is returned.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the node `from` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	a word graph.
from	the starting node.
path	the path to follow.

Returns: A value of type Node1. If one or more edges in path are not defined, then UNDEFINED is returned.

Exceptions

LibsemigroupsException if from is not a node in the word graph or path contains a value that is not an edge-label.

Complexity: Linear in the length of path.

◆ follow_path() [2/2]

template<typename Node1, typename Node2, typename Iterator>

Node1 follow_path	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Iterator	first,
		Iterator	last )

nodiscard

This function attempts to follow the path in the word graph wg starting at the node from labelled by the word defined by first and last. If this path exists, then the last node on that path is returned. If this path does not exist, then UNDEFINED is returned.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the node `from` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).
Iterator	the type of `first` and `last`.

Parameters

wg	a word graph.
source	the starting node.
first	an iterator point at the start of the word.
last	an iterator point one beyond the last letter of the word.

Returns: A value of type Node1. If one or more edges in path are not defined, then UNDEFINED is returned.

Exceptions

LibsemigroupsException if from is not a node in the word graph or the word defined by first and last contains a value that is not an edge-label.

Complexity: Linear in the distance between first and last.

◆ follow_path_no_checks() [1/2]

template<typename Node1, typename Node2, typename Iterator>

Node1 follow_path_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	from,
		Iterator	first,
		Iterator	last )

nodiscardnoexcept

This function returns the last node on the path in the word graph wg starting at the node from labelled by the word defined by first and last or UNDEFINED.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the node `from` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	a word graph.
from	the source node.
first	iterator into a word.
last	iterator into a word.

Returns: A value of type Node1.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: At worst the distance from first to last.

Warning: No checks on the arguments of this function are performed.

◆ follow_path_no_checks() [2/2]

template<typename Node1, typename Node2>

Node1 follow_path_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	from,
		word_type const &	path )

nodiscardnoexcept

This function returns the last node on the path in the word graph wg starting at the node from labelled by path or UNDEFINED.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the node `from` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	a word graph.
from	the source node.
path	the word.

Returns: A value of type Node1.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: At worst the length of path.

Warning: No checks on the arguments of this function are performed.

◆ is_acyclic() [1/3]

template<typename Node>

bool is_acyclic ( WordGraph< Node > const & wg )

nodiscard

This function returns true if the word graph wg is acyclic and false otherwise. A word graph is acyclic if every directed cycle in the word graph is trivial.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the WordGraph object to check.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the out_degree.

Example: WordGraph<size_t> wg;

wg.add_nodes(2);

wg.add_to_out_degree(1);

wg.target(0, 0, 1);

wg.target(1, 0, 0);

word_graph::is_acyclic(wg); // returns false

libsemigroups::WordGraph
Class for representing word graphs.
Definition word-graph.hpp:82

libsemigroups::WordGraph::target
WordGraph & target(node_type s, label_type a, node_type t)
Add an edge from one node to another with a given label.

libsemigroups::WordGraph::add_nodes
WordGraph & add_nodes(size_type nr)
Add a number of new nodes.

libsemigroups::WordGraph::add_to_out_degree
WordGraph & add_to_out_degree(size_type nr)
Add to the out-degree of every node.

libsemigroups::word_graph::is_acyclic
bool is_acyclic(WordGraph< Node > const &wg)
Check if a word graph is acyclic.

◆ is_acyclic() [2/3]

template<typename Node1, typename Node2>

bool is_acyclic	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

This function returns true if the word graph consisting of the nodes reachable from source in the word graph wg is acyclic and false if not. A word graph is acyclic if every directed cycle in the word graph is trivial.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the node `source` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	the WordGraph object to check.
source	the source node.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the out_degree.

Example: WordGraph<size_t> wg;

wg.add_nodes(4);

wg.add_to_out_degree(1);

wg.target(0, 0, 1);

wg.target(1, 0, 0);

wg.target(2, 0, 3);

word_graph::is_acyclic(wg); // returns false

word_graph::is_acyclic(wg, 0); // returns false

word_graph::is_acyclic(wg, 1); // returns false

word_graph::is_acyclic(wg, 2); // returns true

word_graph::is_acyclic(wg, 3); // returns true

◆ is_acyclic() [3/3]

template<typename Node1, typename Node2>

bool is_acyclic	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Node2	target )

nodiscard

This function returns true if the word graph consisting of the nodes reachable from source and from which target is reachable, in the word graph wg, is acyclic; and false if not. A word graph is acyclic if every directed cycle of the word graph is trivial.

Template Parameters

Node1	the type of the nodes of the WordGraph `wg`.
Node2	the type of the nodes `source` and `target` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	the WordGraph object to check.
source	the source node.
target	the target node.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the out_degree.

◆ is_compatible() [1/2]

template<typename Node, typename Iterator1, typename Iterator2, typename Iterator3, std::enable_if_t<!std::is_same_v< std::decay_t< Iterator3 >, word_type > >>

bool is_compatible	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node,
		Iterator3	first_rule,
		Iterator3	last_rule )

nodiscard

This function returns true if the word graph wg is compatible with the relations in the range first_rule to last_rule at every node in the range from first_node to last_node. This means that the paths with given sources that are labelled by one side of a relation leads to the same node as the path labelled by the other side of the relation.

Template Parameters

Node	the type of the nodes of the WordGraph. `wg`.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.
Iterator3	the type of `first_rule` and `last_rule`.

Parameters

wg	the word graph.
first_node	iterator pointing at the first node.
last_node	iterator pointing at one beyond the last node.
first_rule	iterator pointing to the first rule.
last_rule	iterator pointing one beyond the last rule.

Returns: Whether or not the word graph is compatible with the given rules at each one of the given nodes.

Exceptions

LibsemigroupsException	if any of the nodes in the range between `first_node` and `last_node` does not belong to `wg` (i.e. is greater than or equal to WordGraph::number_of_nodes).
LibsemigroupsException	if any of the rules in the range between `first_rule` and `last_rule` contains an invalid label (i.e. one greater than or equal to WordGraph::out_degree).

Note: This function ignores out of bound targets in wg (if any).

◆ is_compatible() [2/2]

template<typename Node, typename Iterator1, typename Iterator2>

bool is_compatible	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node,
		word_type const &	lhs,
		word_type const &	rhs )

This function returns true if the word graph wg is compatible with the words lhs and rhs at every node in the range from first_node to last_node. This means that the paths with given sources that are labelled by lhs leads to the same node as the path labelled by rhs.

Template Parameters

Node	the type of the nodes of the WordGraph `wg`.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.

Parameters

wg	the word graph.
first_node	iterator pointing at the first node.
last_node	iterator pointing at one beyond the last node.
lhs	the first rule.
rhs	the second rule.

Returns: Whether or not the word graph is compatible with the given rules at each one of the given nodes.

Exceptions

LibsemigroupsException	if any of the nodes in the range between `first_node` and `last_node` does not belong to `wg` (i.e. is greater than or equal to WordGraph::number_of_nodes).
LibsemigroupsException	if any of the rules in the range between `first_rule` and `last_rule` contains an invalid label (i.e. one greater than or equal to WordGraph::out_degree).

◆ is_compatible_no_checks() [1/2]

template<typename Node, typename Iterator1, typename Iterator2, typename Iterator3>

bool is_compatible_no_checks	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node,
		Iterator3	first_rule,
		Iterator3	last_rule )

nodiscard

This function returns true if the word graph wg is compatible with the relations in the range first_rule to last_rule at every node in the range from first_node to last_node. This means that the paths with given sources that are labelled by one side of a relation leads to the same node as the path labelled by the other side of the relation.

Template Parameters

Node	the type of the nodes of the WordGraph `wg`.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.
Iterator3	the type of `first_rule` and `last_rule`.

Parameters

wg	the word graph.
first_node	iterator pointing at the first node.
last_node	iterator pointing at one beyond the last node.
first_rule	iterator pointing to the first rule.
last_rule	iterator pointing one beyond the last rule.

Returns: Whether or not the word graph is compatible with the given rules at each one of the given nodes.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function ignores out of bound targets in wg (if any).

Warning: No checks on the arguments of this function are performed.

◆ is_compatible_no_checks() [2/2]

template<typename Node, typename Iterator1, typename Iterator2>

bool is_compatible_no_checks	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node,
		word_type const &	lhs,
		word_type const &	rhs )

This function returns true if the word graph wg is compatible with the words lhs and rhs at every node in the range from first_node to last_node. This means that the paths with given sources that are labelled by lhs leads to the same node as the path labelled by rhs.

Template Parameters

Node	the type of the nodes of the WordGraph `wg`.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.

Parameters

wg	the word graph.
first_node	iterator pointing at the first node.
last_node	iterator pointing at one beyond the last node.
lhs	the first rule.
rhs	the second rule.

Returns: Whether or not the word graph is compatible with the given rules at each one of the given nodes.

Note: This function ignores out of bound targets in wg (if any).

Warning: This function does not check that its arguments are valid.

◆ is_complete() [1/2]

template<typename Node>

bool is_complete ( WordGraph< Node > const & wg )

nodiscardnoexcept

This function returns true if a WordGraph is complete, meaning that every node is the source of an edge with every possible label.

Template Parameters

Node	the type of the nodes in the word graph.

Parameters

wg	the word graph.

Returns: Whether or not the word graph is complete.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: \(O(mn)\) where m is number_of_nodes() and n is out_degree().

◆ is_complete() [2/2]

template<typename Node, typename Iterator1, typename Iterator2>

bool is_complete	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node )

nodiscard

This function returns true if every node in the range defined by first_node and last_node is complete, meaning that every such node is the source of an edge with every possible label.

Template Parameters

Node	the type of the nodes in the word graph.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.

Parameters

wg	the word graph.
first_node	iterator pointing to the first node in the range.
last_node	iterator pointing one beyond the last node in the range.

Returns: Whether or not the word graph is complete on the given range of nodes.

Exceptions

LibsemigroupsException if any item in the range defined by first_node and last_node is not a node of wg.

Complexity: \(O(mn)\) where m is the number of nodes in the range and n is out_degree().

◆ is_complete_no_checks()

template<typename Node, typename Iterator1, typename Iterator2>

bool is_complete_no_checks	(	WordGraph< Node > const &	wg,
		Iterator1	first_node,
		Iterator2	last_node )

nodiscard

This function returns true if every node in the range defined by first_node and last_node is complete, meaning that every such node is the source of an edge with every possible label.

Template Parameters

Node	the type of the nodes in the word graph.
Iterator1	the type of `first_node`.
Iterator2	the type of `last_node`.

Parameters

wg	the word graph.
first_node	iterator pointing to the first node in the range.
last_node	iterator pointing one beyond the last node in the range.

Returns: Whether or not the word graph is complete on the given range of nodes.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is the number of nodes in the range and n is out_degree().

Warning: No checks are performed on the arguments.

◆ is_connected()

template<typename Node>

bool is_connected ( WordGraph< Node > const & wg )

nodiscard

This function returns true if the word graph wg is connected and false if it is not. A word graph is connected if for every pair of nodes s and t in the graph there exists a sequence \(u_0 = s, \ldots, u_{n}= t\) for some \(n\in \mathbb{N}\) such that for every \(i\) there exists a label a such that \((u_i, a, u_{i + 1})\) or \((u_{i + 1}, a, u_i)\) is an edge in the graph.

Template Parameters

Node	the type of the nodes in the word graph.

Parameters

wg	the word graph.

Returns: Whether or not the word graph is connected.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ is_reachable()

template<typename Node1, typename Node2>

bool is_reachable	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Node2	target )

nodiscard

This function returns true if there is a path from the node source to the node target in the word graph wg.

Template Parameters

Node1	the type of the nodes in the WordGraph.
Node	2 the types of `source` and `target` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	the WordGraph object to check.
source	the source node.
target	the source node.

Returns: Whether or not the node target is reachable from the node source in the word graph wg.

Exceptions

LibsemigroupsException	if `source` or `target` is out of bounds.
LibsemigroupsException	if any target in `wg` is out of bounds.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph::out_degree.

Note: If source and target are equal, then, by convention, we consider target to be reachable from source, via the empty path.

◆ is_reachable_no_checks()

template<typename Node1, typename Node2>

bool is_reachable_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Node2	target )

nodiscard

This function returns true if there is a path from the node source to the node target in the word graph wg.

Template Parameters

Node1	the type of the nodes in the WordGraph.
Node	2 the types of `source` and `target` (must satisfy `sizeof(Node2) <= sizeof(Node1)`).

Parameters

wg	the WordGraph object to check.
source	the source node.
target	the source node.

Returns: Whether or not the node target is reachable from the node source in the word graph wg.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph::out_degree.

Note: If source and target are equal, then, by convention, we consider target to be reachable from source, via the empty path.; This function ignores out of bound targets in wg (if any).

Warning: No checks are performed on the arguments.

Example: WordGraph<size_t> wg;

wg.add_nodes(4);

wg.add_to_out_degree(1);

wg.target(0, 1, 0);

wg.target(1, 0, 0);

wg.target(2, 3, 0);

word_graph::is_reachable_no_checks(wg, 0, 1); // returns true

word_graph::is_reachable_no_checks(wg, 1, 0); // returns true

word_graph::is_reachable_no_checks(wg, 1, 2); // returns false

word_graph::is_reachable_no_checks(wg, 2, 3); // returns true

word_graph::is_reachable_no_checks(wg, 3, 2); // returns false

libsemigroups::word_graph::is_reachable_no_checks
bool is_reachable_no_checks(WordGraph< Node1 > const &wg, Node2 source, Node2 target)
Check if there is a path from one node to another.

◆ is_standardized()

template<typename Node>

bool is_standardized	(	WordGraph< Node > const &	wg,
		Order	val = Order::shortlex )

This function checks if the word graph wg is standardized according to the reduction order specified by val.

Template Parameters

Node	the type of the node in `wg`.

Parameters

wg	the word graph to check.
val	the order to use for standardization check (defaults to Order::shortlex).

Exceptions

LibsemigroupsException if val is not one of: Order::none, Order::shortlex, Order::lex or Order::recursive.

See also: standardize.

◆ is_strictly_cyclic()

template<typename Node>

bool is_strictly_cyclic ( WordGraph< Node > const & wg )

nodiscard

This function returns true if there exists a node in wg from which every other node is reachable; and false otherwise. A word graph is strictly cyclic if there exists a node \(v\) from which every node is reachable (including \(v\)). There must be a path of length at least \(1\) from the original node \(v\) to itself (i.e. \(v\) is not considered to be reachable from itself by default).

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the WordGraph object to check.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if any target in wg is out of bounds.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph::out_degree.

Example: auto wg = make<WordGraph<uint8_t>>(

5, {{0, 0}, {1, 1}, {2}, {3, 3}});

word_graph::is_strictly_cyclic(wg); // returns false

libsemigroups::make
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:798

libsemigroups::word_graph::is_strictly_cyclic
bool is_strictly_cyclic(WordGraph< Node > const &wg)
Check if every node is reachable from some node.

◆ last_node_on_path() [1/2]

template<typename Node1, typename Node2, typename Iterator>

std::pair< Node1, Iterator > last_node_on_path	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Iterator	first,
		Iterator	last )

nodiscard

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.
Iterator	the type of the iterators into a word.

Parameters

wg	a word graph.
source	the source node.
first	iterator into a word.
last	iterator into a word.

Returns: A pair consisting of WordGraph::node_type and S.

Exceptions

LibsemigroupsException if source is out of bounds.

Complexity: At worst the distance from first to last.

Note: If any value in wg or in the word described by first and last is out of bounds (greater than or equal to WordGraph::number_of_nodes), the path labelled by the word exits the word graph, which is reflected in the result value of this function, but does not cause an exception to be thrown.

◆ last_node_on_path() [2/2]

template<typename Node1, typename Node2>

std::pair< Node1, word_type::const_iterator > last_node_on_path	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		word_type const &	w )

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	a word graph.
source	the source node.
w	the word.

Returns: A pair consisting of the last node reached and an iterator pointing at the last letter in the word labelling an edge.

Complexity: At worst the distance from w.size().

Note: If any value in wg or in the word described by first and last is out of bounds (greater than or equal to WordGraph::number_of_nodes), the path labelled by the word exits the word graph, which is reflected in the result value of this function, but does not cause an exception to be thrown.

◆ last_node_on_path_no_checks() [1/2]

template<typename Node1, typename Node2, typename Iterator>

std::pair< Node1, Iterator > last_node_on_path_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		Iterator	first,
		Iterator	last )

nodiscardnoexcept

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.
Iterator	the type of the iterators into a word.

Parameters

wg	a word graph.
source	the source node.
first	iterator into a word.
last	iterator into a word.

Returns: A pair consisting of the last node reached and an iterator pointing at the last letter in the word labelling an edge.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: At worst the distance from first to last.

Warning: No checks on the arguments of this function are performed, it is assumed that source is a node in the word graph wg; and that the letters in the word described by first and last belong to the range 0 to WordGraph::out_degree.

◆ last_node_on_path_no_checks() [2/2]

template<typename Node1, typename Node2>

std::pair< Node1, word_type::const_iterator > last_node_on_path_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	source,
		word_type const &	w )

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	a word graph.
source	the source node.
w	the word.

Returns: A pair consisting of the last node reached and an iterator pointing at the last letter in the word labelling an edge.

Complexity: At worst the distance from w.size().

Warning: No checks on the arguments of this function are performed, it is assumed that source is a node in the word graph wg; and that the letters in the word described by first and last belong to the range 0 to WordGraph::out_degree.

◆ nodes_reachable_from()

template<typename Node1, typename Node2>

std::unordered_set< Node1 > nodes_reachable_from	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

This function returns a std::unordered_set consisting of all the nodes in the word graph wg that are reachable from source.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	the word graph.
source	the source node.

Returns: A std::unordered_set consisting of all the nodes in the word graph wg that are reachable from source.

Exceptions

LibsemigroupsException if source is out of bounds (greater than or equal to WordGraph::number_of_nodes).

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ nodes_reachable_from_no_checks()

template<typename Node1, typename Node2>

std::unordered_set< Node1 > nodes_reachable_from_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

This function returns a std::unordered_set consisting of all the nodes in the word graph wg that are reachable from source.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	the word graph.
source	the source node.

Returns: A std::unordered_set consisting of all the nodes in the word graph wg that are reachable from source.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

Warning: The arguments are not checked, and in particular it is assumed that source is a node of wg (i.e. less than WordGraph::number_of_nodes).

◆ number_of_nodes_reachable_from()

template<typename Node1, typename Node2>

size_t number_of_nodes_reachable_from	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

This function returns the number of nodes in the word graph wg that are reachable from source.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	the word graph.
source	the source node.

Returns: The number of nodes in the word graph wg that are reachable from source.

Exceptions

LibsemigroupsException if source is out of bounds (greater than or equal to WordGraph::number_of_nodes).

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ number_of_nodes_reachable_from_no_checks()

template<typename Node1, typename Node2>

size_t number_of_nodes_reachable_from_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	the word graph.
source	the source node.

Returns: The number of nodes in the word graph wg that are reachable from source.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

Warning: The arguments are not checked, and in particular it is assumed that source is a node of wg (i.e. less than WordGraph::number_of_nodes).

◆ random_acyclic()

template<typename Node>

WordGraph< Node > random_acyclic	(	size_t	number_of_nodes,
		size_t	out_degree,
		std::mt19937	mt = std::mt19937(std::random_device()()) )

This function constructs a random acyclic connected word graph with number_of_nodes nodes, and out-degree out_degree. This function implements the Markov chain algorithm given in [13].

Parameters

number_of_nodes	the number of nodes.
out_degree	the out-degree of every node.
mt	a std::mt19937 used as a random source (defaults to: std::mt19937(std::random_device()())).

Returns: A random connected acyclic word graph.

Exceptions

LibsemigroupsException

if any of the following hold:

number_of_nodes is less than 2
out_degree is less than 2

Complexity: The complexity of the implementation is \(O(n^2)\) where n is the number of nodes.

◆ spanning_tree() [1/2]

template<typename Node1, typename Node2>

Forest spanning_tree	(	WordGraph< Node1 > const &	wg,
		Node2	root )

nodiscard

This function returns a Forest containing a spanning tree of the nodes reachable from root in the word graph wg.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `root`.

Parameters

wg	the word graph.
root	the source node.

Returns: A Forest object containing a spanning tree.

Exceptions

LibsemigroupsException if root is out of bounds, i.e. greater than or equal to WordGraph::number_of_nodes.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ spanning_tree() [2/2]

template<typename Node1, typename Node2>

void spanning_tree	(	WordGraph< Node1 > const &	wg,
		Node2	root,
		Forest &	f )

This function replaces the content of the Forest f with a spanning tree of the nodes reachable from root in the word graph wg.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `root`.

Parameters

wg	the word graph.
root	the source node.
f	the Forest object to hold the result.

Exceptions

LibsemigroupsException if root is out of bounds, i.e. greater than or equal to WordGraph::number_of_nodes.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ spanning_tree_no_checks() [1/2]

template<typename Node1, typename Node2>

Forest spanning_tree_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	root )

nodiscard

This function returns a Forest containing a spanning tree of the nodes reachable from root in the word graph wg.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `root`.

Parameters

wg	the word graph.
root	the source node.

Returns: A Forest object containing a spanning tree.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

Warning: The arguments are not checked, and in particular it is assumed that root is a node of wg (i.e. less than WordGraph::number_of_nodes).

◆ spanning_tree_no_checks() [2/2]

template<typename Node1, typename Node2>

void spanning_tree_no_checks	(	WordGraph< Node1 > const &	wg,
		Node2	root,
		Forest &	f )

This function replaces the content of the Forest f with a spanning tree of the nodes reachable from root in the word graph wg.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `root`.

Parameters

wg	the word graph.
root	the source node.
f	the Forest object to hold the result.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

Warning: The arguments are not checked, and in particular it is assumed that root is a node of wg (i.e. less than WordGraph::number_of_nodes).

◆ standardize() [1/2]

template<typename Graph>

bool standardize	(	Graph &	wg,
		Forest &	f,
		Order	val )

This function standardizes the word graph wg according to the reduction order specified by val, and replaces the contents of the Forest f with a spanning tree rooted at 0 for the node reachable from 0. The spanning tree corresponds to the order val.

Template Parameters

Graph the type of the word graph wg.

Parameters

wg	the word graph.
f	the Forest object to store the spanning tree.
val	the order to use for standardization.

Returns: This function returns true if the word graph wg is modified by this function (i.e. it was not standardized already), and false otherwise.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ standardize() [2/2]

template<typename Graph>

std::pair< bool, Forest > standardize	(	Graph &	wg,
		Order	val = Order::shortlex )

This function standardizes the word graph wg according to the reduction order specified by val, and returns a Forest object containing a spanning tree rooted at 0 for the node reachable from 0. The spanning tree corresponds to the order val.

Template Parameters

Graph the type of the word graph wg.

Parameters

wg	the word graph.
val	the order to use for standardization.

Returns: A std::pair the first entry of which is true if the word graph wg is modified by this function (i.e. it was not standardized already), and false otherwise. The second entry is a Forest object containing a spanning tree for wg.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: If any target of any edge in the word graph wg that is out of bounds, then this is ignored by this function.

◆ throw_if_any_target_out_of_bounds() [1/2]

template<typename Node>

void throw_if_any_target_out_of_bounds ( WordGraph< Node > const & wg )

This function throws if any target of any edge in wg is out of bounds (i.e. is greater than or equal to WordGraph::number_of_nodes, and not equal to UNDEFINED).

Template Parameters

Node	the type of the nodes in `wg`.

Parameters

wg	the word graph to check.

Exceptions

LibsemigroupsException if any target of any edge in wg is greater than or equal to WordGraph::number_of_nodes and not equal to UNDEFINED.

◆ throw_if_any_target_out_of_bounds() [2/2]

template<typename Node, typename Iterator>

void throw_if_any_target_out_of_bounds	(	WordGraph< Node > const &	wg,
		Iterator	first,
		Iterator	last )

This function throws if any target of any edge in wg whose source is in the range defined by first and last is out of bounds (i.e. is greater than or equal to WordGraph::number_of_nodes, and not equal to UNDEFINED).

Template Parameters

Node	the type of the nodes in `wg`.
Iterator	the type of the 2nd and 3rd arguments.

Parameters

wg	the word graph to check.
first	iterator pointing at the first node to check.
last	iterator pointing one beyond the last node to check.

Exceptions

LibsemigroupsException	if any target of any edge in `wg` with source in the range `first` to `last` is greater than or equal to WordGraph::number_of_nodes and not equal to UNDEFINED.
LibsemigroupsException	if any node in the range `first` to `last` is out of bounds (i.e. not a node of `wg`).

◆ throw_if_label_out_of_bounds() [1/3]

template<typename Node, typename Iterator>

void throw_if_label_out_of_bounds	(	WordGraph< Node > const &	wg,
		Iterator	first,
		Iterator	last )

This function throws if any of the letters in the word defined by first and last is out of bounds, i.e. if they are greater than or equal to wg.out_degree().

Template Parameters

Node	the type of the nodes in `wg`.
Iterator	the type of the arguments `first` and `last`.

Parameters

wg	the word graph.
first	iterator pointing at the first letter to check.
last	iterator pointing one beyond the last letter to check.

Exceptions

LibsemigroupsException if any value in the word word defined by first and last is out of bounds.

◆ throw_if_label_out_of_bounds() [2/3]

template<typename Node>

void throw_if_label_out_of_bounds	(	WordGraph< Node > const &	wg,
		typename WordGraph< Node >::label_type	a )

This function throws if the label a is out of bounds, i.e. it is greater than or equal to wg.out_degree().

Template Parameters

Node	the type of the nodes in `wg`.

Parameters

wg	the word graph.
a	the label to check.

Exceptions

LibsemigroupsException if the label a is out of bounds.

◆ throw_if_label_out_of_bounds() [3/3]

template<typename Node>

void throw_if_label_out_of_bounds	(	WordGraph< Node > const &	wg,
		word_type const &	word )

This function throws if any of the letters in word are out of bounds, i.e. if they are greater than or equal to wg.out_degree().

Template Parameters

Node	the type of the nodes in `wg`.

Parameters

wg	the word graph.
word	the word to check.

Exceptions

LibsemigroupsException if any value in word is out of bounds.

◆ throw_if_node_out_of_bounds() [1/2]

template<typename Node, typename Iterator1, typename Iterator2>

void throw_if_node_out_of_bounds	(	WordGraph< Node > const &	wg,
		Iterator1	first,
		Iterator2	last )

This function throws if any node in the range from first to last is out of bounds i.e. if they are greater than or equal to wg.number_of_nodes().

Template Parameters

Node	the node type of the word graph.
Iterator	the type of the parameters `first` and `last`.

Parameters

wg	the word graph.
first	an iterator pointing at the first node to check.
last	an iterator pointing one beyond the last node to check.

Exceptions

LibsemigroupsException if any node in the range first to last is out of bounds.

◆ throw_if_node_out_of_bounds() [2/2]

template<typename Node1, typename Node2>

void throw_if_node_out_of_bounds	(	WordGraph< Node1 > const &	wg,
		Node2	n )

This function throws if the node n is out of bounds i.e. if it is greater than or equal to wg.number_of_nodes().

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `n`.

Parameters

wg	the word graph.
n	the node to check.

Exceptions

LibsemigroupsException if n is out of bounds.

◆ topological_sort() [1/2]

template<typename Node>

std::vector< Node > topological_sort ( WordGraph< Node > const & wg )

nodiscard

If it is not empty, the returned vector has the property that if an edge from a node n points to a node m, then m occurs before n in the vector.

Template Parameters

Node	the type of the nodes of the WordGraph.

Parameters

wg	the word graph.

Returns: A std::vector of Node types that contains the nodes of wg in topological order (if possible) and is otherwise empty.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph::out_degree.

◆ topological_sort() [2/2]

template<typename Node1, typename Node2>

std::vector< Node1 > topological_sort	(	WordGraph< Node1 > const &	wg,
		Node2	source )

nodiscard

Returns the nodes of the word graph reachable from a given node in topological order (see below) if possible.

If it is not empty, the returned vector has the property that if an edge from a node n points to a node m, then m occurs before n in the vector, and the last item in the vector is source.

Template Parameters

Node1	the node type of the word graph.
Node2	the type of the node `source`.

Parameters

wg	the WordGraph object to check.
source	the source node.

Returns: A std::vector of Node types that contains the nodes reachable from source in wg in topological order (if possible) and is otherwise empty.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(m + n)\) where \(m\) is the number of nodes in the subword graph of those nodes reachable from source and \(n\) is the number of edges.

Functions

Function Documentation

◆ add_cycle()

◆ add_cycle_no_checks()

◆ adjacency_matrix()

◆ dot()

◆ equal_to()

◆ equal_to_no_checks()

◆ follow_path() [1/2]

◆ follow_path() [2/2]

◆ follow_path_no_checks() [1/2]

◆ follow_path_no_checks() [2/2]

◆ is_acyclic() [1/3]

◆ is_acyclic() [2/3]

◆ is_acyclic() [3/3]

◆ is_compatible() [1/2]

◆ is_compatible() [2/2]

◆ is_compatible_no_checks() [1/2]

◆ is_compatible_no_checks() [2/2]

◆ is_complete() [1/2]

◆ is_complete() [2/2]

◆ is_complete_no_checks()

◆ is_connected()

◆ is_reachable()

◆ is_reachable_no_checks()

◆ is_standardized()

◆ is_strictly_cyclic()

◆ last_node_on_path() [1/2]

◆ last_node_on_path() [2/2]

◆ last_node_on_path_no_checks() [1/2]

◆ last_node_on_path_no_checks() [2/2]

◆ nodes_reachable_from()

◆ nodes_reachable_from_no_checks()

◆ number_of_nodes_reachable_from()

◆ number_of_nodes_reachable_from_no_checks()

◆ random_acyclic()

◆ spanning_tree() [1/2]

◆ spanning_tree() [2/2]

◆ spanning_tree_no_checks() [1/2]

◆ spanning_tree_no_checks() [2/2]

◆ standardize() [1/2]

◆ standardize() [2/2]

◆ throw_if_any_target_out_of_bounds() [1/2]

◆ throw_if_any_target_out_of_bounds() [2/2]

◆ throw_if_label_out_of_bounds() [1/3]

◆ throw_if_label_out_of_bounds() [2/3]

◆ throw_if_label_out_of_bounds() [3/3]

◆ throw_if_node_out_of_bounds() [1/2]

◆ throw_if_node_out_of_bounds() [2/2]

◆ topological_sort() [1/2]

◆ topological_sort() [2/2]