nordisk/facett

facett-graphview/src/analysis/kcore.rs

//! **k-core decomposition** — each node's *core number*: the largest `k` such that the
//! node survives repeatedly peeling away every node of undirected degree `< k`. High
//! core numbers mark the dense, well-connected heart of the graph.

use super::Adjacency;

/// The **core number** of every node (undirected). `core[i] = k` means `i` belongs to
/// the k-core but not the (k+1)-core. Batagelj–Zaveršnik `O(m)` peeling.
#[must_use]
pub fn core_numbers(g: &Adjacency) -> Vec<usize> {
    let n = g.n;
    let mut deg: Vec<usize> = (0..n).map(|i| g.degree(i)).collect();
    let mut core = vec![0usize; n];
    // Process nodes in non-decreasing current degree; peel, decrementing neighbours.
    let mut removed = vec![false; n];
    for _ in 0..n {
        // Find the not-yet-removed node of minimum current degree (lowest index tie).
        let mut pick = usize::MAX;
        let mut best = usize::MAX;
        for v in 0..n {
            if !removed[v] && deg[v] < best {
                best = deg[v];
                pick = v;
            }
        }
        if pick == usize::MAX {
            break;
        }
        core[pick] = best;
        removed[pick] = true;
        for &(w, _) in &g.und[pick] {
            if !removed[w] && deg[w] > best {
                deg[w] -= 1;
            }
        }
    }
    // Core number is monotone along the peel order: a node's core is the max of the
    // degree it was peeled at and never less than any earlier-peeled neighbour's — the
    // classic algorithm already yields this because we peel min-degree first.
    core
}

/// The **max core** value (the *degeneracy* of the graph) — the largest `k` for which
/// a non-empty k-core exists. `0` for an edgeless graph.
#[must_use]
pub fn degeneracy(g: &Adjacency) -> usize {
    core_numbers(g).into_iter().max().unwrap_or(0)
}

/// The node indices in the **k-core**: every node whose core number is `≥ k`.
#[must_use]
pub fn k_core(g: &Adjacency, k: usize) -> Vec<usize> {
    core_numbers(g).into_iter().enumerate().filter(|&(_, c)| c >= k).map(|(i, _)| i).collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn a_triangle_is_a_2_core() {
        // Triangle 0-1-2: every node has degree 2, so core number 2 all round.
        let g = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
        assert_eq!(core_numbers(&g), vec![2, 2, 2]);
        assert_eq!(degeneracy(&g), 2);
        assert_eq!(k_core(&g, 2).len(), 3);
        assert!(k_core(&g, 3).is_empty());
    }

    #[test]
    fn a_pendant_node_drops_out_of_the_core() {
        // Triangle 0-1-2 plus a pendant 3 hung off 0. The triangle stays a 2-core;
        // the pendant is only a 1-core.
        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 0), (0, 3)]);
        let core = core_numbers(&g);
        assert_eq!(core[3], 1, "the pendant is a 1-core node");
        assert_eq!(core[1], 2, "the triangle interior stays a 2-core");
        assert_eq!(k_core(&g, 2), vec![0, 1, 2], "the 2-core is exactly the triangle");
    }

    #[test]
    fn a_path_is_a_1_core() {
        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 3)]);
        assert_eq!(degeneracy(&g), 1);
    }

    #[test]
    fn edgeless_graph_has_zero_cores() {
        let g = Adjacency::from_edges(3, &[]);
        assert_eq!(core_numbers(&g), vec![0, 0, 0]);
        assert_eq!(degeneracy(&g), 0);
    }
}