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() and n 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 label lbl.
LibsemigroupsException – if i is not in the range 0 to number_of_scc() - 1.

Returns:

A const_iterator_scc.

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() and n 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 label lbl. If an exception is thrown, this might be modified but is guaranteed to be in a valid state (basic exception guarantee).
Returns:: A const_iterator_scc_roots.

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() and n 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 label lbl. If an exception is thrown, this might be modified but is guaranteed to be in a valid state (basic exception guarantee).
Returns:: A const_iterator_sccs.

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() and n 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 label lbl.
LibsemigroupsException – if i is not in the range 0 to number_of_scc() - 1.

Returns:

A const_iterator_scc.

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() and n 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 label lbl. If an exception is thrown, this might be modified but is guaranteed to be in a valid state (basic exception guarantee).
Returns:: A const_iterator_scc_roots.

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() and n 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 label lbl. If an exception is thrown, this might be modified but is guaranteed to be in a valid state (basic exception guarantee).
Returns:: A const_iterator_sccs.

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() and n 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 label lbl. 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() and n 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 label lbl. 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() and n 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.