zrx_graph/graph/visitor/
path.rs

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

zrx_graph/graph/visitor/
path.rs
