Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/digraph.rs

15.1 KiB, 55 runs

created by r1870400018:8854, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Directed graph data structure with typed nodes and links.
2//!
3//! This module provides a generic directed graph implementation where nodes
4//! and links can carry arbitrary data. The graph supports efficient lookups
5//! and traversals through HashMap-based storage.
6//!
7//! The parallel search methods are behind the `par` feature, which is enabled
8//! by default. Disable default features to build for targets without threads.
9
10use std::{
11 collections::HashMap,
12 fmt,
13 hash::Hash,
14};
15
16#[cfg(feature = "par")]
17use rayon::prelude::*;
18
19/// Trait for types that can serve as node identifiers in the graph.
20///
21/// Implementors must be cloneable, debuggable, equatable, and hashable
22/// to work as HashMap keys.
23pub trait NodeId: Clone + fmt::Debug + Eq + Hash + Send + Sync {}
24
25/// Trait for data stored within graph nodes.
26///
27/// Node data must be cloneable, debuggable, and displayable for graph operations.
28pub trait NodeData: Clone + fmt::Debug + fmt::Display + Send + Sync {}
29
30/// Trait for data stored on graph links (edges).
31///
32/// Link data must be cloneable, debuggable, and displayable for graph operations.
33pub trait LinkData: Clone + fmt::Debug + fmt::Display + Send + Sync {}
34
35/// A node in the directed graph.
36///
37/// Each node contains its associated data and a list of outgoing links
38/// to other nodes in the graph.
39#[derive(Clone, Debug)]
40pub struct Node<ID: NodeId, ND: NodeData, LD: LinkData> {
41 /// Outgoing links from this node.
42 links: Vec<Link<ID, LD>>,
43 /// Data associated with this node.
44 data: ND,
45}
46
47/// A directed link (edge) between nodes.
48///
49/// Each link carries optional data and points to a target node.
50#[allow(dead_code)]
51#[derive(Clone, Debug)]
52pub struct Link<ID: NodeId, LD: LinkData> {
53 /// Data associated with this link.
54 data: LD,
55 /// Target node identifier.
56 to: ID,
57}
58
59/// A directed graph with typed nodes and links.
60///
61/// The graph uses a HashMap for O(1) node lookups by identifier.
62/// Nodes can have arbitrary data attached, as can the links between them.
63///
64/// # Type Parameters
65///
66/// * `ID` - The type used for node identifiers.
67/// * `ND` - The type of data stored in nodes.
68/// * `LD` - The type of data stored on links.
69#[derive(Clone, Debug)]
70pub struct DiGraph<ID: NodeId, ND: NodeData, LD: LinkData> {
71 /// HashMap storing all nodes indexed by their identifiers.
72 nodes: HashMap<ID, Node<ID, ND, LD>>,
73}
74
75impl<ID: NodeId, ND: NodeData, LD: LinkData> DiGraph<ID, ND, LD> {
76
77 /// Creates a new, empty directed graph.
78 ///
79 /// # Examples
80 ///
81 /// ```
82 /// use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
83 /// use std::fmt;
84 ///
85 /// // Node and link data opt in through the marker traits. Wrap standard
86 /// // types in a newtype to satisfy the orphan rule.
87 /// #[derive(Clone, Debug, Eq, Hash, PartialEq)]
88 /// struct Id(u32);
89 /// impl NodeId for Id {}
90 ///
91 /// #[derive(Clone, Debug)]
92 /// struct Label(String);
93 /// impl fmt::Display for Label {
94 /// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) }
95 /// }
96 /// impl NodeData for Label {}
97 /// impl LinkData for Label {}
98 ///
99 /// let graph: DiGraph<Id, Label, Label> = DiGraph::new();
100 /// assert_eq!(graph.len(), 0);
101 /// ```
102 pub fn new() -> Self {
103 Self {
104 nodes: HashMap::new(),
105 }
106 }
107
108 pub fn len(&self) -> usize {
109 self.nodes.len()
110 }
111
112 /// Inserts a new node into the graph.
113 ///
114 /// Returns the previous node if one existed with the same identifier.
115 ///
116 /// # Arguments
117 ///
118 /// * `id` - The unique identifier for the node.
119 /// * `data` - The data to store in the node.
120 ///
121 /// # Examples
122 ///
123 /// ```
124 /// # use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
125 /// # use std::fmt;
126 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
127 /// # impl NodeId for Id {}
128 /// # #[derive(Clone, Debug)] struct Label(String);
129 /// # impl fmt::Display for Label { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) } }
130 /// # impl NodeData for Label {}
131 /// # impl LinkData for Label {}
132 /// let mut graph: DiGraph<Id, Label, Label> = DiGraph::new();
133 /// graph.insert(Id(1), Label("Node A".into()));
134 /// graph.insert(Id(2), Label("Node B".into()));
135 /// assert_eq!(graph.len(), 2);
136 /// ```
137 pub fn insert(&mut self, id: ID, data: ND) -> Option<Node<ID, ND, LD>> {
138 let node = Node {
139 links: Vec::new(),
140 data,
141 };
142 self.nodes.insert(id, node)
143 }
144
145 /// Creates a directed link between two nodes.
146 ///
147 /// If the source node doesn't exist, this operation is silently ignored.
148 /// The target node doesn't need to exist for the link to be created.
149 ///
150 /// # Arguments
151 ///
152 /// * `from` - The identifier of the source node.
153 /// * `to` - The identifier of the target node.
154 /// * `data` - The data to associate with the link.
155 ///
156 /// # Examples
157 ///
158 /// ```
159 /// # use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
160 /// # use std::fmt;
161 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
162 /// # impl NodeId for Id {}
163 /// # #[derive(Clone, Debug)] struct Label(String);
164 /// # impl fmt::Display for Label { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) } }
165 /// # impl NodeData for Label {}
166 /// # impl LinkData for Label {}
167 /// let mut graph: DiGraph<Id, Label, Label> = DiGraph::new();
168 /// graph.insert(Id(1), Label("Node A".into()));
169 /// graph.insert(Id(2), Label("Node B".into()));
170 /// graph.link(&Id(1), &Id(2), Label("Edge A->B".into()));
171 /// ```
172 pub fn link(&mut self, from: &ID, to: &ID, data: LD) {
173 if let Some(from_node) = self.nodes.get_mut(from) {
174 from_node.links.push(Link { data, to: to.clone() });
175 }
176 }
177
178 /// Finds all nodes matching a predicate on their data.
179 ///
180 /// Returns a vector of node identifiers that match the given criteria.
181 /// This is the most memory-efficient option when you only need the identifiers.
182 ///
183 /// # Arguments
184 ///
185 /// * `predicate` - A closure that returns `true` for matching node data.
186 ///
187 /// # Returns
188 ///
189 /// A vector containing the identifiers of all matching nodes.
190 ///
191 /// # Examples
192 ///
193 /// ```
194 /// # use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
195 /// # use std::fmt;
196 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
197 /// # impl NodeId for Id {}
198 /// # #[derive(Clone, Debug)] struct Val(i64);
199 /// # impl fmt::Display for Val { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) } }
200 /// # impl NodeData for Val {}
201 /// # impl LinkData for Val {}
202 /// let mut graph: DiGraph<Id, Val, Val> = DiGraph::new();
203 /// graph.insert(Id(1), Val(100));
204 /// graph.insert(Id(2), Val(200));
205 /// graph.insert(Id(3), Val(150));
206 ///
207 /// // Find all nodes with values greater than 120.
208 /// let large_nodes = graph.find_nodes(|value| value.0 > 120);
209 /// assert_eq!(large_nodes.len(), 2);
210 /// ```
211 pub fn find_nodes<F>(&self, predicate: F) -> Vec<ID>
212 where
213 F: Fn(&ND) -> bool,
214 {
215 self.nodes
216 .iter()
217 .filter_map(|(id, node)| {
218 if predicate(&node.data) {
219 Some(id.clone())
220 } else {
221 None
222 }
223 })
224 .collect()
225 }
226
227 /// Finds all nodes matching a predicate, returning both identifiers and data.
228 ///
229 /// This method is more efficient than `find_nodes` when you need both the
230 /// identifier and the data, as it avoids a second lookup operation.
231 ///
232 /// # Arguments
233 ///
234 /// * `predicate` - A closure that returns `true` for matching node data.
235 ///
236 /// # Returns
237 ///
238 /// A vector of tuples containing the identifier and a reference to the data
239 /// for each matching node.
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
245 /// use std::fmt;
246 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
247 /// # impl NodeId for Id {}
248 ///
249 /// #[derive(Clone, Debug)]
250 /// struct Person {
251 /// name: String,
252 /// age: u32,
253 /// }
254 /// impl fmt::Display for Person {
255 /// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
256 /// write!(f, "{} ({})", self.name, self.age)
257 /// }
258 /// }
259 /// impl NodeData for Person {}
260 /// impl LinkData for Person {}
261 ///
262 /// let mut graph: DiGraph<Id, Person, Person> = DiGraph::new();
263 /// graph.insert(Id(1), Person { name: "Alice".into(), age: 30 });
264 /// graph.insert(Id(2), Person { name: "Bob".into(), age: 25 });
265 /// graph.insert(Id(3), Person { name: "Charlie".into(), age: 35 });
266 ///
267 /// // Find all people aged 30 or over.
268 /// let adults = graph.find_nodes_with_data(|person| person.age >= 30);
269 /// assert_eq!(adults.len(), 2);
270 /// ```
271 pub fn find_nodes_with_data<F>(&self, predicate: F) -> Vec<(ID, &ND)>
272 where
273 F: Fn(&ND) -> bool,
274 {
275 self.nodes
276 .iter()
277 .filter_map(|(id, node)| {
278 if predicate(&node.data) {
279 Some((id.clone(), &node.data))
280 } else {
281 None
282 }
283 })
284 .collect()
285 }
286
287 /// Finds all nodes matching a predicate using parallel processing.
288 ///
289 /// This method parallelises the search across CPU cores for better performance
290 /// with large graphs. Requires the `par` feature, which is enabled by default.
291 ///
292 /// # Arguments
293 ///
294 /// * `predicate` - A closure that returns `true` for matching node data.
295 ///
296 /// # Returns
297 ///
298 /// A vector containing the identifiers of all matching nodes.
299 ///
300 /// # Examples
301 ///
302 /// ```
303 /// # use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
304 /// # use std::fmt;
305 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
306 /// # impl NodeId for Id {}
307 /// # #[derive(Clone, Debug)] struct Val(i64);
308 /// # impl fmt::Display for Val { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.0) } }
309 /// # impl NodeData for Val {}
310 /// # impl LinkData for Val {}
311 /// let mut graph: DiGraph<Id, Val, Val> = DiGraph::new();
312 /// for i in 0..10_000u32 {
313 /// graph.insert(Id(i), Val((i as i64) * 2));
314 /// }
315 ///
316 /// // Find all nodes with values greater than 5000 in parallel.
317 /// let large_nodes = graph.find_nodes_par(|value| value.0 > 5000);
318 /// assert!(!large_nodes.is_empty());
319 /// ```
320 #[cfg(feature = "par")]
321 pub fn find_nodes_par<F>(&self, predicate: F) -> Vec<ID>
322 where
323 F: Fn(&ND) -> bool + Sync + Send,
324 {
325 self.nodes
326 .iter()
327 .collect::<Vec<_>>()
328 .par_iter()
329 .filter_map(|(id, node)| {
330 if predicate(&node.data) {
331 Some((*id).clone())
332 } else {
333 None
334 }
335 })
336 .collect()
337 }
338
339 /// Finds all nodes matching a predicate using parallel processing, returning both identifiers and data.
340 ///
341 /// This method parallelises the search and returns both the identifier and
342 /// data reference for matched nodes. Requires the `par` feature, which is
343 /// enabled by default.
344 ///
345 /// # Arguments
346 ///
347 /// * `predicate` - A closure that returns `true` for matching node data.
348 ///
349 /// # Returns
350 ///
351 /// A vector of tuples containing the identifier and a reference to the data
352 /// for each matching node.
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use oxedyne_fe2o3_data::digraph::{DiGraph, NodeId, NodeData, LinkData};
358 /// use std::fmt;
359 /// # #[derive(Clone, Debug, Eq, Hash, PartialEq)] struct Id(u32);
360 /// # impl NodeId for Id {}
361 ///
362 /// #[derive(Clone, Debug)]
363 /// struct Sensor {
364 /// name: String,
365 /// temperature: f64,
366 /// }
367 /// impl fmt::Display for Sensor {
368 /// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
369 /// write!(f, "{}: {:.1}", self.name, self.temperature)
370 /// }
371 /// }
372 /// impl NodeData for Sensor {}
373 /// impl LinkData for Sensor {}
374 ///
375 /// let mut graph: DiGraph<Id, Sensor, Sensor> = DiGraph::new();
376 /// for i in 0..10_000u32 {
377 /// graph.insert(Id(i), Sensor {
378 /// name: format!("Sensor_{}", i),
379 /// temperature: (i as f64) * 0.1,
380 /// });
381 /// }
382 ///
383 /// // Find all sensors with high temperature readings in parallel.
384 /// let hot_sensors = graph.find_nodes_with_data_par(|sensor| sensor.temperature > 500.0);
385 /// assert!(!hot_sensors.is_empty());
386 /// ```
387 #[cfg(feature = "par")]
388 pub fn find_nodes_with_data_par<F>(&self, predicate: F) -> Vec<(ID, &ND)>
389 where
390 F: Fn(&ND) -> bool + Sync + Send,
391 {
392 self.nodes
393 .iter()
394 .collect::<Vec<_>>()
395 .par_iter()
396 .filter_map(|(id, node)| {
397 if predicate(&node.data) {
398 Some(((*id).clone(), &node.data))
399 } else {
400 None
401 }
402 })
403 .collect()
404 }
405
406 /// Gets a node's data by ID.
407 ///
408 /// # Arguments
409 /// * `id` - The node identifier.
410 ///
411 /// # Returns
412 /// Reference to the node's data if it exists.
413 pub fn get_node(&self, id: &ID) -> Option<&ND> {
414 self.nodes.get(id).map(|node| &node.data)
415 }
416
417 /// Gets all outgoing links from a node.
418 ///
419 /// # Arguments
420 /// * `id` - The source node identifier.
421 ///
422 /// # Returns
423 /// Vector of (target_id, link_data) tuples for all outgoing links.
424 pub fn get_links_from(&self, id: &ID) -> Vec<(&ID, &LD)> {
425 self.nodes
426 .get(id)
427 .map(|node| {
428 node.links
429 .iter()
430 .map(|link| (&link.to, &link.data))
431 .collect()
432 })
433 .unwrap_or_default()
434 }
435
436 /// Gets all incoming links to a node.
437 ///
438 /// # Arguments
439 /// * `id` - The target node identifier.
440 ///
441 /// # Returns
442 /// Vector of (source_id, link_data) tuples for all incoming links.
443 pub fn get_links_to(&self, id: &ID) -> Vec<(&ID, &LD)> {
444 let mut incoming = Vec::new();
445 for (from_id, node) in &self.nodes {
446 for link in &node.links {
447 if &link.to == id {
448 incoming.push((from_id, &link.data));
449 }
450 }
451 }
452 incoming
453 }
454
455 /// Iterates over all nodes in the graph.
456 ///
457 /// # Returns
458 /// Iterator over (node_id, node_data) pairs.
459 pub fn iter_nodes(&self) -> impl Iterator<Item = (&ID, &ND)> {
460 self.nodes.iter().map(|(id, node)| (id, &node.data))
461 }
462}