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.
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::is_acyclic” with arguments (ActionDigraph<T> const&) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T> bool is_acyclic(ActionDigraph<T> const &ad)
- template<typename T> bool is_acyclic(ActionDigraph<T> const &ad, node_type<T> const source)
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::is_acyclic” with arguments (ActionDigraph<T> const&, node_type<T> const) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T> bool is_acyclic(ActionDigraph<T> const &ad)
- template<typename T> bool is_acyclic(ActionDigraph<T> const &ad, node_type<T> const source)
-
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.
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::topological_sort” with arguments (ActionDigraph<T> const&) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T> detail::topological_sort_type<T> topological_sort(ActionDigraph<T> const &ad)
- template<typename T> detail::topological_sort_type<T> topological_sort(ActionDigraph<T> const &ad, node_type<T> const source)
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::topological_sort” with arguments (ActionDigraph<T> const&, node_type<T> const) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T> detail::topological_sort_type<T> topological_sort(ActionDigraph<T> const &ad)
- template<typename T> detail::topological_sort_type<T> topological_sort(ActionDigraph<T> const &ad, node_type<T> const source)
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::add_cycle” with arguments (ActionDigraph<T>&, U const, U const) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T, typename U> void add_cycle(ActionDigraph<T> &ad, U const first, U const last)
- template<typename T> void add_cycle(ActionDigraph<T> &ad, size_t const N)
Warning
doxygenfunction: Unable to resolve multiple matches for function “libsemigroups::action_digraph_helper::add_cycle” with arguments (ActionDigraph<T>&, size_t const) in doxygen xml output for project “libsemigroups” from directory: ../build/xml. Potential matches:
- template<typename T, typename U> void add_cycle(ActionDigraph<T> &ad, U const first, U const last)
- template<typename T> void add_cycle(ActionDigraph<T> &ad, size_t const N)