Struct rustc_data_structures::graph::scc::Sccs

pub struct Sccs<N: Idx, S: Idx> {
    scc_indices: IndexVec<N, S>,
    scc_data: SccData<S>,
}

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>

Data about each SCC.

Implementations

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

pub fn new(
    graph: &impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors
) -> Self

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> DirectedGraph for Sccs<N, S>

type Node = S

impl<'graph, N: Idx, S: Idx> GraphSuccessors<'graph> for Sccs<N, S>

type Item = S

type Iter = Cloned<Iter<'graph, S>>

impl<N: Idx, S: Idx> WithNumEdges for Sccs<N, S>

fn num_edges(&self) -> usize

impl<N: Idx, S: Idx + Ord> WithNumNodes for Sccs<N, S>

fn num_nodes(&self) -> usize

impl<N: Idx, S: Idx + Ord> WithSuccessors for Sccs<N, S>

fn successors(&self, node: S) -> <Self as GraphSuccessors<'_>>::Iter

fn depth_first_search(&self, from: Self::Node) -> DepthFirstSearch<'_, Self> where
    Self: WithNumNodes,

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