rust_igraph/algorithms/properties/
mean_distance_weighted.rs

1//! Weighted mean distance / average path length (ALGO-PR-044).
2//!
3//! Computes the average shortest-path distance across all vertex pairs
4//! using Dijkstra's algorithm. Supports directed/undirected graphs with
5//! non-negative edge weights.
6//!
7//! Counterpart of `igraph_i_average_path_length_dijkstra` from
8//! `references/igraph/src/paths/shortest_paths.c`.
9
10use crate::algorithms::paths::dijkstra::{DijkstraMode, dijkstra_distances_with_mode};
11use crate::core::{Graph, IgraphError, IgraphResult};
12
13/// Compute the weighted mean distance (average shortest path length).
14///
15/// Runs Dijkstra from every vertex and averages all finite pairwise distances.
16///
17/// - `weights`: non-negative edge weights (length must equal edge count).
18/// - `directed`: if true, only follow edge directions; if false, treat
19///   edges as undirected (ignored for undirected graphs).
20/// - `unconn`: if true, average only over connected pairs; if false,
21///   return `f64::INFINITY` if any pair is disconnected.
22///
23/// Returns `None` if the graph has fewer than 2 vertices, or if `unconn`
24/// is true and no pairs are connected.
25///
26/// # Examples
27///
28/// ```
29/// use rust_igraph::{Graph, mean_distance_weighted};
30///
31/// let mut g = Graph::with_vertices(3);
32/// g.add_edge(0, 1).unwrap();
33/// g.add_edge(1, 2).unwrap();
34/// let weights = vec![1.0, 2.0];
35/// let md = mean_distance_weighted(&g, &weights, false, false).unwrap();
36/// // pairs: (0,1)=1, (1,0)=1, (0,2)=3, (2,0)=3, (1,2)=2, (2,1)=2
37/// // mean = (1+1+3+3+2+2)/6 = 12/6 = 2.0
38/// assert!((md.unwrap() - 2.0).abs() < 1e-10);
39/// ```
40pub fn mean_distance_weighted(
41    graph: &Graph,
42    weights: &[f64],
43    directed: bool,
44    unconn: bool,
45) -> IgraphResult<Option<f64>> {
46    let n = graph.vcount();
47    if n < 2 {
48        return Ok(None);
49    }
50
51    let ecount = graph.ecount();
52    if weights.len() != ecount {
53        return Err(IgraphError::InvalidArgument(format!(
54            "mean_distance_weighted: weight vector length ({}) does not match edge count ({ecount})",
55            weights.len()
56        )));
57    }
58
59    if ecount > 0 {
60        for &w in weights {
61            if w < 0.0 {
62                return Err(IgraphError::InvalidArgument(
63                    "mean_distance_weighted: weights must be non-negative".to_string(),
64                ));
65            }
66            if w.is_nan() {
67                return Err(IgraphError::InvalidArgument(
68                    "mean_distance_weighted: weights must not contain NaN".to_string(),
69                ));
70            }
71        }
72    }
73
74    let mode = if graph.is_directed() && directed {
75        DijkstraMode::Out
76    } else {
77        DijkstraMode::All
78    };
79
80    let mut sum = 0.0_f64;
81    let mut conn_pairs = 0_u64;
82
83    for source in 0..n {
84        let dists = dijkstra_distances_with_mode(graph, source, weights, mode)?;
85        for (target, dist_opt) in dists.iter().enumerate() {
86            #[allow(clippy::cast_possible_truncation)]
87            if target as u32 == source {
88                continue;
89            }
90            if let Some(d) = dist_opt {
91                sum += d;
92                conn_pairs += 1;
93            }
94        }
95    }
96
97    #[allow(clippy::cast_precision_loss)]
98    let total_pairs = u64::from(n) * (u64::from(n) - 1);
99
100    if unconn {
101        if conn_pairs == 0 {
102            Ok(None)
103        } else {
104            #[allow(clippy::cast_precision_loss)]
105            Ok(Some(sum / conn_pairs as f64))
106        }
107    } else if conn_pairs < total_pairs {
108        Ok(Some(f64::INFINITY))
109    } else {
110        #[allow(clippy::cast_precision_loss)]
111        Ok(Some(sum / total_pairs as f64))
112    }
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    fn approx_eq(a: f64, b: f64) -> bool {
120        (a - b).abs() < 1e-10
121    }
122
123    #[test]
124    fn empty_graph() {
125        let g = Graph::with_vertices(0);
126        assert_eq!(mean_distance_weighted(&g, &[], false, false).unwrap(), None);
127    }
128
129    #[test]
130    fn single_vertex() {
131        let g = Graph::with_vertices(1);
132        assert_eq!(mean_distance_weighted(&g, &[], false, false).unwrap(), None);
133    }
134
135    #[test]
136    fn path_3_unweighted_equivalent() {
137        let mut g = Graph::with_vertices(3);
138        g.add_edge(0, 1).unwrap();
139        g.add_edge(1, 2).unwrap();
140        let weights = vec![1.0, 1.0];
141        let md = mean_distance_weighted(&g, &weights, false, false)
142            .unwrap()
143            .unwrap();
144        // same as unweighted: (1+1+2+2+1+1)/6 = 8/6 = 4/3
145        assert!(approx_eq(md, 4.0 / 3.0));
146    }
147
148    #[test]
149    fn path_3_weighted() {
150        let mut g = Graph::with_vertices(3);
151        g.add_edge(0, 1).unwrap();
152        g.add_edge(1, 2).unwrap();
153        let weights = vec![1.0, 2.0];
154        let md = mean_distance_weighted(&g, &weights, false, false)
155            .unwrap()
156            .unwrap();
157        // (0,1)=1, (1,0)=1, (0,2)=3, (2,0)=3, (1,2)=2, (2,1)=2 → 12/6=2
158        assert!(approx_eq(md, 2.0));
159    }
160
161    #[test]
162    fn disconnected_unconn_false() {
163        let mut g = Graph::with_vertices(4);
164        g.add_edge(0, 1).unwrap();
165        g.add_edge(2, 3).unwrap();
166        let weights = vec![1.0, 1.0];
167        let md = mean_distance_weighted(&g, &weights, false, false)
168            .unwrap()
169            .unwrap();
170        assert!(md.is_infinite());
171    }
172
173    #[test]
174    fn disconnected_unconn_true() {
175        let mut g = Graph::with_vertices(4);
176        g.add_edge(0, 1).unwrap();
177        g.add_edge(2, 3).unwrap();
178        let weights = vec![1.0, 1.0];
179        let md = mean_distance_weighted(&g, &weights, false, true)
180            .unwrap()
181            .unwrap();
182        // Connected pairs: (0,1),(1,0),(2,3),(3,2) all dist 1 → mean=1.0
183        assert!(approx_eq(md, 1.0));
184    }
185
186    #[test]
187    fn directed_graph() {
188        let mut g = Graph::new(3, true).unwrap();
189        g.add_edge(0, 1).unwrap();
190        g.add_edge(1, 2).unwrap();
191        let weights = vec![1.0, 1.0];
192        let md = mean_distance_weighted(&g, &weights, true, true)
193            .unwrap()
194            .unwrap();
195        // Directed: only 0→1=1, 0→2=2, 1→2=1 are reachable
196        // mean = (1+2+1)/3 = 4/3
197        assert!(approx_eq(md, 4.0 / 3.0));
198    }
199
200    #[test]
201    fn directed_as_undirected() {
202        let mut g = Graph::new(3, true).unwrap();
203        g.add_edge(0, 1).unwrap();
204        g.add_edge(1, 2).unwrap();
205        let weights = vec![1.0, 1.0];
206        let md = mean_distance_weighted(&g, &weights, false, false)
207            .unwrap()
208            .unwrap();
209        // Treats as undirected: all pairs connected, same as path_3 unweighted
210        assert!(approx_eq(md, 4.0 / 3.0));
211    }
212
213    #[test]
214    fn complete_k3_weighted() {
215        let mut g = Graph::with_vertices(3);
216        g.add_edge(0, 1).unwrap();
217        g.add_edge(0, 2).unwrap();
218        g.add_edge(1, 2).unwrap();
219        let weights = vec![1.0, 10.0, 1.0];
220        let md = mean_distance_weighted(&g, &weights, false, false)
221            .unwrap()
222            .unwrap();
223        // Shortest paths: 0-1=1, 0-2=min(10, 1+1)=2, 1-2=1
224        // All pairs: (0,1)=1, (1,0)=1, (0,2)=2, (2,0)=2, (1,2)=1, (2,1)=1
225        // mean = 8/6 = 4/3
226        assert!(approx_eq(md, 4.0 / 3.0));
227    }
228
229    #[test]
230    fn negative_weight_error() {
231        let mut g = Graph::with_vertices(2);
232        g.add_edge(0, 1).unwrap();
233        assert!(mean_distance_weighted(&g, &[-1.0], false, false).is_err());
234    }
235
236    #[test]
237    fn nan_weight_error() {
238        let mut g = Graph::with_vertices(2);
239        g.add_edge(0, 1).unwrap();
240        assert!(mean_distance_weighted(&g, &[f64::NAN], false, false).is_err());
241    }
242
243    #[test]
244    fn weight_mismatch() {
245        let mut g = Graph::with_vertices(2);
246        g.add_edge(0, 1).unwrap();
247        assert!(mean_distance_weighted(&g, &[1.0, 2.0], false, false).is_err());
248    }
249
250    #[test]
251    fn all_isolated_unconn_true() {
252        let g = Graph::with_vertices(5);
253        let md = mean_distance_weighted(&g, &[], false, true).unwrap();
254        assert_eq!(md, None);
255    }
256}
rust_igraph/algorithms/properties/mean_distance_weighted.rs

rust_igraph/algorithms/properties/
mean_distance_weighted.rs
