Trait-based Strongly Connected Components Calculation

Based on Tarjan's SCC algorithm. Just implement the Scc trait on your graph type to be able to compute the SCC in linear time.

lib.rs:

This crate provides the [Scc] trait that you can implement on any directed graph datatype to compute the Strongly Connected Components (SCC) in linear time, based on Tarjan's SCC algorithm.

Usage

First, implement the Scc trait on your custom graph type, providing enough information about the graph structure:

struct MyGraphType {
  vertices: Vec<Vertex>,
  edges: HashMap<Vertex, HashSet<Vertex>>
}

impl Scc for MyGraphType {
  type Vertex = Vertex;

  fn vertices(&self) -> impl '_ + IntoIterator<Item = Self::Vertex> {
    self.vertices.iter().copied()
  }

  fn successors(&self, v: Self::Vertex) -> impl '_ + IntoIterator<Item = Self::Vertex> {
    self.edges[&v].iter().copied()
  }
}

This trait is also implemented for a few default types like Vec<HashSet<usize>> and HashMap<T, HashSet<T>>. It provides the strongly_connected_components method returning the strongly connected Components of the graph. This type allows you to iterate through the components, get successors of a component, order the components by depth, etc.

use scc_trait::Scc;

// Compute the strongly connected components.
let components = graph.strongly_connected_components();

// Print vertices grouped by component.
for component in components {
  for vertex in component {
    println!("{vertex}");
  }
}

// Order components by depth.
for i in components.order_by_depth() {
  let component = components.get_by_index(i).unwrap();
  // ...
}