webgraph_algo/sccs/
symm_par.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 crate::prelude::*;
9use crossbeam_utils::CachePadded;
10use dsi_progress_logger::ConcurrentProgressLog;
11use no_break::NoBreak;
12use std::{
13    mem::MaybeUninit,
14    ops::ControlFlow::Continue,
15    sync::atomic::{AtomicUsize, Ordering},
16};
17use sync_cell_slice::SyncSlice;
18use webgraph::traits::RandomAccessGraph;
19use webgraph::visits::{
20    Parallel,
21    breadth_first::{EventNoPred, ParFairNoPred},
22};
23
24/// Connected components of symmetric graphs by parallel visits.
25pub fn symm_par(graph: impl RandomAccessGraph + Sync, pl: &mut impl ConcurrentProgressLog) -> Sccs {
26    // TODO debug_assert!(check_symmetric(&graph));
27
28    let num_nodes = graph.num_nodes();
29    pl.item_name("node");
30    pl.expected_updates(Some(num_nodes));
31    pl.start("Computing strongly connected components...");
32
33    let mut visit = ParFairNoPred::new(&graph);
34    let mut component = Box::new_uninit_slice(num_nodes);
35
36    let number_of_components = CachePadded::new(AtomicUsize::new(0));
37    let slice = component.as_sync_slice();
38
39    for node in 0..num_nodes {
40        visit
41            .par_visit_with([node], pl.clone(), |pl, event| {
42                match event {
43                    EventNoPred::Init { .. } => {}
44                    EventNoPred::Visit { node, .. } => {
45                        pl.light_update();
46                        unsafe {
47                            slice[node].set(MaybeUninit::new(
48                                number_of_components.load(Ordering::Relaxed),
49                            ))
50                        };
51                    }
52                    EventNoPred::Done { .. } => {
53                        number_of_components.fetch_add(1, Ordering::Relaxed);
54                    }
55                    _ => (),
56                }
57                Continue(())
58            })
59            .continue_value_no_break();
60    }
61
62    let component = unsafe { component.assume_init() };
63
64    pl.done();
65
66    Sccs::new(number_of_components.load(Ordering::Relaxed), component)
67}
webgraph_algo/sccs/symm_par.rs

webgraph_algo/sccs/
symm_par.rs
