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.

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.

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> bool libsemigroups::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> 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.

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 node m, then m occurs before n 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 node m, then m occurs before n in the vector, and the last item in the vector is source.

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, typename U> void libsemigroups::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 and last.

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

template<typename T> void libsemigroups::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.