graph_traversal/
dfs.rs

1use graph_collections::Stack;
2use graph_core::{Graph, NodeId};
3use std::collections::HashSet;
4
5// ── Recursive DFS ─────────────────────────────────────────────────────────────
6
7/// Runs a **recursive** depth-first search from `start`, calling `visitor` the
8/// first time each node is discovered.
9///
10/// Returns nodes in **finish order** (post-order): a node appears in the
11/// output only after all nodes reachable from it have been visited. This
12/// ordering is the reverse of a topological sort for DAGs.
13///
14/// # Caveats
15///
16/// Recursive DFS uses the call stack. For graphs with millions of nodes this
17/// may overflow. Use [`dfs_iterative`] for deep graphs.
18///
19/// # Examples
20///
21/// ```
22/// use graph_core::{AdjacencyList, Graph};
23/// use graph_traversal::dfs_recursive;
24///
25/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
26/// let a = g.add_node(());
27/// let b = g.add_node(());
28/// let c = g.add_node(());
29/// g.add_edge(a, b, 1.0).unwrap();
30/// g.add_edge(b, c, 1.0).unwrap();
31///
32/// let mut visited = Vec::new();
33/// let finish = dfs_recursive(&g, a, &mut |id| visited.push(id));
34///
35/// assert_eq!(visited[0], a); // a discovered first
36/// assert_eq!(finish.last(), Some(&a)); // a finishes last (post-order)
37/// ```
38pub fn dfs_recursive<G, F>(graph: &G, start: NodeId, visitor: &mut F) -> Vec<NodeId>
39where
40    G: Graph,
41    F: FnMut(NodeId),
42{
43    let mut visited: HashSet<NodeId> = HashSet::new();
44    let mut finish_order: Vec<NodeId> = Vec::new();
45    dfs_recurse(graph, start, visitor, &mut visited, &mut finish_order);
46    finish_order
47}
48
49fn dfs_recurse<G, F>(
50    graph: &G,
51    node: NodeId,
52    visitor: &mut F,
53    visited: &mut HashSet<NodeId>,
54    finish_order: &mut Vec<NodeId>,
55) where
56    G: Graph,
57    F: FnMut(NodeId),
58{
59    if !visited.insert(node) {
60        return;
61    }
62    visitor(node);
63    for (neighbour, _) in graph.neighbors(node) {
64        dfs_recurse(graph, neighbour, visitor, visited, finish_order);
65    }
66    finish_order.push(node);
67}
68
69// ── Iterative DFS ─────────────────────────────────────────────────────────────
70
71/// Runs an **iterative** depth-first search from `start` using an explicit
72/// [`Stack`], calling `visitor` the first time each node is discovered.
73///
74/// Safe from stack overflow on arbitrarily deep graphs. Note that visit order
75/// may differ slightly from the recursive variant because the stack reverses
76/// the neighbour ordering.
77///
78/// # Examples
79///
80/// ```
81/// use graph_core::{AdjacencyList, Graph};
82/// use graph_traversal::dfs_iterative;
83///
84/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
85/// let a = g.add_node(());
86/// let b = g.add_node(());
87/// let c = g.add_node(());
88/// g.add_edge(a, b, 1.0).unwrap();
89/// g.add_edge(a, c, 1.0).unwrap();
90///
91/// let mut visited = Vec::new();
92/// dfs_iterative(&g, a, &mut |id| visited.push(id));
93///
94/// assert_eq!(visited.len(), 3);
95/// assert!(visited.contains(&a));
96/// assert!(visited.contains(&b));
97/// assert!(visited.contains(&c));
98/// ```
99pub fn dfs_iterative<G, F>(graph: &G, start: NodeId, visitor: &mut F)
100where
101    G: Graph,
102    F: FnMut(NodeId),
103{
104    let mut stack: Stack<NodeId> = Stack::new();
105    let mut visited: HashSet<NodeId> = HashSet::new();
106
107    stack.push(start);
108
109    while let Some(node) = stack.pop() {
110        if visited.insert(node) {
111            visitor(node);
112            for (neighbour, _) in graph.neighbors(node) {
113                if !visited.contains(&neighbour) {
114                    stack.push(neighbour);
115                }
116            }
117        }
118    }
119}
120
121// ── DFS over all components ───────────────────────────────────────────────────
122
123/// Runs [`dfs_recursive`] from every unvisited node, covering all connected
124/// components. Returns a single finish-order vec spanning the whole graph.
125///
126/// Used internally by topological sort and SCC algorithms.
127///
128/// # Examples
129///
130/// ```
131/// use graph_core::{AdjacencyList, Graph};
132/// use graph_traversal::dfs::dfs_full;
133///
134/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
135/// let a = g.add_node(());
136/// let b = g.add_node(()); // isolated
137///
138/// let finish = dfs_full(&g, &mut |_| {});
139/// assert_eq!(finish.len(), 2);
140/// ```
141pub fn dfs_full<G, F>(graph: &G, visitor: &mut F) -> Vec<NodeId>
142where
143    G: Graph,
144    F: FnMut(NodeId),
145{
146    let mut visited: HashSet<NodeId> = HashSet::new();
147    let mut finish_order: Vec<NodeId> = Vec::new();
148
149    for node in graph.nodes() {
150        if !visited.contains(&node) {
151            dfs_recurse(graph, node, visitor, &mut visited, &mut finish_order);
152        }
153    }
154
155    finish_order
156}
graph_traversal/dfs.rs

graph_traversal/
dfs.rs
