gridline_engine/engine/
cycle.rs

1use std::collections::HashSet;
2
3use super::{CellRef, Grid};
4
5/// Detect circular dependencies starting from a cell.
6/// Returns Some(cycle_path) if a cycle is found, None otherwise.
7pub fn detect_cycle(start: &CellRef, grid: &Grid) -> Option<Vec<CellRef>> {
8    let mut visiting = HashSet::new();
9    let mut path = Vec::new();
10
11    if detect_cycle_dfs(start, grid, &mut visiting, &mut path) {
12        Some(path)
13    } else {
14        None
15    }
16}
17
18fn detect_cycle_dfs(
19    current: &CellRef,
20    grid: &Grid,
21    visiting: &mut HashSet<CellRef>,
22    path: &mut Vec<CellRef>,
23) -> bool {
24    if visiting.contains(current) {
25        path.push(current.clone());
26        return true;
27    }
28
29    let deps = match grid.get(current) {
30        Some(entry) => entry.depends_on.clone(),
31        None => return false,
32    };
33
34    visiting.insert(current.clone());
35    path.push(current.clone());
36
37    for dep in &deps {
38        if detect_cycle_dfs(dep, grid, visiting, path) {
39            return true;
40        }
41    }
42
43    path.pop();
44    visiting.remove(current);
45    false
46}
gridline_engine/engine/cycle.rs

gridline_engine/engine/
cycle.rs
