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

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

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

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges(node_type i) const¶
Returns a random access iterator pointing onepastthelast neighbor of a node.
 Complexity
Constant.
 Parameters
i – a node in the digraph.
 Throws
LibsemigroupsException – if
i
is not valid. Returns

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges_nc(node_type i) const noexcept¶
Returns a random access iterator pointing onepastthelast neighbor of a node.
See also
 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

inline const_iterator_nodes libsemigroups::ActionDigraph::cend_nodes() const noexcept¶
Returns a random access iterator pointing onepastthelast node of the digraph.
 Complexity
Constant.
 Parameters
(None)
 Throws
(None) – This function is
noexcept
and is guaranteed never to throw. Returns

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

inline const_reverse_iterator_nodes libsemigroups::ActionDigraph::crend_nodes() const noexcept¶
Returns a random access iterator pointing onepastthefirst node of the digraph.
 Complexity
Constant.
 Parameters
(None)
 Throws
(None) – This function is
noexcept
and is guaranteed never to throw. Returns

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
orlbl
is not valid. Returns
Returns the node adjacent to
v
via the edge labelledlbl
, 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() thenx.first
andx.second
equal libsemigroups::UNDEFINED.See also
 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 inthis
. Returns
Returns a std::pair
x
where:x.first
is adjacent tov
via an edge labelledx.second
;x.second
is the minimum value in the range \([i, n)\) such thatneighbor(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() andn
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 outdegree.
 Complexity
Constant.
 Parameters
(None)
 Throws
(None) – This function is
noexcept
and is guaranteed never to throw. Returns
The number of outedges 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 andn
is the outdegree. 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
orlbl
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 labelledlbl
, 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() thenx.first
andx.second
equal libsemigroups::UNDEFINED.See also
 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 ofthis
. 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 tov
via an edge labelledx.second
;x.second
is the minimum value in the range \([i, n)\) such thatneighbor(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() outedges.
 Complexity
\(O(mn)\) where
m
is number_of_nodes() andn
is out_degree(). Parameters
(None)
 Throws
(None) – This function is
noexcept
and is guaranteed never to throw. Returns
A
bool
.