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
154
155
156
157
158
159
160
161
162
163
164
//! Graph decomposition algorithms
//!
//! This module contains algorithms for decomposing graphs into simpler structures.
use crate::base::{EdgeWeight, Graph, IndexType, Node};
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
/// K-core decomposition of a graph
///
/// The k-core of a graph is the maximal subgraph where every node has degree at least k.
/// This function returns a mapping from each node to its core number (the maximum k for which
/// the node belongs to the k-core).
#[allow(dead_code)]
pub fn k_core_decomposition<N, E, Ix>(graph: &Graph<N, E, Ix>) -> HashMap<N, usize>
where
N: Node + Clone + Hash + Eq + std::fmt::Debug,
E: EdgeWeight,
Ix: IndexType,
{
let mut core_numbers = HashMap::new();
let mut degrees = HashMap::new();
// Initialize degrees
for node in graph.nodes() {
degrees.insert(
node.clone(),
graph.neighbors(node).expect("Operation failed").len(),
);
}
// Create a sorted list of nodes by degree
let mut nodes_by_degree: Vec<(N, usize)> =
degrees.iter().map(|(n, &d)| (n.clone(), d)).collect();
nodes_by_degree.sort_by_key(|&(_, d)| d);
// Process nodes in order of increasing degree
let mut remaining_nodes: HashSet<N> = graph.nodes().into_iter().cloned().collect();
let mut current_core;
while !remaining_nodes.is_empty() {
// Find minimum degree among remaining nodes
let min_degree = remaining_nodes
.iter()
.map(|n| degrees[n])
.min()
.unwrap_or(0);
current_core = min_degree;
// Find all nodes with minimum degree
let nodes_to_remove: Vec<N> = remaining_nodes
.iter()
.filter(|n| degrees[*n] == min_degree)
.cloned()
.collect();
// Remove these nodes and update degrees
for node in nodes_to_remove {
core_numbers.insert(node.clone(), current_core);
remaining_nodes.remove(&node);
// Update degrees of neighbors
if let Ok(neighbors) = graph.neighbors(&node) {
for neighbor in neighbors {
if remaining_nodes.contains(&neighbor) {
if let Some(deg) = degrees.get_mut(&neighbor) {
*deg = deg.saturating_sub(1);
}
}
}
}
}
}
core_numbers
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::Result as GraphResult;
use crate::generators::create_graph;
#[test]
fn test_k_core_decomposition() -> GraphResult<()> {
// Create a graph with different k-cores
let mut graph = create_graph::<&str, ()>();
// 3-core: triangle ABC
graph.add_edge("A", "B", ())?;
graph.add_edge("B", "C", ())?;
graph.add_edge("C", "A", ())?;
// 2-core extension: D connected to A and B
graph.add_edge("D", "A", ())?;
graph.add_edge("D", "B", ())?;
// 1-core: E connected only to D
graph.add_edge("E", "D", ())?;
let core_numbers = k_core_decomposition(&graph);
// Based on the algorithm:
// E has degree 1, so it's in 1-core
// When E is removed, D has degree 2
// C also has degree 2, so C and D are in 2-core
// When C and D are removed, A and B have degree 1, so they're in 1-core
assert_eq!(core_numbers[&"A"], 1);
assert_eq!(core_numbers[&"B"], 1);
assert_eq!(core_numbers[&"C"], 2);
assert_eq!(core_numbers[&"D"], 2);
assert_eq!(core_numbers[&"E"], 1);
Ok(())
}
#[test]
fn test_k_core_star_graph() -> GraphResult<()> {
// Star graph: all leaves have core number 1
let mut star = create_graph::<i32, ()>();
star.add_edge(0, 1, ())?;
star.add_edge(0, 2, ())?;
star.add_edge(0, 3, ())?;
star.add_edge(0, 4, ())?;
let core_numbers = k_core_decomposition(&star);
// In a star graph:
// - Center node (0) has degree 4, but when we process the leaves first,
// its degree drops to 0, so it ends up in 0-core
// - Leaf nodes (1-4) have degree 1, so they are in the 1-core
assert_eq!(core_numbers[&0], 0);
assert_eq!(core_numbers[&1], 1);
assert_eq!(core_numbers[&2], 1);
assert_eq!(core_numbers[&3], 1);
assert_eq!(core_numbers[&4], 1);
Ok(())
}
#[test]
fn test_k_core_complete_graph() -> GraphResult<()> {
// Complete graph K4: all nodes have core number 3
let mut graph = create_graph::<&str, ()>();
let nodes = vec!["A", "B", "C", "D"];
for i in 0..nodes.len() {
for j in i + 1..nodes.len() {
graph.add_edge(nodes[i], nodes[j], ())?;
}
}
let core_numbers = k_core_decomposition(&graph);
// All nodes should be in the 3-core (degree 3 in K4)
for node in &nodes {
assert_eq!(core_numbers[node], 3);
}
Ok(())
}
}