# ActionDigraph¶

template<typename T>
class ActionDigraph : private libsemigroups::ActionDigraphBase

Defined in digraph.hpp.

This class represents the digraph of an action of a semigroup on a set. If the digraph has n nodes, they are represented by the numbers $${0, ..., n - 1}$$, and every node has the same number m of out-edges (edges with source that node and range any other node). The number m is referred to as the out-degree of the digraph, or any of its nodes.

Template Parameters

T – the type of the nodes in the digraph, must be an unsigned integer type.

Subclassed by libsemigroups::DigraphWithSources< coset_type >, libsemigroups::DigraphWithSources< N >, libsemigroups::DigraphWithSources< T >

## Member types¶

 adjacency_matrix_type The type of the adjacency matrix. algorithm An enum for specifying the algorithm to the functions number_of_paths() . const_iterator_edges The type of an iterator pointing to the out-edges of a node in a digraph. const_iterator_nodes The type of an iterator pointing to the nodes of a digraph. const_iterator_scc The type of an iterator pointing to the nodes in a strongly connected component of a digraph. const_iterator_scc_roots The type of an iterator pointing to the roots of a strongly connected components of a digraph. const_iterator_sccs The type of an iterator pointing to the strongly connected components of a digraph. const_pilo_iterator Return type of cbegin_pilo and cend_pilo . const_pislo_iterator Return type of cbegin_pislo and cend_pislo . const_pstislo_iterator Return type of cbegin_pstislo and cend_pstislo . const_reverse_iterator_nodes The type of a reverse iterator pointing to the nodes of a digraph. label_type The type of edge labels in a digraph. node_type The type of nodes in a digraph. scc_index_type The type of an index in a strongly connected component of a digraph. size_type Unsigned integer type.

## Constructors¶

 ActionDigraph(ActionDigraph const&) Default copy constructor. ActionDigraph(ActionDigraph&&) Default move constructor. ActionDigraph(T, T) Construct from number of nodes and out degree. operator=(ActionDigraph const&) Default copy assignment constructor. operator=(ActionDigraph&&) Default move assignment constructor.

## Static member functions¶

 random(T, T, T, std::mt19937) Construct a random digraph from number of nodes, edges, and out-degree. random(T, T, std::mt19937) Construct a random digraph from number of nodes and out-degree. random_acyclic(T, T, T, std::mt19937) Construct a random acyclic digraph from number of nodes, edges, and out-degree.

## Initialization¶

 add_edge(node_type, node_type, label_type) Add an edge from one node to another with a given label. add_edge_nc(node_type, node_type, label_type) Add an edge from one node to another with a given label. add_nodes(size_t) Adds a number of new nodes. add_to_out_degree(size_t) Adds to the out-degree. init(T,T) Re-initialize the digraph to have m nodes and out-degree n. remove_edge_nc(node_type, label_type) Remove an edge from a node with a given label. reserve(T, T) const Ensures that the digraph has capacity for a given number of nodes, and out-degree. restrict(size_t) Restrict the digraph to its first n nodes. swap_edges_nc(node_type, node_type, label_type) Swaps the edge with specified label from one node with another.

## Operators¶

 operator==(ActionDigraph const &) const Check if two action digraphs are equal.

## Nodes, edges, neighbors¶

 cbegin_edges(node_type) const Returns a random access iterator pointing at the first neighbor of a node. cbegin_edges_nc(node_type) const noexcept Returns a random access iterator pointing at the first neighbor of a node. cbegin_nodes() const noexcept Returns a random access iterator pointing at the first node of the digraph. cend_edges(node_type) const Returns a random access iterator pointing one-past-the-last neighbor of a node. cend_edges_nc(node_type) const noexcept Returns a random access iterator pointing one-past-the-last neighbor of a node. cend_nodes() const noexcept Returns a random access iterator pointing one-past-the-last node of the digraph. crbegin_nodes() const noexcept Returns a random access iterator pointing at the last node of the digraph. crend_nodes() const noexcept Returns a random access iterator pointing one-past-the-first node of the digraph. neighbor(node_type, label_type) const Get the range of the edge with given source node and label. next_neighbor(node_type, label_type) const Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED . number_of_edges() const Returns the number of edges. number_of_edges(node_type) const Returns the number of edges with given source node. number_of_nodes() const noexcept Returns the number of nodes. out_degree() const noexcept Returns the out-degree. remove_all_edges() Remove all of the edges in the digraph. table() const noexcept Returns a const reference to the underlying array. unsafe_neighbor(node_type, label_type) const Get the range of the edge with given source node and label. unsafe_next_neighbor(node_type, label_type) const Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED . validate() const noexcept Check every node has exactly out_degree() out-edges.

## Strongly connected components¶

 cbegin_scc(scc_index_type) const Returns an iterator pointing to the first node in the scc with the specified id-number. cbegin_scc_roots() const Returns an iterator pointing to the root of the first scc. cbegin_sccs() const Returns an iterator pointing to the vector of nodes in the first scc. cend_scc(scc_index_type) const Returns an iterator pointing one past the last node in the scc with the specified id-number. cend_scc_roots() const Returns an iterator pointing one past the root of the last scc. cend_sccs() const Returns an iterator pointing one past the last vector of nodes in the final scc. number_of_scc() const Returns the number of strongly connected components. root_of_scc(node_type) const Returns the root of a strongly connected components containing a given node. scc_id(node_type) const Returns the id-number of the strongly connected component of a node.

## Subdigraphs¶

 induced_subdigraph(node_type,node_type) reverse_spanning_forest() const Returns a reverse spanning forest of the strongly connected components. spanning_forest() const Returns a spanning forest of the strongly connected components.

## Path iterators¶

 cbegin_panilo(node_type, size_t, size_t) const Returns an iterator for PANILO (Path And Node In Lex Order). cbegin_panislo(node_type, size_t, size_t) const Returns an iterator for PANISLO (Path And Node In Short Lex Order). cbegin_pilo(node_type, size_t, size_t) const Returns an iterator for PILO (Path In Lex Order). cbegin_pislo(node_type, size_t, size_t) const Returns an iterator for PISLO (Path In Short Lex Order). cbegin_pstilo(node_type, node_type, size_t, size_t) const Returns an iterator for PSTILO (Path Source Target In Lex Order). cbegin_pstislo(node_type, node_type, size_t, size_t) const Returns an iterator for PSTISLO (Path Source Target In Short Lex Order). cend_panilo() const Returns an iterator for PANILO (Path And Node In Lex Order). cend_panislo() const Returns an iterator for PANISLO (Path And Node In Short Lex Order). cend_pilo() const Returns an iterator for PILO (Path In Lex Order). cend_pislo() const Returns an iterator for PISLO (Path In Short Lex Order). cend_pstilo() const Returns an iterator for PSTILO (Path Source Target In Lex Order). cend_pstislo() const Returns an iterator for PSTISLO (Path Source Target In Short Lex Order).

## Counting paths¶

 number_of_paths(node_type) const Returns the number of paths from a source node. number_of_paths(node_type, node_type, size_t, size_t, algorithm) const Returns the number of paths between a pair of nodes with length in a given range. number_of_paths(node_type, size_t, size_t, algorithm) const Returns the number of paths starting at a given node with length in a given range. number_of_paths_algorithm(node_type) const noexcept Returns the algorithm used by number_of_paths() . number_of_paths_algorithm(node_type, node_type, size_t, size_t) const Returns the algorithm used by number_of_paths() . number_of_paths_algorithm(node_type, size_t, size_t) const Returns the algorithm used by number_of_paths() .