graph_traversal/
cycle.rs

1use graph_core::{Graph, NodeId};
2use std::collections::{HashMap, HashSet};
3
4// ── Directed cycle detection ──────────────────────────────────────────────────
5
6/// DFS colouring state for directed cycle detection.
7#[derive(Clone, PartialEq, Eq)]
8enum Colour {
9    /// Not yet visited.
10    White,
11    /// Currently on the DFS stack (in progress).
12    Gray,
13    /// Fully processed.
14    Black,
15}
16
17/// Returns `true` if the **directed** graph contains at least one cycle.
18///
19/// Uses three-colour DFS: a back-edge (an edge to a `Gray` node that is still
20/// on the current DFS path) proves a cycle exists.
21///
22/// # Examples
23///
24/// ```
25/// use graph_core::{AdjacencyList, Graph};
26/// use graph_traversal::has_cycle_directed;
27///
28/// // Acyclic: A → B → C
29/// let mut dag: AdjacencyList<()> = AdjacencyList::directed();
30/// let a = dag.add_node(());
31/// let b = dag.add_node(());
32/// let c = dag.add_node(());
33/// dag.add_edge(a, b, 1.0).unwrap();
34/// dag.add_edge(b, c, 1.0).unwrap();
35/// assert!(!has_cycle_directed(&dag));
36///
37/// // Cyclic: A → B → A
38/// let mut cyclic: AdjacencyList<()> = AdjacencyList::directed();
39/// let a = cyclic.add_node(());
40/// let b = cyclic.add_node(());
41/// cyclic.add_edge(a, b, 1.0).unwrap();
42/// cyclic.add_edge(b, a, 1.0).unwrap();
43/// assert!(has_cycle_directed(&cyclic));
44/// ```
45pub fn has_cycle_directed<G: Graph>(graph: &G) -> bool {
46    let mut colour: HashMap<NodeId, Colour> = graph.nodes().map(|n| (n, Colour::White)).collect();
47
48    for node in graph.nodes() {
49        if colour[&node] == Colour::White && dfs_cycle_directed(graph, node, &mut colour) {
50            return true;
51        }
52    }
53    false
54}
55
56fn dfs_cycle_directed<G: Graph>(
57    graph: &G,
58    node: NodeId,
59    colour: &mut HashMap<NodeId, Colour>,
60) -> bool {
61    *colour.get_mut(&node).unwrap() = Colour::Gray;
62
63    for (neighbour, _) in graph.neighbors(node) {
64        match colour[&neighbour] {
65            Colour::Gray => return true, // back-edge → cycle
66            Colour::White => {
67                if dfs_cycle_directed(graph, neighbour, colour) {
68                    return true;
69                }
70            }
71            Colour::Black => {}
72        }
73    }
74
75    *colour.get_mut(&node).unwrap() = Colour::Black;
76    false
77}
78
79// ── Undirected cycle detection ────────────────────────────────────────────────
80
81/// Returns `true` if the **undirected** graph contains at least one cycle.
82///
83/// Uses DFS with parent tracking. A back-edge to any node other than the
84/// immediate DFS parent signals a cycle.
85///
86/// # Examples
87///
88/// ```
89/// use graph_core::{AdjacencyList, Graph};
90/// use graph_traversal::has_cycle_undirected;
91///
92/// // Tree (no cycle): A — B — C
93/// let mut tree: AdjacencyList<()> = AdjacencyList::undirected();
94/// let a = tree.add_node(());
95/// let b = tree.add_node(());
96/// let c = tree.add_node(());
97/// tree.add_edge(a, b, 1.0).unwrap();
98/// tree.add_edge(b, c, 1.0).unwrap();
99/// assert!(!has_cycle_undirected(&tree));
100///
101/// // Triangle: A — B — C — A
102/// let mut tri: AdjacencyList<()> = AdjacencyList::undirected();
103/// let a = tri.add_node(());
104/// let b = tri.add_node(());
105/// let c = tri.add_node(());
106/// tri.add_edge(a, b, 1.0).unwrap();
107/// tri.add_edge(b, c, 1.0).unwrap();
108/// tri.add_edge(c, a, 1.0).unwrap();
109/// assert!(has_cycle_undirected(&tri));
110/// ```
111pub fn has_cycle_undirected<G: Graph>(graph: &G) -> bool {
112    let mut visited: HashSet<NodeId> = HashSet::new();
113
114    for node in graph.nodes() {
115        if !visited.contains(&node) && dfs_cycle_undirected(graph, node, None, &mut visited) {
116            return true;
117        }
118    }
119    false
120}
121
122fn dfs_cycle_undirected<G: Graph>(
123    graph: &G,
124    node: NodeId,
125    parent: Option<NodeId>,
126    visited: &mut HashSet<NodeId>,
127) -> bool {
128    visited.insert(node);
129
130    for (neighbour, _) in graph.neighbors(node) {
131        if !visited.contains(&neighbour) {
132            if dfs_cycle_undirected(graph, neighbour, Some(node), visited) {
133                return true;
134            }
135        } else if Some(neighbour) != parent {
136            // Back-edge to a visited non-parent node.
137            return true;
138        }
139    }
140    false
141}
graph_traversal/cycle.rs

graph_traversal/
cycle.rs
