sloop/domain/
graph.rs

1use std::collections::BTreeMap;
2
3pub(crate) fn find_cycle(graph: &BTreeMap<String, Vec<String>>) -> Option<Vec<String>> {
4    fn visit(
5        node: &str,
6        graph: &BTreeMap<String, Vec<String>>,
7        states: &mut BTreeMap<String, u8>,
8        stack: &mut Vec<String>,
9    ) -> Option<Vec<String>> {
10        states.insert(node.to_owned(), 1);
11        stack.push(node.to_owned());
12        let mut neighbors = graph.get(node).cloned().unwrap_or_default();
13        neighbors.sort();
14        neighbors.dedup();
15        for neighbor in neighbors {
16            match states.get(&neighbor).copied().unwrap_or_default() {
17                0 => {
18                    if let Some(cycle) = visit(&neighbor, graph, states, stack) {
19                        return Some(cycle);
20                    }
21                }
22                1 => {
23                    let start = stack
24                        .iter()
25                        .position(|entry| entry == &neighbor)
26                        .expect("visiting node is on the DFS stack");
27                    let mut cycle = stack[start..].to_vec();
28                    cycle.push(neighbor);
29                    return Some(cycle);
30                }
31                _ => {}
32            }
33        }
34        stack.pop();
35        states.insert(node.to_owned(), 2);
36        None
37    }
38
39    let mut states = BTreeMap::new();
40    for node in graph.keys() {
41        if states.get(node).copied().unwrap_or_default() == 0 {
42            if let Some(cycle) = visit(node, graph, &mut states, &mut Vec::new()) {
43                return Some(cycle);
44            }
45        }
46    }
47    None
48}
sloop/domain/graph.rs

sloop/domain/
graph.rs
