webgraph_algo/sccs/
symm_seq.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;
14
15/// Connected components of symmetric graphs by sequential visits.
16pub fn symm_seq(graph: impl RandomAccessGraph, pl: &mut impl ProgressLog) -> Sccs {
17    // debug_assert!(check_symmetric(&graph)); requires sync
18
19    let num_nodes = graph.num_nodes();
20    pl.item_name("node");
21    pl.expected_updates(Some(num_nodes));
22    pl.start("Computing connected components...");
23
24    let mut visit = depth_first::SeqNoPred::new(&graph);
25    let mut component = Box::new_uninit_slice(num_nodes);
26    let mut number_of_components = 0;
27
28    visit
29        .visit(0..num_nodes, |event| {
30            match event {
31                depth_first::EventNoPred::Previsit { node, .. } => {
32                    pl.light_update();
33                    component[node].write(number_of_components);
34                }
35                depth_first::EventNoPred::Done { .. } => {
36                    number_of_components += 1;
37                }
38                _ => (),
39            }
40            Continue(())
41        })
42        .continue_value_no_break();
43
44    let component = unsafe { component.assume_init() };
45
46    pl.done();
47
48    Sccs::new(number_of_components, component)
49}
webgraph_algo/sccs/symm_seq.rs

webgraph_algo/sccs/
symm_seq.rs
