swh_graph/
stats.rs

1/*
2 * Copyright (C) 2024  The Software Heritage developers
3 * See the AUTHORS file at the top-level directory of this distribution
4 * License: GNU General Public License version 3, or any later version
5 * See top-level LICENSE file for more information
6 */
7
8//! Computes statistics on the graph
9
10use rayon::prelude::*;
11
12use crate::graph::*;
13
14pub struct DegreeStats {
15    pub min: u64,
16    pub max: u64,
17    pub avg: f64,
18}
19
20pub fn outdegree<G: SwhForwardGraph + Sync>(graph: &G) -> DegreeStats {
21    let identity = (u64::MAX, u64::MIN, 0u64);
22    let (min, max, total) = crate::utils::shuffle::par_iter_shuffled_range(0..graph.num_nodes())
23        .into_par_iter()
24        // Compute stats in parallel
25        .fold(
26            || identity,
27            |(min, max, total), node: usize| {
28                let outdegree =
29                    u64::try_from(graph.outdegree(node)).expect("outdegree overflowed u64");
30                (
31                    std::cmp::min(min, outdegree),
32                    std::cmp::max(max, outdegree),
33                    total.saturating_add(outdegree),
34                )
35            },
36        )
37        // Merge each thread's work
38        .reduce(
39            || identity,
40            |(min1, max1, total1), (min2, max2, total2)| {
41                (
42                    std::cmp::min(min1, min2),
43                    std::cmp::max(max1, max2),
44                    total1.saturating_add(total2),
45                )
46            },
47        );
48    DegreeStats {
49        min,
50        max,
51        avg: (total as f64) / (graph.num_nodes() as f64),
52    }
53}