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

scirs2_graph/algorithms/
decomposition.rs
