pub struct TarjanScc<N> { /* private fields */ }
Expand description
A reusable state for computing the strongly connected components using Tarjan’s algorithm.
Implementations§
source§impl<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
pub fn node_component_index<G>(&self, g: G, v: N) -> usize
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().