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.

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()` .