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 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
-
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
- 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 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
-
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 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
-
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 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 andn
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
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() out-edges.
- 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
.