Strongly connected components¶
This page contains information about the strongly connected components functionality of the ActionDigraph
class.
-
inline const_iterator_scc libsemigroups::ActionDigraph::cbegin_scc(scc_index_type i) const¶
Returns an iterator pointing to the first node in the scc with the specified id-number.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().
Note
If an exception is thrown,
this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Parameters
i – the id-number of the scc.
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
.LibsemigroupsException – if
i
is not in the range0
tonumber_of_scc()
- 1.
- Returns
-
inline const_iterator_scc_roots libsemigroups::ActionDigraph::cbegin_scc_roots() const¶
Returns an iterator pointing to the root of the first scc.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().- Parameters
(None)
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
-
inline const_iterator_sccs libsemigroups::ActionDigraph::cbegin_sccs() const¶
Returns an iterator pointing to the vector of nodes in the first scc.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().- Parameters
(None)
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
-
inline const_iterator_scc libsemigroups::ActionDigraph::cend_scc(scc_index_type i) const¶
Returns an iterator pointing one past the last node in the scc with the specified id-number.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().
Note
If an exception is thrown,
this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Parameters
i – the id-number of the scc.
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
.LibsemigroupsException – if
i
is not in the range0
tonumber_of_scc()
- 1.
- Returns
-
inline const_iterator_scc_roots libsemigroups::ActionDigraph::cend_scc_roots() const¶
Returns an iterator pointing one past the root of the last scc.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().- Parameters
(None)
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
-
inline const_iterator_sccs libsemigroups::ActionDigraph::cend_sccs() const¶
Returns an iterator pointing one past the last vector of nodes in the final scc.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().- Parameters
(None)
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
-
inline size_t libsemigroups::ActionDigraph::number_of_scc() const¶
Returns the number of strongly connected components.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().- Parameters
(None)
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
A
size_t
.
-
inline node_type libsemigroups::ActionDigraph::root_of_scc(node_type nd) const¶
Returns the root of a strongly connected components containing a given node.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().
- Parameters
nd – a node.
- Throws
LibsemigroupsException – if it is not the case that every node has exactly out_degree() out-neighbors. In other words, if neighbor() is libsemigroups::UNDEFINED for any node
nd
and any labellbl
. If an exception is thrown,this
might be modified but is guaranteed to be in a valid state (basic exception guarantee).- Returns
The root of the scc containing the node
nd
, a value of node_type.
-
inline scc_index_type libsemigroups::ActionDigraph::scc_id(node_type nd) const¶
Returns the id-number of the strongly connected component of a node.
- Complexity
At most \(O(mn)\) where
m
is number_of_nodes() andn
is out_degree().
- Parameters
nd – the node.
- Throws
LibsemigroupsException – if
nd
is not valid.- Returns
The index of the node
nd
, a value of type scc_index_type.