rust_igraph/algorithms/properties/
edge_betweenness.rs

1//! Edge betweenness centrality (ALGO-PR-010).
2//!
3//! Counterpart of `igraph_edge_betweenness()` from
4//! `references/igraph/src/centrality/betweenness.c:766+`. Same Brandes
5//! framework as vertex betweenness ([`super::betweenness::betweenness`]) but
6//! accumulating the dependency on edge ids rather than vertices.
7//!
8//! For each source `s`:
9//! 1. BFS that records `sigma[v]` (number of shortest paths from `s`)
10//!    and `pred_edges[w]` = `(predecessor_vertex, edge_id)` pairs along
11//!    shortest paths into `w`.
12//! 2. Reverse-BFS dependency accumulation:
13//!    `c = (sigma[v] / sigma[w]) * (1 + delta_v[w])`,
14//!    then `delta_v[v] += c` and `betweenness_e[e] += c`.
15//!
16//! For undirected graphs the result is halved (each unordered pair is
17//! discovered from both endpoints).
18//!
19//! Phase-1 minimal slice: undirected / `IGRAPH_OUT`, unweighted, raw
20//! counts (`normalized = false`).
21
22use std::collections::VecDeque;
23
24use crate::core::graph::EdgeId;
25use crate::core::{Graph, IgraphResult, VertexId};
26
27/// Per-edge unweighted betweenness centrality.
28///
29/// `result[e]` is the number of shortest paths between all vertex
30/// pairs `(s, t)` (`s != t`) that use edge `e`. For undirected graphs
31/// the result is halved (each unordered pair counted once).
32///
33/// Counterpart of
34/// `igraph_edge_betweenness(_, NULL_weights, _, /*eids=*/all, /*directed=*/g.is_directed(), /*normalized=*/false)`.
35///
36/// # Examples
37///
38/// ```
39/// use rust_igraph::{Graph, edge_betweenness};
40///
41/// // Path 0-1-2-3 (3 edges): every edge sits on every pair through it.
42/// // Edge 0 (0-1) carries (0,1),(0,2),(0,3) = 3 pairs.
43/// // Edge 1 (1-2) carries (0,2),(0,3),(1,2),(1,3) = 4 pairs.
44/// // Edge 2 (2-3) carries (0,3),(1,3),(2,3) = 3 pairs.
45/// let mut g = Graph::with_vertices(4);
46/// for i in 0..3u32 { g.add_edge(i, i + 1).unwrap(); }
47/// let eb = edge_betweenness(&g).unwrap();
48/// assert_eq!(eb, vec![3.0, 4.0, 3.0]);
49/// ```
50pub fn edge_betweenness(graph: &Graph) -> IgraphResult<Vec<f64>> {
51    let n = graph.vcount();
52    let n_us = n as usize;
53    let m = graph.ecount();
54    let mut betweenness_e = vec![0.0_f64; m];
55
56    if n == 0 || m == 0 {
57        return Ok(betweenness_e);
58    }
59
60    let mut sigma = vec![0.0_f64; n_us];
61    let mut dist = vec![-1i64; n_us];
62    let mut pred: Vec<Vec<(VertexId, EdgeId)>> = vec![Vec::new(); n_us];
63    let mut stack: Vec<VertexId> = Vec::with_capacity(n_us);
64    let mut delta_v = vec![0.0_f64; n_us];
65
66    for s in 0..n {
67        sigma.fill(0.0);
68        dist.fill(-1);
69        for slot in &mut pred {
70            slot.clear();
71        }
72        stack.clear();
73        delta_v.fill(0.0);
74
75        sigma[s as usize] = 1.0;
76        dist[s as usize] = 0;
77        let mut queue: VecDeque<VertexId> = VecDeque::new();
78        queue.push_back(s);
79
80        while let Some(v) = queue.pop_front() {
81            stack.push(v);
82            for e in graph.incident(v)? {
83                let w = graph.edge_other(e, v)?;
84                if dist[w as usize] < 0 {
85                    queue.push_back(w);
86                    dist[w as usize] = dist[v as usize] + 1;
87                }
88                if dist[w as usize] == dist[v as usize] + 1 {
89                    sigma[w as usize] += sigma[v as usize];
90                    pred[w as usize].push((v, e));
91                }
92            }
93        }
94
95        // Reverse-BFS dependency accumulation, deposited on edges.
96        while let Some(w) = stack.pop() {
97            for &(v, e) in &pred[w as usize] {
98                let c = (sigma[v as usize] / sigma[w as usize]) * (1.0 + delta_v[w as usize]);
99                delta_v[v as usize] += c;
100                betweenness_e[e as usize] += c;
101            }
102        }
103    }
104
105    // Undirected: every unordered pair was counted twice (from both endpoints).
106    if !graph.is_directed() {
107        for slot in &mut betweenness_e {
108            *slot /= 2.0;
109        }
110    }
111
112    Ok(betweenness_e)
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    fn close(actual: &[f64], expected: &[f64], tol: f64) {
120        assert_eq!(actual.len(), expected.len(), "length mismatch");
121        for (i, (a, e)) in actual.iter().zip(expected.iter()).enumerate() {
122            assert!((a - e).abs() < tol, "edge {i}: actual={a} expected={e}");
123        }
124    }
125
126    #[test]
127    fn empty_graph_yields_empty() {
128        let g = Graph::with_vertices(0);
129        assert!(edge_betweenness(&g).unwrap().is_empty());
130    }
131
132    #[test]
133    fn isolated_vertices_no_edges_empty() {
134        let g = Graph::with_vertices(5);
135        assert!(edge_betweenness(&g).unwrap().is_empty());
136    }
137
138    #[test]
139    fn path_3_edge_betweenness() {
140        // 0-1-2: edge 0 (0-1) carries (0,1),(0,2)=2; edge 1 (1-2) carries (0,2),(1,2)=2.
141        let mut g = Graph::with_vertices(3);
142        g.add_edge(0, 1).unwrap();
143        g.add_edge(1, 2).unwrap();
144        let eb = edge_betweenness(&g).unwrap();
145        close(&eb, &[2.0, 2.0], 1e-12);
146    }
147
148    #[test]
149    fn path_4_edge_betweenness() {
150        // 0-1-2-3: edges 0:(0,1), 1:(1,2), 2:(2,3).
151        // Edge 0 = pairs through {0-1}: (0,1),(0,2),(0,3) = 3.
152        // Edge 1 = (0,2),(0,3),(1,2),(1,3) = 4.
153        // Edge 2 = (0,3),(1,3),(2,3) = 3.
154        let mut g = Graph::with_vertices(4);
155        for i in 0..3u32 {
156            g.add_edge(i, i + 1).unwrap();
157        }
158        let eb = edge_betweenness(&g).unwrap();
159        close(&eb, &[3.0, 4.0, 3.0], 1e-12);
160    }
161
162    #[test]
163    fn k3_triangle_uniform_one() {
164        // Each edge sits on exactly one pair-shortest-path of length 1 →
165        // 3 pairs, 1 edge each direct → each edge has betweenness 1.0.
166        let mut g = Graph::with_vertices(3);
167        g.add_edge(0, 1).unwrap();
168        g.add_edge(1, 2).unwrap();
169        g.add_edge(2, 0).unwrap();
170        let eb = edge_betweenness(&g).unwrap();
171        close(&eb, &[1.0, 1.0, 1.0], 1e-12);
172    }
173
174    #[test]
175    fn star_4_each_edge_three() {
176        // 0-1, 0-2, 0-3: each edge connects centre to one leaf;
177        // each edge serves (centre,leaf) + 2 (leaf,other-leaf) pairs = 3.
178        let mut g = Graph::with_vertices(4);
179        for v in 1..4 {
180            g.add_edge(0, v).unwrap();
181        }
182        let eb = edge_betweenness(&g).unwrap();
183        close(&eb, &[3.0, 3.0, 3.0], 1e-12);
184    }
185
186    #[test]
187    fn cycle_4_uniform_two() {
188        // 0-1, 1-2, 2-3, 3-0. Each direct adjacent pair contributes 1.0
189        // to its edge. Antipodal pairs (0,2) and (1,3) each have two
190        // shortest paths of length 2; each pair contributes 0.5 to all 4
191        // edges. Per-edge total: 1.0 + 2 * 0.5 = 2.0. (Verified vs
192        // python-igraph 0.11.)
193        let mut g = Graph::with_vertices(4);
194        for i in 0..4u32 {
195            g.add_edge(i, (i + 1) % 4).unwrap();
196        }
197        let eb = edge_betweenness(&g).unwrap();
198        close(&eb, &[2.0, 2.0, 2.0, 2.0], 1e-12);
199    }
200
201    #[test]
202    fn directed_path_3_edge_betweenness() {
203        // 0->1->2: edge 0 = (0,1),(0,2) = 2 (ordered); edge 1 = (0,2),(1,2) = 2.
204        let mut g = Graph::new(3, true).unwrap();
205        g.add_edge(0, 1).unwrap();
206        g.add_edge(1, 2).unwrap();
207        let eb = edge_betweenness(&g).unwrap();
208        close(&eb, &[2.0, 2.0], 1e-12);
209    }
210}
rust_igraph/algorithms/properties/edge_betweenness.rs

rust_igraph/algorithms/properties/
edge_betweenness.rs
