rust_igraph/algorithms/properties/
augmented_zagreb.rs

1//! Augmented Zagreb index and atom-bond sum-connectivity (ALGO-TR-046).
2//!
3//! - **Augmented Zagreb index** `AZI(G) = Σ_{(u,v)∈E} (d_u·d_v / (d_u+d_v-2))³`
4//!   Introduced by Furtula et al. (2010); a powerful predictor of
5//!   physico-chemical properties. Edges with `d_u + d_v ≤ 2` (which
6//!   requires isolated endpoints that shouldn't have edges) are skipped.
7//! - **Atom-bond sum-connectivity** `ABS(G) = Σ_{(u,v)∈E} √((d_u+d_v-2)/(d_u+d_v))`
8//!   A variant of the ABC index using degree sums instead of products.
9//!   Edges with `d_u + d_v ≤ 2` are skipped (degenerate).
10//! - **Geometric-arithmetic index** `GA(G) = Σ_{(u,v)∈E} 2√(d_u·d_v)/(d_u+d_v)`
11//!   Ratio of geometric to arithmetic mean of endpoint degrees.
12
13#![allow(
14    clippy::cast_possible_truncation,
15    clippy::cast_precision_loss,
16    clippy::many_single_char_names,
17    clippy::needless_range_loop,
18    clippy::too_many_lines
19)]
20
21use crate::core::{Graph, IgraphResult};
22
23/// Compute the augmented Zagreb index.
24///
25/// `AZI(G) = Σ_{(u,v)∈E} (d_u · d_v / (d_u + d_v - 2))³`
26///
27/// Self-loops and edges where `d_u + d_v ≤ 2` are skipped.
28///
29/// # Examples
30///
31/// ```
32/// use rust_igraph::{Graph, augmented_zagreb_index};
33///
34/// // Path 0-1-2: degrees [1,2,1]
35/// // edge(0,1): (1·2/(1+2-2))³ = 2³ = 8
36/// // edge(1,2): same = 8
37/// // AZI = 16
38/// let g = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
39/// assert!((augmented_zagreb_index(&g).unwrap() - 16.0).abs() < 1e-10);
40/// ```
41pub fn augmented_zagreb_index(graph: &Graph) -> IgraphResult<f64> {
42    let n = graph.vcount();
43    if n == 0 {
44        return Ok(0.0);
45    }
46
47    let mut azi = 0.0_f64;
48
49    for (u, v) in graph.edges() {
50        if u == v {
51            continue;
52        }
53        let du = graph.degree(u)? as f64;
54        let dv = graph.degree(v)? as f64;
55        let denom = du + dv - 2.0;
56        if denom <= 0.0 {
57            continue;
58        }
59        let frac = du * dv / denom;
60        azi += frac * frac * frac;
61    }
62
63    Ok(azi)
64}
65
66/// Compute the atom-bond sum-connectivity index.
67///
68/// `ABS(G) = Σ_{(u,v)∈E} √((d_u + d_v - 2) / (d_u + d_v))`
69///
70/// Self-loops and degenerate edges are skipped.
71///
72/// # Examples
73///
74/// ```
75/// use rust_igraph::{Graph, atom_bond_sum_connectivity};
76///
77/// // Path 0-1-2: degrees [1,2,1]
78/// // edge(0,1): √((3-2)/3) = √(1/3)
79/// // edge(1,2): same
80/// // ABS = 2/√3
81/// let g = Graph::from_edges(&[(0,1),(1,2)], false, Some(3)).unwrap();
82/// assert!((atom_bond_sum_connectivity(&g).unwrap() - 2.0/3.0_f64.sqrt()).abs() < 1e-10);
83/// ```
84pub fn atom_bond_sum_connectivity(graph: &Graph) -> IgraphResult<f64> {
85    let n = graph.vcount();
86    if n == 0 {
87        return Ok(0.0);
88    }
89
90    let mut abs_val = 0.0_f64;
91
92    for (u, v) in graph.edges() {
93        if u == v {
94            continue;
95        }
96        let du = graph.degree(u)? as f64;
97        let dv = graph.degree(v)? as f64;
98        let sum_d = du + dv;
99        if sum_d <= 2.0 {
100            continue;
101        }
102        abs_val += ((sum_d - 2.0) / sum_d).sqrt();
103    }
104
105    Ok(abs_val)
106}
107
108/// Compute the geometric-arithmetic index.
109///
110/// `GA(G) = Σ_{(u,v)∈E} 2√(d_u · d_v) / (d_u + d_v)`
111///
112/// For each edge, this is the ratio of the geometric mean to the
113/// arithmetic mean of the endpoint degrees.
114///
115/// # Examples
116///
117/// ```
118/// use rust_igraph::{Graph, geometric_arithmetic_index};
119///
120/// // K_3: all degrees 2 → each term = 2√4/4 = 1
121/// // GA = 3
122/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
123/// assert!((geometric_arithmetic_index(&g).unwrap() - 3.0).abs() < 1e-10);
124/// ```
125pub fn geometric_arithmetic_index(graph: &Graph) -> IgraphResult<f64> {
126    let n = graph.vcount();
127    if n == 0 {
128        return Ok(0.0);
129    }
130
131    let mut ga = 0.0_f64;
132
133    for (u, v) in graph.edges() {
134        if u == v {
135            continue;
136        }
137        let du = graph.degree(u)? as f64;
138        let dv = graph.degree(v)? as f64;
139        let sum_d = du + dv;
140        if sum_d <= 0.0 {
141            continue;
142        }
143        ga += 2.0 * (du * dv).sqrt() / sum_d;
144    }
145
146    Ok(ga)
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    fn single_edge() -> Graph {
154        Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap()
155    }
156
157    fn path3() -> Graph {
158        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
159    }
160
161    fn path4() -> Graph {
162        Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false, Some(4)).unwrap()
163    }
164
165    fn k3() -> Graph {
166        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
167    }
168
169    fn k4() -> Graph {
170        Graph::from_edges(
171            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
172            false,
173            Some(4),
174        )
175        .unwrap()
176    }
177
178    fn cycle4() -> Graph {
179        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
180    }
181
182    fn cycle5() -> Graph {
183        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], false, Some(5)).unwrap()
184    }
185
186    fn star5() -> Graph {
187        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
188    }
189
190    // --- augmented_zagreb_index ---
191
192    #[test]
193    fn azi_empty() {
194        let g = Graph::with_vertices(0);
195        assert!((augmented_zagreb_index(&g).unwrap() - 0.0).abs() < 1e-10);
196    }
197
198    #[test]
199    fn azi_single_vertex() {
200        let g = Graph::with_vertices(1);
201        assert!((augmented_zagreb_index(&g).unwrap() - 0.0).abs() < 1e-10);
202    }
203
204    #[test]
205    fn azi_no_edges() {
206        let g = Graph::with_vertices(3);
207        assert!((augmented_zagreb_index(&g).unwrap() - 0.0).abs() < 1e-10);
208    }
209
210    #[test]
211    fn azi_single_edge() {
212        // d_u=d_v=1, denom=0 → skipped → AZI=0
213        assert!((augmented_zagreb_index(&single_edge()).unwrap() - 0.0).abs() < 1e-10);
214    }
215
216    #[test]
217    fn azi_path3() {
218        // (0,1): (1·2/(1+2-2))³ = (2/1)³ = 8
219        // (1,2): same = 8
220        // AZI = 16
221        assert!((augmented_zagreb_index(&path3()).unwrap() - 16.0).abs() < 1e-10);
222    }
223
224    #[test]
225    fn azi_path4() {
226        // (0,1): (1·2/1)³ = 8
227        // (1,2): (2·2/2)³ = 8
228        // (2,3): (2·1/1)³ = 8
229        // AZI = 24
230        assert!((augmented_zagreb_index(&path4()).unwrap() - 24.0).abs() < 1e-10);
231    }
232
233    #[test]
234    fn azi_k3() {
235        // all degrees 2, each edge: (2·2/(2+2-2))³ = (4/2)³ = 8
236        // AZI = 3·8 = 24
237        assert!((augmented_zagreb_index(&k3()).unwrap() - 24.0).abs() < 1e-10);
238    }
239
240    #[test]
241    fn azi_k4() {
242        // all degrees 3, each edge: (3·3/(3+3-2))³ = (9/4)³ = 729/64
243        // AZI = 6·729/64 = 4374/64 = 2187/32
244        let expected = 6.0 * (9.0_f64 / 4.0).powi(3);
245        assert!((augmented_zagreb_index(&k4()).unwrap() - expected).abs() < 1e-10);
246    }
247
248    #[test]
249    fn azi_cycle4() {
250        // all degrees 2: same as K3 per edge but 4 edges
251        // each: (4/2)³ = 8, AZI = 32
252        assert!((augmented_zagreb_index(&cycle4()).unwrap() - 32.0).abs() < 1e-10);
253    }
254
255    #[test]
256    fn azi_cycle5() {
257        // all degrees 2, 5 edges: 5·8 = 40
258        assert!((augmented_zagreb_index(&cycle5()).unwrap() - 40.0).abs() < 1e-10);
259    }
260
261    #[test]
262    fn azi_star5() {
263        // center deg=4, leaf deg=1
264        // (4·1/(4+1-2))³ = (4/3)³ = 64/27
265        // AZI = 4 · 64/27 = 256/27
266        let expected = 4.0 * (4.0_f64 / 3.0).powi(3);
267        assert!((augmented_zagreb_index(&star5()).unwrap() - expected).abs() < 1e-10);
268    }
269
270    #[test]
271    fn azi_positive_for_path() {
272        for g in &[path3(), path4(), k3(), k4(), cycle4(), star5()] {
273            assert!(augmented_zagreb_index(g).unwrap() > 0.0);
274        }
275    }
276
277    #[test]
278    fn azi_regular_formula() {
279        // r-regular: AZI = m · (r²/(2r-2))³ = m · (r/2·(r/(r-1)))³
280        for g in &[k3(), k4(), cycle4(), cycle5()] {
281            let m = g.ecount() as f64;
282            let r = g.degree(0).unwrap() as f64;
283            let expected = m * (r * r / (2.0 * r - 2.0)).powi(3);
284            assert!((augmented_zagreb_index(g).unwrap() - expected).abs() < 1e-8);
285        }
286    }
287
288    // --- atom_bond_sum_connectivity ---
289
290    #[test]
291    fn abs_empty() {
292        let g = Graph::with_vertices(0);
293        assert!((atom_bond_sum_connectivity(&g).unwrap() - 0.0).abs() < 1e-10);
294    }
295
296    #[test]
297    fn abs_single_edge() {
298        // d_u+d_v=2, skipped → 0
299        assert!((atom_bond_sum_connectivity(&single_edge()).unwrap() - 0.0).abs() < 1e-10);
300    }
301
302    #[test]
303    fn abs_path3() {
304        // (0,1): √((3-2)/3) = √(1/3) = 1/√3
305        // (1,2): same
306        // ABS = 2/√3
307        let expected = 2.0 / 3.0_f64.sqrt();
308        assert!((atom_bond_sum_connectivity(&path3()).unwrap() - expected).abs() < 1e-10);
309    }
310
311    #[test]
312    fn abs_k3() {
313        // each: √((4-2)/4) = √(1/2) = 1/√2
314        // ABS = 3/√2
315        let expected = 3.0 / 2.0_f64.sqrt();
316        assert!((atom_bond_sum_connectivity(&k3()).unwrap() - expected).abs() < 1e-10);
317    }
318
319    #[test]
320    fn abs_k4() {
321        // each: √((6-2)/6) = √(2/3)
322        // ABS = 6·√(2/3)
323        let expected = 6.0 * (2.0_f64 / 3.0).sqrt();
324        assert!((atom_bond_sum_connectivity(&k4()).unwrap() - expected).abs() < 1e-10);
325    }
326
327    #[test]
328    fn abs_cycle4() {
329        // each: √(2/4) = √(1/2), 4 edges
330        // ABS = 4/√2 = 2√2
331        let expected = 4.0 / 2.0_f64.sqrt();
332        assert!((atom_bond_sum_connectivity(&cycle4()).unwrap() - expected).abs() < 1e-10);
333    }
334
335    #[test]
336    fn abs_star5() {
337        // center=4, leaf=1: (4+1-2)/(4+1) = 3/5
338        // √(3/5), 4 edges
339        let expected = 4.0 * (3.0_f64 / 5.0).sqrt();
340        assert!((atom_bond_sum_connectivity(&star5()).unwrap() - expected).abs() < 1e-10);
341    }
342
343    #[test]
344    fn abs_leq_m() {
345        // ABS(G) <= m since √((d_u+d_v-2)/(d_u+d_v)) < 1
346        for g in &[path3(), k3(), k4(), cycle4(), star5()] {
347            let abs_val = atom_bond_sum_connectivity(g).unwrap();
348            assert!(abs_val < g.ecount() as f64 + 1e-10);
349        }
350    }
351
352    // --- geometric_arithmetic_index ---
353
354    #[test]
355    fn ga_empty() {
356        let g = Graph::with_vertices(0);
357        assert!((geometric_arithmetic_index(&g).unwrap() - 0.0).abs() < 1e-10);
358    }
359
360    #[test]
361    fn ga_single_edge() {
362        // 2√(1·1)/(1+1) = 2/2 = 1
363        assert!((geometric_arithmetic_index(&single_edge()).unwrap() - 1.0).abs() < 1e-10);
364    }
365
366    #[test]
367    fn ga_path3() {
368        // (0,1): 2√2/3, (1,2): same → GA = 4√2/3
369        let expected = 4.0 * 2.0_f64.sqrt() / 3.0;
370        assert!((geometric_arithmetic_index(&path3()).unwrap() - expected).abs() < 1e-10);
371    }
372
373    #[test]
374    fn ga_k3() {
375        // all equal degrees → each term = 1. GA = 3
376        assert!((geometric_arithmetic_index(&k3()).unwrap() - 3.0).abs() < 1e-10);
377    }
378
379    #[test]
380    fn ga_k4() {
381        // all equal degrees → GA = 6
382        assert!((geometric_arithmetic_index(&k4()).unwrap() - 6.0).abs() < 1e-10);
383    }
384
385    #[test]
386    fn ga_cycle4() {
387        // all equal degrees → GA = 4
388        assert!((geometric_arithmetic_index(&cycle4()).unwrap() - 4.0).abs() < 1e-10);
389    }
390
391    #[test]
392    fn ga_star5() {
393        // 2√(4·1)/5 = 4/5, 4 edges → GA = 16/5
394        let expected = 4.0 * 4.0 / 5.0;
395        assert!((geometric_arithmetic_index(&star5()).unwrap() - expected).abs() < 1e-10);
396    }
397
398    #[test]
399    fn ga_leq_m() {
400        // GA(G) <= m by AM-GM inequality (geometric mean ≤ arithmetic mean)
401        for g in &[single_edge(), path3(), k3(), k4(), cycle4(), star5()] {
402            let ga = geometric_arithmetic_index(g).unwrap();
403            assert!(ga <= g.ecount() as f64 + 1e-10);
404        }
405    }
406
407    #[test]
408    fn ga_equals_m_for_regular() {
409        // For r-regular graphs: each term = 2√(r²)/(2r) = 2r/(2r) = 1
410        // GA = m
411        for g in &[k3(), k4(), cycle4(), cycle5()] {
412            let ga = geometric_arithmetic_index(g).unwrap();
413            assert!((ga - g.ecount() as f64).abs() < 1e-10);
414        }
415    }
416
417    #[test]
418    fn ga_path4() {
419        // (0,1): 2√(1·2)/3 = 2√2/3
420        // (1,2): 2√(2·2)/4 = 2·2/4 = 1
421        // (2,3): 2√(2·1)/3 = 2√2/3
422        // GA = 4√2/3 + 1
423        let expected = 4.0 * 2.0_f64.sqrt() / 3.0 + 1.0;
424        assert!((geometric_arithmetic_index(&path4()).unwrap() - expected).abs() < 1e-10);
425    }
426
427    #[test]
428    fn ga_diamond() {
429        // K4 minus (2,3): edges 0-1,0-2,0-3,1-2,1-3
430        // deg=[3,3,2,2]
431        // (0,1): 2√9/6=1, (0,2): 2√6/5, (0,3): 2√6/5
432        // (1,2): 2√6/5, (1,3): 2√6/5
433        // GA = 1 + 4·(2√6/5) = 1 + 8√6/5
434        let g =
435            Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)], false, Some(4)).unwrap();
436        let expected = 1.0 + 8.0 * 6.0_f64.sqrt() / 5.0;
437        assert!((geometric_arithmetic_index(&g).unwrap() - expected).abs() < 1e-10);
438    }
439
440    // --- cross-consistency ---
441
442    #[test]
443    fn all_positive_for_connected() {
444        for g in &[path3(), k3(), k4(), cycle4(), star5()] {
445            assert!(augmented_zagreb_index(g).unwrap() > 0.0);
446            assert!(atom_bond_sum_connectivity(g).unwrap() > 0.0);
447            assert!(geometric_arithmetic_index(g).unwrap() > 0.0);
448        }
449    }
450
451    #[test]
452    fn with_isolated_vertex() {
453        // 0-1 plus isolated 2
454        let g = Graph::from_edges(&[(0, 1)], false, Some(3)).unwrap();
455        // single edge: d_u+d_v-2 = 0, so AZI and ABS skip it
456        assert!((augmented_zagreb_index(&g).unwrap() - 0.0).abs() < 1e-10);
457        assert!((atom_bond_sum_connectivity(&g).unwrap() - 0.0).abs() < 1e-10);
458        // GA: 2√1/2 = 1
459        assert!((geometric_arithmetic_index(&g).unwrap() - 1.0).abs() < 1e-10);
460    }
461}
rust_igraph/algorithms/properties/augmented_zagreb.rs

rust_igraph/algorithms/properties/
augmented_zagreb.rs
