directed_graph/lib.rs
1//! A generic directed graph implementation with core graph operations and cycle detection capabilities.
2//!
3//! This crate provides a type-safe `DirectedGraph` structure that supports generic node types
4//! (with basic constraints for hashing and ordering) and common graph operations like node/edge
5//! addition, removal, adjacency query, and node/edge count statistics. It also includes an
6//! `analyze` module for cycle detection in directed graphs.
7//!
8//! # Key Features
9//! - Generic node support (works with all types that implement `NodeConstraints`)
10//! - Efficient adjacency list storage with `IndexMap` and `IndexSet`
11//! - Core graph operations: add/remove nodes/edges, query adjacent nodes
12//! - Node/edge count statistics
13//! - Cycle detection and graph analysis (in the `analyze` module)
14//!
15//! # Basic Usage
16//! ```
17//! use directed_graph::DirectedGraph;
18//!
19//! // Create a new directed graph with integer nodes
20//! let mut graph = DirectedGraph::new();
21//!
22//! // Add nodes and edges
23//! graph.add_node(1, vec![2, 3]);
24//! graph.add_node(2, vec![3]);
25//! graph.add_node(3, vec![]);
26//!
27//! // Query adjacent nodes
28//! assert!(graph.get_adjacent_nodes(&1).unwrap().contains(&2));
29//!
30//! // Get node/edge counts
31//! assert_eq!(graph.node_count(), 3);
32//! assert_eq!(graph.edge_count(), 3);
33//!
34//! // Remove an edge
35//! graph.remove_edge(&1, &3);
36//! assert_eq!(graph.edge_count(), 2);
37//! ```
38
39pub use indexmap::IndexMap as NodeMap;
40pub use indexmap::IndexSet as NodeSet;
41use std::fmt::Debug;
42use std::hash::Hash;
43
44mod algorithm;
45/// Graph analysis module (cycle detection core logic)
46pub mod analyze;
47
48/// Trait defining the core constraints for node types in a `DirectedGraph`.
49///
50/// Nodes must implement this trait to be used in the directed graph. The trait aggregates
51/// common Rust traits required for hashing, equality, ordering, cloning, and debugging—
52/// all essential for graph storage and operations (e.g., `IndexMap` keys, set operations).
53///
54/// This trait is **automatically implemented** for all types that satisfy the underlying bounds,
55/// so you do not need to implement it manually for your custom node types.
56pub trait NodeConstraints: Clone + Debug + Eq + PartialEq + Hash + PartialOrd + Ord {}
57
58// Automatic implementation for all types meeting the NodeConstraints bounds
59impl<T> NodeConstraints for T where T: Clone + Debug + Eq + PartialEq + Hash + PartialOrd + Ord {}
60
61/// A generic directed graph data structure implemented with an adjacency list.
62///
63/// The graph uses a `IndexMap` to map each node to an `IndexSet` of its adjacent nodes (outgoing edges),
64/// ensuring efficient:
65/// - Node/edge lookups (O(1) average for hash map)
66/// - Duplicate edge prevention (via `IndexSet`)
67/// - Node/edge addition/removal
68///
69/// The node type `N` must implement the `NodeConstraints` trait for core operations.
70#[derive(Debug, Clone)]
71pub struct DirectedGraph<N: NodeConstraints> {
72 /// Internal adjacency list storage: maps each node to its set of adjacent nodes (outgoing edges)
73 adjacency_list: NodeMap<N, NodeSet<N>>,
74}
75
76impl<N: NodeConstraints> Default for DirectedGraph<N> {
77 /// Create a new empty `DirectedGraph` using the default implementation.
78 ///
79 /// Equivalent to calling `DirectedGraph::new()`.
80 fn default() -> Self {
81 Self::new()
82 }
83}
84
85impl<N: NodeConstraints> DirectedGraph<N> {
86 /// Create a new empty directed graph.
87 ///
88 /// # Examples
89 /// ```
90 /// use directed_graph::DirectedGraph;
91 /// let graph: DirectedGraph<u32> = DirectedGraph::new();
92 /// assert_eq!(graph.node_count(), 0);
93 /// ```
94 pub fn new() -> Self {
95 DirectedGraph {
96 adjacency_list: NodeMap::new(),
97 }
98 }
99
100 /// Check if the graph contains a specific node.
101 ///
102 /// # Arguments
103 /// * `n` - Reference to the node to check for existence
104 ///
105 /// # Returns
106 /// `true` if the node exists in the graph, `false` otherwise.
107 ///
108 /// # Examples
109 /// ```
110 /// use directed_graph::DirectedGraph;
111 /// let mut graph = DirectedGraph::new();
112 /// graph.add_node("Alice", vec![]);
113 /// assert!(graph.contains(&"Alice"));
114 /// assert!(!graph.contains(&"Bob"));
115 /// ```
116 pub fn contains(&self, n: &N) -> bool {
117 self.adjacency_list.contains_key(n)
118 }
119
120 /// Add a node to the graph with a list of outgoing edges (adjacent nodes).
121 ///
122 /// If the node **already exists** in the graph, the new edges are **appended** (duplicate edges are ignored).
123 /// If the node **does not exist**, it is created with the provided outgoing edges.
124 ///
125 /// # Arguments
126 /// * `start` - The node to add to the graph (source node for the outgoing edges)
127 /// * `ends_vec` - Vector of adjacent nodes (target nodes for the outgoing edges from `start`)
128 ///
129 /// # Notes
130 /// - The target nodes in `ends_vec` **do not need to exist** in the graph (orphaned edges are allowed)
131 /// - Duplicate edges in `ends_vec` are automatically removed (via `IndexSet`)
132 ///
133 /// # Examples
134 /// ```
135 /// use directed_graph::DirectedGraph;
136 /// let mut graph = DirectedGraph::new();
137 /// // Add a new node with two outgoing edges
138 /// graph.add_node(1, vec![2, 3]);
139 /// // Append a new edge to an existing node (duplicate 3 is ignored)
140 /// graph.add_node(1, vec![3, 4]);
141 /// assert!(graph.get_adjacent_nodes(&1).unwrap().contains(&4));
142 /// ```
143 pub fn add_node(&mut self, start: N, ends_vec: Vec<N>) {
144 self.adjacency_list
145 .entry(start)
146 .and_modify(|end_set| {
147 ends_vec.iter().for_each(|end| {
148 if !end_set.contains(end) {
149 end_set.insert(end.clone());
150 }
151 });
152 })
153 .or_insert({
154 let mut end_set = NodeSet::new();
155 ends_vec.iter().for_each(|end| {
156 if !end_set.contains(end) {
157 end_set.insert(end.clone());
158 }
159 });
160 end_set
161 });
162 }
163
164 /// Get the set of adjacent nodes (outgoing edges) for a specific node.
165 ///
166 /// # Arguments
167 /// * `n` - Reference to the node to query for adjacent nodes
168 ///
169 /// # Returns
170 /// `Some(&NodeSet<N>)` if the node exists (containing all adjacent nodes), `None` otherwise.
171 ///
172 /// # Examples
173 /// ```
174 /// use directed_graph::DirectedGraph;
175 /// let mut graph = DirectedGraph::new();
176 /// graph.add_node(1, vec![2, 3]);
177 /// let adj = graph.get_adjacent_nodes(&1).unwrap();
178 /// assert!(adj.contains(&2) && adj.contains(&3));
179 /// ```
180 pub fn get_adjacent_nodes(&self, n: &N) -> Option<&NodeSet<N>> {
181 self.adjacency_list.get(n)
182 }
183
184 /// Get the total number of **unique nodes** in the graph.
185 ///
186 /// # Returns
187 /// The count of nodes in the graph (length of the adjacency list).
188 ///
189 /// # Examples
190 /// ```
191 /// use directed_graph::DirectedGraph;
192 /// let mut graph = DirectedGraph::new();
193 /// graph.add_node(1, vec![2]);
194 /// graph.add_node(2, vec![3]);
195 /// assert_eq!(graph.node_count(), 2);
196 /// ```
197 pub fn node_count(&self) -> usize {
198 self.adjacency_list.len()
199 }
200
201 /// Get the total number of **unique edges** in the graph.
202 ///
203 /// Counts all outgoing edges across all nodes (duplicate edges are not counted, via `IndexSet`).
204 ///
205 /// # Returns
206 /// The total number of unique outgoing edges in the graph.
207 ///
208 /// # Examples
209 /// ```
210 /// use directed_graph::DirectedGraph;
211 /// let mut graph = DirectedGraph::new();
212 /// graph.add_node(1, vec![2, 3]);
213 /// graph.add_node(2, vec![3]);
214 /// assert_eq!(graph.edge_count(), 3);
215 /// ```
216 pub fn edge_count(&self) -> usize {
217 self.adjacency_list.values().map(|edges| edges.len()).sum()
218 }
219
220 /// Remove a node from the graph and return its outgoing edges (if the node existed).
221 ///
222 /// Removes the node **and all its outgoing edges** from the adjacency list. Incoming edges to this node
223 /// are **not removed** (they remain as orphaned edges from other nodes).
224 ///
225 /// # Arguments
226 /// * `n` - The node to remove from the graph
227 ///
228 /// # Returns
229 /// `Some(NodeSet<N>)` if the node existed (containing its outgoing edges), `None` otherwise.
230 ///
231 /// # Examples
232 /// ```
233 /// use directed_graph::DirectedGraph;
234 /// let mut graph = DirectedGraph::new();
235 /// graph.add_node(1, vec![2, 3]);
236 /// let edges = graph.remove_node(1).unwrap();
237 /// assert_eq!(edges.len(), 2);
238 /// assert!(!graph.contains(&1));
239 /// ```
240 pub fn remove_node(&mut self, n: N) -> Option<NodeSet<N>> {
241 self.adjacency_list.shift_remove(&n)
242 }
243
244 /// Remove a single outgoing edge from a source node to a target node.
245 ///
246 /// # Arguments
247 /// * `start` - The source node of the edge to remove
248 /// * `end` - The target node of the edge to remove
249 ///
250 /// # Returns
251 /// `true` if the edge existed and was removed, `false` otherwise (either the source node
252 /// does not exist, or the edge does not exist).
253 ///
254 /// # Examples
255 /// ```
256 /// use directed_graph::DirectedGraph;
257 /// let mut graph = DirectedGraph::new();
258 /// graph.add_node(1, vec![2, 3]);
259 /// assert!(graph.remove_edge(&1, &3));
260 /// assert!(!graph.remove_edge(&1, &4));
261 /// ```
262 pub fn remove_edge(&mut self, start: &N, end: &N) -> bool {
263 match self.adjacency_list.get_mut(start) {
264 Some(ends) => ends.shift_remove(end),
265 None => false,
266 }
267 }
268}
269
270#[cfg(test)]
271mod tests {
272 use std::hash::{Hash, Hasher};
273
274 use crate::DirectedGraph;
275
276 #[test]
277 fn test_string_graph() {
278 let mut digraph = DirectedGraph::new();
279 digraph.add_node("Alice", vec![]);
280 assert!(digraph.contains(&"Alice"));
281 digraph.add_node("Bob", vec!["Eve"]);
282 assert!(digraph.contains(&"Bob"));
283 assert!(!digraph.contains(&"Eve"));
284 digraph.add_node("Carl", vec!["Alice", "Bob"]);
285 assert!(digraph.contains(&"Carl"));
286 }
287
288 #[test]
289 fn test_integer_graph() {
290 let mut digraph = DirectedGraph::new();
291 digraph.add_node(1, vec![]);
292 assert!(digraph.contains(&1));
293 digraph.add_node(2, vec![3]);
294 assert!(digraph.contains(&2));
295 assert!(!digraph.contains(&3));
296 digraph.add_node(-3, vec![1, 2]);
297 assert!(digraph.contains(&-3));
298 }
299
300 #[test]
301 fn test_get_edges() {
302 let mut digraph = DirectedGraph::new();
303 digraph.add_node(1, vec![2, 3]);
304 let edges_of_1 = digraph.get_adjacent_nodes(&1);
305 assert!(edges_of_1.is_some());
306 let edges_of_1 = edges_of_1.unwrap();
307 assert!(edges_of_1.contains(&2));
308 assert!(edges_of_1.contains(&3));
309 digraph.add_node(11, vec![22]);
310 digraph.add_node(11, vec![33]);
311 let edges_of_11 = digraph.get_adjacent_nodes(&11);
312 assert!(edges_of_11.is_some());
313 let edges_of_11 = edges_of_11.unwrap();
314 assert!(edges_of_11.contains(&22));
315 assert!(edges_of_11.contains(&33));
316 }
317
318 #[test]
319 fn test_node_count() {
320 let mut digraph = DirectedGraph::new();
321 digraph.add_node(1, vec![2, 3]);
322 assert_eq!(digraph.node_count(), 1);
323 digraph.add_node(11, vec![22]);
324 digraph.add_node(11, vec![33]);
325 assert_eq!(digraph.node_count(), 2);
326 }
327
328 #[test]
329 fn test_edge_count() {
330 let mut digraph = DirectedGraph::new();
331 digraph.add_node(1, vec![2, 3]);
332 assert_eq!(digraph.edge_count(), 2);
333 digraph.add_node(11, vec![22]);
334 digraph.add_node(11, vec![33]);
335 assert_eq!(digraph.edge_count(), 4);
336 }
337
338 #[test]
339 fn test_remove_node() {
340 let mut digraph = DirectedGraph::new();
341 digraph.add_node(1, vec![2, 3]);
342 assert_eq!(digraph.remove_node(2), None);
343 let edges_of_1 = digraph.remove_node(1);
344 assert!(edges_of_1.is_some());
345 let edges_of_1 = edges_of_1.unwrap();
346 assert_eq!(edges_of_1.len(), 2);
347 assert!(edges_of_1.contains(&2));
348 assert!(edges_of_1.contains(&3));
349 }
350
351 #[test]
352 fn test_remove_edge() {
353 let mut digraph = DirectedGraph::new();
354 digraph.add_node(1, vec![2, 3]);
355 assert!(!digraph.remove_edge(&2, &3));
356 let edges_of_1 = digraph.get_adjacent_nodes(&1);
357 assert!(edges_of_1.is_some());
358 let edges_of_1 = edges_of_1.unwrap();
359 assert_eq!(edges_of_1.len(), 2);
360 assert!(edges_of_1.contains(&2));
361 assert!(edges_of_1.contains(&3));
362 assert!(digraph.remove_edge(&1, &3));
363 let edges_of_1 = digraph.get_adjacent_nodes(&1);
364 assert!(edges_of_1.is_some());
365 let edges_of_1 = edges_of_1.unwrap();
366 assert_eq!(edges_of_1.len(), 1);
367 assert!(edges_of_1.contains(&2));
368 assert!(!edges_of_1.contains(&3));
369 }
370
371 #[test]
372 fn test_custom_node() {
373 #[derive(Debug, Clone, Default)]
374 struct BigNode {
375 id: u64,
376 _desc: String,
377 _text: Vec<Vec<u32>>,
378 }
379 impl BigNode {
380 pub fn new(id: u64) -> Self {
381 BigNode {
382 id,
383 _desc: "some custom big node".to_owned(),
384 _text: vec![vec![8], vec![8], vec![4], vec![8]],
385 }
386 }
387 }
388 impl PartialEq for BigNode {
389 fn eq(&self, other: &Self) -> bool {
390 self.id == other.id
391 }
392 }
393 impl Eq for BigNode {}
394 impl Hash for BigNode {
395 fn hash<H: Hasher>(&self, state: &mut H) {
396 self.id.hash(state);
397 }
398 }
399 // Manual Ord: only compare id (ignore all other fields)
400 impl Ord for BigNode {
401 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
402 self.id.cmp(&other.id)
403 }
404 }
405 // Manual PartialOrd (required for Ord)
406 impl PartialOrd for BigNode {
407 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
408 // align with Ord
409 Some(self.cmp(other))
410 }
411 }
412 let mut digraph: DirectedGraph<BigNode> = DirectedGraph::new();
413 {
414 let node1 = BigNode::new(1);
415 let node2 = BigNode::new(2);
416 let node3 = BigNode::new(3);
417 digraph.add_node(node1.clone(), vec![node2, node3]);
418 let edges_of_1 = digraph.get_adjacent_nodes(&node1);
419 assert!(edges_of_1.is_some());
420 let edges_of_1 = edges_of_1.unwrap();
421 assert!(edges_of_1.contains(&BigNode::new(2)));
422 assert!(edges_of_1.contains(&BigNode::new(3)));
423 }
424 {
425 let node11 = BigNode::new(11);
426 let node22 = BigNode::new(22);
427 let node33 = BigNode::new(33);
428 digraph.add_node(node11.clone(), vec![node22, node33]);
429 let edges_of_11 = digraph.get_adjacent_nodes(&node11);
430 assert!(edges_of_11.is_some());
431 let edges_of_11 = edges_of_11.unwrap();
432 assert!(edges_of_11.contains(&BigNode::new(22)));
433 assert!(edges_of_11.contains(&BigNode::new(33)));
434 }
435 }
436}