webgraph_algo/sccs/
mod.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
8//! Algorithms used to compute and work with strongly connected components.
9//!
10//! There are two implementations for directed graph: [Tarjan's
11//! algorithm](tarjan) and [Kosaraju's algorithm](kosaraju). The former is to be
12//! preferred in almost all cases: Kosaraju's algorithm is slower and requires
13//! the transpose of the graph—it is mainly useful for testing and debugging.
14//!
15//! For symmetric (i.e., undirected) graphs there is a [sequential](symm_seq)
16//! and a [parallel](symm_par) implementation that computes connected
17//! components.
18//!
19//! # Examples
20//! ```
21//! use dsi_progress_logger::no_logging;
22//! use webgraph::{graphs::vec_graph::VecGraph};
23//! use webgraph_algo::sccs::*;
24//!
25//! let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
26//!
27//! // Let's build the graph SCCS with Tarjan's algorithm
28//! let mut scc = tarjan(graph, no_logging![]);
29//!
30//! // Let's sort the SCC by size
31//! let sizes = scc.sort_by_size();
32//!
33//! assert_eq!(sizes, vec![3, 1].into_boxed_slice());
34//! assert_eq!(scc.components(), &vec![0, 0, 0, 1]);
35//! ```
36
37mod tarjan;
38pub use tarjan::*;
39
40mod kosaraju;
41pub use kosaraju::*;
42mod symm_seq;
43pub use symm_seq::*;
44
45mod symm_par;
46pub use symm_par::*;
47
48use crate::llp;
49use rayon::{
50    iter::{IntoParallelRefMutIterator, ParallelIterator},
51    slice::ParallelSliceMut,
52};
53
54/// Strongly connected components.
55///
56/// An instance of this structure stores the [index of the
57/// component](Sccs::components) of each node. Components are numbered from 0 to
58/// [`num_components`](Sccs::num_components).
59///
60/// Moreover, this structure makes it possible to [sort the components by
61/// size](Sccs::sort_by_size), possibly using [parallel
62/// methods](Sccs::par_sort_by_size).
63pub struct Sccs {
64    num_components: usize,
65    components: Box<[usize]>,
66}
67
68impl Sccs {
69    pub fn new(num_components: usize, components: Box<[usize]>) -> Self {
70        Sccs {
71            num_components,
72            components,
73        }
74    }
75
76    /// Returns the number of strongly connected components.
77    pub fn num_components(&self) -> usize {
78        self.num_components
79    }
80
81    /// Returns a slice containing, for each node, the index of the component
82    /// it belongs to.
83    #[inline(always)]
84    pub fn components(&self) -> &[usize] {
85        &self.components
86    }
87
88    /// Returns the sizes of all components.
89    pub fn compute_sizes(&self) -> Box<[usize]> {
90        let mut sizes = vec![0; self.num_components()];
91        for &node_component in self.components() {
92            sizes[node_component] += 1;
93        }
94        sizes.into_boxed_slice()
95    }
96
97    /// Renumbers the components by decreasing size.
98    ///
99    /// After a call to this method, the sizes of strongly connected components
100    /// will decreasing in the component index. The method returns the sizes of
101    /// the components after the renumbering.
102    pub fn sort_by_size(&mut self) -> Box<[usize]> {
103        let mut sizes = self.compute_sizes();
104        assert!(sizes.len() == self.num_components());
105        let mut sort_perm = Vec::from_iter(0..sizes.len());
106        sort_perm.sort_unstable_by(|&x, &y| sizes[y].cmp(&sizes[x]));
107        let mut inv_perm = vec![0; sizes.len()];
108        sort_perm
109            .iter()
110            .enumerate()
111            .for_each(|(i, &x)| inv_perm[x] = i);
112
113        self.components
114            .iter_mut()
115            .for_each(|node_component| *node_component = inv_perm[*node_component]);
116        sizes.sort_by(|&x, &y| y.cmp(&x));
117        sizes
118    }
119
120    /// Renumbers the components by decreasing size using parallel methods.
121    ///
122    /// After a call to this method, the sizes of strongly connected components
123    /// will decreasing in the component index. The method returns the sizes of
124    /// the components after the renumbering.
125    pub fn par_sort_by_size(&mut self) -> Box<[usize]> {
126        let mut sizes = self.compute_sizes();
127        assert!(sizes.len() == self.num_components());
128        let mut sort_perm = Vec::from_iter(0..sizes.len());
129        sort_perm.par_sort_unstable_by(|&x, &y| sizes[y].cmp(&sizes[x]));
130        let mut inv_perm = vec![0; sizes.len()];
131        llp::invert_permutation(&sort_perm, &mut inv_perm);
132        self.components
133            .par_iter_mut()
134            .for_each(|node_component| *node_component = inv_perm[*node_component]);
135        sizes.sort_by(|&x, &y| y.cmp(&x));
136        sizes
137    }
138}
webgraph_algo/sccs/mod.rs

webgraph_algo/sccs/
mod.rs
