Struct TarjanScc

pub struct TarjanScc<N> { /* private fields */ }

A reusable state for computing the strongly connected components using Tarjan’s algorithm.

Implementations

impl<N> TarjanScc<N>

pub fn new() -> Self

Creates a new TarjanScc

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.

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

impl<N: Debug> Debug for TarjanScc<N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<N> Default for TarjanScc<N>

fn default() -> Self

Returns the “default value” for a type.