agm_core/graph/
cycles.rs

1//! Cycle detection using Tarjan's SCC algorithm.
2
3use petgraph::algo::tarjan_scc;
4use petgraph::visit::EdgeRef;
5use thiserror::Error;
6
7use super::{AgmGraph, depends_subgraph};
8
9// ---------------------------------------------------------------------------
10// CycleError
11// ---------------------------------------------------------------------------
12
13/// Error returned when a cycle is detected in the `depends` graph.
14#[derive(Debug, Clone, PartialEq, Error)]
15#[error("cycle detected in depends graph: {}", .cycle.join(" -> "))]
16pub struct CycleError {
17    /// The node IDs forming the cycle, in order.
18    /// The first and last elements are the same node (closing the loop).
19    /// Example: `["a", "b", "c", "a"]`
20    pub cycle: Vec<String>,
21}
22
23impl CycleError {
24    /// Creates a new `CycleError` from a cycle path.
25    ///
26    /// `path` should be the ordered sequence of nodes in the cycle.
27    /// The closing node (same as first) will be appended automatically
28    /// if not already present.
29    #[must_use]
30    pub fn new(mut path: Vec<String>) -> Self {
31        if path.len() >= 2 && path.first() != path.last() {
32            let first = path[0].clone();
33            path.push(first);
34        }
35        Self { cycle: path }
36    }
37
38    /// Returns the cycle path as a human-readable string: `"a -> b -> c -> a"`.
39    #[must_use]
40    pub fn display_path(&self) -> String {
41        self.cycle.join(" -> ")
42    }
43}
44
45// ---------------------------------------------------------------------------
46// detect_cycles
47// ---------------------------------------------------------------------------
48
49/// Detects all cycles in the `depends` subgraph.
50///
51/// Uses Tarjan's SCC algorithm (`petgraph::algo::tarjan_scc`) to find
52/// strongly connected components of size > 1, which represent cycles.
53/// Also checks size-1 SCCs for self-loops.
54///
55/// Returns a `Vec<Vec<String>>` where each inner `Vec` is the set of node
56/// IDs participating in a cycle. Returns an empty `Vec` if the graph is
57/// acyclic.
58///
59/// Only considers `Depends` edges.
60#[must_use]
61pub fn detect_cycles(graph: &AgmGraph) -> Vec<Vec<String>> {
62    let sub = depends_subgraph(graph);
63    let sccs = tarjan_scc(&sub);
64
65    let mut cycles: Vec<Vec<String>> = Vec::new();
66
67    for scc in sccs {
68        if scc.len() > 1 {
69            // Multiple nodes in one SCC = cycle.
70            let ids: Vec<String> = scc.iter().map(|&idx| sub[idx].clone()).collect();
71            cycles.push(ids);
72        } else if scc.len() == 1 {
73            // Check for self-loop.
74            let node_idx = scc[0];
75            let has_self_loop = sub.edges(node_idx).any(|e| e.target() == node_idx);
76            if has_self_loop {
77                cycles.push(vec![sub[node_idx].clone()]);
78            }
79        }
80    }
81
82    cycles
83}
84
85// ---------------------------------------------------------------------------
86// Tests
87// ---------------------------------------------------------------------------
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use crate::graph::build::build_graph;
93    use crate::graph::test_helpers::*;
94
95    #[test]
96    fn test_detect_cycles_acyclic_returns_empty() {
97        let mut a = make_node("a");
98        let b = make_node("b");
99        let c = make_node("c");
100        a.depends = Some(vec!["b".to_owned(), "c".to_owned()]);
101        let graph = build_graph(&make_file(vec![a, b, c]));
102        assert!(detect_cycles(&graph).is_empty());
103    }
104
105    #[test]
106    fn test_detect_cycles_self_loop_detected() {
107        let mut a = make_node("a");
108        a.depends = Some(vec!["a".to_owned()]);
109        let graph = build_graph(&make_file(vec![a]));
110        let cycles = detect_cycles(&graph);
111        assert_eq!(cycles.len(), 1);
112        assert_eq!(cycles[0], vec!["a"]);
113    }
114
115    #[test]
116    fn test_detect_cycles_two_node_cycle_detected() {
117        let mut a = make_node("a");
118        let mut b = make_node("b");
119        a.depends = Some(vec!["b".to_owned()]);
120        b.depends = Some(vec!["a".to_owned()]);
121        let graph = build_graph(&make_file(vec![a, b]));
122        let cycles = detect_cycles(&graph);
123        assert_eq!(cycles.len(), 1);
124        let mut ids = cycles[0].clone();
125        ids.sort();
126        assert_eq!(ids, vec!["a", "b"]);
127    }
128
129    #[test]
130    fn test_detect_cycles_multiple_sccs_detected() {
131        // Two disconnected cycles: (a->b->a) and (c->d->c)
132        let mut a = make_node("a");
133        let mut b = make_node("b");
134        let mut c = make_node("c");
135        let mut d = make_node("d");
136        a.depends = Some(vec!["b".to_owned()]);
137        b.depends = Some(vec!["a".to_owned()]);
138        c.depends = Some(vec!["d".to_owned()]);
139        d.depends = Some(vec!["c".to_owned()]);
140        let graph = build_graph(&make_file(vec![a, b, c, d]));
141        let cycles = detect_cycles(&graph);
142        assert_eq!(cycles.len(), 2);
143    }
144}
agm_core/graph/cycles.rs

agm_core/graph/
cycles.rs
