1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
//! Closeness centrality (ALGO-PR-007).
//!
//! Counterpart of `igraph_closeness()` from
//! `references/igraph/src/centrality/closeness.c:33+`. The closeness
//! of vertex `v` is the inverse of its mean distance to all reachable
//! vertices.
//!
//! Phase-1 minimal slice: undirected/IGRAPH_OUT-mode unweighted
//! closeness with `normalized = true` (per the upstream default).
//! Reuses the existing [`distances`] primitive for BFS-from-each-vertex.
//!
//! For an isolated vertex (no reachable vertices besides itself) the
//! definition is undefined → returns `None`. For graphs with multiple
//! components, the score is computed within each vertex's reachable
//! set (matches upstream's `unconn = true` semantics).
use crate::algorithms::paths::distances::distances;
use crate::core::{Graph, IgraphResult};
/// Per-vertex closeness centrality (`Vec<Option<f64>>`).
///
/// `result[v]` is `Some(reachable_count / sum_of_distances)` if vertex
/// `v` has at least one reachable neighbour; `None` for isolated
/// vertices (matches upstream's `IGRAPH_NAN`).
///
/// Edge directions follow [`distances`]: out-edges for directed
/// graphs (`IGRAPH_OUT`), full undirected reachability otherwise.
///
/// # Examples
///
/// ```
/// use rust_igraph::{Graph, closeness};
///
/// // Star with centre 0 and 3 leaves: centre has the highest closeness.
/// let mut g = Graph::with_vertices(4);
/// for v in 1..4 { g.add_edge(0, v).unwrap(); }
/// let c = closeness(&g).unwrap();
/// // Centre: 3 reachable, sum_dist = 3 → 3/3 = 1.0.
/// assert_eq!(c[0], Some(1.0));
/// // Leaves: 3 reachable (centre + 2 other leaves), sum = 1 + 2 + 2 = 5 → 3/5 = 0.6.
/// for leaf in 1..4 {
/// assert_eq!(c[leaf], Some(0.6));
/// }
/// ```
pub fn closeness(graph: &Graph) -> IgraphResult<Vec<Option<f64>>> {
let n = graph.vcount();
let n_us = n as usize;
let mut out = Vec::with_capacity(n_us);
for v in 0..n {
let d = distances(graph, v)?;
let mut sum_dist: u64 = 0;
let mut reach: u64 = 0;
let v_us = v as usize;
for (target, &val) in d.iter().enumerate() {
if target == v_us {
continue;
}
if let Some(dist) = val {
sum_dist += u64::from(dist);
reach += 1;
}
}
if reach == 0 || sum_dist == 0 {
// Isolated (no reachable vertices) — upstream returns NaN.
// sum_dist == 0 with reach > 0 only happens for degenerate
// self-loop graphs which we treat as isolated for closeness.
out.push(None);
} else {
// Counts fit in u64; ratio fits in f64 mantissa for any
// graph that survives u32 vertex ids.
#[allow(clippy::cast_precision_loss)]
let val = (reach as f64) / (sum_dist as f64);
out.push(Some(val));
}
}
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
fn approx_eq(a: Option<f64>, b: Option<f64>, tol: f64) {
match (a, b) {
(Some(x), Some(y)) => {
assert!((x - y).abs() < tol, "{x} vs {y}");
}
(None, None) => {}
_ => panic!("{a:?} vs {b:?}"),
}
}
#[test]
fn empty_graph_yields_empty() {
let g = Graph::with_vertices(0);
assert!(closeness(&g).unwrap().is_empty());
}
#[test]
fn isolated_vertices_all_none() {
let g = Graph::with_vertices(3);
let c = closeness(&g).unwrap();
assert_eq!(c, vec![None, None, None]);
}
#[test]
fn singleton_is_none() {
let g = Graph::with_vertices(1);
assert_eq!(closeness(&g).unwrap(), vec![None]);
}
#[test]
fn k3_triangle_uniform_one() {
// Triangle: every vertex has 2 reachable, sum_dist = 1+1 = 2 → 2/2 = 1.0.
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
g.add_edge(2, 0).unwrap();
let c = closeness(&g).unwrap();
for &val in &c {
approx_eq(val, Some(1.0), 1e-12);
}
}
#[test]
fn star_centre_has_highest() {
let mut g = Graph::with_vertices(4);
for v in 1..4 {
g.add_edge(0, v).unwrap();
}
let c = closeness(&g).unwrap();
// Centre: 3 reachable, sum=3 → 1.0.
approx_eq(c[0], Some(1.0), 1e-12);
// Leaves: 3 reachable (centre at 1, two leaves at 2 each), sum=5 → 0.6.
for &leaf_val in &c[1..4] {
approx_eq(leaf_val, Some(0.6), 1e-12);
}
}
#[test]
fn path_5_endpoints_lower_than_centre() {
// 0-1-2-3-4: centre at 2 has min mean distance.
let mut g = Graph::with_vertices(5);
for i in 0..4 {
g.add_edge(i, i + 1).unwrap();
}
let c = closeness(&g).unwrap();
// Vertex 0: reach=4, sum=1+2+3+4=10 → 0.4
approx_eq(c[0], Some(0.4), 1e-12);
// Vertex 1: reach=4, sum=1+1+2+3=7 → 4/7
approx_eq(c[1], Some(4.0 / 7.0), 1e-12);
// Vertex 2 (centre): reach=4, sum=2+1+1+2=6 → 4/6
approx_eq(c[2], Some(4.0 / 6.0), 1e-12);
// Symmetric for 3 and 4.
approx_eq(c[3], Some(4.0 / 7.0), 1e-12);
approx_eq(c[4], Some(0.4), 1e-12);
}
#[test]
fn disconnected_components_within_component_only() {
// {0-1-2} and {3}: vertex 3 isolated → None.
let mut g = Graph::with_vertices(4);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let c = closeness(&g).unwrap();
// 0: reach=2 (1,2), sum=1+2=3 → 2/3
approx_eq(c[0], Some(2.0 / 3.0), 1e-12);
// 1: reach=2 (0,2), sum=1+1=2 → 1.0
approx_eq(c[1], Some(1.0), 1e-12);
approx_eq(c[2], Some(2.0 / 3.0), 1e-12);
// 3: isolated.
assert_eq!(c[3], None);
}
#[test]
fn directed_path_uses_out_edges() {
// 0->1->2: from 0 reach {1,2} sum=1+2=3 → 2/3; from 1 reach {2} sum=1 → 1.0;
// from 2 reach {} → None.
let mut g = Graph::new(3, true).unwrap();
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let c = closeness(&g).unwrap();
approx_eq(c[0], Some(2.0 / 3.0), 1e-12);
approx_eq(c[1], Some(1.0), 1e-12);
assert_eq!(c[2], None);
}
}