Module sccs

Algorithms used to compute and work with strongly connected components.

There are two implementations for directed graph: Tarjan’s algorithm and Kosaraju’s algorithm. The former is to be preferred in almost all cases: Kosaraju’s algorithm is slower and requires the transpose of the graph—it is mainly useful for testing and debugging.

For symmetric (i.e., undirected) graphs there is a sequential and a parallel implementation that computes connected components.

Examples

use dsi_progress_logger::no_logging;
use webgraph::{graphs::vec_graph::VecGraph};
use webgraph_algo::sccs::*;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);

// Let's build the graph SCCS with Tarjan's algorithm
let mut scc = tarjan(graph, no_logging![]);

// Let's sort the SCC by size
let sizes = scc.sort_by_size();

assert_eq!(sizes, vec![3, 1].into_boxed_slice());
assert_eq!(scc.components(), &vec![0, 0, 0, 1]);

Structs

Sccs

Strongly connected components.

Functions

kosaraju

Computes the strongly connected components of a graph using Kosaraju’s algorithm.

symm_par

Connected components of symmetric graphs by parallel visits.

symm_seq

Connected components of symmetric graphs by sequential visits.

tarjan

Tarjan’s algorithm for strongly connected components.