rust_igraph/algorithms/properties/
harmonic_weighted.rs

1//! Weighted harmonic centrality (ALGO-PR-009b).
2//!
3//! Counterpart of `igraph_harmonic_centrality(_, _, vss_all(),
4//! IGRAPH_OUT, &weights, /*normalized=*/true)` from
5//! `references/igraph/src/centrality/closeness.c`. Same shape as
6//! [`crate::harmonic_centrality`] but uses weighted (Dijkstra)
7//! shortest distances instead of BFS hops.
8//!
9//! Phase-1 minimal slice: undirected/OUT, normalized = true.
10
11use crate::algorithms::paths::dijkstra::dijkstra_distances;
12use crate::core::{Graph, IgraphResult};
13
14/// Per-vertex weighted harmonic centrality.
15///
16/// `result[v] = (1/(n-1)) * sum_{u != v, reachable} 1/d_w(v, u)`,
17/// where `d_w` is the Dijkstra weighted distance. Unreachable vertices
18/// contribute 0 (defining `1/inf = 0`), so harmonic centrality is
19/// well-defined on disconnected graphs (unlike closeness).
20///
21/// `weights[e]` is the weight of edge `e`; weights must be
22/// non-negative and finite (forwarded from
23/// [`crate::dijkstra_distances`]). Zero-weight edges that produce a
24/// distance of `0` between distinct vertices are silently skipped to
25/// avoid division by zero.
26///
27/// # Examples
28///
29/// ```
30/// use rust_igraph::{Graph, harmonic_centrality_weighted};
31///
32/// // Path 0-1-2 with weights (1, 1) recovers the unweighted answer.
33/// let mut g = Graph::with_vertices(3);
34/// g.add_edge(0, 1).unwrap();
35/// g.add_edge(1, 2).unwrap();
36/// let h = harmonic_centrality_weighted(&g, &[1.0, 1.0]).unwrap();
37/// assert!((h[0] - 0.75).abs() < 1e-12);
38/// assert!((h[1] - 1.00).abs() < 1e-12);
39/// assert!((h[2] - 0.75).abs() < 1e-12);
40/// ```
41pub fn harmonic_centrality_weighted(graph: &Graph, weights: &[f64]) -> IgraphResult<Vec<f64>> {
42    let n = graph.vcount();
43    let n_us = n as usize;
44    if n < 2 {
45        return Ok(vec![0.0; n_us]);
46    }
47    let mut out = Vec::with_capacity(n_us);
48    let denom = f64::from(n - 1);
49    for v in 0..n {
50        let d = dijkstra_distances(graph, v, weights)?;
51        let mut sum_inv: f64 = 0.0;
52        let v_us = v as usize;
53        for (target, val) in d.iter().enumerate() {
54            if target == v_us {
55                continue;
56            }
57            if let Some(dist) = val {
58                if *dist > 0.0 {
59                    sum_inv += 1.0 / *dist;
60                }
61            }
62        }
63        out.push(sum_inv / denom);
64    }
65    Ok(out)
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    fn close(a: f64, b: f64, tol: f64) {
73        assert!((a - b).abs() < tol, "{a} vs {b}");
74    }
75
76    #[test]
77    fn empty_graph_yields_empty() {
78        let g = Graph::with_vertices(0);
79        assert!(harmonic_centrality_weighted(&g, &[]).unwrap().is_empty());
80    }
81
82    #[test]
83    fn singleton_yields_zero() {
84        let g = Graph::with_vertices(1);
85        assert_eq!(harmonic_centrality_weighted(&g, &[]).unwrap(), vec![0.0]);
86    }
87
88    #[test]
89    fn isolated_vertices_all_zero() {
90        let g = Graph::with_vertices(3);
91        assert_eq!(
92            harmonic_centrality_weighted(&g, &[]).unwrap(),
93            vec![0.0, 0.0, 0.0]
94        );
95    }
96
97    #[test]
98    fn unit_weights_match_unweighted() {
99        // Path 0-1-2.
100        let mut g = Graph::with_vertices(3);
101        g.add_edge(0, 1).unwrap();
102        g.add_edge(1, 2).unwrap();
103        let hw = harmonic_centrality_weighted(&g, &[1.0, 1.0]).unwrap();
104        let hu = crate::harmonic_centrality(&g).unwrap();
105        for (a, b) in hw.iter().zip(hu.iter()) {
106            close(*a, *b, 1e-12);
107        }
108    }
109
110    #[test]
111    fn weighted_path_3_with_doubled_middle_edge() {
112        // 0-1 (w=1), 1-2 (w=2). Distances from 0: {1@1, 2@3}.
113        // Vertex 0: 1/1 + 1/3 = 1.333...; /2 ≈ 0.6667.
114        let mut g = Graph::with_vertices(3);
115        g.add_edge(0, 1).unwrap();
116        g.add_edge(1, 2).unwrap();
117        let h = harmonic_centrality_weighted(&g, &[1.0, 2.0]).unwrap();
118        // 0: 1 + 1/3 = 4/3; /2 = 2/3.
119        close(h[0], 2.0 / 3.0, 1e-12);
120        // 1: 1/1 + 1/2 = 1.5; /2 = 0.75.
121        close(h[1], 0.75, 1e-12);
122        // 2: 1/2 + 1/3 = 5/6; /2 = 5/12.
123        close(h[2], 5.0 / 12.0, 1e-12);
124    }
125
126    #[test]
127    fn directed_path_uses_out_edges() {
128        let mut g = Graph::new(3, true).unwrap();
129        g.add_edge(0, 1).unwrap();
130        g.add_edge(1, 2).unwrap();
131        let h = harmonic_centrality_weighted(&g, &[1.0, 1.0]).unwrap();
132        close(h[0], 0.75, 1e-12);
133        close(h[1], 0.5, 1e-12);
134        close(h[2], 0.0, 1e-12);
135    }
136
137    #[test]
138    fn disconnected_components_well_defined() {
139        // {0-1-2} and isolated 3.
140        let mut g = Graph::with_vertices(4);
141        g.add_edge(0, 1).unwrap();
142        g.add_edge(1, 2).unwrap();
143        let h = harmonic_centrality_weighted(&g, &[1.0, 1.0]).unwrap();
144        // 0: 1 + 0.5 = 1.5; /3 = 0.5.
145        close(h[0], 0.5, 1e-12);
146        // 1: 1 + 1 = 2; /3 = 2/3.
147        close(h[1], 2.0 / 3.0, 1e-12);
148        close(h[2], 0.5, 1e-12);
149        close(h[3], 0.0, 1e-12);
150    }
151
152    #[test]
153    fn weights_size_mismatch_errors() {
154        let mut g = Graph::with_vertices(2);
155        g.add_edge(0, 1).unwrap();
156        assert!(harmonic_centrality_weighted(&g, &[]).is_err());
157    }
158
159    #[test]
160    fn negative_weight_errors() {
161        let mut g = Graph::with_vertices(2);
162        g.add_edge(0, 1).unwrap();
163        assert!(harmonic_centrality_weighted(&g, &[-1.0]).is_err());
164    }
165}
rust_igraph/algorithms/properties/harmonic_weighted.rs

rust_igraph/algorithms/properties/
harmonic_weighted.rs
