Nodes, edges, neighbors¶

This page contains information about accessing the nodes, edges, and neighbours of the ActionDigraph class.

inline const_iterator_edges libsemigroups::ActionDigraph::cbegin_edges(node_type i) const¶

Returns a random access iterator pointing at the first neighbor of a node.

Complexity: Constant.

Parameters:: i – a node in the digraph.
Throws:: LibsemigroupsException – if i is not valid.
Returns:: A const_iterator_edges.

inline const_iterator_edges libsemigroups::ActionDigraph::cbegin_edges_nc(node_type i) const noexcept¶

Returns a random access iterator pointing at the first neighbor of a node.

See also

cbegin_edges.

Complexity: Constant.

Warning

No checks whatsoever on the validity of the arguments are performed.

Parameters:: i – a node in the digraph.
Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: A const_iterator_edges.

inline const_iterator_nodes libsemigroups::ActionDigraph::cbegin_nodes() const noexcept¶

Returns a random access iterator pointing at the first node of the digraph.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: An const_iterator_nodes.

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges(node_type i) const¶

Returns a random access iterator pointing one-past-the-last neighbor of a node.

Complexity: Constant.

Parameters:: i – a node in the digraph.
Throws:: LibsemigroupsException – if i is not valid.
Returns:: A const_iterator_edges.

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges_nc(node_type i) const noexcept¶

Returns a random access iterator pointing one-past-the-last neighbor of a node.

See also

cend_edges.

Complexity: Constant.

Warning

No checks whatsoever on the validity of the arguments are performed.

Parameters:: i – a node in the digraph.
Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: A const_iterator_edges.

inline const_iterator_nodes libsemigroups::ActionDigraph::cend_nodes() const noexcept¶

Returns a random access iterator pointing one-past-the-last node of the digraph.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: An const_iterator_nodes.

inline const_reverse_iterator_nodes libsemigroups::ActionDigraph::crbegin_nodes() const noexcept¶

Returns a random access iterator pointing at the last node of the digraph.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: An const_reverse_iterator_nodes.

inline const_reverse_iterator_nodes libsemigroups::ActionDigraph::crend_nodes() const noexcept¶

Returns a random access iterator pointing one-past-the-first node of the digraph.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: An const_reverse_iterator_nodes.

inline node_type libsemigroups::ActionDigraph::neighbor(node_type v, label_type lbl) const¶

Get the range of the edge with given source node and label.

Complexity: Constant.

Parameters:

v – the node
lbl – the label

Throws:

LibsemigroupsException – if v or lbl is not valid.

Returns:

Returns the node adjacent to v via the edge labelled lbl, or libsemigroups::UNDEFINED; both are values of type node_type.

inline std::pair<node_type, label_type> libsemigroups::ActionDigraph::next_neighbor(node_type v, label_type i) const¶

Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED.

If neighbor(v, i) equals libsemigroups::UNDEFINED for every value in the range \([i, n)\), where \(n\) is the return value of out_degree() then x.first and x.second equal libsemigroups::UNDEFINED.

See also

unsafe_next_neighbor.

Complexity: At worst \(O(n)\) where \(n\) equals out_degree().

Parameters:

v – the node
i – the label

Throws:

LibsemigroupsException – if v does not represent a node in this.

Returns:

Returns a std::pair x where:

x.first is adjacent to v via an edge labelled x.second;
x.second is the minimum value in the range \([i, n)\) such that neighbor(v, x.second) is not equal to libsemigroups::UNDEFINED where \(n\) is the return value of out_degree(); and

inline size_t libsemigroups::ActionDigraph::number_of_edges() const¶

Returns the number of edges.

Complexity: \(O(mn)\) where m is number_of_nodes() and n is out_degree().
Parameters: (None)

Throws:: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns:: The total number of edges, a value of type size_t.

inline size_t libsemigroups::ActionDigraph::number_of_edges(node_type n) const¶

Returns the number of edges with given source node.

Complexity: \(O(n)\) where n is out_degree().

Parameters:: n – the node.
Throws:: LibsemigroupsException – if n is not a node.
Returns:: A value of type size_t.

inline T libsemigroups::ActionDigraph::number_of_nodes() const noexcept¶

Returns the number of nodes.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: The number of nodes, a value of type T.

inline T libsemigroups::ActionDigraph::out_degree() const noexcept¶

Returns the out-degree.

Complexity: Constant.
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: The number of out-edges of every node, a value of type T.

inline void libsemigroups::ActionDigraph::remove_all_edges()¶

Remove all of the edges in the digraph.

Complexity: \(O(mn)\) where m is the number of nodes and n is the out-degree.
Parameters: (None)

Throws:: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns:: (None)

inline detail::DynamicArray2<T> const &libsemigroups::ActionDigraph::table() const noexcept¶

Returns a const reference to the underlying array.

This function returns a const reference to the underlying container for the edges of a digraph.

Parameters (None)
Complexity: Constant.

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: A const reference to a detail::DynamicArray2<node_type>.

inline node_type libsemigroups::ActionDigraph::unsafe_neighbor(node_type v, label_type lbl) const¶

Get the range of the edge with given source node and label.

Complexity: Constant.

Warning

This function is unsafe because it does not verify v or lbl is valid.

Parameters:

v – the node
lbl – the label

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

Returns the node adjacent to v via the edge labelled lbl, or libsemigroups::UNDEFINED; both are values of type node_type.

inline std::pair<node_type, label_type> libsemigroups::ActionDigraph::unsafe_next_neighbor(node_type v, label_type i) const¶

Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED.

If neighbor(v, i) equals libsemigroups::UNDEFINED for every value in the range \([i, n)\), where \(n\) is the return value of out_degree() then x.first and x.second equal libsemigroups::UNDEFINED.

See also

next_neighbor.

Complexity: At worst \(O(n)\) where \(n\) equals out_degree().

Warning

This function is unsafe because it is not verified that the parameter v represents a node of this.

Parameters:

v – the node
i – the label

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

Returns a std::pair x where:

x.first is adjacent to v via an edge labelled x.second;
x.second is the minimum value in the range \([i, n)\) such that neighbor(v, x.second) is not equal to libsemigroups::UNDEFINED where \(n\) is the return value of out_degree(); and

inline bool libsemigroups::ActionDigraph::validate() const noexcept¶

Check every node has exactly out_degree() out-edges.

Complexity: \(O(mn)\) where m is number_of_nodes() and n is out_degree().
Parameters: (None)

Throws:: (None) – This function is noexcept and is guaranteed never to throw.
Returns:: A bool.