pub struct TarjanScc<N> { /* private fields */ }
Expand description
A reusable state for computing the strongly connected components using Tarjan’s algorithm.
Implementations
sourceimpl<N> TarjanScc<N>
impl<N> TarjanScc<N>
sourcepub fn run<G, F>(&mut self, g: G, f: F) where
G: IntoNodeIdentifiers<NodeId = N> + IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
F: FnMut(&[N]),
N: Copy + PartialEq,
pub fn run<G, F>(&mut self, g: G, f: F) where
G: IntoNodeIdentifiers<NodeId = N> + IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
F: FnMut(&[N]),
N: Copy + PartialEq,
[Generic] Compute the strongly connected components using Algorithm 3 in A Space-Efficient Algorithm for Finding Strongly Connected Components by David J. Pierce, which is a memory-efficient variation of Tarjan’s algorithm.
Calls f
for each strongly strongly connected component (scc).
The order of node ids within each scc is arbitrary, but the order of
the sccs is their postorder (reverse topological sort).
For an undirected graph, the sccs are simply the connected components.
This implementation is recursive and does one pass over the nodes.
sourcepub fn node_component_index<G>(&self, g: G, v: N) -> usize where
G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
N: Copy + PartialEq,
pub fn node_component_index<G>(&self, g: G, v: N) -> usize where
G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
N: Copy + PartialEq,
Returns the index of the component in which v has been assigned. Allows for using self as a lookup table for an scc decomposition produced by self.run().
Trait Implementations
Auto Trait Implementations
impl<N> RefUnwindSafe for TarjanScc<N> where
N: RefUnwindSafe,
impl<N> Send for TarjanScc<N> where
N: Send,
impl<N> Sync for TarjanScc<N> where
N: Sync,
impl<N> Unpin for TarjanScc<N> where
N: Unpin,
impl<N> UnwindSafe for TarjanScc<N> where
N: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more