Struct rustc_data_structures::graph::scc::Sccs[−][src]

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

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>

Data about each SCC.

Implementations

[src]

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

[src]

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

[src]

pub fn num_sccs(&self) -> usize

Returns the number of SCCs in the graph.

[src]

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.

[src]

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

Returns the SCC to which a node r belongs.

[src]

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

Returns the successors of the given SCC.

[src]

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

Construct the reverse graph of the SCC graph.

Trait Implementations

[src]

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

type Node = S

[src]

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

type Item = S

fn successors(&self, node: S) -> Cloned<Iter<'_, S>>ⓘ
Notable traits for Cloned
`impl<'a, I, T> Iterator for Cloned where T: 'a + Clone, I: Iterator<Item = &'a T>, type Item = T;`

[src]

fn depth_first_search(&self, from: Self::Node) -> DepthFirstSearch<'_, Self>ⓘ
Notable traits for DepthFirstSearch<'_, G>
`impl<G> Iterator for DepthFirstSearch<'_, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, type Item = G::Node;`
where
Self: WithNumNodes,

Auto Trait Implementations

impl<N, S> RefUnwindSafe for Sccs<N, S> where
S: RefUnwindSafe,

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

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

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

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

Blanket Implementations

[src]

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

[src]

pub fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

[src]

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

[src]

pub fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

[src]

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

[src]

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

Mutably borrows from an owned value. Read more

[src]

impl<T> From<T> for T

[src]

pub fn from(t: T) -> T

Performs the conversion.

[src]

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

[src]

pub fn into(self) -> U

Performs the conversion.

[src]

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

type Error = Infallible

The type returned in the event of a conversion error.

[src]

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

Performs the conversion.

[src]

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

type Error = >::Error

The type returned in the event of a conversion error.

[src]

pub fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

[src]

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

[src]

impl<T> Erased for T

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

Struct rustc_data_structures::graph::scc::Sccs[−][src]

Fields

Implementations

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

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

pub fn num_sccs(&self) -> usize

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

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

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

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

Trait Implementations

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

type Node = S

impl<N: Idx, S: Idx, 'graph> 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> WithNumNodes for Sccs<N, S>

fn num_nodes(&self) -> usize

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

fn successors(&self, node: S) -> Cloned<Iter<'_, S>>ⓘNotable traits for Cloned<I>impl<'a, I, T> Iterator for Cloned<I> where T: 'a + Clone, I: Iterator<Item = &'a T>, type Item = T;

fn depth_first_search(&self, from: Self::Node) -> DepthFirstSearch<'_, Self>ⓘNotable traits for DepthFirstSearch<'_, G>impl<G> Iterator for DepthFirstSearch<'_, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, type Item = G::Node; where Self: WithNumNodes,

Auto Trait Implementations

impl<N, S> RefUnwindSafe for Sccs<N, S> where S: RefUnwindSafe,

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

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

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

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

Blanket Implementations

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

pub fn type_id(&self) -> TypeId

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

pub fn borrow(&self) -> &T

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

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

impl<T> From<T> for T

pub fn from(t: T) -> T

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

pub fn into(self) -> U

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

type Error = Infallible

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

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

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

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

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

impl<T> Erased for T

Layout

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

fn successors(&self, node: S) -> Cloned<Iter<'_, S>>ⓘ
Notable traits for Cloned<I>
`impl<'a, I, T> Iterator for Cloned<I> where T: 'a + Clone, I: Iterator<Item = &'a T>, type Item = T;`

fn depth_first_search(&self, from: Self::Node) -> DepthFirstSearch<'_, Self>ⓘ
Notable traits for DepthFirstSearch<'_, G>
`impl<G> Iterator for DepthFirstSearch<'_, G> where G: ?Sized + DirectedGraph + WithNumNodes + WithSuccessors, type Item = G::Node;`
where
Self: WithNumNodes,

impl<N, S> RefUnwindSafe for Sccs<N, S> where
S: RefUnwindSafe,

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

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

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

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

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

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

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

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

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

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

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