facett_graphview/analysis/
kcore.rs

1//! **k-core decomposition** — each node's *core number*: the largest `k` such that the
2//! node survives repeatedly peeling away every node of undirected degree `< k`. High
3//! core numbers mark the dense, well-connected heart of the graph.
4
5use super::Adjacency;
6
7/// The **core number** of every node (undirected). `core[i] = k` means `i` belongs to
8/// the k-core but not the (k+1)-core. Batagelj–Zaveršnik `O(m)` peeling.
9#[must_use]
10pub fn core_numbers(g: &Adjacency) -> Vec<usize> {
11    let n = g.n;
12    let mut deg: Vec<usize> = (0..n).map(|i| g.degree(i)).collect();
13    let mut core = vec![0usize; n];
14    // Process nodes in non-decreasing current degree; peel, decrementing neighbours.
15    let mut removed = vec![false; n];
16    for _ in 0..n {
17        // Find the not-yet-removed node of minimum current degree (lowest index tie).
18        let mut pick = usize::MAX;
19        let mut best = usize::MAX;
20        for v in 0..n {
21            if !removed[v] && deg[v] < best {
22                best = deg[v];
23                pick = v;
24            }
25        }
26        if pick == usize::MAX {
27            break;
28        }
29        core[pick] = best;
30        removed[pick] = true;
31        for &(w, _) in &g.und[pick] {
32            if !removed[w] && deg[w] > best {
33                deg[w] -= 1;
34            }
35        }
36    }
37    // Core number is monotone along the peel order: a node's core is the max of the
38    // degree it was peeled at and never less than any earlier-peeled neighbour's — the
39    // classic algorithm already yields this because we peel min-degree first.
40    core
41}
42
43/// The **max core** value (the *degeneracy* of the graph) — the largest `k` for which
44/// a non-empty k-core exists. `0` for an edgeless graph.
45#[must_use]
46pub fn degeneracy(g: &Adjacency) -> usize {
47    core_numbers(g).into_iter().max().unwrap_or(0)
48}
49
50/// The node indices in the **k-core**: every node whose core number is `≥ k`.
51#[must_use]
52pub fn k_core(g: &Adjacency, k: usize) -> Vec<usize> {
53    core_numbers(g).into_iter().enumerate().filter(|&(_, c)| c >= k).map(|(i, _)| i).collect()
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn a_triangle_is_a_2_core() {
62        // Triangle 0-1-2: every node has degree 2, so core number 2 all round.
63        let g = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
64        assert_eq!(core_numbers(&g), vec![2, 2, 2]);
65        assert_eq!(degeneracy(&g), 2);
66        assert_eq!(k_core(&g, 2).len(), 3);
67        assert!(k_core(&g, 3).is_empty());
68    }
69
70    #[test]
71    fn a_pendant_node_drops_out_of_the_core() {
72        // Triangle 0-1-2 plus a pendant 3 hung off 0. The triangle stays a 2-core;
73        // the pendant is only a 1-core.
74        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 0), (0, 3)]);
75        let core = core_numbers(&g);
76        assert_eq!(core[3], 1, "the pendant is a 1-core node");
77        assert_eq!(core[1], 2, "the triangle interior stays a 2-core");
78        assert_eq!(k_core(&g, 2), vec![0, 1, 2], "the 2-core is exactly the triangle");
79    }
80
81    #[test]
82    fn a_path_is_a_1_core() {
83        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 3)]);
84        assert_eq!(degeneracy(&g), 1);
85    }
86
87    #[test]
88    fn edgeless_graph_has_zero_cores() {
89        let g = Adjacency::from_edges(3, &[]);
90        assert_eq!(core_numbers(&g), vec![0, 0, 0]);
91        assert_eq!(degeneracy(&g), 0);
92    }
93}
facett_graphview/analysis/kcore.rs

facett_graphview/analysis/
kcore.rs
