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

scirs2_graph/algorithms/
decomposition.rs
