Helper functions for ActionDigraph¶
Overview¶
Defined in action-digraph-helper.hpp
.
This page contains the documentation for helper function for the class
libsemigroups::ActionDigraph
.
Full API¶
-
template<typename T>
std::ostream &libsemigroups::operator<<(std::ostream &os, ActionDigraph<T> const &ad)¶ Output the edges of an ActionDigraph to a stream.
This function outputs the action digraph
ad
to the streamos
. The digraph is represented by the out-neighbours of each node ordered according to their labels. The symbol-
is used to denote that an edge is not defined. For example, the digraph with 1 nodes, out-degree 2, and a single loop labelled 1 from node 0 to 0 is represented as{{-, 0}}
.- Parameters
os – the ostream
ad – the action digraph
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
The first parameter
os
.
-
template<typename T>
node_type<T> libsemigroups::action_digraph_helper::follow_path(ActionDigraph<T> const &ad, node_type<T> const first, word_type const &path)¶ Find the node that a path starting at a given node leads to.
- Complexity
Linear in the length of
path
.
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
first – the starting node.
path – the path to follow.
- Throws
LibsemigroupsException – if
first
is not a node in the digraph orpath
contains a value that is not an edge-label.- Returns
A value of type ActionDigraph::node_type. If one or more edges in
path
are not defined, then UNDEFINED is returned.
-
template<typename T>
node_type<T> libsemigroups::action_digraph_helper::follow_path_nc(ActionDigraph<T> const &ad, node_type<T> const from, word_type const &path) noexcept¶ Follow the path from a specified node labelled by a word.
This function returns the last node on the path in the action digraph
ad
starting at the nodefrom
labelled bypath
or libsemigroups::UNDEFINED.- Complexity
At worst the length of
path
.
Warning
No checks on the arguments of this function are performed.
- Template Parameters
T – the node type of the action digraph
- Parameters
ad – an action digraph
from – the source node
path – the word
- Throws
This – function is
noexcept
and is guaranteed never to throw.- Returns
A value of type ActionDigraph::node_type.
-
template<typename T, typename S>
node_type<T> libsemigroups::action_digraph_helper::follow_path_nc(ActionDigraph<T> const &ad, node_type<T> const from, S first, S last) noexcept¶ Follow the path from a specified node labelled by a word.
This function returns the last node on the path in the action digraph
ad
starting at the nodefrom
labelled by \([first, last)\) or libsemigroups::UNDEFINED.- Complexity
At worst the distance from
first
tolast
.
Warning
No checks on the arguments of this function are performed.
- Parameters
ad – an action digraph
from – the source node
first – iterator into a word
last – iterator into a word.
- Throws
This – function is
noexcept
and is guaranteed never to throw.- Returns
A value of type ActionDigraph::node_type.
-
template<typename T, typename S>
std::pair<node_type<T>, S> libsemigroups::action_digraph_helper::last_node_on_path(ActionDigraph<T> const &ad, node_type<T> from, S const &first, S const &last)¶ Returns the last node on the path labelled by a word and an iterator to the position in the word reached.
- Complexity
At worst the distance from
first
tolast
.
- Template Parameters
T – the node type of the action digraph
S – the type of the iterators into a word
- Parameters
ad – an action digraph
from – the source node
first – iterator into a word
last – iterator into a word.
- Throws
LibsemigroupsException – if any of the letters in word
[first, last)
is out of bounds.- Returns
A pair consisting of ActionDigraph::node_type and
S
.
-
template<typename T, typename S>
std::pair<node_type<T>, S> libsemigroups::action_digraph_helper::last_node_on_path_nc(ActionDigraph<T> const &ad, node_type<T> from, S const &first, S const &last) noexcept¶ Returns the last node on the path labelled by a word and an iterator to the position in the word reached.
- Complexity
At worst the distance from
first
tolast
.
Warning
No checks on the arguments of this function are performed.
- Template Parameters
T – the node type of the action digraph
S – the type of the iterators into a word
- Parameters
ad – an action digraph
from – the source node
first – iterator into a word
last – iterator into a word.
- Throws
This – function is
noexcept
and is guaranteed never to throw.- Returns
A pair consisting of ActionDigraph::node_type and
S
.
-
template<typename T>
bool libsemigroups::action_digraph_helper::is_acyclic(ActionDigraph<T> const &ad)¶ Check if a digraph is acyclic.
A digraph is acyclic if every directed cycle on the digraph is trivial.
- Complexity
\(O(m + n)\) where \(m\) is the number of nodes in the ActionDigraph
ad
and \(n\) is the number of edges. Note that for ActionDigraph objects the number of edges is always at most \(mk\) where \(k\) is the ActionDigraph::out_degree.
- Example
ActionDigraph<size_t> ad; ad.add_nodes(2); ad.add_to_out_degree(1); ad.add_edge(0, 1, 0); ad.add_edge(1, 0, 0); action_digraph_helper::is_acyclic(ad); // returns false
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.
-
template<typename T>
bool libsemigroups::action_digraph_helper::is_acyclic(ActionDigraph<T> const &ad, node_type<T> source)¶ Check if the subdigraph induced by the nodes reachable from a source node is acyclic.
A digraph is acyclic if every directed cycle on the digraph is trivial.
- Complexity
\(O(m + n)\) where \(m\) is the number of nodes in the ActionDigraph
ad
and \(n\) is the number of edges. Note that for ActionDigraph objects the number of edges is always at most \(mk\) where \(k\) is the ActionDigraph::out_degree.
- Example
ActionDigraph<size_t> ad; ad.add_nodes(4); ad.add_to_out_degree(1); ad.add_edge(0, 1, 0); ad.add_edge(1, 0, 0); ad.add_edge(2, 3, 0); action_digraph_helper::is_acyclic(ad); // returns false action_digraph_helper::is_acyclic(ad, 0); // returns false action_digraph_helper::is_acyclic(ad, 1); // returns false action_digraph_helper::is_acyclic(ad, 2); // returns true action_digraph_helper::is_acyclic(ad, 3); // returns true
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
source – the source node.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.
-
template<typename T>
bool libsemigroups::action_digraph_helper::is_reachable(ActionDigraph<T> const &ad, node_type<T> const source, node_type<T> const target)¶ Check if there is a path from one node to another.
- Complexity
\(O(m + n)\) where \(m\) is the number of nodes in the ActionDigraph
ad
and \(n\) is the number of edges. Note that for ActionDigraph objects the number of edges is always at most \(mk\) where \(k\) is the ActionDigraph::out_degree.- Example
ActionDigraph<size_t> ad; ad.add_nodes(4); ad.add_to_out_degree(1); ad.add_edge(0, 1, 0); ad.add_edge(1, 0, 0); ad.add_edge(2, 3, 0); action_digraph_helper::is_reachable(ad, 0, 1); // returns true action_digraph_helper::is_reachable(ad, 1, 0); // returns true action_digraph_helper::is_reachable(ad, 1, 2); // returns false action_digraph_helper::is_reachable(ad, 2, 3); // returns true action_digraph_helper::is_reachable(ad, 3, 2); // returns false
Note
If
source
andtarget
are equal, then, by convention, we considertarget
to be reachable fromsource
, via the empty path.- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
source – the source node.
target – the source node.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.
-
template<typename T>
detail::topological_sort_type<T> libsemigroups::action_digraph_helper::topological_sort(ActionDigraph<T> const &ad)¶ Returns the nodes of the digraph 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 nodem
, thenm
occurs beforen
in the vector.- Complexity
\(O(m + n)\) where \(m\) is the number of nodes in the ActionDigraph
ad
and \(n\) is the number of edges. Note that for ActionDigraph objects the number of edges is always at most \(mk\) where \(k\) is the ActionDigraph::out_degree.
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A std::vector<ActionDigraph<T>::node_type> that contains the nodes of
ad
in topological order (if possible) and is otherwise empty.
-
template<typename T>
detail::topological_sort_type<T> libsemigroups::action_digraph_helper::topological_sort(ActionDigraph<T> const &ad, node_type<T> source)¶ Returns the nodes of the digraph 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 nodem
, thenm
occurs beforen
in the vector, and the last item in the vector issource
.- Complexity
At worst \(O(m + n)\) where \(m\) is the number of nodes in the subdigraph of those nodes reachable from
source
and \(n\) is the number of edges.
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
source – the source node.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A std::vector<ActionDigraph<T>::node_type> that contains the nodes of
ad
in topological order (if possible) and is otherwise empty.
-
template<typename T, typename U>
void libsemigroups::action_digraph_helper::add_cycle(ActionDigraph<T> &ad, U first, U last)¶ Adds a cycle involving the specified range of nodes.
- Complexity
\(O(m)\) where \(m\) is the distance between
first
andlast
.
Note
The edges added by this function are all labelled
0
.- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
U – the type of an iterator pointing to nodes of an ActionDigraph
- Parameters
ad – the ActionDigraph object to add a cycle to.
first – a const iterator to nodes of
ad
last – a const iterator to nodes of
ad
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename T>
void libsemigroups::action_digraph_helper::add_cycle(ActionDigraph<T> &ad, size_t N)¶ Adds a cycle consisting of
N
new nodes.- Complexity
\(O(N)\) where \(N\) is the second parameter.
Note
The edges added by this function are all labelled
0
.- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to add a cycle to.
N – the length of the cycle and number of new nodes to add.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename T>
ActionDigraph<T> libsemigroups::action_digraph_helper::make(size_t num_nodes, std::initializer_list<std::initializer_list<T>> il)¶ Constructs a digraph from number of nodes and an
initializer_list
.This function constructs an ActionDigraph from its arguments whose out-degree is specified by the length of the first
initializer_list
in the 2nd parameter.- Complexity
\(O(mn)\) where \(m\) is the length of
il
and \(n\) is the parameternum_nodes
.- Example
// Construct an action digraph with 5 nodes and 10 edges (7 specified) action_digraph_helper::make<uint8_t>( 5, {{0, 0}, {1, 1}, {2}, {3, 3}});
- Template Parameters
T – the type of the nodes of the digraph
- Parameters
num_nodes – the number of nodes in the digraph.
il – the out-neighbors of the digraph.
- Throws
LibsemigroupsException – if ActionDigraph<T>::add_edge throws when adding edges from
il
.- Returns
A value of type ActionDigraph.
-
template<typename T>
bool libsemigroups::action_digraph_helper::is_connected(ActionDigraph<T> const &ad)¶ Check if a digraph is connected.
A digraph is connected if for every pair of nodes \(u\) and \(v\) there exists a sequence \(u_0 := u, \ldots, u_{n - 1} := v\) such that either \((u_i, u_{i + 1})\) or \((u_{i + 1}, u_i)\) is an edge. Note that \(u\) and \(v\) can be equal, and the sequence above can be of length \(0\).
- Complexity
\(O(m + n)\) where \(m\) is the number of nodes in the ActionDigraph
ad
and \(n\) is the number of edges. Note that for ActionDigraph objects the number of edges is always at most \(mk\) where \(k\) is the ActionDigraph::out_degree.
- Example
auto ad = action_digraph_helper::make<uint8_t>( 5, {{0, 0}, {1, 1}, {2}, {3, 3}}); action_digraph_helper::is_connected(ad); // returns false
- Template Parameters
T – the type used as the template parameter for the ActionDigraph.
- Parameters
ad – the ActionDigraph object to check.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.