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