Struct rustc_data_structures::graph::scc::Sccs

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

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§

source§

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

source

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

Compute SCCs without annotations.

source§

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

source

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

source

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

source

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

source

pub fn num_sccs(&self) -> usize

Returns the number of SCCs in the graph.

source

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.

source

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

Returns the SCC to which a node r belongs.

source

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

Returns the successors of the given SCC.

source

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

Construct the reverse graph of the SCC graph.

Trait Implementations§

source§

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

source§

type Node = S

source§

fn num_nodes(&self) -> usize

source§

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

source§

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

source§

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

Auto Trait Implementations§

§

impl<N, S, A> Freeze for Sccs<N, S, A>

§

impl<N, S, A> RefUnwindSafe for Sccs<N, S, A>

§

impl<N, S, A> Send for Sccs<N, S, A>
where S: Send, A: Send,

§

impl<N, S, A> Sync for Sccs<N, S, A>
where S: Sync, A: Sync,

§

impl<N, S, A> Unpin for Sccs<N, S, A>
where S: Unpin, A: Unpin,

§

impl<N, S, A> UnwindSafe for Sccs<N, S, A>
where S: UnwindSafe, A: UnwindSafe,

Blanket Implementations§

source§

impl<T> Aligned for T

source§

const ALIGN: Alignment = const ALIGN: Alignment = Alignment::of::<Self>();

Alignment of Self.
source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T> Instrument for T

source§

fn instrument(self, span: Span) -> Instrumented<Self>

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
source§

fn in_current_span(self) -> Instrumented<Self>

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> IntoEither for T

source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

source§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
source§

impl<T> WithSubscriber for T

source§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

fn with_current_subscriber(self) -> WithDispatch<Self>

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
source§

impl<'a, T> Captures<'a> for T
where T: ?Sized,

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