zrx_graph/graph/visitor/
paths.rs

1// Copyright (c) 2025 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// Third-party contributions licensed under 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//! Visitor for paths between two nodes.
27
28use crate::graph::topology::Topology;
29use crate::graph::Graph;
30
31// ----------------------------------------------------------------------------
32// Structs
33// ----------------------------------------------------------------------------
34
35/// Visitor for paths between two nodes.
36pub struct Paths<'a> {
37    /// Graph topology.
38    topology: &'a Topology,
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 all paths between the given nodes.
53    ///
54    /// # Examples
55    ///
56    /// ```
57    /// # use std::error::Error;
58    /// # fn main() -> Result<(), Box<dyn Error>> {
59    /// use zrx_graph::Graph;
60    ///
61    /// // Create graph builder and add nodes
62    /// let mut builder = Graph::builder();
63    /// let a = builder.add_node("a");
64    /// let b = builder.add_node("b");
65    /// let c = builder.add_node("c");
66    ///
67    /// // Create edges between nodes
68    /// builder.add_edge(a, b, 0)?;
69    /// builder.add_edge(b, c, 0)?;
70    ///
71    /// // Create graph from builder
72    /// let graph = builder.build();
73    ///
74    /// // Create iterator over paths
75    /// for path in graph.paths(a, c) {
76    ///     println!("{path:?}");
77    /// }
78    /// # Ok(())
79    /// # }
80    /// ```
81    #[inline]
82    #[must_use]
83    pub fn paths(&self, source: usize, target: usize) -> Paths<'_> {
84        Paths {
85            topology: &self.topology,
86            target,
87            stack: Vec::from([(source, 0)]),
88            path: Vec::from([source]),
89        }
90    }
91}
92
93// ----------------------------------------------------------------------------
94// Trait implementations
95// ----------------------------------------------------------------------------
96
97impl Iterator for Paths<'_> {
98    type Item = Vec<usize>;
99
100    /// Returns the next path.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// # use std::error::Error;
106    /// # fn main() -> Result<(), Box<dyn Error>> {
107    /// use zrx_graph::Graph;
108    ///
109    /// // Create graph builder and add nodes
110    /// let mut builder = Graph::builder();
111    /// let a = builder.add_node("a");
112    /// let b = builder.add_node("b");
113    /// let c = builder.add_node("c");
114    ///
115    /// // Create edges between nodes
116    /// builder.add_edge(a, b, 0)?;
117    /// builder.add_edge(b, c, 0)?;
118    ///
119    /// // Create graph from builder
120    /// let graph = builder.build();
121    ///
122    /// // Create iterator over paths
123    /// let mut paths = graph.paths(a, c);
124    /// while let Some(path) = paths.next() {
125    ///     println!("{path:?}");
126    /// }
127    /// # Ok(())
128    /// # }
129    /// ```
130    fn next(&mut self) -> Option<Self::Item> {
131        let outgoing = self.topology.outgoing();
132
133        // Perform a depth-first search to find all paths from the source to
134        // the target, and emit them in the order of discovery
135        while let Some((node, depth)) = self.stack.pop() {
136            // Backtrack by truncating the current path to the depth of the
137            // current node, and then add the current node to the path
138            self.path.truncate(depth);
139            self.path.push(node);
140
141            // In case we've reached the target, yield the current path. Note
142            // that we need to clone it, since we can't return a reference
143            if node == self.target {
144                return Some(self.path.clone());
145            }
146
147            // Add descendants to stack in reverse order for consistent depth-
148            // first ordering. Additionally, perform a debug assertion to ensure
149            // that we don't revisit nodes within the current path, which would
150            // lead to infinite loops, but should never happen in a DAG.
151            for &descendant in outgoing[node].iter().rev() {
152                debug_assert!(!self.path.contains(&descendant));
153                self.stack.push((descendant, depth + 1));
154            }
155        }
156
157        // No more paths to visit
158        None
159    }
160}
zrx_graph/graph/visitor/paths.rs

zrx_graph/graph/visitor/
paths.rs
