sz_orm_graph/
graph_stats.rs

1//! 图属性统计（Graph Stats）
2//!
3//! 计算图的各种属性：度分布、密度、聚类系数等。
4
5use std::collections::HashMap;
6
7use crate::algorithm::{DirectedGraph, NodeId, UndirectedGraph};
8
9/// 图统计信息
10#[derive(Debug, Clone, serde::Serialize)]
11pub struct GraphStats {
12    pub node_count: usize,
13    pub edge_count: usize,
14    pub density: f64,
15    pub avg_degree: f64,
16    pub max_degree: usize,
17    pub min_degree: usize,
18    pub is_connected: bool,
19    pub component_count: usize,
20    pub has_cycle: bool,
21    pub largest_component_size: usize,
22}
23
24/// 度分布统计
25#[derive(Debug, Clone, serde::Serialize)]
26pub struct DegreeDistribution {
27    pub degree: usize,
28    pub count: usize,
29    pub fraction: f64,
30}
31
32/// 图统计计算器
33pub struct GraphStatsCalculator;
34
35impl GraphStatsCalculator {
36    /// 计算有向图统计
37    pub fn directed(graph: &DirectedGraph) -> GraphStats {
38        let node_count = graph.node_count();
39        let edge_count = graph.edge_count();
40        let components = graph.connected_components();
41        let component_count = components.len();
42        let largest_component_size = components.iter().map(|c| c.len()).max().unwrap_or(0);
43        let mut degrees: Vec<usize> = graph
44            .nodes()
45            .map(|n| graph.in_degree(n) + graph.out_degree(n))
46            .collect();
47        degrees.sort_unstable();
48        let max_degree = degrees.last().copied().unwrap_or(0);
49        let min_degree = degrees.first().copied().unwrap_or(0);
50        let avg_degree = if node_count > 0 {
51            degrees.iter().sum::<usize>() as f64 / node_count as f64
52        } else {
53            0.0
54        };
55        let density = if node_count > 1 {
56            edge_count as f64 / (node_count * (node_count - 1)) as f64
57        } else {
58            0.0
59        };
60        GraphStats {
61            node_count,
62            edge_count,
63            density,
64            avg_degree,
65            max_degree,
66            min_degree,
67            is_connected: component_count <= 1,
68            component_count,
69            has_cycle: graph.has_cycle(),
70            largest_component_size,
71        }
72    }
73
74    /// 计算无向图统计
75    pub fn undirected(graph: &UndirectedGraph) -> GraphStats {
76        let node_count = graph.node_count();
77        let edge_count = graph.edge_count();
78        let components = graph.connected_components();
79        let component_count = components.len();
80        let largest_component_size = components.iter().map(|c| c.len()).max().unwrap_or(0);
81        let mut degrees: Vec<usize> = (0..node_count as NodeId).map(|n| graph.degree(n)).collect();
82        degrees.sort_unstable();
83        let max_degree = degrees.last().copied().unwrap_or(0);
84        let min_degree = degrees.first().copied().unwrap_or(0);
85        let avg_degree = if node_count > 0 {
86            degrees.iter().sum::<usize>() as f64 / node_count as f64
87        } else {
88            0.0
89        };
90        let density = if node_count > 1 {
91            2.0 * edge_count as f64 / (node_count * (node_count - 1)) as f64
92        } else {
93            0.0
94        };
95        GraphStats {
96            node_count,
97            edge_count,
98            density,
99            avg_degree,
100            max_degree,
101            min_degree,
102            is_connected: component_count <= 1,
103            component_count,
104            has_cycle: false,
105            largest_component_size,
106        }
107    }
108
109    /// 计算度分布
110    pub fn degree_distribution_directed(graph: &DirectedGraph) -> Vec<DegreeDistribution> {
111        let mut degree_counts: HashMap<usize, usize> = HashMap::new();
112        let node_count = graph.node_count();
113        for node in graph.nodes() {
114            let degree = graph.in_degree(node) + graph.out_degree(node);
115            *degree_counts.entry(degree).or_insert(0) += 1;
116        }
117        let mut dist: Vec<DegreeDistribution> = degree_counts
118            .into_iter()
119            .map(|(degree, count)| DegreeDistribution {
120                degree,
121                count,
122                fraction: if node_count > 0 {
123                    count as f64 / node_count as f64
124                } else {
125                    0.0
126                },
127            })
128            .collect();
129        dist.sort_by_key(|d| d.degree);
130        dist
131    }
132
133    /// 计算度分布
134    pub fn degree_distribution_undirected(graph: &UndirectedGraph) -> Vec<DegreeDistribution> {
135        let mut degree_counts: HashMap<usize, usize> = HashMap::new();
136        let node_count = graph.node_count();
137        for node in 0..node_count as NodeId {
138            let degree = graph.degree(node);
139            *degree_counts.entry(degree).or_insert(0) += 1;
140        }
141        let mut dist: Vec<DegreeDistribution> = degree_counts
142            .into_iter()
143            .map(|(degree, count)| DegreeDistribution {
144                degree,
145                count,
146                fraction: if node_count > 0 {
147                    count as f64 / node_count as f64
148                } else {
149                    0.0
150                },
151            })
152            .collect();
153        dist.sort_by_key(|d| d.degree);
154        dist
155    }
156}
157
158impl GraphStats {
159    pub fn to_json(&self) -> serde_json::Value {
160        serde_json::to_value(self).unwrap_or(serde_json::Value::Null)
161    }
162
163    pub fn to_summary(&self) -> String {
164        format!(
165            "Graph: {} nodes, {} edges, density={:.4}, {} components, cycle={}",
166            self.node_count, self.edge_count, self.density, self.component_count, self.has_cycle
167        )
168    }
169}
170
171#[cfg(test)]
172mod tests {
173    use super::*;
174
175    #[test]
176    fn test_graph_stats_empty() {
177        let g = DirectedGraph::new();
178        let stats = GraphStatsCalculator::directed(&g);
179        assert_eq!(stats.node_count, 0);
180        assert_eq!(stats.edge_count, 0);
181    }
182
183    #[test]
184    fn test_graph_stats_single_node() {
185        let mut g = DirectedGraph::new();
186        g.add_node(1);
187        let stats = GraphStatsCalculator::directed(&g);
188        assert_eq!(stats.node_count, 1);
189        assert_eq!(stats.edge_count, 0);
190        assert!(stats.is_connected);
191    }
192
193    #[test]
194    fn test_graph_stats_simple() {
195        let mut g = DirectedGraph::new();
196        g.add_edge_unweighted(1, 2);
197        g.add_edge_unweighted(2, 3);
198        let stats = GraphStatsCalculator::directed(&g);
199        assert_eq!(stats.node_count, 3);
200        assert_eq!(stats.edge_count, 2);
201        assert!(stats.is_connected);
202        assert!(!stats.has_cycle);
203    }
204
205    #[test]
206    fn test_graph_stats_density() {
207        let mut g = DirectedGraph::new();
208        g.add_edge_unweighted(1, 2);
209        g.add_edge_unweighted(2, 1);
210        let stats = GraphStatsCalculator::directed(&g);
211        assert!((stats.density - 1.0).abs() < 0.001);
212    }
213
214    #[test]
215    fn test_graph_stats_disconnected() {
216        let mut g = DirectedGraph::new();
217        g.add_edge_unweighted(1, 2);
218        g.add_edge_unweighted(3, 4);
219        let stats = GraphStatsCalculator::directed(&g);
220        assert!(!stats.is_connected);
221        assert_eq!(stats.component_count, 2);
222    }
223
224    #[test]
225    fn test_graph_stats_with_cycle() {
226        let mut g = DirectedGraph::new();
227        g.add_edge_unweighted(1, 2);
228        g.add_edge_unweighted(2, 3);
229        g.add_edge_unweighted(3, 1);
230        let stats = GraphStatsCalculator::directed(&g);
231        assert!(stats.has_cycle);
232    }
233
234    #[test]
235    fn test_graph_stats_largest_component() {
236        let mut g = DirectedGraph::new();
237        g.add_edge_unweighted(1, 2);
238        g.add_edge_unweighted(2, 3);
239        g.add_edge_unweighted(4, 5);
240        let stats = GraphStatsCalculator::directed(&g);
241        assert_eq!(stats.largest_component_size, 3);
242    }
243
244    #[test]
245    fn test_graph_stats_avg_degree() {
246        let mut g = DirectedGraph::new();
247        g.add_edge_unweighted(1, 2);
248        g.add_edge_unweighted(1, 3);
249        let stats = GraphStatsCalculator::directed(&g);
250        assert!((stats.avg_degree - 4.0 / 3.0).abs() < 0.001);
251    }
252
253    #[test]
254    fn test_graph_stats_max_min_degree() {
255        let mut g = DirectedGraph::new();
256        g.add_edge_unweighted(1, 2);
257        g.add_edge_unweighted(1, 3);
258        g.add_edge_unweighted(1, 4);
259        let stats = GraphStatsCalculator::directed(&g);
260        assert_eq!(stats.max_degree, 3);
261        assert_eq!(stats.min_degree, 1);
262    }
263
264    #[test]
265    fn test_degree_distribution_directed() {
266        let mut g = DirectedGraph::new();
267        g.add_edge_unweighted(1, 2);
268        g.add_edge_unweighted(1, 3);
269        let dist = GraphStatsCalculator::degree_distribution_directed(&g);
270        assert!(!dist.is_empty());
271        let total: usize = dist.iter().map(|d| d.count).sum();
272        assert_eq!(total, 3);
273    }
274
275    #[test]
276    fn test_degree_distribution_undirected() {
277        let mut g = UndirectedGraph::new();
278        g.add_edge_unweighted(1, 2);
279        g.add_edge_unweighted(1, 3);
280        let dist = GraphStatsCalculator::degree_distribution_undirected(&g);
281        assert!(!dist.is_empty());
282    }
283
284    #[test]
285    fn test_graph_stats_to_json() {
286        let g = DirectedGraph::new();
287        let stats = GraphStatsCalculator::directed(&g);
288        let json = stats.to_json();
289        assert!(json.is_object());
290    }
291
292    #[test]
293    fn test_graph_stats_to_summary() {
294        let mut g = DirectedGraph::new();
295        g.add_edge_unweighted(1, 2);
296        let stats = GraphStatsCalculator::directed(&g);
297        let summary = stats.to_summary();
298        assert!(summary.contains("2 nodes"));
299    }
300
301    #[test]
302    fn test_undirected_stats() {
303        let mut g = UndirectedGraph::new();
304        g.add_edge_unweighted(1, 2);
305        g.add_edge_unweighted(2, 3);
306        let stats = GraphStatsCalculator::undirected(&g);
307        assert_eq!(stats.node_count, 3);
308        assert_eq!(stats.edge_count, 2);
309        assert!(stats.is_connected);
310    }
311
312    #[test]
313    fn test_undirected_stats_density() {
314        let mut g = UndirectedGraph::new();
315        g.add_edge_unweighted(1, 2);
316        g.add_edge_unweighted(1, 3);
317        g.add_edge_unweighted(2, 3);
318        let stats = GraphStatsCalculator::undirected(&g);
319        assert!((stats.density - 1.0).abs() < 0.001);
320    }
321}
sz_orm_graph/graph_stats.rs

sz_orm_graph/
graph_stats.rs
