rust_igraph/algorithms/properties/
edge_irregularity.rs

1//! Edge-based irregularity indices (ALGO-TR-079).
2//!
3//! Bond-additive irregularity measures that quantify how much edge
4//! endpoints differ in degree:
5//!
6//! - **IRD** (square-difference irregularity)
7//!   `IRD(G) = Σ_{(u,v)∈E} |d(u)² - d(v)²|`
8//! - **IRA** (power-difference irregularity)
9//!   `IRA_α(G) = Σ_{(u,v)∈E} |d(u)^α - d(v)^α|` for real α
10//! - **IRB** (root-difference irregularity)
11//!   `IRB(G) = Σ_{(u,v)∈E} (√d(u) - √d(v))²`
12//! - **IRGA** (geometric-arithmetic irregularity)
13//!   `IRGA(G) = Σ_{(u,v)∈E} ln((d(u)+d(v))/(2√(d(u)·d(v))))`
14
15#![allow(
16    clippy::cast_possible_truncation,
17    clippy::cast_precision_loss,
18    clippy::many_single_char_names,
19    clippy::needless_range_loop,
20    clippy::too_many_lines
21)]
22
23use crate::core::{Graph, IgraphResult};
24
25/// Compute the square-difference irregularity index.
26///
27/// `IRD(G) = Σ_{(u,v)∈E} |d(u)² - d(v)²|`
28///
29/// Equals 0 for regular graphs. Self-loops are skipped.
30///
31/// # Examples
32///
33/// ```
34/// use rust_igraph::{Graph, ird_index};
35///
36/// // K_3: all degrees 2, IRD = 0
37/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
38/// assert!(ird_index(&g).unwrap().abs() < 1e-10);
39/// ```
40pub fn ird_index(graph: &Graph) -> IgraphResult<f64> {
41    let mut result = 0.0_f64;
42
43    for (u, v) in graph.edges() {
44        if u == v {
45            continue;
46        }
47        let du = graph.degree(u)? as f64;
48        let dv = graph.degree(v)? as f64;
49        result += (du * du - dv * dv).abs();
50    }
51
52    Ok(result)
53}
54
55/// Compute the power-difference irregularity index.
56///
57/// `IRA_α(G) = Σ_{(u,v)∈E} |d(u)^α - d(v)^α|` for real α.
58///
59/// Special cases:
60/// - `α = 1`: equals the Albertson index `Σ |d(u)-d(v)|`
61/// - `α = 2`: equals `IRD(G)`
62/// - `α = 0.5`: equals `Σ |√d(u) - √d(v)|`
63///
64/// Edges with degree-0 endpoint are skipped when `α < 0`.
65/// Self-loops are skipped.
66///
67/// # Examples
68///
69/// ```
70/// use rust_igraph::{Graph, ira_index};
71///
72/// // Star S_5: 4 edges (4,1), α=2 → 4·|16-1| = 60
73/// let g = Graph::from_edges(&[(0,1),(0,2),(0,3),(0,4)], false, Some(5)).unwrap();
74/// assert!((ira_index(&g, 2.0).unwrap() - 60.0).abs() < 1e-10);
75/// ```
76pub fn ira_index(graph: &Graph, alpha: f64) -> IgraphResult<f64> {
77    let mut result = 0.0_f64;
78
79    for (u, v) in graph.edges() {
80        if u == v {
81            continue;
82        }
83        let du = graph.degree(u)? as f64;
84        let dv = graph.degree(v)? as f64;
85        if alpha < 0.0 && (du == 0.0 || dv == 0.0) {
86            continue;
87        }
88        result += (du.powf(alpha) - dv.powf(alpha)).abs();
89    }
90
91    Ok(result)
92}
93
94/// Compute the root-difference irregularity index.
95///
96/// `IRB(G) = Σ_{(u,v)∈E} (√d(u) - √d(v))²`
97///
98/// This is always non-negative and equals 0 for regular graphs.
99/// Self-loops are skipped.
100///
101/// # Examples
102///
103/// ```
104/// use rust_igraph::{Graph, irb_index};
105///
106/// // K_3: all degrees 2, IRB = 0
107/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
108/// assert!(irb_index(&g).unwrap().abs() < 1e-10);
109/// ```
110pub fn irb_index(graph: &Graph) -> IgraphResult<f64> {
111    let mut result = 0.0_f64;
112
113    for (u, v) in graph.edges() {
114        if u == v {
115            continue;
116        }
117        let du = (graph.degree(u)? as f64).sqrt();
118        let dv = (graph.degree(v)? as f64).sqrt();
119        let diff = du - dv;
120        result += diff * diff;
121    }
122
123    Ok(result)
124}
125
126/// Compute the geometric-arithmetic irregularity index.
127///
128/// `IRGA(G) = Σ_{(u,v)∈E} ln((d(u)+d(v)) / (2√(d(u)·d(v))))`
129///
130/// By AM-GM inequality, each term is ≥ 0. Equals 0 for regular graphs.
131/// Edges with degree-0 endpoint are skipped. Self-loops are skipped.
132///
133/// # Examples
134///
135/// ```
136/// use rust_igraph::{Graph, irga_index};
137///
138/// // K_3: all degrees 2, IRGA = 0
139/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
140/// assert!(irga_index(&g).unwrap().abs() < 1e-10);
141/// ```
142pub fn irga_index(graph: &Graph) -> IgraphResult<f64> {
143    let mut result = 0.0_f64;
144
145    for (u, v) in graph.edges() {
146        if u == v {
147            continue;
148        }
149        let du = graph.degree(u)? as f64;
150        let dv = graph.degree(v)? as f64;
151        let product = du * dv;
152        if product <= 0.0 {
153            continue;
154        }
155        let am = f64::midpoint(du, dv);
156        let gm = product.sqrt();
157        result += (am / gm).ln();
158    }
159
160    Ok(result)
161}
162
163#[cfg(test)]
164mod tests {
165    use super::*;
166
167    fn single_edge() -> Graph {
168        Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap()
169    }
170
171    fn path3() -> Graph {
172        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
173    }
174
175    fn k3() -> Graph {
176        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
177    }
178
179    fn k4() -> Graph {
180        Graph::from_edges(
181            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
182            false,
183            Some(4),
184        )
185        .unwrap()
186    }
187
188    fn cycle4() -> Graph {
189        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
190    }
191
192    fn star5() -> Graph {
193        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
194    }
195
196    fn paw() -> Graph {
197        Graph::from_edges(&[(0, 1), (1, 2), (0, 2), (2, 3)], false, Some(4)).unwrap()
198    }
199
200    // --- ird_index ---
201
202    #[test]
203    fn ird_empty() {
204        let g = Graph::with_vertices(0);
205        assert!(ird_index(&g).unwrap().abs() < 1e-10);
206    }
207
208    #[test]
209    fn ird_isolated() {
210        let g = Graph::with_vertices(5);
211        assert!(ird_index(&g).unwrap().abs() < 1e-10);
212    }
213
214    #[test]
215    fn ird_regular_zero() {
216        assert!(ird_index(&k3()).unwrap().abs() < 1e-10);
217        assert!(ird_index(&k4()).unwrap().abs() < 1e-10);
218        assert!(ird_index(&cycle4()).unwrap().abs() < 1e-10);
219    }
220
221    #[test]
222    fn ird_single_edge() {
223        // d=(1,1): |1-1|=0
224        assert!(ird_index(&single_edge()).unwrap().abs() < 1e-10);
225    }
226
227    #[test]
228    fn ird_star5() {
229        // 4 edges (4,1): 4·|16-1| = 60
230        assert!((ird_index(&star5()).unwrap() - 60.0).abs() < 1e-10);
231    }
232
233    #[test]
234    fn ird_path3() {
235        // 2 edges (1,2): 2·|1-4| = 6
236        assert!((ird_index(&path3()).unwrap() - 6.0).abs() < 1e-10);
237    }
238
239    #[test]
240    fn ird_paw() {
241        // (0,1) d=(2,2): |4-4|=0
242        // (0,2) d=(2,3): |4-9|=5
243        // (1,2) d=(2,3): |4-9|=5
244        // (2,3) d=(3,1): |9-1|=8
245        assert!((ird_index(&paw()).unwrap() - 18.0).abs() < 1e-10);
246    }
247
248    // --- ira_index ---
249
250    #[test]
251    fn ira_empty() {
252        let g = Graph::with_vertices(0);
253        assert!(ira_index(&g, 2.0).unwrap().abs() < 1e-10);
254    }
255
256    #[test]
257    fn ira_regular_zero() {
258        assert!(ira_index(&k3(), 2.0).unwrap().abs() < 1e-10);
259        assert!(ira_index(&k4(), 3.0).unwrap().abs() < 1e-10);
260    }
261
262    #[test]
263    fn ira_alpha1_is_albertson() {
264        // α=1: Σ |du-dv| = Albertson index
265        // Star S_5: 4·|4-1| = 12
266        assert!((ira_index(&star5(), 1.0).unwrap() - 12.0).abs() < 1e-10);
267        // Paw: |2-2|+|2-3|+|2-3|+|3-1| = 0+1+1+2 = 4
268        assert!((ira_index(&paw(), 1.0).unwrap() - 4.0).abs() < 1e-10);
269    }
270
271    #[test]
272    fn ira_alpha2_equals_ird() {
273        // α=2: equals IRD
274        for g in &[single_edge(), path3(), k3(), star5(), paw()] {
275            let square_diff = ird_index(g).unwrap();
276            let power_diff = ira_index(g, 2.0).unwrap();
277            assert!(
278                (square_diff - power_diff).abs() < 1e-10,
279                "IRD={square_diff} IRA_2={power_diff}"
280            );
281        }
282    }
283
284    #[test]
285    fn ira_star5_alpha2() {
286        assert!((ira_index(&star5(), 2.0).unwrap() - 60.0).abs() < 1e-10);
287    }
288
289    #[test]
290    fn ira_star5_alpha3() {
291        // 4·|64-1| = 252
292        assert!((ira_index(&star5(), 3.0).unwrap() - 252.0).abs() < 1e-10);
293    }
294
295    // --- irb_index ---
296
297    #[test]
298    fn irb_empty() {
299        let g = Graph::with_vertices(0);
300        assert!(irb_index(&g).unwrap().abs() < 1e-10);
301    }
302
303    #[test]
304    fn irb_isolated() {
305        let g = Graph::with_vertices(5);
306        assert!(irb_index(&g).unwrap().abs() < 1e-10);
307    }
308
309    #[test]
310    fn irb_regular_zero() {
311        assert!(irb_index(&k3()).unwrap().abs() < 1e-10);
312        assert!(irb_index(&k4()).unwrap().abs() < 1e-10);
313        assert!(irb_index(&cycle4()).unwrap().abs() < 1e-10);
314    }
315
316    #[test]
317    fn irb_single_edge() {
318        assert!(irb_index(&single_edge()).unwrap().abs() < 1e-10);
319    }
320
321    #[test]
322    fn irb_star5() {
323        // 4 edges (4,1): (√4-√1)² = (2-1)² = 1 → 4·1 = 4
324        assert!((irb_index(&star5()).unwrap() - 4.0).abs() < 1e-10);
325    }
326
327    #[test]
328    fn irb_path3() {
329        // 2 edges (1,2): (1-√2)² each → 2·(1-√2)² = 2·(3-2√2)
330        let expected = 2.0 * (3.0 - 2.0 * 2.0_f64.sqrt());
331        assert!((irb_index(&path3()).unwrap() - expected).abs() < 1e-10);
332    }
333
334    #[test]
335    fn irb_paw() {
336        // (0,1) d=(2,2): 0
337        // (0,2) d=(2,3): (√2-√3)²
338        // (1,2) d=(2,3): (√2-√3)²
339        // (2,3) d=(3,1): (√3-1)²
340        let d23 = (2.0_f64.sqrt() - 3.0_f64.sqrt()).powi(2);
341        let d31 = (3.0_f64.sqrt() - 1.0).powi(2);
342        let expected = 2.0 * d23 + d31;
343        assert!((irb_index(&paw()).unwrap() - expected).abs() < 1e-10);
344    }
345
346    #[test]
347    fn irb_nonnegative() {
348        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
349            assert!(irb_index(g).unwrap() >= -1e-10);
350        }
351    }
352
353    // --- irga_index ---
354
355    #[test]
356    fn irga_empty() {
357        let g = Graph::with_vertices(0);
358        assert!(irga_index(&g).unwrap().abs() < 1e-10);
359    }
360
361    #[test]
362    fn irga_isolated() {
363        let g = Graph::with_vertices(5);
364        assert!(irga_index(&g).unwrap().abs() < 1e-10);
365    }
366
367    #[test]
368    fn irga_regular_zero() {
369        assert!(irga_index(&k3()).unwrap().abs() < 1e-10);
370        assert!(irga_index(&k4()).unwrap().abs() < 1e-10);
371        assert!(irga_index(&cycle4()).unwrap().abs() < 1e-10);
372    }
373
374    #[test]
375    fn irga_single_edge() {
376        // d=(1,1): ln(1/1)=0
377        assert!(irga_index(&single_edge()).unwrap().abs() < 1e-10);
378    }
379
380    #[test]
381    fn irga_star5() {
382        // 4 edges (4,1): ln((4+1)/(2·√4)) = ln(5/4)
383        let expected = 4.0 * (5.0_f64 / 4.0).ln();
384        assert!((irga_index(&star5()).unwrap() - expected).abs() < 1e-10);
385    }
386
387    #[test]
388    fn irga_path3() {
389        // 2 edges (1,2): ln((1+2)/(2·√2)) = ln(3/(2√2))
390        let expected = 2.0 * (3.0 / (2.0 * 2.0_f64.sqrt())).ln();
391        assert!((irga_index(&path3()).unwrap() - expected).abs() < 1e-10);
392    }
393
394    #[test]
395    fn irga_nonnegative() {
396        // By AM-GM, each term ≥ 0
397        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
398            assert!(irga_index(g).unwrap() >= -1e-10);
399        }
400    }
401
402    #[test]
403    fn irga_paw() {
404        // (0,1) d=(2,2): ln(4/(2·2))=ln(1)=0
405        // (0,2) d=(2,3): ln(5/(2·√6))
406        // (1,2) d=(2,3): ln(5/(2·√6))
407        // (2,3) d=(3,1): ln(4/(2·√3))=ln(2/√3)
408        let t1 = (5.0 / (2.0 * 6.0_f64.sqrt())).ln();
409        let t2 = (2.0 / 3.0_f64.sqrt()).ln();
410        let expected = 2.0 * t1 + t2;
411        assert!((irga_index(&paw()).unwrap() - expected).abs() < 1e-10);
412    }
413
414    // --- cross-consistency ---
415
416    #[test]
417    fn ird_nonnegative() {
418        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
419            assert!(ird_index(g).unwrap() >= -1e-10);
420        }
421    }
422
423    #[test]
424    fn ira_nonnegative() {
425        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
426            assert!(ira_index(g, 1.0).unwrap() >= -1e-10);
427            assert!(ira_index(g, 2.0).unwrap() >= -1e-10);
428            assert!(ira_index(g, 0.5).unwrap() >= -1e-10);
429        }
430    }
431}
rust_igraph/algorithms/properties/edge_irregularity.rs

rust_igraph/algorithms/properties/
edge_irregularity.rs
