Struct ra_ap_rustc_data_structures::graph::scc::Sccs

pub struct Sccs<N: Idx, S: Idx> { /* private fields */ }

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.

Implementations

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

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

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

pub fn scc_data(&self) -> &SccData<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> 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,