sz_orm_graph/
path_analysis.rs

1//! 图路径分析（Path Analysis）
2//!
3//! 提供路径查找、路径枚举、可达性分析等功能。
4
5use std::collections::{HashMap, HashSet, VecDeque};
6
7use crate::algorithm::{DirectedGraph, NodeId};
8
9/// 路径分析器
10pub struct PathAnalyzer;
11
12impl PathAnalyzer {
13    /// 检查从 `from` 到 `to` 是否可达
14    pub fn is_reachable(graph: &DirectedGraph, from: NodeId, to: NodeId) -> bool {
15        if from == to {
16            return true;
17        }
18        if !graph.has_node(from) || !graph.has_node(to) {
19            return false;
20        }
21        let bfs = graph.bfs(from);
22        bfs.contains(&to)
23    }
24
25    /// 查找从 `from` 到 `to` 的所有简单路径（限制最大长度）
26    ///
27    /// 简单路径：不重复访问节点。
28    /// `max_depth` 限制路径最大长度，防止指数爆炸。
29    pub fn find_all_paths(
30        graph: &DirectedGraph,
31        from: NodeId,
32        to: NodeId,
33        max_depth: usize,
34    ) -> Vec<Vec<NodeId>> {
35        if !graph.has_node(from) || !graph.has_node(to) {
36            return Vec::new();
37        }
38        let mut results = Vec::new();
39        let mut current_path = vec![from];
40        let mut visited = HashSet::new();
41        visited.insert(from);
42        Self::find_paths_dfs(
43            graph,
44            from,
45            to,
46            max_depth,
47            &mut current_path,
48            &mut visited,
49            &mut results,
50        );
51        results
52    }
53
54    fn find_paths_dfs(
55        graph: &DirectedGraph,
56        current: NodeId,
57        target: NodeId,
58        max_depth: usize,
59        current_path: &mut Vec<NodeId>,
60        visited: &mut HashSet<NodeId>,
61        results: &mut Vec<Vec<NodeId>>,
62    ) {
63        if current == target {
64            results.push(current_path.clone());
65            return;
66        }
67        if current_path.len() >= max_depth {
68            return;
69        }
70        if let Some(neighbors) = graph.neighbors(current) {
71            for &(neighbor, _) in neighbors {
72                if visited.insert(neighbor) {
73                    current_path.push(neighbor);
74                    Self::find_paths_dfs(
75                        graph,
76                        neighbor,
77                        target,
78                        max_depth,
79                        current_path,
80                        visited,
81                        results,
82                    );
83                    current_path.pop();
84                    visited.remove(&neighbor);
85                }
86            }
87        }
88    }
89
90    /// 计算从 `from` 到 `to` 的最短路径长度（BFS）
91    pub fn shortest_path_length(graph: &DirectedGraph, from: NodeId, to: NodeId) -> Option<usize> {
92        if from == to {
93            return Some(0);
94        }
95        if !graph.has_node(from) || !graph.has_node(to) {
96            return None;
97        }
98        let mut visited = HashSet::new();
99        let mut queue = VecDeque::new();
100        visited.insert(from);
101        queue.push_back((from, 0usize));
102        while let Some((node, dist)) = queue.pop_front() {
103            if let Some(neighbors) = graph.neighbors(node) {
104                for &(neighbor, _) in neighbors {
105                    if neighbor == to {
106                        return Some(dist + 1);
107                    }
108                    if visited.insert(neighbor) {
109                        queue.push_back((neighbor, dist + 1));
110                    }
111                }
112            }
113        }
114        None
115    }
116
117    /// 计算从 `start` 到所有可达节点的最短距离
118    pub fn bfs_distances(graph: &DirectedGraph, start: NodeId) -> HashMap<NodeId, usize> {
119        let mut distances = HashMap::new();
120        if !graph.has_node(start) {
121            return distances;
122        }
123        let mut visited = HashSet::new();
124        let mut queue = VecDeque::new();
125        distances.insert(start, 0);
126        visited.insert(start);
127        queue.push_back(start);
128        while let Some(node) = queue.pop_front() {
129            let dist = distances[&node];
130            if let Some(neighbors) = graph.neighbors(node) {
131                for &(neighbor, _) in neighbors {
132                    if visited.insert(neighbor) {
133                        distances.insert(neighbor, dist + 1);
134                        queue.push_back(neighbor);
135                    }
136                }
137            }
138        }
139        distances
140    }
141
142    /// 查找从 `start` 可达的所有节点
143    pub fn reachable_nodes(graph: &DirectedGraph, start: NodeId) -> HashSet<NodeId> {
144        graph.bfs(start).into_iter().collect()
145    }
146
147    /// 计算图的直径（最长最短路径）
148    ///
149    /// 对于无权图，直径是所有节点对之间最短路径的最大值。
150    pub fn diameter(graph: &DirectedGraph) -> Option<usize> {
151        let nodes: Vec<NodeId> = graph.nodes().collect();
152        let mut max_dist = 0;
153        let mut found = false;
154        for &start in &nodes {
155            let distances = Self::bfs_distances(graph, start);
156            for &dist in distances.values() {
157                if dist > max_dist {
158                    max_dist = dist;
159                    found = true;
160                }
161            }
162        }
163        if found {
164            Some(max_dist)
165        } else {
166            None
167        }
168    }
169
170    /// 计算节点偏心度（到最远可达节点的距离）
171    pub fn eccentricity(graph: &DirectedGraph, node: NodeId) -> Option<usize> {
172        let distances = Self::bfs_distances(graph, node);
173        distances.values().copied().max()
174    }
175
176    /// 计算图的半径（最小偏心度）
177    pub fn radius(graph: &DirectedGraph) -> Option<usize> {
178        let nodes: Vec<NodeId> = graph.nodes().collect();
179        let mut min_ecc = usize::MAX;
180        for &node in &nodes {
181            if let Some(ecc) = Self::eccentricity(graph, node) {
182                if ecc < min_ecc {
183                    min_ecc = ecc;
184                }
185            }
186        }
187        if min_ecc != usize::MAX {
188            Some(min_ecc)
189        } else {
190            None
191        }
192    }
193}
194
195/// 可达性矩阵
196pub struct ReachabilityMatrix {
197    matrix: HashMap<(NodeId, NodeId), bool>,
198    node_count: usize,
199}
200
201impl ReachabilityMatrix {
202    /// 从图构建可达性矩阵
203    pub fn from_graph(graph: &DirectedGraph) -> Self {
204        let nodes: Vec<NodeId> = graph.nodes().collect();
205        let mut matrix = HashMap::new();
206        for &start in &nodes {
207            let reachable = PathAnalyzer::reachable_nodes(graph, start);
208            for &end in &nodes {
209                matrix.insert((start, end), reachable.contains(&end));
210            }
211        }
212        Self {
213            matrix,
214            node_count: nodes.len(),
215        }
216    }
217
218    /// 检查 `from` 是否可达 `to`
219    pub fn is_reachable(&self, from: NodeId, to: NodeId) -> bool {
220        self.matrix.get(&(from, to)).copied().unwrap_or(false)
221    }
222
223    /// 节点数
224    pub fn node_count(&self) -> usize {
225        self.node_count
226    }
227
228    /// 可达对数
229    pub fn reachable_pairs(&self) -> usize {
230        self.matrix.values().filter(|&&v| v).count()
231    }
232
233    /// 总对数
234    pub fn total_pairs(&self) -> usize {
235        self.matrix.len()
236    }
237
238    /// 可达率
239    pub fn reachability_rate(&self) -> f64 {
240        let total = self.total_pairs();
241        if total > 0 {
242            self.reachable_pairs() as f64 / total as f64
243        } else {
244            0.0
245        }
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    #[test]
254    fn test_is_reachable_same_node() {
255        let mut g = DirectedGraph::new();
256        g.add_node(1);
257        assert!(PathAnalyzer::is_reachable(&g, 1, 1));
258    }
259
260    #[test]
261    fn test_is_reachable_direct_edge() {
262        let mut g = DirectedGraph::new();
263        g.add_edge_unweighted(1, 2);
264        assert!(PathAnalyzer::is_reachable(&g, 1, 2));
265    }
266
267    #[test]
268    fn test_is_reachable_transitive() {
269        let mut g = DirectedGraph::new();
270        g.add_edge_unweighted(1, 2);
271        g.add_edge_unweighted(2, 3);
272        assert!(PathAnalyzer::is_reachable(&g, 1, 3));
273    }
274
275    #[test]
276    fn test_is_reachable_unreachable() {
277        let mut g = DirectedGraph::new();
278        g.add_edge_unweighted(1, 2);
279        g.add_node(3);
280        assert!(!PathAnalyzer::is_reachable(&g, 1, 3));
281    }
282
283    #[test]
284    fn test_find_all_paths_single() {
285        let mut g = DirectedGraph::new();
286        g.add_edge_unweighted(1, 2);
287        let paths = PathAnalyzer::find_all_paths(&g, 1, 2, 10);
288        assert_eq!(paths.len(), 1);
289        assert_eq!(paths[0], vec![1, 2]);
290    }
291
292    #[test]
293    fn test_find_all_paths_multiple() {
294        let mut g = DirectedGraph::new();
295        g.add_edge_unweighted(1, 2);
296        g.add_edge_unweighted(2, 4);
297        g.add_edge_unweighted(1, 3);
298        g.add_edge_unweighted(3, 4);
299        let paths = PathAnalyzer::find_all_paths(&g, 1, 4, 10);
300        assert_eq!(paths.len(), 2);
301    }
302
303    #[test]
304    fn test_find_all_paths_none() {
305        let mut g = DirectedGraph::new();
306        g.add_edge_unweighted(1, 2);
307        g.add_node(3);
308        let paths = PathAnalyzer::find_all_paths(&g, 1, 3, 10);
309        assert!(paths.is_empty());
310    }
311
312    #[test]
313    fn test_shortest_path_length_direct() {
314        let mut g = DirectedGraph::new();
315        g.add_edge_unweighted(1, 2);
316        assert_eq!(PathAnalyzer::shortest_path_length(&g, 1, 2), Some(1));
317    }
318
319    #[test]
320    fn test_shortest_path_length_transitive() {
321        let mut g = DirectedGraph::new();
322        g.add_edge_unweighted(1, 2);
323        g.add_edge_unweighted(2, 3);
324        assert_eq!(PathAnalyzer::shortest_path_length(&g, 1, 3), Some(2));
325    }
326
327    #[test]
328    fn test_shortest_path_length_same() {
329        let mut g = DirectedGraph::new();
330        g.add_node(1);
331        assert_eq!(PathAnalyzer::shortest_path_length(&g, 1, 1), Some(0));
332    }
333
334    #[test]
335    fn test_shortest_path_length_unreachable() {
336        let mut g = DirectedGraph::new();
337        g.add_edge_unweighted(1, 2);
338        g.add_node(3);
339        assert_eq!(PathAnalyzer::shortest_path_length(&g, 1, 3), None);
340    }
341
342    #[test]
343    fn test_bfs_distances() {
344        let mut g = DirectedGraph::new();
345        g.add_edge_unweighted(1, 2);
346        g.add_edge_unweighted(1, 3);
347        g.add_edge_unweighted(2, 4);
348        let dist = PathAnalyzer::bfs_distances(&g, 1);
349        assert_eq!(dist[&1], 0);
350        assert_eq!(dist[&2], 1);
351        assert_eq!(dist[&3], 1);
352        assert_eq!(dist[&4], 2);
353    }
354
355    #[test]
356    fn test_reachable_nodes() {
357        let mut g = DirectedGraph::new();
358        g.add_edge_unweighted(1, 2);
359        g.add_edge_unweighted(2, 3);
360        g.add_node(4);
361        let reachable = PathAnalyzer::reachable_nodes(&g, 1);
362        assert_eq!(reachable.len(), 3);
363        assert!(!reachable.contains(&4));
364    }
365
366    #[test]
367    fn test_diameter() {
368        let mut g = DirectedGraph::new();
369        g.add_edge_unweighted(1, 2);
370        g.add_edge_unweighted(2, 3);
371        g.add_edge_unweighted(3, 4);
372        assert_eq!(PathAnalyzer::diameter(&g), Some(3));
373    }
374
375    #[test]
376    fn test_diameter_disconnected() {
377        let mut g = DirectedGraph::new();
378        g.add_edge_unweighted(1, 2);
379        g.add_edge_unweighted(3, 4);
380        assert_eq!(PathAnalyzer::diameter(&g), Some(1));
381    }
382
383    #[test]
384    fn test_eccentricity() {
385        let mut g = DirectedGraph::new();
386        g.add_edge_unweighted(1, 2);
387        g.add_edge_unweighted(2, 3);
388        assert_eq!(PathAnalyzer::eccentricity(&g, 1), Some(2));
389        assert_eq!(PathAnalyzer::eccentricity(&g, 2), Some(1));
390    }
391
392    #[test]
393    fn test_radius() {
394        let mut g = DirectedGraph::new();
395        g.add_edge_unweighted(1, 2);
396        g.add_edge_unweighted(2, 3);
397        let radius = PathAnalyzer::radius(&g).unwrap();
398        assert!((0..=2).contains(&radius));
399    }
400
401    #[test]
402    fn test_reachability_matrix() {
403        let mut g = DirectedGraph::new();
404        g.add_edge_unweighted(1, 2);
405        g.add_edge_unweighted(2, 3);
406        let matrix = ReachabilityMatrix::from_graph(&g);
407        assert!(matrix.is_reachable(1, 3));
408        assert!(!matrix.is_reachable(3, 1));
409    }
410
411    #[test]
412    fn test_reachability_matrix_node_count() {
413        let mut g = DirectedGraph::new();
414        g.add_edge_unweighted(1, 2);
415        let matrix = ReachabilityMatrix::from_graph(&g);
416        assert_eq!(matrix.node_count(), 2);
417    }
418
419    #[test]
420    fn test_reachability_matrix_reachable_pairs() {
421        let mut g = DirectedGraph::new();
422        g.add_edge_unweighted(1, 2);
423        let matrix = ReachabilityMatrix::from_graph(&g);
424        assert!(matrix.reachable_pairs() > 0);
425    }
426
427    #[test]
428    fn test_reachability_matrix_rate() {
429        let mut g = DirectedGraph::new();
430        g.add_edge_unweighted(1, 2);
431        g.add_edge_unweighted(2, 1);
432        let matrix = ReachabilityMatrix::from_graph(&g);
433        assert!((matrix.reachability_rate() - 1.0).abs() < 0.001);
434    }
435
436    #[test]
437    fn test_find_all_paths_max_depth() {
438        let mut g = DirectedGraph::new();
439        g.add_edge_unweighted(1, 2);
440        g.add_edge_unweighted(2, 3);
441        g.add_edge_unweighted(3, 4);
442        let paths = PathAnalyzer::find_all_paths(&g, 1, 4, 2);
443        assert!(paths.is_empty());
444    }
445}
sz_orm_graph/path_analysis.rs

sz_orm_graph/
path_analysis.rs
