zrx_graph/graph/iter/
sources.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 sources.
27
28use crate::graph::topology::Adjacency;
29use crate::graph::Graph;
30
31// ----------------------------------------------------------------------------
32// Structs
33// ----------------------------------------------------------------------------
34
35/// Iterator over sources.
36pub struct Sources<'a> {
37    /// Incoming edges.
38    incoming: &'a Adjacency,
39    /// Current index.
40    index: usize,
41}
42
43// ----------------------------------------------------------------------------
44// Implementations
45// ----------------------------------------------------------------------------
46
47impl<T> Graph<T> {
48    /// Creates an iterator over the sources.
49    ///
50    /// This method returns an iterator over the source node indices of the
51    /// graph, which are the nodes with no incoming edges.
52    ///
53    /// # Examples
54    ///
55    /// ```
56    /// # use std::error::Error;
57    /// # fn main() -> Result<(), Box<dyn Error>> {
58    /// use zrx_graph::Graph;
59    ///
60    /// // Create graph builder and add nodes
61    /// let mut builder = Graph::builder();
62    /// let a = builder.add_node("a");
63    /// let b = builder.add_node("b");
64    /// let c = builder.add_node("c");
65    ///
66    /// // Create edges between nodes
67    /// builder.add_edge(a, b)?;
68    /// builder.add_edge(b, c)?;
69    ///
70    /// // Create graph from builder
71    /// let graph = builder.build();
72    ///
73    /// // Create iterator over sources
74    /// for node in graph.sources() {
75    ///     println!("{node:?}");
76    /// }
77    /// # Ok(())
78    /// # }
79    /// ```
80    #[inline]
81    #[must_use]
82    pub fn sources(&self) -> Sources<'_> {
83        Sources {
84            incoming: self.topology.incoming(),
85            index: 0,
86        }
87    }
88}
89
90// ----------------------------------------------------------------------------
91// Trait implementations
92// ----------------------------------------------------------------------------
93
94impl Iterator for Sources<'_> {
95    type Item = usize;
96
97    /// Returns the next source.
98    fn next(&mut self) -> Option<Self::Item> {
99        while self.index < self.incoming.len() {
100            let node = self.index;
101            self.index += 1;
102
103            // Emit the node if it has no incoming edges
104            if self.incoming[node].is_empty() {
105                return Some(node);
106            }
107        }
108
109        // No more sources to return
110        None
111    }
112}
113
114// ----------------------------------------------------------------------------
115// Tests
116// ----------------------------------------------------------------------------
117
118#[cfg(test)]
119mod tests {
120
121    mod sources {
122        use crate::graph;
123
124        #[test]
125        fn handles_graph() {
126            let graph = graph! {
127                "a" => "b", "a" => "c",
128                "b" => "d", "b" => "e",
129                "c" => "f",
130                "d" => "g",
131                "e" => "g", "e" => "h",
132                "f" => "h",
133                "g" => "i",
134                "h" => "i",
135            };
136            assert_eq!(
137                graph.sources().collect::<Vec<_>>(), // fmt
138                vec![0]
139            );
140        }
141
142        #[test]
143        fn handles_multi_graph() {
144            let graph = graph! {
145                "a" => "b", "a" => "c", "a" => "c",
146                "b" => "d", "b" => "e",
147                "c" => "f",
148                "d" => "g",
149                "e" => "g", "e" => "h",
150                "f" => "h",
151                "g" => "i",
152                "h" => "i",
153            };
154            assert_eq!(
155                graph.sources().collect::<Vec<_>>(), // fmt
156                vec![0]
157            );
158        }
159    }
160}
zrx_graph/graph/iter/sources.rs

zrx_graph/graph/iter/
sources.rs
