zrx_graph/graph/property.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//! Graph properties.
27
28use std::collections::VecDeque;
29
30use super::Graph;
31
32// ----------------------------------------------------------------------------
33// Implementations
34// ----------------------------------------------------------------------------
35
36impl<T> Graph<T> {
37 /// Returns whether the given node is a source.
38 ///
39 /// # Panics
40 ///
41 /// Panics if the node does not exist.
42 ///
43 /// # Examples
44 ///
45 /// ```
46 /// # use std::error::Error;
47 /// # fn main() -> Result<(), Box<dyn Error>> {
48 /// use zrx_graph::{Graph, Topology};
49 ///
50 /// // Create graph builder and add nodes
51 /// let mut builder = Graph::builder();
52 /// let a = builder.add_node("a");
53 /// let b = builder.add_node("b");
54 /// let c = builder.add_node("c");
55 ///
56 /// // Create edges between nodes
57 /// builder.add_edge(a, b)?;
58 /// builder.add_edge(b, c)?;
59 ///
60 /// // Create graph from builder
61 /// let graph = builder.build();
62 ///
63 /// // Ensure nodes are sources (or not)
64 /// assert_eq!(graph.is_source(a), true);
65 /// assert_eq!(graph.is_source(b), false);
66 /// assert_eq!(graph.is_source(c), false);
67 /// # Ok(())
68 /// # }
69 /// ```
70 #[inline]
71 #[must_use]
72 pub fn is_source(&self, node: usize) -> bool {
73 let incoming = self.topology.incoming();
74 incoming[node].is_empty()
75 }
76
77 /// Returns whether the given node is a sink.
78 ///
79 /// # Panics
80 ///
81 /// Panics if the node does not exist.
82 ///
83 /// # Examples
84 ///
85 /// ```
86 /// # use std::error::Error;
87 /// # fn main() -> Result<(), Box<dyn Error>> {
88 /// use zrx_graph::{Graph, Topology};
89 ///
90 /// // Create graph builder and add nodes
91 /// let mut builder = Graph::builder();
92 /// let a = builder.add_node("a");
93 /// let b = builder.add_node("b");
94 /// let c = builder.add_node("c");
95 ///
96 /// // Create edges between nodes
97 /// builder.add_edge(a, b)?;
98 /// builder.add_edge(b, c)?;
99 ///
100 /// // Create graph from builder
101 /// let graph = builder.build();
102 ///
103 /// // Ensure nodes are sinks (or not)
104 /// assert_eq!(graph.is_sink(a), false);
105 /// assert_eq!(graph.is_sink(b), false);
106 /// assert_eq!(graph.is_sink(c), true);
107 /// # Ok(())
108 /// # }
109 /// ```
110 #[inline]
111 #[must_use]
112 pub fn is_sink(&self, node: usize) -> bool {
113 let outgoing = self.topology.outgoing();
114 outgoing[node].is_empty()
115 }
116
117 /// Returns whether the source node is an ancestor of the target node.
118 ///
119 /// # Panics
120 ///
121 /// Panics if the node does not exist.
122 ///
123 /// # Examples
124 ///
125 /// ```
126 /// # use std::error::Error;
127 /// # fn main() -> Result<(), Box<dyn Error>> {
128 /// use zrx_graph::{Graph, Topology};
129 ///
130 /// // Create graph builder and add nodes
131 /// let mut builder = Graph::builder();
132 /// let a = builder.add_node("a");
133 /// let b = builder.add_node("b");
134 /// let c = builder.add_node("c");
135 ///
136 /// // Create edges between nodes
137 /// builder.add_edge(a, b)?;
138 /// builder.add_edge(b, c)?;
139 ///
140 /// // Create graph from builder
141 /// let graph = builder.build();
142 ///
143 /// // Ensure nodes are ancestors (or not)
144 /// assert_eq!(graph.is_ancestor(a, b), true);
145 /// assert_eq!(graph.is_ancestor(a, c), true);
146 /// assert_eq!(graph.is_ancestor(b, a), false);
147 /// # Ok(())
148 /// # }
149 /// ```
150 #[inline]
151 #[must_use]
152 pub fn is_ancestor(&self, source: usize, target: usize) -> bool {
153 let distance = self.topology.distance();
154 distance[source][target] != u8::MAX
155 }
156
157 /// Returns whether the source node is a descendant of the target node.
158 ///
159 /// # Panics
160 ///
161 /// Panics if the node does not exist.
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// # use std::error::Error;
167 /// # fn main() -> Result<(), Box<dyn Error>> {
168 /// use zrx_graph::{Graph, Topology};
169 ///
170 /// // Create graph builder and add nodes
171 /// let mut builder = Graph::builder();
172 /// let a = builder.add_node("a");
173 /// let b = builder.add_node("b");
174 /// let c = builder.add_node("c");
175 ///
176 /// // Create edges between nodes
177 /// builder.add_edge(a, b)?;
178 /// builder.add_edge(b, c)?;
179 ///
180 /// // Create graph from builder
181 /// let graph = builder.build();
182 ///
183 /// // Ensure nodes are descendants (or not)
184 /// assert_eq!(graph.is_descendant(b, a), true);
185 /// assert_eq!(graph.is_descendant(c, a), true);
186 /// assert_eq!(graph.is_descendant(a, b), false);
187 /// # Ok(())
188 /// # }
189 /// ```
190 #[inline]
191 #[must_use]
192 pub fn is_descendant(&self, source: usize, target: usize) -> bool {
193 let distance = self.topology.distance();
194 distance[target][source] != u8::MAX
195 }
196
197 /// Returns whether the source node is a predecessor of the target node.
198 ///
199 /// # Panics
200 ///
201 /// Panics if the node does not exist.
202 ///
203 /// # Examples
204 ///
205 /// ```
206 /// # use std::error::Error;
207 /// # fn main() -> Result<(), Box<dyn Error>> {
208 /// use zrx_graph::{Graph, Topology};
209 ///
210 /// // Create graph builder and add nodes
211 /// let mut builder = Graph::builder();
212 /// let a = builder.add_node("a");
213 /// let b = builder.add_node("b");
214 /// let c = builder.add_node("c");
215 ///
216 /// // Create edges between nodes
217 /// builder.add_edge(a, b)?;
218 /// builder.add_edge(b, c)?;
219 ///
220 /// // Create graph from builder
221 /// let graph = builder.build();
222 ///
223 /// // Ensure nodes are predecessors (or not)
224 /// assert_eq!(graph.is_predecessor(a, b), true);
225 /// assert_eq!(graph.is_predecessor(a, c), false);
226 /// assert_eq!(graph.is_predecessor(b, a), false);
227 /// # Ok(())
228 /// # }
229 /// ```
230 #[inline]
231 #[must_use]
232 pub fn is_predecessor(&self, source: usize, target: usize) -> bool {
233 let distance = self.topology.distance();
234 distance[source][target] == 1
235 }
236
237 /// Returns whether the source node is a successor of the target node.
238 ///
239 /// # Panics
240 ///
241 /// Panics if the node does not exist.
242 ///
243 /// # Examples
244 ///
245 /// ```
246 /// # use std::error::Error;
247 /// # fn main() -> Result<(), Box<dyn Error>> {
248 /// use zrx_graph::{Graph, Topology};
249 ///
250 /// // Create graph builder and add nodes
251 /// let mut builder = Graph::builder();
252 /// let a = builder.add_node("a");
253 /// let b = builder.add_node("b");
254 /// let c = builder.add_node("c");
255 ///
256 /// // Create edges between nodes
257 /// builder.add_edge(a, b)?;
258 /// builder.add_edge(b, c)?;
259 ///
260 /// // Create graph from builder
261 /// let graph = builder.build();
262 ///
263 /// // Ensure nodes are successors (or not)
264 /// assert_eq!(graph.is_successor(b, a), true);
265 /// assert_eq!(graph.is_successor(c, a), false);
266 /// assert_eq!(graph.is_successor(a, b), false);
267 /// # Ok(())
268 /// # }
269 /// ```
270 #[inline]
271 #[must_use]
272 pub fn is_successor(&self, source: usize, target: usize) -> bool {
273 let distance = self.topology.distance();
274 distance[target][source] == 1
275 }
276
277 /// Returns whether the graph is acyclic.
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// # use std::error::Error;
283 /// # fn main() -> Result<(), Box<dyn Error>> {
284 /// use zrx_graph::Graph;
285 ///
286 /// // Create graph builder and add nodes
287 /// let mut builder = Graph::builder();
288 /// let a = builder.add_node("a");
289 /// let b = builder.add_node("b");
290 /// let c = builder.add_node("c");
291 ///
292 /// // Create edges between nodes
293 /// builder.add_edge(a, b)?;
294 /// builder.add_edge(b, c)?;
295 ///
296 /// // Create graph from builder
297 /// let graph = builder.build();
298 ///
299 /// // Ensure there are no cycles
300 /// assert_eq!(graph.is_acyclic(), true);
301 /// # Ok(())
302 /// # }
303 /// ```
304 #[must_use]
305 pub fn is_acyclic(&self) -> bool {
306 let incoming = self.topology.incoming();
307 let outgoing = self.topology.outgoing();
308
309 // Initialize in-degrees and seed queue with source nodes
310 let mut degrees = incoming.degrees().to_vec();
311 let mut queue: VecDeque<usize> =
312 self.iter().filter(|&node| degrees[node] == 0).collect();
313
314 // Process nodes using Kahn's algorithm for topological sorting
315 let mut visited = 0;
316 while let Some(source) = queue.pop_front() {
317 visited += 1;
318
319 // Decrement in-degrees of successors, enqueuing new sources
320 for &target in &outgoing[source] {
321 degrees[target] -= 1;
322 if degrees[target] == 0 {
323 queue.push_back(target);
324 }
325 }
326 }
327
328 // Graph is acyclic if all nodes were visited
329 visited == self.len()
330 }
331}