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, ()>
impl<N: Idx, S: Idx + Ord> Sccs<N, S, ()>
sourcepub fn new(graph: &impl Successors<Node = N>) -> Self
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>
impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A>
sourcepub fn new_with_annotation<F: Fn(N) -> A>(
graph: &impl Successors<Node = N>,
to_annotation: F,
) -> Self
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>
sourcepub fn all_sccs(&self) -> impl Iterator<Item = S>
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.
sourcepub fn successors(&self, scc: S) -> &[S]
pub fn successors(&self, scc: S) -> &[S]
Returns the successors of the given SCC.
Trait Implementations§
source§impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A>
impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A>
source§impl<N: Idx, S: Idx + Ord, A: Annotation> Successors for Sccs<N, S, A>
impl<N: Idx, S: Idx + Ord, A: Annotation> Successors for Sccs<N, S, A>
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>where
S: RefUnwindSafe,
A: RefUnwindSafe,
impl<N, S, A> Send for Sccs<N, S, A>
impl<N, S, A> Sync for Sccs<N, S, A>
impl<N, S, A> Unpin for Sccs<N, S, A>
impl<N, S, A> UnwindSafe for Sccs<N, S, A>where
S: UnwindSafe,
A: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> Instrument for T
impl<T> Instrument for T
source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
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 moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
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 moresource§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
impl<'a, T> Captures<'a> for Twhere
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