zrx_graph/graph/traversal.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//! Topological traversal.
27
28use ahash::HashSet;
29use std::collections::VecDeque;
30use std::mem;
31
32use super::topology::{Topology, Transitive};
33use super::Graph;
34
35mod error;
36mod into_iter;
37
38pub use error::{Error, Result};
39pub use into_iter::IntoIter;
40
41// ----------------------------------------------------------------------------
42// Structs
43// ----------------------------------------------------------------------------
44
45/// Topological traversal.
46///
47/// This data type manages a topological traversal of a directed acyclic graph
48/// (DAG). It allows visiting nodes in a way that respects their dependencies,
49/// meaning that a node can only be visited after all of its dependencies have
50/// been visited. Visitable nodes can be obtained with [`Traversal::take`].
51///
52/// Note that the traversal itself doesn't know whether it's complete or not,
53/// as it only tracks visitable nodes depending on what has been reported back
54/// to [`Traversal::complete`]. This is because we also need to support partial
55/// traversals that can be resumed, which must be managed by the caller. In case
56/// a traversal starts at an intermediate node, only the nodes and dependencies
57/// reachable from this node are considered, which is necessary for implementing
58/// subgraph traversals that are self-contained, allowing for the creation of
59/// frontiers at any point in the graph.
60#[derive(Clone, Debug)]
61pub struct Traversal {
62 /// Graph topology.
63 topology: Topology<Transitive>,
64 /// Dependency counts.
65 dependencies: Vec<u8>,
66 /// Initial nodes.
67 initial: Vec<usize>,
68 /// Visitable nodes.
69 visitable: VecDeque<usize>,
70}
71
72// ----------------------------------------------------------------------------
73// Implementations
74// ----------------------------------------------------------------------------
75
76impl Traversal {
77 /// Creates a topological traversal.
78 ///
79 /// The given initial nodes are immediately marked as visitable, and thus
80 /// returned by [`Traversal::take`], so the caller must make sure they can
81 /// be processed. Note that the canonical way to create a [`Traversal`] is
82 /// to invoke the [`Graph::traverse`] method.
83 ///
84 /// # Examples
85 ///
86 /// ```
87 /// # use std::error::Error;
88 /// # fn main() -> Result<(), Box<dyn Error>> {
89 /// use zrx_graph::{Graph, Traversal};
90 ///
91 /// // Create graph builder and add nodes
92 /// let mut builder = Graph::builder();
93 /// let a = builder.add_node("a");
94 /// let b = builder.add_node("b");
95 /// let c = builder.add_node("c");
96 ///
97 /// // Create edges between nodes
98 /// builder.add_edge(a, b)?;
99 /// builder.add_edge(b, c)?;
100 ///
101 /// // Create graph from builder
102 /// let graph = builder.build().into_transitive();
103 ///
104 /// // Create topological traversal
105 /// let traversal = Traversal::new(graph.topology(), [a]);
106 /// # Ok(())
107 /// # }
108 /// ```
109 #[must_use]
110 pub fn new<I>(topology: &Topology<Transitive>, initial: I) -> Self
111 where
112 I: AsRef<[usize]>,
113 {
114 let mut visitable: VecDeque<_> =
115 unique(initial.as_ref().iter()).collect();
116
117 // Obtain incoming edges.
118 let incoming = topology.incoming();
119
120 // When doing a topological traversal, we only visit a node once all of
121 // its dependencies have been visited. This means that we need to track
122 // the number of dependencies for each node, which is the number of
123 // incoming edges for that node.
124 let mut dependencies = incoming.degrees().to_vec();
125 for node in incoming {
126 // We must adjust the dependency count for each node for all of its
127 // dependencies that are not reachable from the initial nodes
128 for &dependency in &incoming[node] {
129 let mut iter = initial.as_ref().iter();
130 if !iter.any(|&n| topology.has_path(n, dependency)) {
131 dependencies[node] -= 1;
132 }
133 }
134 }
135
136 // Retain only the visitable nodes whose dependencies are satisfied,
137 // as we will discover the other initial nodes during traversal
138 visitable.retain(|&n| dependencies[n] == 0);
139 Self {
140 topology: topology.clone(),
141 dependencies,
142 initial: visitable.iter().copied().collect(),
143 visitable,
144 }
145 }
146
147 /// Returns the next visitable node.
148 ///
149 /// # Examples
150 ///
151 /// ```
152 /// # use std::error::Error;
153 /// # fn main() -> Result<(), Box<dyn Error>> {
154 /// use zrx_graph::Graph;
155 ///
156 /// // Create graph builder and add nodes
157 /// let mut builder = Graph::builder();
158 /// let a = builder.add_node("a");
159 /// let b = builder.add_node("b");
160 /// let c = builder.add_node("c");
161 ///
162 /// // Create edges between nodes
163 /// builder.add_edge(a, b)?;
164 /// builder.add_edge(b, c)?;
165 ///
166 /// // Create graph from builder
167 /// let graph = builder.build().into_transitive();
168 ///
169 /// // Create topological traversal
170 /// let mut traversal = graph.traverse([a]);
171 /// while let Some(node) = traversal.take() {
172 /// println!("{node:?}");
173 /// traversal.complete(node)?;
174 /// }
175 /// # Ok(())
176 /// # }
177 /// ```
178 #[inline]
179 #[must_use]
180 pub fn take(&mut self) -> Option<usize> {
181 self.visitable.pop_front()
182 }
183
184 /// Marks the given node as visited.
185 ///
186 /// This method marks a node as visited as part of a traversal, which might
187 /// allow visiting dependent nodes when all of their dependencies have been
188 /// satisfied. After marking a node as visited, the next nodes that can be
189 /// visited can be obtained using the [`Traversal::take`] method.
190 ///
191 /// # Errors
192 ///
193 /// If the node has already been marked as visited, [`Error::Completed`] is
194 /// returned. This is likely an error in the caller's business logic.
195 ///
196 /// # Panics
197 ///
198 /// Panics if a node does not exist, as this indicates that there's a bug
199 /// in the code that creates or uses the traversal. While the [`Builder`][]
200 /// is designed to be fallible to ensure the structure is valid, methods
201 /// that operate on [`Graph`] panic on violated invariants.
202 ///
203 /// [`Builder`]: crate::graph::Builder
204 ///
205 /// # Examples
206 ///
207 /// ```
208 /// # use std::error::Error;
209 /// # fn main() -> Result<(), Box<dyn Error>> {
210 /// use zrx_graph::Graph;
211 ///
212 /// // Create graph builder and add nodes
213 /// let mut builder = Graph::builder();
214 /// let a = builder.add_node("a");
215 /// let b = builder.add_node("b");
216 /// let c = builder.add_node("c");
217 ///
218 /// // Create edges between nodes
219 /// builder.add_edge(a, b)?;
220 /// builder.add_edge(b, c)?;
221 ///
222 /// // Create graph from builder
223 /// let graph = builder.build().into_transitive();
224 ///
225 /// // Create topological traversal
226 /// let mut traversal = graph.traverse([a]);
227 /// while let Some(node) = traversal.take() {
228 /// println!("{node:?}");
229 /// traversal.complete(node)?;
230 /// }
231 /// # Ok(())
232 /// # }
233 /// ```
234 pub fn complete(&mut self, node: usize) -> Result {
235 if self.dependencies[node] == u8::MAX {
236 return Err(Error::Completed(node));
237 }
238
239 // When the dependency count isn't zero, the traversal converged with
240 // another traversal and restarted at a node occurring before the given
241 // node. In this case, we return an error, and indicate to the caller
242 // that parts of the traversal have to be completed again.
243 if self.dependencies[node] != 0 {
244 return Err(Error::Converged);
245 }
246
247 // Mark node as visited - we can just use the maximum value of `u8` as
248 // a marker, as we don't expect more than 255 dependencies for any node
249 self.dependencies[node] = u8::MAX;
250
251 // Obtain adjacency list of outgoing edges, and decrement the number
252 // of unresolved dependencies for each dependent by one. When the number
253 // of dependencies for a dependent reaches zero, it can be visited, so
254 // we add it to the queue of visitable nodes.
255 let outgoing = self.topology.outgoing();
256 for &dependent in &outgoing[node] {
257 self.dependencies[dependent] -= 1;
258
259 // We satisfied all dependencies, so the dependent can be visited
260 if self.dependencies[dependent] == 0 {
261 self.visitable.push_back(dependent);
262 }
263 }
264
265 // No errors occurred
266 Ok(())
267 }
268
269 /// Attempts to converge with the given traversal.
270 ///
271 /// This method attempts to merge both traversals into a single traversal,
272 /// which is possible when they have common descendants, a condition that
273 /// is always true for directed acyclic graphs with a single component.
274 /// There are several cases to consider when converging two traversals:
275 ///
276 /// - If traversals start from the same set of source nodes, they already
277 /// converged, so we just restart the traversal at these source nodes.
278 ///
279 /// - If traversals start from different source nodes, yet both have common
280 /// descendants, we converge at the first layer of common descendants, as
281 /// all descendants of them must be revisited in the combined traversal.
282 /// Ancestors of the common descendants that have already been visited in
283 /// either traversal don't need to be revisited, and thus are carried over
284 /// from both traversals in their current state.
285 ///
286 /// - If traversals are disjoint, they can't be converged, so we return the
287 /// given traversal back to the caller wrapped in [`Error::Disjoint`].
288 ///
289 /// # Errors
290 ///
291 /// If the given traversal is from a different graph, [`Error::Mismatch`]
292 /// is returned. Otherwise, if the traversals are disjoint, the traversal
293 /// is returned back to the caller wrapped in [`Error::Disjoint`], so the
294 /// caller can decide how to proceed.
295 ///
296 /// # Examples
297 ///
298 /// ```
299 /// # use std::error::Error;
300 /// # fn main() -> Result<(), Box<dyn Error>> {
301 /// use zrx_graph::Graph;
302 ///
303 /// // Create graph builder and add nodes
304 /// let mut builder = Graph::builder();
305 /// let a = builder.add_node("a");
306 /// let b = builder.add_node("b");
307 /// let c = builder.add_node("c");
308 ///
309 /// // Create edges between nodes
310 /// builder.add_edge(a, c)?;
311 /// builder.add_edge(b, c)?;
312 ///
313 /// // Create graph from builder
314 /// let graph = builder.build().into_transitive();
315 ///
316 /// // Create topological traversal
317 /// let mut traversal = graph.traverse([a]);
318 ///
319 /// // Converge with another topological traversal
320 /// let mut other = graph.traverse([b]);
321 /// assert!(traversal.converge(other).is_ok());
322 /// # Ok(())
323 /// # }
324 /// ```
325 pub fn converge(&mut self, other: Self) -> Result {
326 if self.topology != other.topology {
327 return Err(Error::Mismatch);
328 }
329
330 // Compute the initial nodes for the combined traversal, which is the
331 // union of both traversals with all redundant nodes removed
332 let iter = self.initial.iter().chain(&other.initial);
333 let initial: Vec<_> = unique(iter).collect();
334
335 // Create a temporary graph, so we can compute the first layer of nodes
336 // that are common descendants contained in both traversals
337 let graph = Graph {
338 data: (0..self.topology.incoming().len()).collect(),
339 topology: self.topology.clone(),
340 };
341
342 // If there are no common descendants, the traversals are disjoint and
343 // can't converge, so we return the given traversal back to the caller
344 let mut iter = graph.common_descendants(&initial);
345 let Some(common) = iter.next() else {
346 return Err(Error::Disjoint(other));
347 };
348
349 // Create the combined traversal, and mark all already visited nodes
350 // that are ancestors of the common descendants as visited
351 let prior = mem::replace(self, Self::new(&self.topology, initial));
352
353 // Compute the visitable nodes for the combined traversal, which is the
354 // union of both traversals with all redundant nodes removed. Note that
355 // we must collect them in a temporary vector first, or this loop would
356 // run indefinitely, as we'd be adding visitable nodes again and again.
357 let mut visitable = VecDeque::new();
358 while let Some(node) = self.take() {
359 let p = prior.dependencies[node];
360 let o = other.dependencies[node];
361
362 // If the node has been visited in either traversal, and is not part
363 // of the first layer of common descendants, mark it as visited in
364 // the combined traversal, since we don't need to revisit ancestors
365 // that have already been visited in either traversal
366 if (p == u8::MAX || o == u8::MAX) && !common.contains(&node) {
367 self.complete(node)?;
368 } else {
369 visitable.push_back(node);
370 }
371 }
372
373 // Update visitable nodes
374 self.visitable = visitable;
375
376 // No errors occurred
377 Ok(())
378 }
379}
380
381#[allow(clippy::must_use_candidate)]
382impl Traversal {
383 /// Returns a reference to the graph topology.
384 #[inline]
385 pub fn topology(&self) -> &Topology<Transitive> {
386 &self.topology
387 }
388
389 /// Returns a reference to the initial nodes.
390 #[inline]
391 pub fn initial(&self) -> &[usize] {
392 &self.initial
393 }
394
395 /// Returns the number of visitable nodes.
396 #[inline]
397 pub fn len(&self) -> usize {
398 self.visitable.len()
399 }
400
401 /// Returns whether there are any visitable nodes.
402 #[inline]
403 pub fn is_empty(&self) -> bool {
404 self.visitable.is_empty()
405 }
406}
407
408// ----------------------------------------------------------------------------
409// Functions
410// ----------------------------------------------------------------------------
411
412/// Deduplicates the given nodes while preserving their order.
413#[inline]
414fn unique<'a, I>(iter: I) -> impl Iterator<Item = usize>
415where
416 I: IntoIterator<Item = &'a usize>,
417{
418 let mut nodes = HashSet::default();
419 iter.into_iter() // fmt
420 .copied()
421 .filter(move |&node| nodes.insert(node))
422}
423
424// ----------------------------------------------------------------------------
425// Tests
426// ----------------------------------------------------------------------------
427
428#[cfg(test)]
429mod tests {
430
431 mod complete {
432 use crate::graph;
433
434 #[test]
435 fn handles_graph() {
436 let graph = graph! {
437 transitive;
438 "a" => "b", "a" => "c",
439 "b" => "d", "b" => "e",
440 "c" => "f",
441 "d" => "g",
442 "e" => "g", "e" => "h",
443 "f" => "h",
444 "g" => "i",
445 "h" => "i",
446 };
447 for (node, mut descendants) in [
448 (0, vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
449 (1, vec![1, 3, 4, 6, 7, 8]),
450 (2, vec![2, 5, 7, 8]),
451 (3, vec![3, 6, 8]),
452 (4, vec![4, 6, 7, 8]),
453 (5, vec![5, 7, 8]),
454 (6, vec![6, 8]),
455 (7, vec![7, 8]),
456 (8, vec![8]),
457 ] {
458 let mut traversal = graph.traverse([node]);
459 while let Some(node) = traversal.take() {
460 assert_eq!(node, descendants.remove(0));
461 assert!(traversal.complete(node).is_ok());
462 }
463 }
464 }
465
466 #[test]
467 fn handles_multi_graph() {
468 let graph = graph! {
469 transitive;
470 "a" => "b", "a" => "c", "a" => "c",
471 "b" => "d", "b" => "e",
472 "c" => "f",
473 "d" => "g",
474 "e" => "g", "e" => "h",
475 "f" => "h",
476 "g" => "i",
477 "h" => "i",
478 };
479 for (node, mut descendants) in [
480 (0, vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
481 (1, vec![1, 3, 4, 6, 7, 8]),
482 (2, vec![2, 5, 7, 8]),
483 (3, vec![3, 6, 8]),
484 (4, vec![4, 6, 7, 8]),
485 (5, vec![5, 7, 8]),
486 (6, vec![6, 8]),
487 (7, vec![7, 8]),
488 (8, vec![8]),
489 ] {
490 let mut traversal = graph.traverse([node]);
491 while let Some(node) = traversal.take() {
492 assert_eq!(node, descendants.remove(0));
493 assert!(traversal.complete(node).is_ok());
494 }
495 }
496 }
497 }
498
499 mod converge {
500 use crate::graph;
501
502 #[test]
503 fn handles_graph() {
504 let graph = graph! {
505 transitive;
506 "a" => "b", "a" => "c",
507 "b" => "d", "b" => "e",
508 "c" => "f",
509 "d" => "g",
510 "e" => "g", "e" => "h",
511 "f" => "h",
512 "g" => "i",
513 "h" => "i",
514 };
515 for (i, j, descendants) in [
516 (vec![0], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
517 (vec![1], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
518 (vec![8], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
519 (vec![1], vec![1], vec![1, 3, 4, 6, 7, 8]),
520 (vec![1], vec![2], vec![1, 2, 3, 4, 5, 6, 7, 8]),
521 (vec![2], vec![4], vec![2, 4, 5, 6, 7, 8]),
522 (vec![4], vec![2], vec![4, 2, 6, 5, 7, 8]),
523 (vec![3], vec![5], vec![3, 5, 6, 7, 8]),
524 (vec![6], vec![7], vec![6, 7, 8]),
525 (vec![8], vec![8], vec![8]),
526 ] {
527 let mut traversal = graph.traverse(i);
528 assert!(traversal.converge(graph.traverse(j)).is_ok());
529 assert_eq!(
530 traversal.into_iter().collect::<Vec<_>>(), // fmt
531 descendants
532 );
533 }
534 }
535
536 #[test]
537 fn handles_multi_graph() {
538 let graph = graph! {
539 transitive;
540 "a" => "b", "a" => "c", "a" => "c",
541 "b" => "d", "b" => "e",
542 "c" => "f",
543 "d" => "g",
544 "e" => "g", "e" => "h",
545 "f" => "h",
546 "g" => "i",
547 "h" => "i",
548 };
549 for (i, j, descendants) in [
550 (vec![0], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
551 (vec![1], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
552 (vec![8], vec![0], vec![0, 1, 2, 3, 4, 5, 6, 7, 8]),
553 (vec![1], vec![1], vec![1, 3, 4, 6, 7, 8]),
554 (vec![1], vec![2], vec![1, 2, 3, 4, 5, 6, 7, 8]),
555 (vec![2], vec![4], vec![2, 4, 5, 6, 7, 8]),
556 (vec![4], vec![2], vec![4, 2, 6, 5, 7, 8]),
557 (vec![3], vec![5], vec![3, 5, 6, 7, 8]),
558 (vec![6], vec![7], vec![6, 7, 8]),
559 (vec![8], vec![8], vec![8]),
560 ] {
561 let mut traversal = graph.traverse(i);
562 assert!(traversal.converge(graph.traverse(j)).is_ok());
563 assert_eq!(
564 traversal.into_iter().collect::<Vec<_>>(), // fmt
565 descendants
566 );
567 }
568 }
569 }
570}