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 super::Graph;
29
30// ----------------------------------------------------------------------------
31// Implementations
32// ----------------------------------------------------------------------------
33
34impl<T> Graph<T> {
35 /// Returns whether the given node is a source.
36 ///
37 /// # Panics
38 ///
39 /// Panics if the node does not exist.
40 ///
41 /// # Examples
42 ///
43 /// ```
44 /// # use std::error::Error;
45 /// # fn main() -> Result<(), Box<dyn Error>> {
46 /// use zrx_graph::{Graph, Topology};
47 ///
48 /// // Create graph builder and add nodes
49 /// let mut builder = Graph::builder();
50 /// let a = builder.add_node("a");
51 /// let b = builder.add_node("b");
52 /// let c = builder.add_node("c");
53 ///
54 /// // Create edges between nodes
55 /// builder.add_edge(a, b)?;
56 /// builder.add_edge(b, c)?;
57 ///
58 /// // Create graph from builder
59 /// let graph = builder.build();
60 ///
61 /// // Ensure nodes are sources (or not)
62 /// assert_eq!(graph.is_source(a), true);
63 /// assert_eq!(graph.is_source(b), false);
64 /// assert_eq!(graph.is_source(c), false);
65 /// # Ok(())
66 /// # }
67 /// ```
68 #[inline]
69 #[must_use]
70 pub fn is_source(&self, node: usize) -> bool {
71 let incoming = self.topology.incoming();
72 incoming[node].is_empty()
73 }
74
75 /// Returns whether the given node is a sink.
76 ///
77 /// # Panics
78 ///
79 /// Panics if the node does not exist.
80 ///
81 /// # Examples
82 ///
83 /// ```
84 /// # use std::error::Error;
85 /// # fn main() -> Result<(), Box<dyn Error>> {
86 /// use zrx_graph::{Graph, Topology};
87 ///
88 /// // Create graph builder and add nodes
89 /// let mut builder = Graph::builder();
90 /// let a = builder.add_node("a");
91 /// let b = builder.add_node("b");
92 /// let c = builder.add_node("c");
93 ///
94 /// // Create edges between nodes
95 /// builder.add_edge(a, b)?;
96 /// builder.add_edge(b, c)?;
97 ///
98 /// // Create graph from builder
99 /// let graph = builder.build();
100 ///
101 /// // Ensure nodes are sinks (or not)
102 /// assert_eq!(graph.is_sink(a), false);
103 /// assert_eq!(graph.is_sink(b), false);
104 /// assert_eq!(graph.is_sink(c), true);
105 /// # Ok(())
106 /// # }
107 /// ```
108 #[inline]
109 #[must_use]
110 pub fn is_sink(&self, node: usize) -> bool {
111 let outgoing = self.topology.outgoing();
112 outgoing[node].is_empty()
113 }
114
115 /// Returns whether the source node is an ancestor of the target node.
116 ///
117 /// # Panics
118 ///
119 /// Panics if the node does not exist.
120 ///
121 /// # Examples
122 ///
123 /// ```
124 /// # use std::error::Error;
125 /// # fn main() -> Result<(), Box<dyn Error>> {
126 /// use zrx_graph::{Graph, Topology};
127 ///
128 /// // Create graph builder and add nodes
129 /// let mut builder = Graph::builder();
130 /// let a = builder.add_node("a");
131 /// let b = builder.add_node("b");
132 /// let c = builder.add_node("c");
133 ///
134 /// // Create edges between nodes
135 /// builder.add_edge(a, b)?;
136 /// builder.add_edge(b, c)?;
137 ///
138 /// // Create graph from builder
139 /// let graph = builder.build();
140 ///
141 /// // Ensure nodes are ancestors (or not)
142 /// assert_eq!(graph.is_ancestor(a, b), true);
143 /// assert_eq!(graph.is_ancestor(a, c), true);
144 /// assert_eq!(graph.is_ancestor(b, a), false);
145 /// # Ok(())
146 /// # }
147 /// ```
148 #[inline]
149 #[must_use]
150 pub fn is_ancestor(&self, source: usize, target: usize) -> bool {
151 let distance = self.topology.distance();
152 distance[source][target] != u8::MAX
153 }
154
155 /// Returns whether the source node is a descendant of the target node.
156 ///
157 /// # Panics
158 ///
159 /// Panics if the node does not exist.
160 ///
161 /// # Examples
162 ///
163 /// ```
164 /// # use std::error::Error;
165 /// # fn main() -> Result<(), Box<dyn Error>> {
166 /// use zrx_graph::{Graph, Topology};
167 ///
168 /// // Create graph builder and add nodes
169 /// let mut builder = Graph::builder();
170 /// let a = builder.add_node("a");
171 /// let b = builder.add_node("b");
172 /// let c = builder.add_node("c");
173 ///
174 /// // Create edges between nodes
175 /// builder.add_edge(a, b)?;
176 /// builder.add_edge(b, c)?;
177 ///
178 /// // Create graph from builder
179 /// let graph = builder.build();
180 ///
181 /// // Ensure nodes are descendants (or not)
182 /// assert_eq!(graph.is_descendant(b, a), true);
183 /// assert_eq!(graph.is_descendant(c, a), true);
184 /// assert_eq!(graph.is_descendant(a, b), false);
185 /// # Ok(())
186 /// # }
187 /// ```
188 #[inline]
189 #[must_use]
190 pub fn is_descendant(&self, source: usize, target: usize) -> bool {
191 let distance = self.topology.distance();
192 distance[target][source] != u8::MAX
193 }
194
195 /// Returns whether the source node is a predecessor of the target node.
196 ///
197 /// # Panics
198 ///
199 /// Panics if the node does not exist.
200 ///
201 /// # Examples
202 ///
203 /// ```
204 /// # use std::error::Error;
205 /// # fn main() -> Result<(), Box<dyn Error>> {
206 /// use zrx_graph::{Graph, Topology};
207 ///
208 /// // Create graph builder and add nodes
209 /// let mut builder = Graph::builder();
210 /// let a = builder.add_node("a");
211 /// let b = builder.add_node("b");
212 /// let c = builder.add_node("c");
213 ///
214 /// // Create edges between nodes
215 /// builder.add_edge(a, b)?;
216 /// builder.add_edge(b, c)?;
217 ///
218 /// // Create graph from builder
219 /// let graph = builder.build();
220 ///
221 /// // Ensure nodes are predecessors (or not)
222 /// assert_eq!(graph.is_predecessor(a, b), true);
223 /// assert_eq!(graph.is_predecessor(a, c), false);
224 /// assert_eq!(graph.is_predecessor(b, a), false);
225 /// # Ok(())
226 /// # }
227 /// ```
228 #[inline]
229 #[must_use]
230 pub fn is_predecessor(&self, source: usize, target: usize) -> bool {
231 let distance = self.topology.distance();
232 distance[source][target] == 1
233 }
234
235 /// Returns whether the source node is a successor of the target node.
236 ///
237 /// # Panics
238 ///
239 /// Panics if the node does not exist.
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// # use std::error::Error;
245 /// # fn main() -> Result<(), Box<dyn Error>> {
246 /// use zrx_graph::{Graph, Topology};
247 ///
248 /// // Create graph builder and add nodes
249 /// let mut builder = Graph::builder();
250 /// let a = builder.add_node("a");
251 /// let b = builder.add_node("b");
252 /// let c = builder.add_node("c");
253 ///
254 /// // Create edges between nodes
255 /// builder.add_edge(a, b)?;
256 /// builder.add_edge(b, c)?;
257 ///
258 /// // Create graph from builder
259 /// let graph = builder.build();
260 ///
261 /// // Ensure nodes are successors (or not)
262 /// assert_eq!(graph.is_successor(b, a), true);
263 /// assert_eq!(graph.is_successor(c, a), false);
264 /// assert_eq!(graph.is_successor(a, b), false);
265 /// # Ok(())
266 /// # }
267 /// ```
268 #[inline]
269 #[must_use]
270 pub fn is_successor(&self, source: usize, target: usize) -> bool {
271 let distance = self.topology.distance();
272 distance[target][source] == 1
273 }
274}