jstd/graph/
owning.rs

1use std::{
2    collections::{HashMap, HashSet},
3    fmt::Debug,
4    hash::RandomState,
5    ops::{Deref, DerefMut},
6};
7
8use crate::{
9    graph::{
10        Graph, GraphMut,
11        edge::{Edge, EdgeMut},
12        node::{Node, NodeMut},
13    },
14    registry::Identifier,
15};
16
17#[derive(Default, Clone)]
18pub(crate) struct RawNode<EdgeId: Identifier> {
19    pub edges: HashSet<EdgeId>,
20}
21
22#[derive(Clone)]
23pub(crate) struct RawEdge<NodeId: Identifier> {
24    pub from: NodeId,
25    pub to: NodeId,
26}
27
28impl<NodeId: Identifier + Debug> Debug for RawEdge<NodeId> {
29    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
30        f.debug_struct("RawEdge")
31            .field("from", &self.from)
32            .field("to", &self.to)
33            .finish()
34    }
35}
36
37pub struct NodeRef<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> {
38    pub id: NodeId,
39    graph: &'graph OwningGraph<NodeId, EdgeId, NodeData, EdgeData>,
40}
41
42impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData>
43    NodeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
44{
45    fn inner(&self) -> &'graph RawNode<EdgeId> {
46        &self.graph.nodes[&self.id]
47    }
48
49    pub fn data(&self) -> &'graph NodeData {
50        &self.graph.node_data[&self.id]
51    }
52}
53
54impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Node<'graph>
55    for NodeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
56{
57    type Graph = OwningGraph<NodeId, EdgeId, NodeData, EdgeData>;
58
59    fn new(id: NodeId, graph: &'graph Self::Graph) -> Self {
60        NodeRef { id, graph }
61    }
62
63    fn id(&self) -> NodeId {
64        self.id
65    }
66
67    fn graph(&self) -> &'graph Self::Graph {
68        self.graph
69    }
70
71    fn edge_ids(&self) -> &'graph HashSet<EdgeId, RandomState> {
72        &self.inner().edges
73    }
74
75    fn edge_count(&self) -> usize {
76        self.inner().edges.len()
77    }
78}
79
80impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Deref
81    for NodeRef<'_, NodeId, EdgeId, NodeData, EdgeData>
82{
83    type Target = NodeData;
84
85    fn deref(&self) -> &Self::Target {
86        self.data()
87    }
88}
89
90pub struct NodeMutRef<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> {
91    pub id: NodeId,
92    graph: &'graph mut OwningGraph<NodeId, EdgeId, NodeData, EdgeData>,
93}
94
95impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData>
96    NodeMutRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
97{
98    pub fn data(&mut self) -> &mut NodeData {
99        self.graph.node_data.get_mut(&self.id).unwrap()
100    }
101}
102
103impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> NodeMut<'graph>
104    for NodeMutRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
105{
106    type Graph = OwningGraph<NodeId, EdgeId, NodeData, EdgeData>;
107
108    fn new(id: NodeId, graph: &'graph mut Self::Graph) -> Self {
109        NodeMutRef { id, graph }
110    }
111
112    fn id(&self) -> NodeId {
113        self.id
114    }
115
116    fn graph(&mut self) -> &mut Self::Graph {
117        self.graph
118    }
119
120    fn edge_ids(&self) -> &HashSet<EdgeId, RandomState> {
121        &self.graph.nodes.get(&self.id).unwrap().edges
122    }
123
124    fn edge_count(&self) -> usize {
125        self.graph.nodes.get(&self.id).unwrap().edges.len()
126    }
127
128    fn add_edge_id(&mut self, edge: EdgeId) {
129        self.graph
130            .nodes
131            .get_mut(&self.id)
132            .unwrap()
133            .edges
134            .insert(edge);
135    }
136
137    fn remove_edge_id(&mut self, edge: EdgeId) {
138        self.graph
139            .nodes
140            .get_mut(&self.id)
141            .unwrap()
142            .edges
143            .remove(&edge);
144    }
145}
146
147impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Deref
148    for NodeMutRef<'_, NodeId, EdgeId, NodeData, EdgeData>
149{
150    type Target = NodeData;
151
152    fn deref(&self) -> &Self::Target {
153        self.graph.node_data.get(&self.id).unwrap()
154    }
155}
156
157impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> DerefMut
158    for NodeMutRef<'_, NodeId, EdgeId, NodeData, EdgeData>
159{
160    fn deref_mut(&mut self) -> &mut Self::Target {
161        self.graph.node_data.get_mut(&self.id).unwrap()
162    }
163}
164
165pub struct EdgeRef<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> {
166    pub id: EdgeId,
167    graph: &'graph OwningGraph<NodeId, EdgeId, NodeData, EdgeData>,
168}
169
170impl<'graph, EdgeId: Identifier + Debug, NodeId: Identifier + Debug, NodeData, EdgeData> Debug
171    for EdgeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
172{
173    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
174        f.debug_struct("Edge")
175            .field("id", &self.id)
176            .field("raw", self.inner())
177            .finish()
178    }
179}
180
181impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData>
182    EdgeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
183{
184    fn inner(&self) -> &RawEdge<NodeId> {
185        &self.graph.edges[&self.id]
186    }
187
188    pub fn data(&self) -> &EdgeData {
189        &self.graph.edge_data[&self.id]
190    }
191}
192
193impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Edge<'graph>
194    for EdgeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
195{
196    type Graph = OwningGraph<NodeId, EdgeId, NodeData, EdgeData>;
197
198    fn new(id: EdgeId, graph: &'graph Self::Graph) -> Self {
199        EdgeRef { id, graph }
200    }
201
202    fn id(&self) -> EdgeId {
203        self.id
204    }
205
206    fn graph(&self) -> &'graph Self::Graph {
207        self.graph
208    }
209
210    fn from_id(&self) -> NodeId {
211        self.inner().from
212    }
213
214    fn to_id(&self) -> NodeId {
215        self.inner().to
216    }
217}
218
219impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Deref
220    for EdgeRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
221{
222    type Target = EdgeData;
223
224    fn deref(&self) -> &Self::Target {
225        self.data()
226    }
227}
228
229pub struct EdgeMutRef<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> {
230    pub id: EdgeId,
231    graph: &'graph mut OwningGraph<NodeId, EdgeId, NodeData, EdgeData>,
232}
233
234impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData>
235    EdgeMutRef<'_, NodeId, EdgeId, NodeData, EdgeData>
236{
237    pub fn data(&mut self) -> &mut EdgeData {
238        self.graph.edge_data.get_mut(&self.id).unwrap()
239    }
240}
241
242impl<'graph, NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> EdgeMut<'graph>
243    for EdgeMutRef<'graph, NodeId, EdgeId, NodeData, EdgeData>
244{
245    type Graph = OwningGraph<NodeId, EdgeId, NodeData, EdgeData>;
246
247    fn new(id: <Self::Graph as Graph>::EdgeId, graph: &'graph mut Self::Graph) -> Self {
248        EdgeMutRef { id, graph }
249    }
250
251    fn id(&self) -> <Self::Graph as Graph>::EdgeId {
252        self.id
253    }
254
255    fn graph(&mut self) -> &mut Self::Graph {
256        self.graph
257    }
258
259    fn from_id(&self) -> <Self::Graph as Graph>::NodeId {
260        self.graph.get_edge(self.id).unwrap().from_id()
261    }
262
263    fn to_id(&self) -> <Self::Graph as Graph>::NodeId {
264        self.graph.get_edge(self.id).unwrap().to_id()
265    }
266
267    fn set_from(&mut self, node: <Self::Graph as Graph>::NodeId) {
268        self.graph.edges.get_mut(&self.id).unwrap().from = node;
269    }
270}
271
272impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Deref
273    for EdgeMutRef<'_, NodeId, EdgeId, NodeData, EdgeData>
274{
275    type Target = EdgeData;
276
277    fn deref(&self) -> &Self::Target {
278        &self.graph.edge_data[&self.id]
279    }
280}
281
282impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> DerefMut
283    for EdgeMutRef<'_, NodeId, EdgeId, NodeData, EdgeData>
284{
285    fn deref_mut(&mut self) -> &mut Self::Target {
286        self.graph.edge_data.get_mut(&self.id).unwrap()
287    }
288}
289
290/// An example Graph implementation with `usize` identifiers and simple payloads, used in tests.
291pub struct OwningGraph<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> {
292    node_data: HashMap<NodeId, NodeData>,
293    edge_data: HashMap<EdgeId, EdgeData>,
294
295    nodes: HashMap<NodeId, RawNode<EdgeId>>,
296    edges: HashMap<EdgeId, RawEdge<NodeId>>,
297
298    next_node_id: usize,
299    next_edge_id: usize,
300}
301
302impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Default
303    for OwningGraph<NodeId, EdgeId, NodeData, EdgeData>
304{
305    fn default() -> Self {
306        Self {
307            node_data: HashMap::new(),
308            edge_data: HashMap::new(),
309            nodes: HashMap::new(),
310            edges: HashMap::new(),
311            next_node_id: 0,
312            next_edge_id: 0,
313        }
314    }
315}
316
317impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> Graph
318    for OwningGraph<NodeId, EdgeId, NodeData, EdgeData>
319{
320    type NodeId = NodeId;
321    type EdgeId = EdgeId;
322
323    // The generic demo/test graph keeps the std default hasher; consumers that
324    // need deterministic edge iteration (e.g. qcode's `Context`) pick a
325    // fixed-seed hasher via their own `Graph::Hasher`.
326    type Hasher = RandomState;
327
328    type Node<'a>
329        = NodeRef<'a, NodeId, EdgeId, NodeData, EdgeData>
330    where
331        Self: 'a;
332
333    type Edge<'a>
334        = EdgeRef<'a, NodeId, EdgeId, NodeData, EdgeData>
335    where
336        Self: 'a;
337
338    fn get_node(&self, id: Self::NodeId) -> Option<Self::Node<'_>> {
339        if self.node_data.contains_key(&id) {
340            Some(NodeRef { id, graph: self })
341        } else {
342            None
343        }
344    }
345
346    fn get_edge(&self, id: Self::EdgeId) -> Option<Self::Edge<'_>> {
347        if self.edge_data.contains_key(&id) {
348            Some(EdgeRef { id, graph: self })
349        } else {
350            None
351        }
352    }
353
354    fn nodes(&self) -> impl Iterator<Item = Self::Node<'_>> + '_ {
355        self.node_data.keys().map(|id| self.get_node(*id).unwrap())
356    }
357
358    fn edges(&self) -> impl Iterator<Item = Self::Edge<'_>> + '_ {
359        self.edge_data.keys().map(|id| self.get_edge(*id).unwrap())
360    }
361}
362
363impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData> GraphMut
364    for OwningGraph<NodeId, EdgeId, NodeData, EdgeData>
365{
366    type NodeMut<'a>
367        = NodeMutRef<'a, NodeId, EdgeId, NodeData, EdgeData>
368    where
369        Self: 'a;
370
371    type EdgeMut<'a>
372        = EdgeMutRef<'a, NodeId, EdgeId, NodeData, EdgeData>
373    where
374        Self: 'a;
375
376    fn get_node_mut(&mut self, id: Self::NodeId) -> Option<Self::NodeMut<'_>> {
377        if self.node_data.contains_key(&id) {
378            Some(NodeMutRef { id, graph: self })
379        } else {
380            None
381        }
382    }
383
384    fn get_edge_mut(&mut self, id: Self::EdgeId) -> Option<Self::EdgeMut<'_>> {
385        if self.edge_data.contains_key(&id) {
386            Some(EdgeMutRef { id, graph: self })
387        } else {
388            None
389        }
390    }
391}
392
393impl<NodeId: Identifier, EdgeId: Identifier, NodeData, EdgeData>
394    OwningGraph<NodeId, EdgeId, NodeData, EdgeData>
395{
396    /// Creates a new node
397    /// Creates a new node with payload `data` and returns its identifier.
398    pub fn make_node(&mut self, data: NodeData) -> NodeId {
399        let id = NodeId::from(self.next_node_id);
400        self.next_node_id += 1;
401        self.nodes.insert(
402            id,
403            RawNode {
404                edges: HashSet::new(),
405            },
406        );
407        self.node_data.insert(id, data);
408        id
409    }
410
411    /// Creates a new edge from `from` to `to` with payload `data`.
412    ///
413    /// # Panics
414    /// Panics if either endpoint does not exist.
415    pub fn make_edge(&mut self, from: NodeId, to: NodeId, data: EdgeData) -> EdgeId {
416        let id = EdgeId::from(self.next_edge_id);
417        self.next_edge_id += 1;
418        self.edges.insert(id, RawEdge { from, to });
419        self.edge_data.insert(id, data);
420        self.nodes.get_mut(&from).unwrap().edges.insert(id);
421        self.nodes.get_mut(&to).unwrap().edges.insert(id);
422        id
423    }
424
425    /// Removes an edge by identifier.
426    ///
427    /// # Panics
428    /// Panics if the edge does not exist.
429    pub fn remove_edge(&mut self, id: EdgeId) {
430        let edge = self.edges.remove(&id).unwrap();
431        self.edge_data.remove(&id);
432
433        self.nodes.get_mut(&edge.from).unwrap().edges.remove(&id);
434
435        self.nodes.get_mut(&edge.to).unwrap().edges.remove(&id);
436    }
437
438    /// Edits an edge's endpoints
439    pub fn edit_edge(&mut self, id: EdgeId, new_from: NodeId, new_to: NodeId) {
440        let edge = self.edges.get_mut(&id).unwrap();
441
442        // Remove from old endpoints
443        self.nodes.get_mut(&edge.from).unwrap().edges.remove(&id);
444        self.nodes.get_mut(&edge.to).unwrap().edges.remove(&id);
445
446        // Update edge endpoints
447        edge.from = new_from;
448        edge.to = new_to;
449
450        // Add to new endpoints
451        self.nodes.get_mut(&new_from).unwrap().edges.insert(id);
452        self.nodes.get_mut(&new_to).unwrap().edges.insert(id);
453    }
454
455    /// Removes a node and all of its incident edges.
456    ///
457    /// # Panics
458    /// Panics if the node does not exist.
459    pub fn remove_node(&mut self, id: NodeId) {
460        // Remove edges while the node is still present: `remove_edge` updates
461        // both endpoint incident-edge sets, including this node's.
462        let edges: Vec<EdgeId> = self.nodes[&id].edges.iter().copied().collect();
463        for edge_id in edges {
464            self.remove_edge(edge_id);
465        }
466        self.nodes.remove(&id).unwrap();
467        self.node_data.remove(&id);
468    }
469
470    /// Returns an iterator over the immediate successor blocks —
471    /// blocks that this block may transfer control to.
472    pub fn reinterpret<NewNodeData, NewEdgeData, Fn, Fe>(
473        &self,
474        mut node_data_map: Fn,
475        mut edge_data_map: Fe,
476    ) -> OwningGraph<NodeId, EdgeId, NewNodeData, NewEdgeData>
477    where
478        Fn: FnMut(&NodeData) -> NewNodeData,
479        Fe: FnMut(&EdgeData) -> NewEdgeData,
480    {
481        OwningGraph {
482            node_data: self
483                .node_data
484                .iter()
485                .map(|(id, data)| (*id, node_data_map(data)))
486                .collect(),
487            edge_data: self
488                .edge_data
489                .iter()
490                .map(|(id, data)| (*id, edge_data_map(data)))
491                .collect(),
492            nodes: self.nodes.clone(),
493            edges: self.edges.clone(),
494            next_node_id: self.next_node_id,
495            next_edge_id: self.next_edge_id,
496        }
497    }
498}
499
500#[cfg(test)]
501mod tests {
502    use std::collections::HashSet;
503
504    use crate::{
505        graph::{
506            Graph, GraphMut,
507            edge::{Edge, EdgeMut},
508            node::{Node, NodeMut},
509            owning::OwningGraph,
510        },
511        registry::Identifier,
512    };
513
514    #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
515    struct TestNodeId(usize);
516
517    impl From<usize> for TestNodeId {
518        fn from(value: usize) -> Self {
519            Self(value)
520        }
521    }
522
523    impl From<TestNodeId> for usize {
524        fn from(value: TestNodeId) -> Self {
525            value.0
526        }
527    }
528
529    impl Identifier for TestNodeId {}
530
531    #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
532    struct TestEdgeId(usize);
533
534    impl From<usize> for TestEdgeId {
535        fn from(value: usize) -> Self {
536            Self(value)
537        }
538    }
539
540    impl From<TestEdgeId> for usize {
541        fn from(value: TestEdgeId) -> Self {
542            value.0
543        }
544    }
545
546    impl Identifier for TestEdgeId {}
547
548    type TestGraph = OwningGraph<TestNodeId, TestEdgeId, &'static str, i32>;
549
550    #[test]
551    fn editor_creates_nodes_edges_and_root() {
552        let mut graph = TestGraph::default();
553
554        let (root_id, child_id, edge_id) = {
555            let root_id = graph.make_node("root");
556            let child_id = graph.make_node("child");
557            let edge_id = graph.make_edge(root_id, child_id, 7);
558            (root_id, child_id, edge_id)
559        };
560
561        let root = graph.get_node(root_id).unwrap();
562        assert_eq!(root.id(), root_id);
563        assert_eq!(*root.data(), "root");
564
565        let child = graph.get_node(child_id).unwrap();
566        assert_eq!(*child.data(), "child");
567        assert!(child.parents().any(|item| item.node_id() == root_id));
568
569        let edge = graph.get_edge(edge_id).unwrap();
570        assert_eq!(edge.id(), edge_id);
571        assert_eq!(edge.from().id(), root_id);
572        assert_eq!(edge.to().id(), child_id);
573        assert_eq!(*edge.data(), 7);
574        assert!(!edge.is_loop());
575    }
576
577    #[test]
578    fn node_and_edge_iterators_cover_all_items() {
579        let mut graph = TestGraph::default();
580
581        {
582            let a = graph.make_node("a");
583            let b = graph.make_node("b");
584            let c = graph.make_node("c");
585            graph.make_edge(a, b, 1);
586            graph.make_edge(b, c, 2);
587        }
588
589        let node_values: HashSet<_> = graph.nodes().map(|node| *node.data()).collect();
590        let edge_values: HashSet<_> = graph.edges().map(|edge| *edge.data()).collect();
591
592        assert_eq!(node_values, HashSet::from(["a", "b", "c"]));
593        assert_eq!(edge_values, HashSet::from([1, 2]));
594    }
595
596    #[test]
597    fn mutable_handles_can_update_payloads() {
598        let mut graph = TestGraph::default();
599
600        let (node_id, edge_id) = {
601            let n0 = graph.make_node("initial");
602            let n1 = graph.make_node("other");
603            let e0 = graph.make_edge(n0, n1, 10);
604            (n0, e0)
605        };
606
607        *graph.get_node_mut(node_id).unwrap().data() = "updated";
608        *graph.get_edge_mut(edge_id).unwrap().data() = 99;
609
610        assert_eq!(*graph.get_node(node_id).unwrap().data(), "updated");
611        assert_eq!(*graph.get_edge(edge_id).unwrap().data(), 99);
612    }
613
614    #[test]
615    fn remove_edge_updates_connected_nodes() {
616        let mut graph = TestGraph::default();
617
618        let (a, b, edge_id) = {
619            let a = graph.make_node("a");
620            let b = graph.make_node("b");
621            let edge_id = graph.make_edge(a, b, 3);
622            (a, b, edge_id)
623        };
624
625        assert_eq!(graph.get_node(a).unwrap().edge_count(), 1);
626        assert_eq!(graph.get_node(b).unwrap().edge_count(), 1);
627
628        graph.remove_edge(edge_id);
629
630        assert_eq!(graph.get_node(a).unwrap().edge_count(), 0);
631        assert_eq!(graph.get_node(b).unwrap().edge_count(), 0);
632        assert_eq!(graph.edges().count(), 0);
633    }
634
635    #[test]
636    fn make_edge_does_not_overwrite_existing_after_remove() {
637        let mut graph = TestGraph::default();
638
639        let (a, b, c, d) = {
640            let a = graph.make_node("a");
641            let b = graph.make_node("b");
642            let c = graph.make_node("c");
643            let d = graph.make_node("d");
644            (a, b, c, d)
645        };
646
647        let e0 = graph.make_edge(a, b, 10);
648        let _e1 = graph.make_edge(b, c, 20);
649
650        graph.remove_edge(e0);
651
652        let _e2 = graph.make_edge(c, d, 30);
653
654        let edge_values: HashSet<_> = graph.edges().map(|edge| *edge.data()).collect();
655        assert_eq!(edge_values, HashSet::from([20, 30]));
656        assert_eq!(graph.edges().count(), 2);
657    }
658
659    #[test]
660    fn merge_nodes_rehomes_outgoing_edges_to_keep() {
661        // A -e0-> B -e1-> C
662        // merge_nodes(keep=A, remove=B, direct=e0)
663        // Expected: A -e1-> C, B has no edges, e0 is gone from both
664        let mut graph = TestGraph::default();
665
666        let (a, b, c) = {
667            let a = graph.make_node("a");
668            let b = graph.make_node("b");
669            let c = graph.make_node("c");
670            (a, b, c)
671        };
672        let e0 = graph.make_edge(a, b, 1);
673        let e1 = graph.make_edge(b, c, 2);
674
675        graph.merge_nodes(a, b, e0);
676
677        // e0 removed from A and B
678        assert!(!graph.get_node(a).unwrap().edge_ids().contains(&e0));
679        assert!(!graph.get_node(b).unwrap().edge_ids().contains(&e0));
680
681        // e1 rehomed: now originates from A
682        assert_eq!(graph.get_edge(e1).unwrap().from_id(), a);
683        assert!(graph.get_node(a).unwrap().edge_ids().contains(&e1));
684        assert!(!graph.get_node(b).unwrap().edge_ids().contains(&e1));
685
686        // B has no incident edges
687        assert_eq!(graph.get_node(b).unwrap().edge_count(), 0);
688
689        // A has exactly one outgoing edge (e1) to C
690        let a_children: Vec<_> = graph.get_node(a).unwrap().children().collect();
691        assert_eq!(a_children.len(), 1);
692        assert_eq!(a_children[0].node_id(), c);
693        assert_eq!(a_children[0].edge_id(), e1);
694    }
695
696    #[test]
697    fn merge_nodes_handles_multiple_outgoing_edges_on_removed_node() {
698        // A -e0-> B, B -e1-> C, B -e2-> D
699        // merge_nodes(keep=A, remove=B, direct=e0)
700        // Expected: A -e1-> C, A -e2-> D, B has no edges
701        let mut graph = TestGraph::default();
702
703        let (a, b, c, d) = {
704            let a = graph.make_node("a");
705            let b = graph.make_node("b");
706            let c = graph.make_node("c");
707            let d = graph.make_node("d");
708            (a, b, c, d)
709        };
710        let e0 = graph.make_edge(a, b, 10);
711        let e1 = graph.make_edge(b, c, 20);
712        let e2 = graph.make_edge(b, d, 30);
713
714        graph.merge_nodes(a, b, e0);
715
716        assert_eq!(graph.get_node(b).unwrap().edge_count(), 0);
717
718        let a_successors: HashSet<_> = graph
719            .get_node(a)
720            .unwrap()
721            .children()
722            .map(|item| item.node_id())
723            .collect();
724        assert_eq!(a_successors, HashSet::from([c, d]));
725
726        assert_eq!(graph.get_edge(e1).unwrap().from_id(), a);
727        assert_eq!(graph.get_edge(e2).unwrap().from_id(), a);
728    }
729
730    #[test]
731    fn merge_nodes_on_tail_node_leaves_keep_with_no_outgoing_edges() {
732        // A -e0-> B (B has no outgoing edges — it is a tail)
733        // merge_nodes(keep=A, remove=B, direct=e0)
734        // Expected: A has no outgoing edges, B has no incident edges
735        let mut graph = TestGraph::default();
736
737        let (a, b) = {
738            let a = graph.make_node("a");
739            let b = graph.make_node("b");
740            (a, b)
741        };
742        let e0 = graph.make_edge(a, b, 1);
743
744        graph.merge_nodes(a, b, e0);
745
746        assert_eq!(graph.get_node(a).unwrap().children().count(), 0);
747        assert_eq!(graph.get_node(b).unwrap().edge_count(), 0);
748    }
749
750    #[test]
751    fn merge_nodes_does_not_touch_incoming_edges_of_keep() {
752        // P -ep-> A -e0-> B -e1-> C
753        // merge_nodes(keep=A, remove=B, direct=e0)
754        // Expected: P -ep-> A -e1-> C (ep still points to A)
755        let mut graph = TestGraph::default();
756
757        let (p, a, b, c) = {
758            let p = graph.make_node("p");
759            let a = graph.make_node("a");
760            let b = graph.make_node("b");
761            let c = graph.make_node("c");
762            (p, a, b, c)
763        };
764        let ep = graph.make_edge(p, a, 0);
765        let e0 = graph.make_edge(a, b, 1);
766        graph.make_edge(b, c, 2);
767
768        graph.merge_nodes(a, b, e0);
769
770        // ep unchanged: still from P to A
771        assert_eq!(graph.get_edge(ep).unwrap().from_id(), p);
772        assert_eq!(graph.get_edge(ep).unwrap().to_id(), a);
773        assert!(graph.get_node(a).unwrap().edge_ids().contains(&ep));
774
775        // A now has ep (incoming) and e1 (outgoing)
776        assert_eq!(graph.get_node(a).unwrap().edge_count(), 2);
777    }
778
779    #[test]
780    fn directed_dfs_visits_reachable_nodes() {
781        let mut graph = TestGraph::default();
782
783        let (root, b, c, isolated) = {
784            let root = graph.make_node("root");
785            let b = graph.make_node("b");
786            let c = graph.make_node("c");
787            let isolated = graph.make_node("isolated");
788
789            graph.make_edge(root, b, 1);
790            graph.make_edge(b, c, 2);
791
792            (root, b, c, isolated)
793        };
794
795        let mut seen = HashSet::new();
796        let mut root_count = 0;
797
798        for (edge, node) in graph.dfs(root) {
799            if node.id() == root {
800                root_count += 1;
801                assert!(edge.is_none());
802            }
803            seen.insert(node.id());
804        }
805
806        assert_eq!(root_count, 1);
807        assert!(seen.contains(&root));
808        assert!(seen.contains(&b));
809        assert!(seen.contains(&c));
810        assert!(!seen.contains(&isolated));
811    }
812
813    #[test]
814    fn undirected_dfs_can_reach_incoming_neighbors() {
815        let mut graph = TestGraph::default();
816
817        let (root, parent) = {
818            let root = graph.make_node("root");
819            let parent = graph.make_node("parent");
820
821            graph.make_edge(parent, root, 5);
822
823            (root, parent)
824        };
825
826        let directed_seen: HashSet<_> = graph.dfs(root).map(|(_, node)| node.id()).collect();
827
828        let undirected_seen: HashSet<_> = graph
829            .undirected_dfs(root)
830            .map(|(_, node)| node.id())
831            .collect();
832
833        assert!(directed_seen.contains(&root));
834        assert!(!directed_seen.contains(&parent));
835        assert!(undirected_seen.contains(&root));
836        assert!(undirected_seen.contains(&parent));
837    }
838
839    #[test]
840    fn trait_views_traverse_and_mutate_edges_without_losing_connectivity() {
841        let mut graph = TestGraph::default();
842        let a = graph.make_node("a");
843        let b = graph.make_node("b");
844        let loop_node = graph.make_node("loop");
845        let edge = graph.make_edge(a, b, 1);
846        let loop_edge = graph.make_edge(loop_node, loop_node, 2);
847
848        let a_ref = graph.get_node(a).unwrap();
849        assert!(!a_ref.is_leaf());
850        assert_eq!(a_ref.edges().count(), 1);
851        let step = a_ref.children().next().unwrap();
852        assert_eq!(step.edge().id(), edge);
853        assert_eq!(step.node().id(), b);
854        assert!(graph.get_edge(loop_edge).unwrap().is_loop());
855
856        {
857            let mut a_mut = graph.get_node_mut(a).unwrap();
858            assert_eq!(a_mut.edge_count(), 1);
859            a_mut.remove_edge_id(edge);
860            assert!(a_mut.as_ref().is_leaf());
861            a_mut.add_edge_id(edge);
862            assert_eq!(a_mut.as_ref().edge_count(), 1);
863        }
864
865        {
866            let mut edge_mut = graph.get_edge_mut(edge).unwrap();
867            assert_eq!(edge_mut.as_ref().to_id(), b);
868            assert_eq!(edge_mut.from().id(), a);
869            assert_eq!(edge_mut.to().id(), b);
870            *edge_mut.data() = 9;
871            edge_mut.set_from(a);
872        }
873        assert_eq!(*graph.get_edge(edge).unwrap().data(), 9);
874    }
875
876    #[test]
877    fn editing_reinterpreting_and_removing_nodes_preserves_graph_invariants() {
878        let mut graph = TestGraph::default();
879        let a = graph.make_node("a");
880        let b = graph.make_node("b");
881        let c = graph.make_node("c");
882        let edge = graph.make_edge(a, b, 4);
883
884        graph.edit_edge(edge, b, c);
885        let edited = graph.get_edge(edge).unwrap();
886        assert_eq!(edited.from_id(), b);
887        assert_eq!(edited.to_id(), c);
888        assert_eq!(graph.get_node(a).unwrap().edge_count(), 0);
889        assert_eq!(graph.get_node(b).unwrap().edge_count(), 1);
890        assert_eq!(graph.get_node(c).unwrap().edge_count(), 1);
891
892        let reinterpreted = graph.reinterpret(|node| node.len(), |edge| edge * 10);
893        assert_eq!(*reinterpreted.get_node(a).unwrap().data(), 1);
894        assert_eq!(*reinterpreted.get_edge(edge).unwrap().data(), 40);
895
896        graph.remove_node(b);
897        assert!(graph.get_node(b).is_none());
898        assert!(graph.get_edge(edge).is_none());
899        assert_eq!(graph.get_node(c).unwrap().edge_count(), 0);
900    }
901}
jstd/graph/owning.rs

jstd/graph/
owning.rs
