rust_igraph/algorithms/properties/
degree_shape.rs

1//! Degree distribution shape measures (ALGO-TR-085).
2//!
3//! Structural descriptors of the degree-frequency profile:
4//!
5//! - **Degree mode** — most frequent degree value (lowest if tied)
6//! - **Degree concentration** — fraction of vertices with mode degree
7//! - **Degree diversity** — count of distinct degree values
8//! - **Hub dominance** `HD(G) = d_max / (2m)` — max-degree share of total
9
10#![allow(
11    clippy::cast_possible_truncation,
12    clippy::cast_precision_loss,
13    clippy::many_single_char_names,
14    clippy::needless_range_loop,
15    clippy::too_many_lines
16)]
17
18use crate::core::{Graph, IgraphResult};
19use std::collections::HashMap;
20
21/// Compute the mode of the degree sequence.
22///
23/// Returns the most frequent degree value. If multiple degrees share
24/// the highest frequency, the smallest is returned. Returns 0 for
25/// empty graphs.
26///
27/// # Examples
28///
29/// ```
30/// use rust_igraph::{Graph, degree_mode};
31///
32/// // Star S_5: degrees [4,1,1,1,1] → mode = 1
33/// let g = Graph::from_edges(&[(0,1),(0,2),(0,3),(0,4)], false, Some(5)).unwrap();
34/// assert_eq!(degree_mode(&g).unwrap(), 1);
35/// ```
36pub fn degree_mode(graph: &Graph) -> IgraphResult<usize> {
37    let n = graph.vcount() as usize;
38    if n == 0 {
39        return Ok(0);
40    }
41
42    let counts = degree_counts(graph)?;
43
44    let mut best_deg = 0_usize;
45    let mut best_count = 0_usize;
46    for (&deg, &count) in &counts {
47        if count > best_count || (count == best_count && deg < best_deg) {
48            best_deg = deg;
49            best_count = count;
50        }
51    }
52
53    Ok(best_deg)
54}
55
56/// Compute the degree concentration.
57///
58/// Returns the fraction of vertices that have the mode degree.
59/// Values close to 1.0 indicate a nearly regular graph.
60/// Returns 0.0 for empty graphs.
61///
62/// # Examples
63///
64/// ```
65/// use rust_igraph::{Graph, degree_concentration};
66///
67/// // K_3: all degree 2 → concentration = 1.0
68/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2)], false, Some(3)).unwrap();
69/// assert!((degree_concentration(&g).unwrap() - 1.0).abs() < 1e-10);
70/// ```
71pub fn degree_concentration(graph: &Graph) -> IgraphResult<f64> {
72    let n = graph.vcount() as usize;
73    if n == 0 {
74        return Ok(0.0);
75    }
76
77    let counts = degree_counts(graph)?;
78    let max_count = counts.values().copied().max().unwrap_or(0);
79
80    Ok(max_count as f64 / n as f64)
81}
82
83/// Compute the degree diversity (number of distinct degree values).
84///
85/// Returns the count of distinct degrees in the graph.
86/// Regular graphs have diversity 1. Returns 0 for empty graphs.
87///
88/// # Examples
89///
90/// ```
91/// use rust_igraph::{Graph, degree_diversity};
92///
93/// // Paw: degrees {1,2,2,3} → 3 distinct values
94/// let g = Graph::from_edges(&[(0,1),(1,2),(0,2),(2,3)], false, Some(4)).unwrap();
95/// assert_eq!(degree_diversity(&g).unwrap(), 3);
96/// ```
97pub fn degree_diversity(graph: &Graph) -> IgraphResult<usize> {
98    let n = graph.vcount() as usize;
99    if n == 0 {
100        return Ok(0);
101    }
102
103    let counts = degree_counts(graph)?;
104    Ok(counts.len())
105}
106
107/// Compute the hub dominance.
108///
109/// `HD(G) = d_max / (2m)` — the fraction of total degree held by
110/// the maximum-degree vertex. Returns 0.0 for edgeless or empty
111/// graphs.
112///
113/// # Examples
114///
115/// ```
116/// use rust_igraph::{Graph, hub_dominance};
117///
118/// // Star S_5: d_max=4, 2m=8 → HD = 0.5
119/// let g = Graph::from_edges(&[(0,1),(0,2),(0,3),(0,4)], false, Some(5)).unwrap();
120/// assert!((hub_dominance(&g).unwrap() - 0.5).abs() < 1e-10);
121/// ```
122pub fn hub_dominance(graph: &Graph) -> IgraphResult<f64> {
123    let n = graph.vcount() as usize;
124    if n == 0 {
125        return Ok(0.0);
126    }
127
128    let mut d_max = 0_usize;
129    let mut total = 0_usize;
130    for v in 0..n {
131        let d = graph.degree(v as u32)?;
132        if d > d_max {
133            d_max = d;
134        }
135        total += d;
136    }
137
138    if total == 0 {
139        return Ok(0.0);
140    }
141
142    Ok(d_max as f64 / total as f64)
143}
144
145fn degree_counts(graph: &Graph) -> IgraphResult<HashMap<usize, usize>> {
146    let n = graph.vcount() as usize;
147    let mut counts: HashMap<usize, usize> = HashMap::new();
148    for v in 0..n {
149        let d = graph.degree(v as u32)?;
150        *counts.entry(d).or_insert(0) += 1;
151    }
152    Ok(counts)
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    fn single_edge() -> Graph {
160        Graph::from_edges(&[(0, 1)], false, Some(2)).unwrap()
161    }
162
163    fn path3() -> Graph {
164        Graph::from_edges(&[(0, 1), (1, 2)], false, Some(3)).unwrap()
165    }
166
167    fn k3() -> Graph {
168        Graph::from_edges(&[(0, 1), (1, 2), (0, 2)], false, Some(3)).unwrap()
169    }
170
171    fn k4() -> Graph {
172        Graph::from_edges(
173            &[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
174            false,
175            Some(4),
176        )
177        .unwrap()
178    }
179
180    fn cycle4() -> Graph {
181        Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], false, Some(4)).unwrap()
182    }
183
184    fn star5() -> Graph {
185        Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], false, Some(5)).unwrap()
186    }
187
188    fn paw() -> Graph {
189        Graph::from_edges(&[(0, 1), (1, 2), (0, 2), (2, 3)], false, Some(4)).unwrap()
190    }
191
192    // --- degree_mode ---
193
194    #[test]
195    fn mode_empty() {
196        let g = Graph::with_vertices(0);
197        assert_eq!(degree_mode(&g).unwrap(), 0);
198    }
199
200    #[test]
201    fn mode_isolated() {
202        let g = Graph::with_vertices(5);
203        assert_eq!(degree_mode(&g).unwrap(), 0);
204    }
205
206    #[test]
207    fn mode_k3() {
208        assert_eq!(degree_mode(&k3()).unwrap(), 2);
209    }
210
211    #[test]
212    fn mode_k4() {
213        assert_eq!(degree_mode(&k4()).unwrap(), 3);
214    }
215
216    #[test]
217    fn mode_single_edge() {
218        assert_eq!(degree_mode(&single_edge()).unwrap(), 1);
219    }
220
221    #[test]
222    fn mode_star5() {
223        // 4 vertices with degree 1
224        assert_eq!(degree_mode(&star5()).unwrap(), 1);
225    }
226
227    #[test]
228    fn mode_path3() {
229        // [1,2,1] → mode=1
230        assert_eq!(degree_mode(&path3()).unwrap(), 1);
231    }
232
233    #[test]
234    fn mode_paw() {
235        // [2,2,3,1] → mode=2
236        assert_eq!(degree_mode(&paw()).unwrap(), 2);
237    }
238
239    // --- degree_concentration ---
240
241    #[test]
242    fn conc_empty() {
243        let g = Graph::with_vertices(0);
244        assert!(degree_concentration(&g).unwrap().abs() < 1e-10);
245    }
246
247    #[test]
248    fn conc_regular_one() {
249        assert!((degree_concentration(&k3()).unwrap() - 1.0).abs() < 1e-10);
250        assert!((degree_concentration(&k4()).unwrap() - 1.0).abs() < 1e-10);
251        assert!((degree_concentration(&cycle4()).unwrap() - 1.0).abs() < 1e-10);
252    }
253
254    #[test]
255    fn conc_single_edge() {
256        assert!((degree_concentration(&single_edge()).unwrap() - 1.0).abs() < 1e-10);
257    }
258
259    #[test]
260    fn conc_star5() {
261        // 4/5 = 0.8
262        assert!((degree_concentration(&star5()).unwrap() - 0.8).abs() < 1e-10);
263    }
264
265    #[test]
266    fn conc_path3() {
267        // mode=1, count=2, n=3 → 2/3
268        let expected = 2.0 / 3.0;
269        assert!((degree_concentration(&path3()).unwrap() - expected).abs() < 1e-10);
270    }
271
272    #[test]
273    fn conc_paw() {
274        // mode=2, count=2, n=4 → 0.5
275        assert!((degree_concentration(&paw()).unwrap() - 0.5).abs() < 1e-10);
276    }
277
278    #[test]
279    fn conc_in_01() {
280        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
281            let val = degree_concentration(g).unwrap();
282            assert!(val >= -1e-10);
283            assert!(val <= 1.0 + 1e-10);
284        }
285    }
286
287    // --- degree_diversity ---
288
289    #[test]
290    fn div_empty() {
291        let g = Graph::with_vertices(0);
292        assert_eq!(degree_diversity(&g).unwrap(), 0);
293    }
294
295    #[test]
296    fn div_isolated() {
297        let g = Graph::with_vertices(5);
298        assert_eq!(degree_diversity(&g).unwrap(), 1);
299    }
300
301    #[test]
302    fn div_regular_one() {
303        assert_eq!(degree_diversity(&k3()).unwrap(), 1);
304        assert_eq!(degree_diversity(&k4()).unwrap(), 1);
305        assert_eq!(degree_diversity(&cycle4()).unwrap(), 1);
306    }
307
308    #[test]
309    fn div_single_edge() {
310        assert_eq!(degree_diversity(&single_edge()).unwrap(), 1);
311    }
312
313    #[test]
314    fn div_star5() {
315        // {1,4} → 2
316        assert_eq!(degree_diversity(&star5()).unwrap(), 2);
317    }
318
319    #[test]
320    fn div_path3() {
321        // {1,2} → 2
322        assert_eq!(degree_diversity(&path3()).unwrap(), 2);
323    }
324
325    #[test]
326    fn div_paw() {
327        // {1,2,3} → 3
328        assert_eq!(degree_diversity(&paw()).unwrap(), 3);
329    }
330
331    // --- hub_dominance ---
332
333    #[test]
334    fn hub_empty() {
335        let g = Graph::with_vertices(0);
336        assert!(hub_dominance(&g).unwrap().abs() < 1e-10);
337    }
338
339    #[test]
340    fn hub_isolated() {
341        let g = Graph::with_vertices(5);
342        assert!(hub_dominance(&g).unwrap().abs() < 1e-10);
343    }
344
345    #[test]
346    fn hub_regular() {
347        // d_max = d = 2m/n → HD = d/(nd) = 1/n
348        let val = hub_dominance(&k3()).unwrap();
349        assert!((val - 1.0 / 3.0).abs() < 1e-10);
350
351        let val = hub_dominance(&k4()).unwrap();
352        assert!((val - 1.0 / 4.0).abs() < 1e-10);
353    }
354
355    #[test]
356    fn hub_single_edge() {
357        // d_max=1, 2m=2 → 0.5
358        assert!((hub_dominance(&single_edge()).unwrap() - 0.5).abs() < 1e-10);
359    }
360
361    #[test]
362    fn hub_star5() {
363        // d_max=4, 2m=8 → 0.5
364        assert!((hub_dominance(&star5()).unwrap() - 0.5).abs() < 1e-10);
365    }
366
367    #[test]
368    fn hub_path3() {
369        // d_max=2, 2m=4 → 0.5
370        assert!((hub_dominance(&path3()).unwrap() - 0.5).abs() < 1e-10);
371    }
372
373    #[test]
374    fn hub_paw() {
375        // d_max=3, 2m=8 → 3/8 = 0.375
376        assert!((hub_dominance(&paw()).unwrap() - 0.375).abs() < 1e-10);
377    }
378
379    #[test]
380    fn hub_in_01() {
381        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
382            let val = hub_dominance(g).unwrap();
383            assert!(val >= -1e-10);
384            assert!(val <= 1.0 + 1e-10);
385        }
386    }
387
388    // --- cross-consistency ---
389
390    #[test]
391    fn diversity_le_n() {
392        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
393            assert!(degree_diversity(g).unwrap() <= g.vcount() as usize);
394        }
395    }
396
397    #[test]
398    fn conc_ge_1_over_n() {
399        for g in &[single_edge(), path3(), k3(), k4(), star5(), paw()] {
400            let n = f64::from(g.vcount());
401            assert!(degree_concentration(g).unwrap() >= 1.0 / n - 1e-10);
402        }
403    }
404}
rust_igraph/algorithms/properties/degree_shape.rs

rust_igraph/algorithms/properties/
degree_shape.rs
