zrx_graph/graph/visitor/
ancestors.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 ancestors of a node.
27
28use ahash::HashSet;
29
30use crate::graph::topology::Topology;
31use crate::graph::Graph;
32
33// ----------------------------------------------------------------------------
34// Structs
35// ----------------------------------------------------------------------------
36
37/// Visitor for ancestors of a node.
38pub struct Ancestors<'a> {
39    /// Graph topology.
40    topology: &'a Topology,
41    /// Stack for depth-first search.
42    stack: Vec<usize>,
43    /// Set of visited nodes.
44    visited: HashSet<usize>,
45}
46
47// ----------------------------------------------------------------------------
48// Implementations
49// ----------------------------------------------------------------------------
50
51impl<T> Graph<T> {
52    /// Creates an iterator over the ancestors of the given node.
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 ancestors
75    /// for node in graph.ancestors(c) {
76    ///     println!("{node:?}");
77    /// }
78    /// # Ok(())
79    /// # }
80    /// ```
81    #[inline]
82    #[must_use]
83    pub fn ancestors(&self, node: usize) -> Ancestors<'_> {
84        Ancestors {
85            topology: &self.topology,
86            stack: Vec::from([node]),
87            visited: HashSet::default(),
88        }
89    }
90}
91
92// ----------------------------------------------------------------------------
93// Trait implementations
94// ----------------------------------------------------------------------------
95
96impl Iterator for Ancestors<'_> {
97    type Item = usize;
98
99    /// Returns the next ancestor.
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// # use std::error::Error;
105    /// # fn main() -> Result<(), Box<dyn Error>> {
106    /// use zrx_graph::Graph;
107    ///
108    /// // Create graph builder and add nodes
109    /// let mut builder = Graph::builder();
110    /// let a = builder.add_node("a");
111    /// let b = builder.add_node("b");
112    /// let c = builder.add_node("c");
113    ///
114    /// // Create edges between nodes
115    /// builder.add_edge(a, b, 0)?;
116    /// builder.add_edge(b, c, 0)?;
117    ///
118    /// // Create graph from builder
119    /// let graph = builder.build();
120    ///
121    /// // Create iterator over ancestors
122    /// let mut ancestors = graph.ancestors(c);
123    /// while let Some(node) = ancestors.next() {
124    ///     println!("{node:?}");
125    /// }
126    /// # Ok(())
127    /// # }
128    /// ```
129    fn next(&mut self) -> Option<Self::Item> {
130        let incoming = self.topology.incoming();
131
132        // Perform a depth-first search to find all ancestors, using a stack
133        // over recursion, as it's faster and more efficient memory-wise
134        while let Some(node) = self.stack.pop() {
135            for &ancestor in &incoming[node] {
136                // If we haven't visited this ancestor yet, we put it on the
137                // stack after marking it as visited and return it immediately
138                if self.visited.insert(ancestor) {
139                    self.stack.push(ancestor);
140                    return Some(ancestor);
141                }
142            }
143        }
144
145        // No more ancestors to visit
146        None
147    }
148}
zrx_graph/graph/visitor/ancestors.rs

zrx_graph/graph/visitor/
ancestors.rs
