Crate scc_trait

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();
  // ...
}

Structs

Components

Strongly connected components.

Iter

Traits

Scc

Graph on which strongly connected components can be computed.

Functions

depths

Returns the depth of each component.