Struct Sccs

pub struct Sccs<N: Idx, S: Idx, A: Annotation = ()> {
    scc_indices: IndexVec<N, S>,
    scc_data: SccData<S, A>,
}

Strongly connected components (SCC) of a graph. The type N is the index type for the graph nodes and S is the index type for the SCCs. We can map from each node to the SCC that it participates in, and we also have the successors of each SCC.

Fields

scc_indices: IndexVec<N, S>

For each node, what is the SCC index of the SCC to which it belongs.

scc_data: SccData<S, A>

Data about all the SCCs.

Implementations

impl<N: Idx, S: Idx + Ord> Sccs<N, S, ()>

pub fn new(graph: &impl Successors<Node = N>) -> Self

Compute SCCs without annotations.

impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A>

pub fn new_with_annotation<F: Fn(N) -> A>( graph: &impl Successors<Node = N>, to_annotation: F, ) -> Self

Compute SCCs and annotate them with a user-supplied annotation

pub fn annotation(&self, scc: S) -> A

pub fn scc_indices(&self) -> &IndexSlice<N, S>

pub fn num_sccs(&self) -> usize

Returns the number of SCCs in the graph.

pub fn all_sccs(&self) -> impl Iterator<Item = S>

Returns an iterator over the SCCs in the graph.

The SCCs will be iterated in dependency order (or post order), meaning that if S1 -> S2, we will visit S2 first and S1 after. This is convenient when the edges represent dependencies: when you visit S1, the value for S2 will already have been computed.

pub fn scc(&self, r: N) -> S

Returns the SCC to which a node r belongs.

pub fn successors(&self, scc: S) -> &[S]

Returns the successors of the given SCC.

pub fn reverse(&self) -> VecGraph<S>

Construct the reverse graph of the SCC graph.

Trait Implementations

impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A>

type Node = S

fn num_nodes(&self) -> usize

impl<N: Idx, S: Idx + Ord, A: Annotation> NumEdges for Sccs<N, S, A>

fn num_edges(&self) -> usize

impl<N: Idx, S: Idx + Ord, A: Annotation> Successors for Sccs<N, S, A>

fn successors(&self, node: S) -> impl Iterator<Item = Self::Node>

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 72 bytes