webgraph_algo/sccs/
kosaraju.rs

1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8use super::Sccs;
9use crate::prelude::*;
10use dsi_progress_logger::ProgressLog;
11use no_break::NoBreak;
12use std::ops::ControlFlow::Continue;
13use webgraph::traits::RandomAccessGraph;
14use webgraph::visits::{
15    Sequential,
16    depth_first::{EventNoPred, SeqNoPred},
17};
18
19/// Computes the strongly connected components of a graph using Kosaraju's algorithm.
20///
21/// # Arguments
22///
23/// * `graph`: the graph.
24///
25/// * `transpose`: the transpose of `graph`.
26///
27/// * `pl`: a progress logger.
28pub fn kosaraju(
29    graph: impl RandomAccessGraph,
30    transpose: impl RandomAccessGraph,
31    pl: &mut impl ProgressLog,
32) -> Sccs {
33    let num_nodes = graph.num_nodes();
34    pl.item_name("node");
35    pl.expected_updates(Some(num_nodes));
36    pl.start("Computing strongly connected components...");
37
38    let top_sort = top_sort(&graph, pl);
39    let mut number_of_components = 0;
40    let mut visit = SeqNoPred::new(&transpose);
41    let mut components = vec![0; num_nodes].into_boxed_slice();
42
43    visit
44        .visit(top_sort, |event| {
45            match event {
46                EventNoPred::Previsit { node, .. } => {
47                    pl.light_update();
48                    components[node] = number_of_components;
49                }
50                EventNoPred::Done { .. } => {
51                    number_of_components += 1;
52                }
53                _ => (),
54            }
55            Continue(())
56        })
57        .continue_value_no_break();
58
59    pl.done();
60
61    Sccs::new(number_of_components, components)
62}
webgraph_algo/sccs/kosaraju.rs

webgraph_algo/sccs/
kosaraju.rs
