zrx_graph/graph/iter/paths.rs
1// Copyright (c) 2025-2026 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// All contributions are certified under the DCO
5
6// Permission is hereby granted, free of charge, to any person obtaining a copy
7// of this software and associated documentation files (the "Software"), to
8// deal in the Software without restriction, including without limitation the
9// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10// sell copies of the Software, and to permit persons to whom the Software is
11// furnished to do so, subject to the following conditions:
12
13// The above copyright notice and this permission notice shall be included in
14// all copies or substantial portions of the Software.
15
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18// FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE
19// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22// IN THE SOFTWARE.
23
24// ----------------------------------------------------------------------------
25
26//! Iterator over paths between two nodes.
27
28use crate::graph::topology::Adjacency;
29use crate::graph::Graph;
30
31// ----------------------------------------------------------------------------
32// Structs
33// ----------------------------------------------------------------------------
34
35/// Iterator over paths between two nodes.
36pub struct Paths<'a> {
37 /// Outgoing edges.
38 outgoing: &'a Adjacency,
39 /// Target node.
40 target: usize,
41 /// Stack for depth-first search.
42 stack: Vec<(usize, usize)>,
43 /// Current path.
44 path: Vec<usize>,
45}
46
47// ----------------------------------------------------------------------------
48// Implementations
49// ----------------------------------------------------------------------------
50
51impl<T> Graph<T> {
52 /// Creates an iterator over the paths between the given nodes.
53 ///
54 /// # Panics
55 ///
56 /// Panics if the node does not exist, as this indicates that there's a bug
57 /// in the code that creates or uses the iterator. While the [`Builder`][]
58 /// is designed to be fallible to ensure the structure is valid, methods
59 /// that operate on [`Graph`] panic on violated invariants.
60 ///
61 /// [`Builder`]: crate::graph::Builder
62 ///
63 /// # Examples
64 ///
65 /// ```
66 /// # use std::error::Error;
67 /// # fn main() -> Result<(), Box<dyn Error>> {
68 /// use zrx_graph::Graph;
69 ///
70 /// // Create graph builder and add nodes
71 /// let mut builder = Graph::builder();
72 /// let a = builder.add_node("a");
73 /// let b = builder.add_node("b");
74 /// let c = builder.add_node("c");
75 ///
76 /// // Create edges between nodes
77 /// builder.add_edge(a, b)?;
78 /// builder.add_edge(b, c)?;
79 ///
80 /// // Create graph from builder
81 /// let graph = builder.build();
82 ///
83 /// // Create iterator over paths
84 /// for path in graph.paths(a, c) {
85 /// println!("{path:?}");
86 /// }
87 /// # Ok(())
88 /// # }
89 /// ```
90 #[inline]
91 #[must_use]
92 pub fn paths(&self, source: usize, target: usize) -> Paths<'_> {
93 Paths {
94 outgoing: self.topology.outgoing(),
95 target,
96 stack: Vec::from([(source, 0)]),
97 path: Vec::from([source]),
98 }
99 }
100}
101
102// ----------------------------------------------------------------------------
103// Trait implementations
104// ----------------------------------------------------------------------------
105
106impl Iterator for Paths<'_> {
107 type Item = Vec<usize>;
108
109 /// Returns the next path.
110 fn next(&mut self) -> Option<Self::Item> {
111 // Perform a depth-first search to find all paths from the source to
112 // the target, and emit them in the order of discovery
113 while let Some((node, depth)) = self.stack.pop() {
114 // Backtrack by truncating the current path to the depth of the
115 // current node, and then add the current node to the path
116 self.path.truncate(depth);
117 self.path.push(node);
118
119 // In case we've reached the target, emit the current path. Note
120 // that we need to clone it, since we can't return a reference
121 if node == self.target {
122 return Some(self.path.clone());
123 }
124
125 // Add descendants to stack in reverse order for consistent depth-
126 // first ordering. Additionally, perform a debug assertion to ensure
127 // that we don't revisit nodes within the current path, which would
128 // lead to infinite loops, but should never happen in a DAG.
129 for &descendant in self.outgoing[node].iter().rev() {
130 debug_assert!(!self.path.contains(&descendant));
131 self.stack.push((descendant, depth + 1));
132 }
133 }
134
135 // No more paths to return
136 None
137 }
138}
139
140// ----------------------------------------------------------------------------
141// Tests
142// ----------------------------------------------------------------------------
143
144#[cfg(test)]
145mod tests {
146
147 mod paths {
148 use crate::graph;
149
150 #[test]
151 fn handles_graph() {
152 let graph = graph! {
153 "a" => "b", "a" => "c",
154 "b" => "d", "b" => "e",
155 "c" => "f",
156 "d" => "g",
157 "e" => "g", "e" => "h",
158 "f" => "h",
159 "g" => "i",
160 "h" => "i",
161 };
162 assert_eq!(
163 graph.paths(0, 8).collect::<Vec<_>>(),
164 vec![
165 vec![0, 1, 3, 6, 8],
166 vec![0, 1, 4, 6, 8],
167 vec![0, 1, 4, 7, 8],
168 vec![0, 2, 5, 7, 8],
169 ]
170 );
171 }
172
173 #[test]
174 fn handles_graph_and_self_path() {
175 let graph = graph! {
176 "a" => "b", "a" => "c",
177 "b" => "d", "b" => "e",
178 "c" => "f",
179 "d" => "g",
180 "e" => "g", "e" => "h",
181 "f" => "h",
182 "g" => "i",
183 "h" => "i",
184 };
185 assert_eq!(
186 graph.paths(0, 0).collect::<Vec<_>>(), // fmt
187 vec![vec![0]]
188 );
189 }
190
191 #[test]
192 fn handles_graph_and_non_existing_path() {
193 let graph = graph! {
194 "a" => "b", "a" => "c",
195 "b" => "d", "b" => "e",
196 "c" => "f",
197 "d" => "g",
198 "e" => "g", "e" => "h",
199 "f" => "h",
200 "g" => "i",
201 "h" => "i",
202 };
203 assert_eq!(
204 graph.paths(8, 0).collect::<Vec<_>>(),
205 vec![] as Vec<Vec<usize>>
206 );
207 }
208
209 #[test]
210 fn handles_multi_graph() {
211 let graph = graph! {
212 "a" => "b", "a" => "c", "a" => "c",
213 "b" => "d", "b" => "e",
214 "c" => "f",
215 "d" => "g",
216 "e" => "g", "e" => "h",
217 "f" => "h",
218 "g" => "i",
219 "h" => "i",
220 };
221 assert_eq!(
222 graph.paths(0, 8).collect::<Vec<_>>(),
223 vec![
224 vec![0, 1, 3, 6, 8],
225 vec![0, 1, 4, 6, 8],
226 vec![0, 1, 4, 7, 8],
227 vec![0, 2, 5, 7, 8],
228 vec![0, 2, 5, 7, 8],
229 ]
230 );
231 }
232
233 #[test]
234 fn handles_multi_graph_and_self_path() {
235 let graph = graph! {
236 "a" => "b", "a" => "c", "a" => "c",
237 "b" => "d", "b" => "e",
238 "c" => "f",
239 "d" => "g",
240 "e" => "g", "e" => "h",
241 "f" => "h",
242 "g" => "i",
243 "h" => "i",
244 };
245 assert_eq!(
246 graph.paths(0, 0).collect::<Vec<_>>(), // fmt
247 vec![vec![0]]
248 );
249 }
250
251 #[test]
252 fn handles_multi_graph_and_non_existing_path() {
253 let graph = graph! {
254 "a" => "b", "a" => "c", "a" => "c",
255 "b" => "d", "b" => "e",
256 "c" => "f",
257 "d" => "g",
258 "e" => "g", "e" => "h",
259 "f" => "h",
260 "g" => "i",
261 "h" => "i",
262 };
263 assert_eq!(
264 graph.paths(8, 0).collect::<Vec<_>>(),
265 vec![] as Vec<Vec<usize>>
266 );
267 }
268 }
269}