uni_algo/algo/algorithms/
betweenness.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Betweenness Centrality Algorithm (Brandes').
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use rayon::prelude::*;
9use std::collections::VecDeque;
10use uni_common::core::id::Vid;
11
12pub struct Betweenness;
13
14#[derive(Debug, Clone)]
15pub struct BetweennessConfig {
16    pub normalize: bool,
17    pub sampling_size: Option<usize>, // If None, exact computation (all nodes)
18}
19
20impl Default for BetweennessConfig {
21    fn default() -> Self {
22        Self {
23            normalize: true,
24            sampling_size: None,
25        }
26    }
27}
28
29pub struct BetweennessResult {
30    pub scores: Vec<(Vid, f64)>,
31}
32
33impl Algorithm for Betweenness {
34    type Config = BetweennessConfig;
35    type Result = BetweennessResult;
36
37    fn name() -> &'static str {
38        "betweenness"
39    }
40
41    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
42        let n = graph.vertex_count();
43        if n == 0 {
44            return BetweennessResult { scores: Vec::new() };
45        }
46
47        // Determine source nodes (all or sample)
48        let mut sources: Vec<u32> = (0..n as u32).collect();
49        if let Some(size) = config.sampling_size
50            && size < n
51        {
52            use rand::seq::SliceRandom;
53            let mut rng = rand::thread_rng();
54            sources.shuffle(&mut rng);
55            sources.truncate(size);
56        }
57
58        // Parallel execution of Brandes' algorithm
59        // Use fold/reduce to accumulate scores thread-locally, avoiding Mutex contention.
60        let mut cb = sources
61            .par_iter()
62            .fold(
63                || vec![0.0; n],
64                |mut acc_cb, &s| {
65                    // Stack S, queue Q
66                    let mut s_stack = Vec::with_capacity(n);
67                    let mut q = VecDeque::with_capacity(n);
68
69                    // Path counts (sigma) and distances (d)
70                    let mut d: Vec<i32> = vec![-1; n];
71                    let mut sigma: Vec<u64> = vec![0; n];
72                    let mut p: Vec<Vec<u32>> = vec![Vec::new(); n]; // Predecessors
73
74                    sigma[s as usize] = 1;
75                    d[s as usize] = 0;
76                    q.push_back(s);
77
78                    // BFS
79                    while let Some(v) = q.pop_front() {
80                        s_stack.push(v);
81                        let dist_v = d[v as usize];
82
83                        for &w in graph.out_neighbors(v) {
84                            // Path discovery
85                            if d[w as usize] < 0 {
86                                d[w as usize] = dist_v + 1;
87                                q.push_back(w);
88                            }
89                            // Path counting
90                            if d[w as usize] == dist_v + 1 {
91                                sigma[w as usize] += sigma[v as usize];
92                                p[w as usize].push(v);
93                            }
94                        }
95                    }
96
97                    // Accumulation
98                    let mut delta = vec![0.0; n];
99                    while let Some(w) = s_stack.pop() {
100                        for &v in &p[w as usize] {
101                            if sigma[w as usize] > 0 {
102                                delta[v as usize] += (sigma[v as usize] as f64
103                                    / sigma[w as usize] as f64)
104                                    * (1.0 + delta[w as usize]);
105                            }
106                        }
107                        if w != s {
108                            acc_cb[w as usize] += delta[w as usize];
109                        }
110                    }
111                    acc_cb
112                },
113            )
114            .reduce(
115                || vec![0.0; n],
116                |mut a, b| {
117                    for (x, y) in a.iter_mut().zip(b.iter()) {
118                        *x += y;
119                    }
120                    a
121                },
122            );
123
124        // Normalize
125        if config.normalize && n > 2 {
126            // For directed graphs: normalizer = 1 / ((n-1)(n-2))
127            // For undirected: 2 / ((n-1)(n-2))
128            // We assume directed here matching GraphProjection structure unless we detect otherwise,
129            // but standard algo.betweenness usually normalizes for directed.
130            let norm_factor = 1.0 / ((n - 1) as f64 * (n - 2) as f64);
131            for score in cb.iter_mut() {
132                *score *= norm_factor;
133            }
134        }
135
136        let results = cb
137            .into_iter()
138            .enumerate()
139            .map(|(i, score)| (graph.to_vid(i as u32), score))
140            .collect();
141
142        BetweennessResult { scores: results }
143    }
144}
uni_algo/algo/algorithms/betweenness.rs

uni_algo/algo/algorithms/
betweenness.rs
