osmnxr_core/
centrality.rs

1//! Node centrality measures on a weighted [`Graph`].
2
3use crate::graph::Graph;
4use crate::routing::dijkstra;
5use std::cmp::Ordering;
6use std::collections::BinaryHeap;
7
8const EPS: f64 = 1e-9;
9
10/// Min-heap entry by ascending distance.
11struct Entry {
12    dist: f64,
13    node: usize,
14}
15impl PartialEq for Entry {
16    fn eq(&self, other: &Self) -> bool {
17        self.dist == other.dist
18    }
19}
20impl Eq for Entry {}
21impl PartialOrd for Entry {
22    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
23        Some(self.cmp(other))
24    }
25}
26impl Ord for Entry {
27    fn cmp(&self, other: &Self) -> Ordering {
28        other
29            .dist
30            .partial_cmp(&self.dist)
31            .unwrap_or(Ordering::Equal)
32    }
33}
34
35/// Closeness centrality for every node. For node `v` with reachable set of size
36/// `r` and total distance `s`, closeness is `(r - 1) / s`. When `normalized`,
37/// it is scaled by `(r - 1) / (n - 1)` (Wasserman--Faust) to compare nodes in
38/// disconnected graphs. Isolated nodes get `0`.
39pub fn closeness_centrality(graph: &Graph, normalized: bool) -> Vec<f64> {
40    let n = graph.n_nodes;
41    let mut out = vec![0.0; n];
42    for (v, slot) in out.iter_mut().enumerate() {
43        let dist = dijkstra(graph, v);
44        let mut sum = 0.0;
45        let mut reach = 0usize;
46        for &d in dist.iter() {
47            if d.is_finite() && d > 0.0 {
48                sum += d;
49                reach += 1;
50            }
51        }
52        if sum > 0.0 && reach > 0 {
53            let mut c = reach as f64 / sum;
54            if normalized && n > 1 {
55                c *= reach as f64 / (n as f64 - 1.0);
56            }
57            *slot = c;
58        }
59    }
60    out
61}
62
63/// Betweenness centrality via Brandes' algorithm for weighted graphs. When
64/// `normalized`, scores are divided by `(n - 1)(n - 2)` (directed graphs).
65pub fn betweenness_centrality(graph: &Graph, normalized: bool) -> Vec<f64> {
66    let n = graph.n_nodes;
67    let mut bc = vec![0.0f64; n];
68
69    for s in 0..n {
70        let mut dist = vec![f64::INFINITY; n];
71        let mut sigma = vec![0.0f64; n];
72        let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
73        let mut done = vec![false; n];
74        let mut stack: Vec<usize> = Vec::new();
75
76        dist[s] = 0.0;
77        sigma[s] = 1.0;
78        let mut heap = BinaryHeap::new();
79        heap.push(Entry { dist: 0.0, node: s });
80
81        while let Some(Entry { dist: d, node: v }) = heap.pop() {
82            if done[v] {
83                continue;
84            }
85            done[v] = true;
86            stack.push(v);
87            for (w, c) in graph.neighbors(v) {
88                let nd = d + c;
89                if nd < dist[w] - EPS {
90                    dist[w] = nd;
91                    sigma[w] = sigma[v];
92                    preds[w].clear();
93                    preds[w].push(v);
94                    heap.push(Entry { dist: nd, node: w });
95                } else if (nd - dist[w]).abs() <= EPS {
96                    sigma[w] += sigma[v];
97                    preds[w].push(v);
98                }
99            }
100        }
101
102        let mut delta = vec![0.0f64; n];
103        while let Some(w) = stack.pop() {
104            let coeff = (1.0 + delta[w]) / sigma[w];
105            for &v in &preds[w] {
106                delta[v] += sigma[v] * coeff;
107            }
108            if w != s {
109                bc[w] += delta[w];
110            }
111        }
112    }
113
114    if normalized && n > 2 {
115        let scale = 1.0 / ((n as f64 - 1.0) * (n as f64 - 2.0));
116        for x in bc.iter_mut() {
117            *x *= scale;
118        }
119    }
120    bc
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn betweenness_of_a_path_peaks_in_the_middle() {
129        // Directed line 0->1->2->3->4 (and reverse) : node 2 most central.
130        let from = vec![0, 1, 2, 3, 1, 2, 3, 4];
131        let to = vec![1, 2, 3, 4, 0, 1, 2, 3];
132        let w = vec![1.0; 8];
133        let g = Graph::from_edges(&from, &to, &w, 5);
134        let bc = betweenness_centrality(&g, false);
135        assert!(bc[2] > bc[1]);
136        assert!(bc[1] > bc[0]);
137        assert_eq!(bc[0], 0.0); // endpoints lie on no shortest path
138    }
139
140    #[test]
141    fn closeness_center_beats_leaf() {
142        // Star: 0 in the middle connected to 1,2,3 (bidirectional).
143        let from = vec![0, 1, 0, 2, 0, 3];
144        let to = vec![1, 0, 2, 0, 3, 0];
145        let w = vec![1.0; 6];
146        let g = Graph::from_edges(&from, &to, &w, 4);
147        let cc = closeness_centrality(&g, false);
148        assert!(cc[0] > cc[1]);
149    }
150}
osmnxr_core/centrality.rs

osmnxr_core/
centrality.rs
