rust_igraph/algorithms/properties/
degree_ratio_indices.rs

1//! Degree-ratio indices (ALGO-TR-081).
2//!
3//! Bond-additive indices based on degree ratios and harmonic-type
4//! combinations:
5//!
6//! - **Symmetric ratio index** `SR(G) = Σ_{(u,v)∈E} (d(u)/d(v) + d(v)/d(u))`
7//! - **Min-max degree ratio** `mm(G) = Σ_{(u,v)∈E} min(d(u),d(v))/max(d(u),d(v))`
8//! - **Degree harmonic mean index** `DHM(G) = Σ_{(u,v)∈E} 2·d(u)·d(v)/(d(u)+d(v))`
9//! - **Degree difference connectivity** `DDC(G) = Σ_{(u,v)∈E} 1/√(|d(u)-d(v)|+1)`
10
11#![allow(
12    clippy::cast_possible_truncation,
13    clippy::cast_precision_loss,
14    clippy::many_single_char_names,
15    clippy::needless_range_loop,
16    clippy::too_many_lines
17)]
18
19use crate::core::{Graph, IgraphResult};
20
21/// Compute the symmetric degree ratio index.
22///
23/// `SR(G) = Σ_{(u,v)∈E} (d(u)/d(v) + d(v)/d(u))`
24///
25/// Each term ≥ 2 by AM-GM, with equality when d(u)=d(v).
26/// For regular graphs: `SR(G) = 2m`. Edges with a degree-0 endpoint
27/// are skipped. Self-loops are skipped.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, symmetric_degree_ratio};
33///
34/// // K_3: 3 edges, all (2,2) → 3·2 = 6
35/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
36/// assert!((symmetric_degree_ratio(&g).unwrap() - 6.0).abs() < 1e-10);
37/// ```
38pub fn symmetric_degree_ratio(graph: &Graph) -> IgraphResult<f64> {
39    let mut result = 0.0_f64;
40
41    for (u, v) in graph.edges() {
42        if u == v {
43            continue;
44        }
45        let du = graph.degree(u)? as f64;
46        let dv = graph.degree(v)? as f64;
47        if du <= 0.0 || dv <= 0.0 {
48            continue;
49        }
50        result += du / dv + dv / du;
51    }
52
53    Ok(result)
54}
55
56/// Compute the min-max degree ratio index.
57///
58/// `mm(G) = Σ_{(u,v)∈E} min(d(u),d(v))/max(d(u),d(v))`
59///
60/// Each term is in (0,1], equalling 1 when d(u)=d(v).
61/// For regular graphs: `mm(G) = m`. Edges with a degree-0 endpoint
62/// are skipped. Self-loops are skipped.
63///
64/// # Examples
65///
66/// ```
67/// use rust_igraph::{Graph, minmax_degree_ratio};
68///
69/// // K_3: 3 edges → 3·1 = 3
70/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
71/// assert!((minmax_degree_ratio(&g).unwrap() - 3.0).abs() < 1e-10);
72/// ```
73pub fn minmax_degree_ratio(graph: &Graph) -> IgraphResult<f64> {
74    let mut result = 0.0_f64;
75
76    for (u, v) in graph.edges() {
77        if u == v {
78            continue;
79        }
80        let du = graph.degree(u)? as f64;
81        let dv = graph.degree(v)? as f64;
82        if du <= 0.0 || dv <= 0.0 {
83            continue;
84        }
85        result += du.min(dv) / du.max(dv);
86    }
87
88    Ok(result)
89}
90
91/// Compute the degree harmonic mean index.
92///
93/// `DHM(G) = Σ_{(u,v)∈E} 2·d(u)·d(v)/(d(u)+d(v))`
94///
95/// This is the sum of the harmonic means of endpoint degrees.
96/// For regular graphs with degree r: `DHM(G) = m·r`.
97/// Edges with a degree-0 endpoint are skipped. Self-loops are skipped.
98///
99/// # Examples
100///
101/// ```
102/// use rust_igraph::{Graph, degree_harmonic_mean_index};
103///
104/// // K_3: 3 edges, all (2,2) → 3·2 = 6
105/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
106/// assert!((degree_harmonic_mean_index(&g).unwrap() - 6.0).abs() < 1e-10);
107/// ```
108pub fn degree_harmonic_mean_index(graph: &Graph) -> IgraphResult<f64> {
109    let mut result = 0.0_f64;
110
111    for (u, v) in graph.edges() {
112        if u == v {
113            continue;
114        }
115        let du = graph.degree(u)? as f64;
116        let dv = graph.degree(v)? as f64;
117        let s = du + dv;
118        if s <= 0.0 {
119            continue;
120        }
121        result += 2.0 * du * dv / s;
122    }
123
124    Ok(result)
125}
126
127/// Compute the degree difference connectivity index.
128///
129/// `DDC(G) = Σ_{(u,v)∈E} 1/√(|d(u)-d(v)|+1)`
130///
131/// Each term is in (0,1], equalling 1 when d(u)=d(v).
132/// For regular graphs: `DDC(G) = m`. Self-loops are skipped.
133///
134/// # Examples
135///
136/// ```
137/// use rust_igraph::{Graph, degree_diff_connectivity};
138///
139/// // K_3: 3 edges, all (2,2) → 3·1 = 3
140/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
141/// assert!((degree_diff_connectivity(&g).unwrap() - 3.0).abs() < 1e-10);
142/// ```
143pub fn degree_diff_connectivity(graph: &Graph) -> IgraphResult<f64> {
144    let mut result = 0.0_f64;
145
146    for (u, v) in graph.edges() {
147        if u == v {
148            continue;
149        }
150        let du = graph.degree(u)? as f64;
151        let dv = graph.degree(v)? as f64;
152        let diff = (du - dv).abs() + 1.0;
153        result += 1.0 / diff.sqrt();
154    }
155
156    Ok(result)
157}
158
159#[cfg(test)]
160mod tests {
161    use super::*;
162
163    fn single_edge() -> Graph {
164        Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap()
165    }
166
167    fn path3() -> Graph {
168        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
169    }
170
171    fn k3() -> Graph {
172        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
173    }
174
175    fn k4() -> Graph {
176        Graph::from_edges(
177            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
178            false,
179            Some(4),
180        )
181        .unwrap()
182    }
183
184    fn cycle4() -> Graph {
185        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
186    }
187
188    fn star5() -> Graph {
189        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
190    }
191
192    fn paw() -> Graph {
193        Graph::from_edges(&[(0, 1), (1, 2), (0, 2), (2, 3)], false, Some(4)).unwrap()
194    }
195
196    // --- symmetric_degree_ratio ---
197
198    #[test]
199    fn sdr_empty() {
200        let g = Graph::with_vertices(0);
201        assert!(symmetric_degree_ratio(&g).unwrap().abs() < 1e-10);
202    }
203
204    #[test]
205    fn sdr_isolated() {
206        let g = Graph::with_vertices(5);
207        assert!(symmetric_degree_ratio(&g).unwrap().abs() < 1e-10);
208    }
209
210    #[test]
211    fn sdr_regular_is_2m() {
212        // Regular: each term = 2 → SR = 2m
213        assert!((symmetric_degree_ratio(&k3()).unwrap() - 6.0).abs() < 1e-10);
214        assert!((symmetric_degree_ratio(&k4()).unwrap() - 12.0).abs() < 1e-10);
215        assert!((symmetric_degree_ratio(&cycle4()).unwrap() - 8.0).abs() < 1e-10);
216    }
217
218    #[test]
219    fn sdr_single_edge() {
220        // (1,1): 1+1=2
221        assert!((symmetric_degree_ratio(&single_edge()).unwrap() - 2.0).abs() < 1e-10);
222    }
223
224    #[test]
225    fn sdr_star5() {
226        // 4 edges (4,1): 4·(4/1+1/4) = 4·4.25 = 17
227        assert!((symmetric_degree_ratio(&star5()).unwrap() - 17.0).abs() < 1e-10);
228    }
229
230    #[test]
231    fn sdr_path3() {
232        // 2 edges (1,2): 2·(1/2+2/1) = 2·2.5 = 5
233        assert!((symmetric_degree_ratio(&path3()).unwrap() - 5.0).abs() < 1e-10);
234    }
235
236    #[test]
237    fn sdr_paw() {
238        // (0,1)d=(2,2): 2
239        // (0,2)d=(2,3): 2/3+3/2 = 13/6
240        // (1,2)d=(2,3): 13/6
241        // (2,3)d=(3,1): 3+1/3 = 10/3
242        let expected = 2.0 + 2.0 * 13.0 / 6.0 + 10.0 / 3.0;
243        assert!((symmetric_degree_ratio(&paw()).unwrap() - expected).abs() < 1e-10);
244    }
245
246    #[test]
247    fn sdr_ge_2m() {
248        // Each term ≥ 2 by AM-GM
249        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
250            assert!(symmetric_degree_ratio(g).unwrap() >= 2.0 * g.ecount() as f64 - 1e-10);
251        }
252    }
253
254    // --- minmax_degree_ratio ---
255
256    #[test]
257    fn mmr_empty() {
258        let g = Graph::with_vertices(0);
259        assert!(minmax_degree_ratio(&g).unwrap().abs() < 1e-10);
260    }
261
262    #[test]
263    fn mmr_isolated() {
264        let g = Graph::with_vertices(5);
265        assert!(minmax_degree_ratio(&g).unwrap().abs() < 1e-10);
266    }
267
268    #[test]
269    fn mmr_regular_is_m() {
270        // Regular: each term = 1 → mm = m
271        assert!((minmax_degree_ratio(&k3()).unwrap() - 3.0).abs() < 1e-10);
272        assert!((minmax_degree_ratio(&k4()).unwrap() - 6.0).abs() < 1e-10);
273        assert!((minmax_degree_ratio(&cycle4()).unwrap() - 4.0).abs() < 1e-10);
274    }
275
276    #[test]
277    fn mmr_single_edge() {
278        assert!((minmax_degree_ratio(&single_edge()).unwrap() - 1.0).abs() < 1e-10);
279    }
280
281    #[test]
282    fn mmr_star5() {
283        // 4 edges (4,1): 4·(1/4) = 1
284        assert!((minmax_degree_ratio(&star5()).unwrap() - 1.0).abs() < 1e-10);
285    }
286
287    #[test]
288    fn mmr_path3() {
289        // 2 edges (1,2): 2·(1/2) = 1
290        assert!((minmax_degree_ratio(&path3()).unwrap() - 1.0).abs() < 1e-10);
291    }
292
293    #[test]
294    fn mmr_paw() {
295        // (0,1)d=(2,2): 1
296        // (0,2)d=(2,3): 2/3
297        // (1,2)d=(2,3): 2/3
298        // (2,3)d=(3,1): 1/3
299        let expected = 1.0 + 2.0 * 2.0 / 3.0 + 1.0 / 3.0;
300        assert!((minmax_degree_ratio(&paw()).unwrap() - expected).abs() < 1e-10);
301    }
302
303    #[test]
304    fn mmr_le_m() {
305        // Each term ≤ 1 → mm ≤ m
306        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
307            assert!(minmax_degree_ratio(g).unwrap() <= g.ecount() as f64 + 1e-10);
308        }
309    }
310
311    // --- degree_harmonic_mean_index ---
312
313    #[test]
314    fn dhm_empty() {
315        let g = Graph::with_vertices(0);
316        assert!(degree_harmonic_mean_index(&g).unwrap().abs() < 1e-10);
317    }
318
319    #[test]
320    fn dhm_isolated() {
321        let g = Graph::with_vertices(5);
322        assert!(degree_harmonic_mean_index(&g).unwrap().abs() < 1e-10);
323    }
324
325    #[test]
326    fn dhm_regular_is_mr() {
327        // Regular degree r: each term = 2r²/(2r)=r → DHM = m·r
328        // K_3: 3·2=6
329        assert!((degree_harmonic_mean_index(&k3()).unwrap() - 6.0).abs() < 1e-10);
330        // K_4: 6·3=18
331        assert!((degree_harmonic_mean_index(&k4()).unwrap() - 18.0).abs() < 1e-10);
332        // C_4: 4·2=8
333        assert!((degree_harmonic_mean_index(&cycle4()).unwrap() - 8.0).abs() < 1e-10);
334    }
335
336    #[test]
337    fn dhm_single_edge() {
338        // (1,1): 2·1·1/2 = 1
339        assert!((degree_harmonic_mean_index(&single_edge()).unwrap() - 1.0).abs() < 1e-10);
340    }
341
342    #[test]
343    fn dhm_star5() {
344        // 4 edges (4,1): 4·(2·4·1/5) = 4·1.6 = 6.4
345        assert!((degree_harmonic_mean_index(&star5()).unwrap() - 6.4).abs() < 1e-10);
346    }
347
348    #[test]
349    fn dhm_paw() {
350        // (0,1)d=(2,2): 2·4/4=2
351        // (0,2)d=(2,3): 2·6/5=2.4
352        // (1,2)d=(2,3): 2.4
353        // (2,3)d=(3,1): 2·3/4=1.5
354        let expected = 2.0 + 2.0 * 2.4 + 1.5;
355        assert!((degree_harmonic_mean_index(&paw()).unwrap() - expected).abs() < 1e-10);
356    }
357
358    // --- degree_diff_connectivity ---
359
360    #[test]
361    fn ddc_empty() {
362        let g = Graph::with_vertices(0);
363        assert!(degree_diff_connectivity(&g).unwrap().abs() < 1e-10);
364    }
365
366    #[test]
367    fn ddc_isolated() {
368        let g = Graph::with_vertices(5);
369        assert!(degree_diff_connectivity(&g).unwrap().abs() < 1e-10);
370    }
371
372    #[test]
373    fn ddc_regular_is_m() {
374        // Regular: |du-dv|=0 → each 1/√1=1 → DDC = m
375        assert!((degree_diff_connectivity(&k3()).unwrap() - 3.0).abs() < 1e-10);
376        assert!((degree_diff_connectivity(&k4()).unwrap() - 6.0).abs() < 1e-10);
377        assert!((degree_diff_connectivity(&cycle4()).unwrap() - 4.0).abs() < 1e-10);
378    }
379
380    #[test]
381    fn ddc_single_edge() {
382        assert!((degree_diff_connectivity(&single_edge()).unwrap() - 1.0).abs() < 1e-10);
383    }
384
385    #[test]
386    fn ddc_star5() {
387        // 4 edges (4,1): |4-1|=3 → 4·1/√4 = 4·0.5 = 2
388        assert!((degree_diff_connectivity(&star5()).unwrap() - 2.0).abs() < 1e-10);
389    }
390
391    #[test]
392    fn ddc_path3() {
393        // 2 edges (1,2): |1-2|=1 → 2·1/√2
394        let expected = 2.0 / 2.0_f64.sqrt();
395        assert!((degree_diff_connectivity(&path3()).unwrap() - expected).abs() < 1e-10);
396    }
397
398    #[test]
399    fn ddc_paw() {
400        // (0,1)d=(2,2): 1/√1=1
401        // (0,2)d=(2,3): 1/√2
402        // (1,2)d=(2,3): 1/√2
403        // (2,3)d=(3,1): 1/√3
404        let expected = 1.0 + 2.0 / 2.0_f64.sqrt() + 1.0 / 3.0_f64.sqrt();
405        assert!((degree_diff_connectivity(&paw()).unwrap() - expected).abs() < 1e-10);
406    }
407
408    #[test]
409    fn ddc_le_m() {
410        // Each term ≤ 1 → DDC ≤ m
411        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
412            assert!(degree_diff_connectivity(g).unwrap() <= g.ecount() as f64 + 1e-10);
413        }
414    }
415
416    // --- cross-consistency ---
417
418    #[test]
419    fn dhm_positive() {
420        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
421            assert!(degree_harmonic_mean_index(g).unwrap() > 0.0);
422        }
423    }
424
425    #[test]
426    fn sdr_positive() {
427        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
428            assert!(symmetric_degree_ratio(g).unwrap() > 0.0);
429        }
430    }
431}
rust_igraph/algorithms/properties/degree_ratio_indices.rs

rust_igraph/algorithms/properties/
degree_ratio_indices.rs
