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 stream os. 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 or path 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 node from labelled by path 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 node from labelled by \([first, last)\) or libsemigroups::UNDEFINED.

Complexity

At worst the distance from first to last.

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 to last.

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 to last.

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 and target are equal, then, by convention, we consider target to be reachable from source, 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 node m, then m occurs before n 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 node m, then m occurs before n in the vector, and the last item in the vector is source.

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 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

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 parameter num_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.