uni_algo/algo/algorithms/
kcore.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! K-Core Decomposition Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use uni_common::core::id::Vid;
9
10pub struct KCore;
11
12#[derive(Debug, Clone, Default)]
13pub struct KCoreConfig {
14    pub k: Option<usize>, // If Some, returns only nodes in k-core. If None, returns core number for all.
15}
16
17pub struct KCoreResult {
18    pub core_numbers: Vec<(Vid, u32)>,
19}
20
21impl Algorithm for KCore {
22    type Config = KCoreConfig;
23    type Result = KCoreResult;
24
25    fn name() -> &'static str {
26        "kCore"
27    }
28
29    fn needs_reverse() -> bool {
30        // K-core is typically defined for undirected graphs.
31        true
32    }
33
34    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
35        let n = graph.vertex_count();
36        if n == 0 {
37            return KCoreResult {
38                core_numbers: Vec::new(),
39            };
40        }
41
42        // 1. Compute degrees (undirected)
43        let mut degrees = vec![0u32; n];
44        let mut max_degree = 0;
45
46        for (v, deg_ref) in degrees.iter_mut().enumerate() {
47            let mut deg = graph.out_degree(v as u32);
48            if graph.has_reverse() {
49                deg += graph.in_degree(v as u32);
50            }
51            *deg_ref = deg;
52            if deg > max_degree {
53                max_degree = deg;
54            }
55        }
56        // 2. Bucket sort
57        // bins[d] contains list of vertices with degree d
58        // We need efficient move.
59        // Array of list heads? Doubly linked list for vertices?
60        // Standard O(V+E) implementation uses:
61        // - pos[v]: position of v in sorted array
62        // - vert[i]: vertex at position i in sorted array
63        // - bin[d]: starting position of degree d in sorted array
64
65        let mut vert = vec![0u32; n];
66        let mut pos = vec![0usize; n];
67        let mut bin = vec![0usize; max_degree as usize + 1];
68
69        // Histogram
70        for &d in &degrees {
71            bin[d as usize] += 1;
72        }
73
74        // Cumulative sum for start positions
75        let mut start = 0;
76        for b in &mut bin {
77            let num = *b;
78            *b = start;
79            start += num;
80        }
81
82        // Fill array
83        for v in 0..n {
84            let d = degrees[v] as usize;
85            pos[v] = bin[d];
86            vert[pos[v]] = v as u32;
87            bin[d] += 1;
88        }
89
90        // Restore bin starts (shift right)
91        for d in (1..=max_degree as usize).rev() {
92            bin[d] = bin[d - 1];
93        }
94        bin[0] = 0;
95
96        // 3. Peeling
97        // Iterate through vertices in sorted order
98        for i in 0..n {
99            let v = vert[i]; // vertex with smallest current degree
100            let deg_v = degrees[v as usize];
101
102            // Iterate neighbors
103            // We need unique neighbors to avoid double decrementing if u->v and v->u exist
104            let mut neighbors = Vec::new();
105            neighbors.extend_from_slice(graph.out_neighbors(v));
106            if graph.has_reverse() {
107                neighbors.extend_from_slice(graph.in_neighbors(v));
108            }
109            neighbors.sort_unstable();
110            neighbors.dedup();
111
112            for &u in &neighbors {
113                let u_idx = u as usize;
114                if degrees[u_idx] > deg_v {
115                    let deg_u = degrees[u_idx] as usize;
116                    let pos_u = pos[u_idx];
117                    let pos_w = bin[deg_u];
118                    let w = vert[pos_w]; // First vertex with degree deg_u
119
120                    // Swap u with w (move u to start of bin)
121                    if u != w {
122                        pos[u_idx] = pos_w;
123                        pos[w as usize] = pos_u;
124                        vert[pos_u] = w;
125                        vert[pos_w] = u;
126                    }
127
128                    // Increment bin start for deg_u (effectively removing u from bin deg_u)
129                    bin[deg_u] += 1;
130                    // u is now at the end of bin[deg_u-1] (conceptually) or effectively shifted
131                    degrees[u_idx] -= 1;
132                }
133            }
134        }
135
136        let mut results = Vec::new();
137        if let Some(k) = config.k {
138            for (v, &deg) in degrees.iter().enumerate() {
139                if deg >= k as u32 {
140                    results.push((graph.to_vid(v as u32), deg));
141                }
142            }
143        } else {
144            for (v, &deg) in degrees.iter().enumerate() {
145                results.push((graph.to_vid(v as u32), deg));
146            }
147        }
148
149        KCoreResult {
150            core_numbers: results,
151        }
152    }
153}
uni_algo/algo/algorithms/kcore.rs

uni_algo/algo/algorithms/
kcore.rs
