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

webgraph_algo/sccs/
kosaraju.rs
