2 releases (1 stable)
1.0.0 | Nov 19, 2024 |
---|---|
0.1.0 | Aug 25, 2024 |
#1158 in Algorithms
149 downloads per month
12KB
240 lines
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();
// ...
}