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: if first is not a node in the digraph or path 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>
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.

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 and target are equal, then, by convention, we consider target to be reachable from source, 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)