uni_algo/algo/algorithms/
cycle_detection.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Cycle Detection Algorithm.
5//!
6//! Uses DFS to detect cycles in a directed graph.
7//! Returns `true` and the nodes involved in the first detected cycle.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct CycleDetection;
14
15#[derive(Debug, Clone, Default)]
16pub struct CycleDetectionConfig {}
17
18pub struct CycleDetectionResult {
19    pub has_cycle: bool,
20    pub cycle_nodes: Vec<Vid>,
21}
22
23impl Algorithm for CycleDetection {
24    type Config = CycleDetectionConfig;
25    type Result = CycleDetectionResult;
26
27    fn name() -> &'static str {
28        "cycle_detection"
29    }
30
31    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
32        let n = graph.vertex_count();
33        if n == 0 {
34            return CycleDetectionResult {
35                has_cycle: false,
36                cycle_nodes: Vec::new(),
37            };
38        }
39
40        // 0: unvisited, 1: visiting, 2: visited
41        let mut state = vec![0u8; n];
42        let mut parent = vec![None; n];
43
44        for v in 0..n {
45            if state[v] == 0
46                && let Some(cycle) = find_cycle(v as u32, graph, &mut state, &mut parent)
47            {
48                let cycle_vids = cycle.into_iter().map(|idx| graph.to_vid(idx)).collect();
49                return CycleDetectionResult {
50                    has_cycle: true,
51                    cycle_nodes: cycle_vids,
52                };
53            }
54        }
55
56        CycleDetectionResult {
57            has_cycle: false,
58            cycle_nodes: Vec::new(),
59        }
60    }
61}
62
63fn find_cycle(
64    u: u32,
65    graph: &GraphProjection,
66    state: &mut [u8],
67    parent: &mut [Option<u32>],
68) -> Option<Vec<u32>> {
69    state[u as usize] = 1; // visiting
70
71    for &v in graph.out_neighbors(u) {
72        if state[v as usize] == 1 {
73            // Cycle detected! Backtrack from u to v using parent pointers
74            let mut cycle = Vec::new();
75            cycle.push(v);
76            let mut curr = u;
77            while curr != v {
78                cycle.push(curr);
79                curr = parent[curr as usize].unwrap();
80            }
81            cycle.push(v); // Close the loop
82            cycle.reverse();
83            return Some(cycle);
84        } else if state[v as usize] == 0 {
85            parent[v as usize] = Some(u);
86            if let Some(cycle) = find_cycle(v, graph, state, parent) {
87                return Some(cycle);
88            }
89        }
90    }
91
92    state[u as usize] = 2; // visited
93    None
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use crate::algo::test_utils::build_test_graph;
100
101    #[test]
102    fn test_cycle_detection_no_cycle() {
103        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
104        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
105        let graph = build_test_graph(vids, edges);
106
107        let result = CycleDetection::run(&graph, CycleDetectionConfig::default());
108        assert!(!result.has_cycle);
109    }
110
111    #[test]
112    fn test_cycle_detection_simple_cycle() {
113        // 0 -> 1 -> 0
114        let vids = vec![Vid::from(0), Vid::from(1)];
115        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(0))];
116        let graph = build_test_graph(vids, edges);
117
118        let result = CycleDetection::run(&graph, CycleDetectionConfig::default());
119        assert!(result.has_cycle);
120        assert_eq!(result.cycle_nodes.len(), 3); // 0, 1, 0
121
122        // Cycle nodes should be a valid cycle
123        let first = result.cycle_nodes[0];
124        let last = result.cycle_nodes[result.cycle_nodes.len() - 1];
125        assert_eq!(first, last);
126    }
127}
uni_algo/algo/algorithms/cycle_detection.rs

uni_algo/algo/algorithms/
cycle_detection.rs
