Subdigraphs

This page contains information about the functionality of the ActionDigraph class for finding spanning forests and other subdigraphs.

inline void libsemigroups::ActionDigraph::induced_subdigraph(node_type first, node_type last)

inline Forest const &libsemigroups::ActionDigraph::reverse_spanning_forest() const

Returns a reverse spanning forest of the strongly connected components.

Returns a Forest comprised of spanning trees for each scc of this, rooted on the minimum node of that component, with edges oriented towards the root.

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 reference to a Forest.

inline Forest const &libsemigroups::ActionDigraph::spanning_forest() const

Returns a spanning forest of the strongly connected components.

Returns a Forest comprised of spanning trees for each scc of this, rooted on the minimum node of that component, with edges oriented away from the root.

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 reference to a Forest.