kanban_core/graph/
core.rs

1use serde::{Deserialize, Serialize};
2use std::collections::HashMap;
3use uuid::Uuid;
4
5use super::algorithms;
6use super::edge::{Edge, EdgeDirection};
7use crate::KanbanResult;
8
9/// Generic graph structure that can hold any edge type E
10///
11/// Stores edges as an edge list for efficient serialization.
12/// Provides adjacency list views for graph algorithms.
13#[derive(Debug, Clone, Serialize, Deserialize)]
14pub struct Graph<E> {
15    edges: Vec<Edge<E>>,
16}
17
18impl<E> Default for Graph<E> {
19    fn default() -> Self {
20        Self { edges: Vec::new() }
21    }
22}
23
24impl<E> Graph<E> {
25    /// Create a new empty graph
26    pub fn new() -> Self {
27        Self { edges: Vec::new() }
28    }
29
30    /// Add an edge to the graph
31    ///
32    /// Note: Cycle checking must be done by caller if needed
33    /// (see `would_create_cycle` method)
34    pub fn add_edge(&mut self, edge: Edge<E>) -> KanbanResult<()> {
35        self.edges.push(edge);
36        Ok(())
37    }
38
39    /// Remove an edge between two nodes
40    ///
41    /// Returns true if an edge was removed, false if no matching edge found
42    pub fn remove_edge(&mut self, source: Uuid, target: Uuid) -> bool
43    where
44        E: Clone,
45    {
46        let initial_len = self.edges.len();
47        self.edges.retain(|e| !e.connects(source, target));
48        self.edges.len() < initial_len
49    }
50
51    /// Remove all edges involving a node (for deletion cascades)
52    pub fn remove_node(&mut self, node_id: Uuid) {
53        self.edges.retain(|e| !e.involves(node_id));
54    }
55
56    /// Archive all edges involving a node (for archive cascades)
57    pub fn archive_node(&mut self, node_id: Uuid) {
58        for edge in &mut self.edges {
59            if edge.involves(node_id) {
60                edge.archive();
61            }
62        }
63    }
64
65    /// Unarchive all edges involving a node (for unarchive cascades)
66    pub fn unarchive_node(&mut self, node_id: Uuid) {
67        for edge in &mut self.edges {
68            if edge.involves(node_id) {
69                edge.unarchive();
70            }
71        }
72    }
73
74    /// Get all outgoing edges from a node (where node is source)
75    pub fn outgoing(&self, node_id: Uuid) -> Vec<&Edge<E>> {
76        self.edges.iter().filter(|e| e.source == node_id).collect()
77    }
78
79    /// Get all incoming edges to a node (where node is target)
80    pub fn incoming(&self, node_id: Uuid) -> Vec<&Edge<E>> {
81        self.edges.iter().filter(|e| e.target == node_id).collect()
82    }
83
84    /// Get all active outgoing edges from a node
85    pub fn outgoing_active(&self, node_id: Uuid) -> Vec<&Edge<E>> {
86        self.edges
87            .iter()
88            .filter(|e| e.source == node_id && e.is_active())
89            .collect()
90    }
91
92    /// Get all active incoming edges to a node
93    pub fn incoming_active(&self, node_id: Uuid) -> Vec<&Edge<E>> {
94        self.edges
95            .iter()
96            .filter(|e| e.target == node_id && e.is_active())
97            .collect()
98    }
99
100    /// Get all neighbor node IDs (connected nodes, handling bidirectional edges)
101    pub fn neighbors(&self, node_id: Uuid) -> Vec<Uuid>
102    where
103        E: Clone,
104    {
105        let mut neighbors = Vec::new();
106
107        for edge in &self.edges {
108            if edge.source == node_id {
109                neighbors.push(edge.target);
110            } else if edge.target == node_id {
111                match edge.direction {
112                    EdgeDirection::Bidirectional => neighbors.push(edge.source),
113                    EdgeDirection::Directed => {}
114                }
115            }
116        }
117
118        neighbors
119    }
120
121    /// Get all active neighbor node IDs
122    pub fn neighbors_active(&self, node_id: Uuid) -> Vec<Uuid>
123    where
124        E: Clone,
125    {
126        let mut neighbors = Vec::new();
127
128        for edge in self.edges.iter().filter(|e| e.is_active()) {
129            if edge.source == node_id {
130                neighbors.push(edge.target);
131            } else if edge.target == node_id {
132                match edge.direction {
133                    EdgeDirection::Bidirectional => neighbors.push(edge.source),
134                    EdgeDirection::Directed => {}
135                }
136            }
137        }
138
139        neighbors
140    }
141
142    /// Build an adjacency list view of the graph (for algorithms)
143    /// Only includes active edges
144    pub fn adjacency_list(&self) -> HashMap<Uuid, Vec<Uuid>>
145    where
146        E: Clone,
147    {
148        let mut adj_list: HashMap<Uuid, Vec<Uuid>> = HashMap::new();
149
150        for edge in self.edges.iter().filter(|e| e.is_active()) {
151            adj_list.entry(edge.source).or_default().push(edge.target);
152
153            if edge.direction == EdgeDirection::Bidirectional {
154                adj_list.entry(edge.target).or_default().push(edge.source);
155            }
156        }
157
158        adj_list
159    }
160
161    /// Get all edges (for serialization/inspection)
162    pub fn edges(&self) -> &[Edge<E>] {
163        &self.edges
164    }
165
166    /// Get all active edges
167    pub fn active_edges(&self) -> Vec<&Edge<E>> {
168        self.edges.iter().filter(|e| e.is_active()).collect()
169    }
170
171    /// Check if an edge exists between two nodes
172    pub fn has_edge(&self, source: Uuid, target: Uuid) -> bool
173    where
174        E: Clone,
175    {
176        self.edges.iter().any(|e| e.connects(source, target))
177    }
178
179    /// Check if adding an edge would create a cycle
180    /// Only checks active edges
181    pub fn would_create_cycle(&self, source: Uuid, target: Uuid) -> bool
182    where
183        E: Clone,
184    {
185        let adj_list = self.adjacency_list();
186        algorithms::would_create_cycle(&adj_list, source, target)
187    }
188
189    /// Check if the graph contains any cycles
190    /// Only checks active edges
191    pub fn has_cycle(&self) -> bool
192    where
193        E: Clone,
194    {
195        let adj_list = self.adjacency_list();
196        algorithms::has_cycle(&adj_list)
197    }
198
199    /// Get all nodes reachable from a given node
200    /// Only considers active edges
201    pub fn reachable_from(&self, start: Uuid) -> std::collections::HashSet<Uuid>
202    where
203        E: Clone,
204    {
205        let adj_list = self.adjacency_list();
206        algorithms::reachable_from(&adj_list, start)
207    }
208
209    /// Get the count of edges (total, including archived)
210    pub fn edge_count(&self) -> usize {
211        self.edges.len()
212    }
213
214    /// Get the count of active edges
215    pub fn active_edge_count(&self) -> usize {
216        self.edges.iter().filter(|e| e.is_active()).count()
217    }
218}
219
220#[cfg(test)]
221mod tests {
222    use super::*;
223    use crate::graph::edge::EdgeDirection;
224
225    #[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
226    enum TestEdgeType {
227        TypeA,
228        TypeB,
229    }
230
231    #[test]
232    fn test_graph_creation() {
233        let graph: Graph<TestEdgeType> = Graph::new();
234        assert_eq!(graph.edge_count(), 0);
235    }
236
237    #[test]
238    fn test_add_edge() {
239        let mut graph = Graph::new();
240        let source = Uuid::new_v4();
241        let target = Uuid::new_v4();
242        let edge = Edge::new(source, target, TestEdgeType::TypeA, EdgeDirection::Directed);
243
244        graph.add_edge(edge).unwrap();
245        assert_eq!(graph.edge_count(), 1);
246        assert!(graph.has_edge(source, target));
247    }
248
249    #[test]
250    fn test_remove_edge() {
251        let mut graph = Graph::new();
252        let source = Uuid::new_v4();
253        let target = Uuid::new_v4();
254        let edge = Edge::new(source, target, TestEdgeType::TypeA, EdgeDirection::Directed);
255
256        graph.add_edge(edge).unwrap();
257        assert!(graph.remove_edge(source, target));
258        assert_eq!(graph.edge_count(), 0);
259        assert!(!graph.has_edge(source, target));
260    }
261
262    #[test]
263    fn test_remove_node() {
264        let mut graph = Graph::new();
265        let node_a = Uuid::new_v4();
266        let node_b = Uuid::new_v4();
267        let node_c = Uuid::new_v4();
268
269        graph
270            .add_edge(Edge::new(
271                node_a,
272                node_b,
273                TestEdgeType::TypeA,
274                EdgeDirection::Directed,
275            ))
276            .unwrap();
277        graph
278            .add_edge(Edge::new(
279                node_b,
280                node_c,
281                TestEdgeType::TypeA,
282                EdgeDirection::Directed,
283            ))
284            .unwrap();
285        graph
286            .add_edge(Edge::new(
287                node_c,
288                node_a,
289                TestEdgeType::TypeA,
290                EdgeDirection::Directed,
291            ))
292            .unwrap();
293
294        assert_eq!(graph.edge_count(), 3);
295
296        graph.remove_node(node_b);
297        assert_eq!(graph.edge_count(), 1);
298        assert!(graph.has_edge(node_c, node_a));
299        assert!(!graph.has_edge(node_a, node_b));
300        assert!(!graph.has_edge(node_b, node_c));
301    }
302
303    #[test]
304    fn test_archive_node() {
305        let mut graph = Graph::new();
306        let node_a = Uuid::new_v4();
307        let node_b = Uuid::new_v4();
308        let node_c = Uuid::new_v4();
309
310        graph
311            .add_edge(Edge::new(
312                node_a,
313                node_b,
314                TestEdgeType::TypeA,
315                EdgeDirection::Directed,
316            ))
317            .unwrap();
318        graph
319            .add_edge(Edge::new(
320                node_b,
321                node_c,
322                TestEdgeType::TypeA,
323                EdgeDirection::Directed,
324            ))
325            .unwrap();
326
327        assert_eq!(graph.active_edge_count(), 2);
328
329        graph.archive_node(node_b);
330        assert_eq!(graph.edge_count(), 2);
331        assert_eq!(graph.active_edge_count(), 0);
332    }
333
334    #[test]
335    fn test_unarchive_node() {
336        let mut graph = Graph::new();
337        let node_a = Uuid::new_v4();
338        let node_b = Uuid::new_v4();
339
340        graph
341            .add_edge(Edge::new(
342                node_a,
343                node_b,
344                TestEdgeType::TypeA,
345                EdgeDirection::Directed,
346            ))
347            .unwrap();
348        graph.archive_node(node_a);
349        assert_eq!(graph.active_edge_count(), 0);
350
351        graph.unarchive_node(node_a);
352        assert_eq!(graph.active_edge_count(), 1);
353    }
354
355    #[test]
356    fn test_outgoing_incoming() {
357        let mut graph = Graph::new();
358        let node_a = Uuid::new_v4();
359        let node_b = Uuid::new_v4();
360        let node_c = Uuid::new_v4();
361
362        graph
363            .add_edge(Edge::new(
364                node_a,
365                node_b,
366                TestEdgeType::TypeA,
367                EdgeDirection::Directed,
368            ))
369            .unwrap();
370        graph
371            .add_edge(Edge::new(
372                node_a,
373                node_c,
374                TestEdgeType::TypeA,
375                EdgeDirection::Directed,
376            ))
377            .unwrap();
378        graph
379            .add_edge(Edge::new(
380                node_c,
381                node_a,
382                TestEdgeType::TypeA,
383                EdgeDirection::Directed,
384            ))
385            .unwrap();
386
387        assert_eq!(graph.outgoing(node_a).len(), 2);
388        assert_eq!(graph.incoming(node_a).len(), 1);
389        assert_eq!(graph.outgoing(node_b).len(), 0);
390        assert_eq!(graph.incoming(node_b).len(), 1);
391    }
392
393    #[test]
394    fn test_neighbors_directed() {
395        let mut graph = Graph::new();
396        let node_a = Uuid::new_v4();
397        let node_b = Uuid::new_v4();
398        let node_c = Uuid::new_v4();
399
400        graph
401            .add_edge(Edge::new(
402                node_a,
403                node_b,
404                TestEdgeType::TypeA,
405                EdgeDirection::Directed,
406            ))
407            .unwrap();
408        graph
409            .add_edge(Edge::new(
410                node_a,
411                node_c,
412                TestEdgeType::TypeA,
413                EdgeDirection::Directed,
414            ))
415            .unwrap();
416
417        let neighbors = graph.neighbors(node_a);
418        assert_eq!(neighbors.len(), 2);
419        assert!(neighbors.contains(&node_b));
420        assert!(neighbors.contains(&node_c));
421
422        assert_eq!(graph.neighbors(node_b).len(), 0);
423    }
424
425    #[test]
426    fn test_neighbors_bidirectional() {
427        let mut graph = Graph::new();
428        let node_a = Uuid::new_v4();
429        let node_b = Uuid::new_v4();
430
431        graph
432            .add_edge(Edge::new(
433                node_a,
434                node_b,
435                TestEdgeType::TypeA,
436                EdgeDirection::Bidirectional,
437            ))
438            .unwrap();
439
440        let neighbors_a = graph.neighbors(node_a);
441        let neighbors_b = graph.neighbors(node_b);
442
443        assert_eq!(neighbors_a.len(), 1);
444        assert_eq!(neighbors_b.len(), 1);
445        assert!(neighbors_a.contains(&node_b));
446        assert!(neighbors_b.contains(&node_a));
447    }
448
449    #[test]
450    fn test_would_create_cycle() {
451        let mut graph = Graph::new();
452        let node_a = Uuid::new_v4();
453        let node_b = Uuid::new_v4();
454        let node_c = Uuid::new_v4();
455
456        graph
457            .add_edge(Edge::new(
458                node_a,
459                node_b,
460                TestEdgeType::TypeA,
461                EdgeDirection::Directed,
462            ))
463            .unwrap();
464        graph
465            .add_edge(Edge::new(
466                node_b,
467                node_c,
468                TestEdgeType::TypeA,
469                EdgeDirection::Directed,
470            ))
471            .unwrap();
472
473        // c -> a would create cycle: a -> b -> c -> a
474        assert!(graph.would_create_cycle(node_c, node_a));
475
476        // c -> b would also create cycle: b -> c -> b
477        assert!(graph.would_create_cycle(node_c, node_b));
478    }
479
480    #[test]
481    fn test_adjacency_list() {
482        let mut graph = Graph::new();
483        let node_a = Uuid::new_v4();
484        let node_b = Uuid::new_v4();
485        let node_c = Uuid::new_v4();
486
487        graph
488            .add_edge(Edge::new(
489                node_a,
490                node_b,
491                TestEdgeType::TypeA,
492                EdgeDirection::Directed,
493            ))
494            .unwrap();
495        graph
496            .add_edge(Edge::new(
497                node_b,
498                node_c,
499                TestEdgeType::TypeA,
500                EdgeDirection::Directed,
501            ))
502            .unwrap();
503
504        let adj_list = graph.adjacency_list();
505        assert_eq!(adj_list.len(), 2);
506        assert_eq!(adj_list.get(&node_a).unwrap().len(), 1);
507        assert_eq!(adj_list.get(&node_b).unwrap().len(), 1);
508    }
509}
kanban_core/graph/core.rs

kanban_core/graph/
core.rs
