ascii_dag/
cycles.rs

1//! Cycle detection algorithms for directed graphs.
2//!
3//! This module provides functionality to detect cycles in a DAG,
4//! which would make it not a valid DAG.
5//!
6//! ## Generic Cycle Detection
7//!
8//! For more flexibility, see the [`generic`] submodule which provides
9//! cycle detection that works with any data structure through higher-order
10//! functions or traits.
11//!
12//! ```
13//! # #[cfg(feature = "generic")]
14//! # {
15//! use ascii_dag::cycles::generic::detect_cycle_fn;
16//!
17//! // Example: Error chain
18//! let get_caused_by = |error_id: &usize| -> Vec<usize> {
19//!     match error_id {
20//!         1 => vec![2],
21//!         2 => vec![3],
22//!         3 => vec![],
23//!         _ => vec![],
24//!     }
25//! };
26//!
27//! let all_errors = vec![1, 2, 3];
28//! let cycle = detect_cycle_fn(&all_errors, get_caused_by);
29//! assert!(cycle.is_none()); // No cycle
30//! # }
31//! ```
32
33#[cfg(feature = "generic")]
34pub mod generic;
35
36use crate::graph::DAG;
37use alloc::{vec, vec::Vec};
38
39impl<'a> DAG<'a> {
40    /// Check if the graph contains cycles (making it not a valid DAG).
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// use ascii_dag::graph::DAG;
46    ///
47    /// let mut dag = DAG::new();
48    /// dag.add_node(1, "A");
49    /// dag.add_node(2, "B");
50    /// dag.add_edge(1, 2);
51    /// dag.add_edge(2, 1);  // Creates a cycle!
52    ///
53    /// assert!(dag.has_cycle());
54    /// ```
55    pub fn has_cycle(&self) -> bool {
56        let mut visited = vec![false; self.nodes.len()];
57        let mut rec_stack = vec![false; self.nodes.len()];
58
59        for i in 0..self.nodes.len() {
60            if self.has_cycle_util(i, &mut visited, &mut rec_stack) {
61                return true;
62            }
63        }
64        false
65    }
66
67    /// Helper function for cycle detection using DFS.
68    fn has_cycle_util(&self, idx: usize, visited: &mut [bool], rec_stack: &mut [bool]) -> bool {
69        if rec_stack[idx] {
70            return true;
71        }
72        if visited[idx] {
73            return false;
74        }
75
76        visited[idx] = true;
77        rec_stack[idx] = true;
78
79        let node_id = self.nodes[idx].0;
80        for &(from, to) in &self.edges {
81            if from == node_id {
82                // O(1) HashMap lookup instead of O(n) scan
83                if let Some(child_idx) = self.node_index(to) {
84                    if self.has_cycle_util(child_idx, visited, rec_stack) {
85                        return true;
86                    }
87                }
88            }
89        }
90
91        rec_stack[idx] = false;
92        false
93    }
94
95    /// Find a cycle path in the graph.
96    ///
97    /// Returns the node IDs that form a cycle, if one exists.
98    pub(crate) fn find_cycle_path(&self) -> Option<Vec<usize>> {
99        for i in 0..self.nodes.len() {
100            let mut visited = vec![false; self.nodes.len()];
101            let mut path = Vec::new();
102
103            if let Some(cycle) = self.find_cycle_from(i, &mut visited, &mut path) {
104                return Some(cycle);
105            }
106        }
107        None
108    }
109
110    /// Helper function to find a cycle starting from a specific node.
111    fn find_cycle_from(
112        &self,
113        start_idx: usize,
114        visited: &mut [bool],
115        path: &mut Vec<usize>,
116    ) -> Option<Vec<usize>> {
117        if visited[start_idx] {
118            // Found a cycle - extract it from path
119            if let Some(cycle_start) = path.iter().position(|&idx| idx == start_idx) {
120                return Some(
121                    path[cycle_start..]
122                        .iter()
123                        .map(|&idx| self.nodes[idx].0)
124                        .collect(),
125                );
126            }
127            return None;
128        }
129
130        visited[start_idx] = true;
131        path.push(start_idx);
132
133        let node_id = self.nodes[start_idx].0;
134        for &(from, to) in &self.edges {
135            if from == node_id {
136                // O(1) HashMap lookup instead of O(n) scan
137                if let Some(child_idx) = self.node_index(to) {
138                    if let Some(cycle) = self.find_cycle_from(child_idx, visited, path) {
139                        return Some(cycle);
140                    }
141                }
142            }
143        }
144
145        path.pop();
146        None
147    }
148}
149
150#[cfg(test)]
151mod tests {
152    use crate::graph::DAG;
153
154    #[test]
155    fn test_cycle_detection() {
156        let mut dag = DAG::new();
157        dag.add_node(1, "A");
158        dag.add_node(2, "B");
159        dag.add_edge(1, 2);
160        dag.add_edge(2, 1); // Cycle!
161
162        assert!(dag.has_cycle());
163    }
164
165    #[test]
166    fn test_no_cycle() {
167        let dag = DAG::from_edges(&[(1, "A"), (2, "B")], &[(1, 2)]);
168
169        assert!(!dag.has_cycle());
170    }
171
172    #[test]
173    fn test_cycle_with_auto_created_nodes() {
174        let mut dag = DAG::new();
175        dag.add_node(1, "A");
176        // Node 2 will be auto-created
177        dag.add_edge(1, 2);
178        dag.add_edge(2, 1); // Creates cycle
179
180        assert!(dag.has_cycle());
181    }
182}
ascii_dag/cycles.rs

ascii_dag/
cycles.rs
