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
>
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.
- Return
A value of type ActionDigraph::node_type. If one or more edges in
path
are not defined, then libsemigroups::UNDEFINED is returned.- 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.
- Exceptions
LibsemigroupsException
: iffirst
is not a node in the digraph orpath
contains a value that is not an edge-label.
-
template<typename
T
>
boollibsemigroups::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.
- Return
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 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.
- 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<typename
T
>
boollibsemigroups::action_digraph_helper
::
is_acyclic
(ActionDigraph<T> const &ad, node_type<T> const 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.
- Return
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 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.source
: the source node.
- 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<typename
T
>
boollibsemigroups::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.
- Return
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 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.- Note
If
source
andtarget
are equal, then, by convention, we considertarget
to be reachable fromsource
, via the empty path.- 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
- 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.
-
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.- Return
A std::vector<ActionDigraph<T>::node_type> that contains the nodes of
ad
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 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.
-
template<typename
T
>
detail::topological_sort_type<T>libsemigroups::action_digraph_helper
::
topological_sort
(ActionDigraph<T> const &ad, node_type<T> const 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
.- Return
A std::vector<ActionDigraph<T>::node_type> that contains the nodes of
ad
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 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.
-
template<typename
T
, typenameU
>
voidlibsemigroups::action_digraph_helper
::
add_cycle
(ActionDigraph<T> &ad, U const first, U const last) Adds a cycle involving the specified range of nodes.
- Return
(None)
- Exceptions
This function guarantees not to throw a LibsemigroupsException.
- 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 ofad
last
: a const iterator to nodes ofad
-
template<typename
T
>
voidlibsemigroups::action_digraph_helper
::
add_cycle
(ActionDigraph<T> &ad, size_t const N) Adds a cycle consisting of
N
new nodes.- Return
(None)
- 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
.- 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.