srcgraph_metrics/

betweenness.rs

//! Betweenness centrality — Brandes' algorithm. The headline perf target
//! versus networkx's Python-loop O(VE) implementation.
//!
//! Reference: Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality",
//! Journal of Mathematical Sociology 25(2):163-177, 2001.
//!
//! Time complexity: O(V·E) for unweighted graphs. We treat all edges as
//! unweighted (BFS), since the visiting tool's class-dependency graphs don't
//! carry semantically meaningful weights.
//!
//! See `DESIGN.md` (Phase 1) at the workspace root.
//!
//! @yah:ticket(R152-T4, "metrics::betweenness — Brandes' algorithm + perf benchmark vs networkx (headline win)")
//! @yah:assignee(agent:claude)
//! @yah:at(2026-05-12T22:14:30Z)
//! @yah:status(review)
//! @yah:parent(R152)
//! @yah:verify("cargo test -p srcgraph-metrics betweenness")
//! @yah:verify("cargo bench -p srcgraph-metrics --bench betweenness && python3 crates/srcgraph-metrics/benches/networkx_betweenness.py")
//! @yah:handoff("Brandes' O(VE) betweenness implemented generic over N:ClassNode/E:EdgeKind; networkx-default normalization (1/((n-1)(n-2))) for directed graphs. 6 unit tests (path, hub, parallel-split-credit, isolated, empty, 3-cycle). Harness-less bench at benches/betweenness.rs writes synthetic Erdős–Rényi-ish DAGs to target/bench-graphs/, companion Python script benches/networkx_betweenness.py reads the same GraphML and times nx.betweenness_centrality. Result on aarch64: Rust 0.24/7.0/20.7/90/604 ms vs networkx 9.4/207/898/3975/28771 ms for n=100/500/1000/2000/5000 — roughly 30–48× speedup, growing with n. Headline win confirmed.")

use petgraph::graph::{Graph, NodeIndex};
use petgraph::visit::EdgeRef;
use petgraph::Directed;
use serde::{Deserialize, Serialize};
use std::collections::VecDeque;

use srcgraph_core::{ClassNode, EdgeKind};

/// Per-node betweenness score, parallel to the input graph's node indices.
///
/// `scores[i]` is the centrality of `NodeIndex::new(i)`.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct BetweennessResult {
    pub scores: Vec<f64>,
    /// Whether `scores` were normalized to `[0, 1]` (matches networkx's default).
    pub normalized: bool,
}

impl BetweennessResult {
    pub fn get(&self, n: NodeIndex) -> f64 {
        self.scores[n.index()]
    }
}

/// Compute betweenness centrality for every node in `graph`.
///
/// `normalized=true` matches networkx's default behavior: scores are scaled by
/// `1 / ((n-1)·(n-2))` for directed graphs with `n ≥ 3`. For `n < 3` scores
/// are returned unscaled (would divide by zero).
///
/// Treats the graph as **directed** and unweighted. To run on an undirected
/// view of the same data, add reverse edges before calling.
pub fn compute_betweenness<N, E>(
    graph: &Graph<N, E, Directed>,
    normalized: bool,
) -> BetweennessResult
where
    N: ClassNode,
    E: EdgeKind,
{
    let n = graph.node_count();
    let mut cb = vec![0.0_f64; n];

    if n == 0 {
        return BetweennessResult { scores: cb, normalized: false };
    }

    // Precompute outgoing-neighbor lists once: avoids repeated graph-edge walks
    // inside the per-source BFS hot loop.
    let mut out: Vec<Vec<usize>> = vec![Vec::new(); n];
    for e in graph.edge_references() {
        out[e.source().index()].push(e.target().index());
    }

    let mut stack: Vec<usize> = Vec::with_capacity(n);
    let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut sigma = vec![0.0_f64; n];
    let mut dist = vec![-1_i64; n];
    let mut delta = vec![0.0_f64; n];
    let mut queue: VecDeque<usize> = VecDeque::with_capacity(n);

    for s in 0..n {
        stack.clear();
        for p in preds.iter_mut() {
            p.clear();
        }
        for x in sigma.iter_mut() {
            *x = 0.0;
        }
        for d in dist.iter_mut() {
            *d = -1;
        }
        for d in delta.iter_mut() {
            *d = 0.0;
        }
        queue.clear();

        sigma[s] = 1.0;
        dist[s] = 0;
        queue.push_back(s);

        while let Some(v) = queue.pop_front() {
            stack.push(v);
            for &w in &out[v] {
                if dist[w] < 0 {
                    dist[w] = dist[v] + 1;
                    queue.push_back(w);
                }
                if dist[w] == dist[v] + 1 {
                    sigma[w] += sigma[v];
                    preds[w].push(v);
                }
            }
        }

        while let Some(w) = stack.pop() {
            let coeff = (1.0 + delta[w]) / sigma[w];
            for &v in &preds[w] {
                delta[v] += sigma[v] * coeff;
            }
            if w != s {
                cb[w] += delta[w];
            }
        }
    }

    if normalized && n > 2 {
        let scale = 1.0 / ((n - 1) as f64 * (n - 2) as f64);
        for x in cb.iter_mut() {
            *x *= scale;
        }
        return BetweennessResult { scores: cb, normalized: true };
    }

    BetweennessResult { scores: cb, normalized: false }
}

#[cfg(test)]
mod tests {
    use super::*;
    use srcgraph_core::{EdgeType, OwnedClassNode, OwnedGraph};
    use petgraph::Graph;

    fn node(id: &str) -> OwnedClassNode {
        OwnedClassNode {
            id: id.to_owned(),
            name: id.to_owned(),
            namespace: "test".to_owned(),
            line_count: 1,
            method_count: 1,
            halstead_eta1: 0,
            halstead_eta2: 0,
            halstead_n1: 0,
            halstead_n2: 0,
            method_connectivity: None,
            method_fingerprints: None,
            method_tokens: None,
            call_sequences: None,
            cyclomatic_complexity: None,
            path_conditions: None,
            invariants: None,
            error_messages: None,
            magic_numbers: None,
            dead_code: None,
            tenant_branches: None,
            state_transitions: None,
        }
    }

    fn approx(a: f64, b: f64) -> bool {
        (a - b).abs() < 1e-9
    }

    #[test]
    fn betweenness_path_graph_unnormalized() {
        // A → B → C → D — directed path.
        //   pairs through B: (A,C), (A,D)  → 2
        //   pairs through C: (A,D), (B,D)  → 2
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(node("A"));
        let b = g.add_node(node("B"));
        let c = g.add_node(node("C"));
        let d = g.add_node(node("D"));
        g.add_edge(a, b, EdgeType::MethodCall);
        g.add_edge(b, c, EdgeType::MethodCall);
        g.add_edge(c, d, EdgeType::MethodCall);

        let r = compute_betweenness(&g, false);
        assert!(approx(r.get(a), 0.0));
        assert!(approx(r.get(b), 2.0), "B={}", r.get(b));
        assert!(approx(r.get(c), 2.0), "C={}", r.get(c));
        assert!(approx(r.get(d), 0.0));
        assert!(!r.normalized);
    }

    #[test]
    fn betweenness_hub_normalized() {
        // Bidirectional star: A↔B, A↔C, A↔D. Every leaf-pair shortest path
        // routes through A. Raw σ_A = 6 (ordered pairs); n=4 ⇒ scale=1/6 ⇒ 1.0.
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(node("A"));
        let leaves: Vec<_> = ["B", "C", "D"].iter().map(|l| g.add_node(node(l))).collect();
        for &l in &leaves {
            g.add_edge(a, l, EdgeType::MethodCall);
            g.add_edge(l, a, EdgeType::MethodCall);
        }

        let r = compute_betweenness(&g, true);
        assert!(r.normalized);
        assert!(approx(r.get(a), 1.0), "hub={}", r.get(a));
        for &l in &leaves {
            assert!(approx(r.get(l), 0.0), "leaf={}", r.get(l));
        }
    }

    #[test]
    fn betweenness_parallel_paths_split_credit() {
        // A → {B,C} → D — two equal-length paths A↦D.
        // For source A, σ_D = 2; each intermediate gets 1/2.
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(node("A"));
        let b = g.add_node(node("B"));
        let c = g.add_node(node("C"));
        let d = g.add_node(node("D"));
        g.add_edge(a, b, EdgeType::MethodCall);
        g.add_edge(a, c, EdgeType::MethodCall);
        g.add_edge(b, d, EdgeType::MethodCall);
        g.add_edge(c, d, EdgeType::MethodCall);

        let r = compute_betweenness(&g, false);
        assert!(approx(r.get(a), 0.0));
        assert!(approx(r.get(b), 0.5), "B={}", r.get(b));
        assert!(approx(r.get(c), 0.5), "C={}", r.get(c));
        assert!(approx(r.get(d), 0.0));
    }

    #[test]
    fn betweenness_isolated_nodes_zero() {
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(node("A"));
        let b = g.add_node(node("B"));
        let c = g.add_node(node("C"));
        let r = compute_betweenness(&g, true);
        for nx in [a, b, c] {
            assert!(approx(r.get(nx), 0.0));
        }
    }

    #[test]
    fn betweenness_empty_graph() {
        let g: OwnedGraph = Graph::new();
        let r = compute_betweenness(&g, true);
        assert!(r.scores.is_empty());
    }

    #[test]
    fn betweenness_three_cycle_symmetric() {
        // A→B→C→A. Each node lies on exactly one shortest path of the
        // remaining pair (directed 2-hop), so all three scores equal 1.
        let mut g: OwnedGraph = Graph::new();
        let a = g.add_node(node("A"));
        let b = g.add_node(node("B"));
        let c = g.add_node(node("C"));
        g.add_edge(a, b, EdgeType::MethodCall);
        g.add_edge(b, c, EdgeType::MethodCall);
        g.add_edge(c, a, EdgeType::MethodCall);

        let r = compute_betweenness(&g, false);
        assert!(approx(r.get(a), 1.0), "A={}", r.get(a));
        assert!(approx(r.get(b), 1.0), "B={}", r.get(b));
        assert!(approx(r.get(c), 1.0), "C={}", r.get(c));
    }
}