bigraph/implementation/
node_bigraph_wrapper.rs

1use crate::interface::dynamic_bigraph::DynamicEdgeCentricBigraph;
2use crate::interface::dynamic_bigraph::DynamicNodeCentricBigraph;
3use crate::interface::{
4    dynamic_bigraph::DynamicBigraph,
5    static_bigraph::StaticBigraph,
6    static_bigraph::{
7        StaticBigraphFromDigraph, StaticEdgeCentricBigraph, StaticNodeCentricBigraph,
8    },
9    BidirectedData,
10};
11use std::collections::HashMap;
12use std::fmt::Debug;
13use std::hash::Hash;
14use traitgraph::index::{GraphIndex, OptionalGraphIndex};
15use traitgraph::interface::subgraph::SubgraphBase;
16use traitgraph::interface::{
17    DynamicGraph, Edge, GraphBase, ImmutableGraphContainer, MutableGraphContainer, NavigableGraph,
18    StaticGraph,
19};
20
21/// Represent arbitrary bigraphs with petgraph.
22pub type PetBigraph<NodeData, EdgeData> =
23    crate::implementation::node_bigraph_wrapper::NodeBigraphWrapper<
24        crate::traitgraph::implementation::petgraph_impl::PetGraph<NodeData, EdgeData>,
25    >;
26
27/// Wrapper for a static graph that adds a mirror node mapping function.
28///
29/// Bigraphs can be represented with this struct by creating their topology as normal directed graph where each binode is split into its two parts.
30/// The binode mapping function then associates the parts with each other.
31///
32/// ```rust
33/// use traitgraph::implementation::petgraph_impl::PetGraph;
34/// use bigraph::implementation::node_bigraph_wrapper::NodeBigraphWrapper;
35/// use bigraph::interface::static_bigraph::{StaticBigraph, StaticBigraphFromDigraph};
36/// use bigraph::traitgraph::interface::MutableGraphContainer;
37/// use bigraph::interface::BidirectedData;
38///
39/// #[derive(Clone, Eq, PartialEq, Hash, Debug)]
40/// struct NodeData(i32);
41/// impl BidirectedData for NodeData {
42///     fn mirror(&self) -> Self {
43///         Self(1000 - self.0)
44///     }
45/// }
46///
47/// let mut graph = PetGraph::new();
48/// let n1 = graph.add_node(NodeData(0));
49/// let n2 = graph.add_node(NodeData(1000));
50/// graph.add_edge(n1.clone(), n2.clone(), ());
51/// graph.add_edge(n2.clone(), n1.clone(), ());
52/// let bigraph = NodeBigraphWrapper::new(graph);
53/// debug_assert_eq!(Some(n2.clone()), bigraph.mirror_node(n1.clone()));
54/// debug_assert_eq!(Some(n1.clone()), bigraph.mirror_node(n2.clone()));
55/// ```
56#[derive(Debug, Clone)]
57pub struct NodeBigraphWrapper<Topology: GraphBase> {
58    /// The underlying topology of the bigraph.
59    pub topology: Topology,
60    binode_map: Vec<Topology::OptionalNodeIndex>,
61}
62
63impl<Topology: GraphBase> GraphBase for NodeBigraphWrapper<Topology> {
64    type NodeData = Topology::NodeData;
65    type EdgeData = Topology::EdgeData;
66    type OptionalNodeIndex = Topology::OptionalNodeIndex;
67    type OptionalEdgeIndex = Topology::OptionalEdgeIndex;
68    type NodeIndex = Topology::NodeIndex;
69    type EdgeIndex = Topology::EdgeIndex;
70}
71
72impl<Topology: GraphBase + ImmutableGraphContainer> NodeBigraphWrapper<Topology> {
73    /// Converts the given topology into a bigraph without any mapping.
74    /// This leaves the resulting type in a potentially illegal state.
75    pub fn new_unmapped(topology: Topology) -> Self {
76        let node_count = topology.node_count();
77        Self {
78            topology,
79            binode_map: vec![<Self as GraphBase>::OptionalNodeIndex::new_none(); node_count],
80        }
81    }
82}
83
84impl<Topology: StaticGraph> StaticBigraph for NodeBigraphWrapper<Topology> {
85    fn mirror_node(&self, node_id: Self::NodeIndex) -> Option<Self::NodeIndex> {
86        self.binode_map[node_id.as_usize()].into()
87    }
88}
89
90impl<Topology: StaticGraph> NodeBigraphWrapper<Topology>
91where
92    <Self as GraphBase>::NodeData: BidirectedData + Eq + Hash + Debug,
93{
94    fn new_internal(topology: Topology, checked: bool) -> Self {
95        //let mut data_map = HashMap::new();
96        let mut data_map: HashMap<<Self as GraphBase>::NodeData, <Self as GraphBase>::NodeIndex> =
97            HashMap::new();
98        let mut binode_map =
99            vec![<Self as GraphBase>::OptionalNodeIndex::new_none(); topology.node_count()];
100
101        for node_index in topology.node_indices() {
102            let node_data = topology.node_data(node_index);
103
104            if let Some(mirror_index) = data_map.get(node_data).cloned() {
105                //debug_assert_ne!(node_index, mirror_index);
106                debug_assert!(!binode_map[node_index.as_usize()].is_valid());
107                debug_assert!(!binode_map[mirror_index.as_usize()].is_valid());
108                debug_assert_eq!(node_data, &topology.node_data(mirror_index).mirror());
109                binode_map[node_index.as_usize()] = mirror_index.into();
110                binode_map[mirror_index.as_usize()] = node_index.into();
111                data_map.remove(node_data);
112            } else {
113                let mirror_data = node_data.mirror();
114                //debug_assert_ne!(&mirror_data, node_data);
115                debug_assert_eq!(None, data_map.insert(mirror_data, node_index));
116            }
117        }
118
119        if checked {
120            debug_assert!(data_map.is_empty());
121        } else {
122            for node_index in topology.node_indices() {
123                let node_data = topology.node_data(node_index);
124                debug_assert!(!data_map.contains_key(node_data));
125            }
126        }
127        Self {
128            topology,
129            binode_map,
130        }
131    }
132}
133
134impl<Topology: StaticGraph> StaticBigraphFromDigraph for NodeBigraphWrapper<Topology>
135where
136    <Self as GraphBase>::NodeData: BidirectedData + Eq + Hash + Debug,
137{
138    type Topology = Topology;
139
140    fn new(topology: Self::Topology) -> Self {
141        Self::new_internal(topology, true)
142    }
143
144    fn new_unchecked(topology: Self::Topology) -> Self {
145        Self::new_internal(topology, false)
146    }
147}
148
149impl<Topology: DynamicGraph> DynamicBigraph for NodeBigraphWrapper<Topology> {
150    fn set_mirror_nodes(&mut self, a: Self::NodeIndex, b: Self::NodeIndex) {
151        debug_assert!(self.contains_node_index(a));
152        debug_assert!(self.contains_node_index(b));
153        self.binode_map[a.as_usize()] = b.into();
154        self.binode_map[b.as_usize()] = a.into();
155    }
156}
157
158impl<Topology: ImmutableGraphContainer> ImmutableGraphContainer for NodeBigraphWrapper<Topology> {
159    type NodeIndices<'a>
160        = Topology::NodeIndices<'a>
161    where
162        Self: 'a;
163    type EdgeIndices<'a>
164        = Topology::EdgeIndices<'a>
165    where
166        Self: 'a;
167    type NodeIndicesCopied = Topology::NodeIndicesCopied;
168    type EdgeIndicesCopied = Topology::EdgeIndicesCopied;
169
170    fn node_indices(&self) -> Self::NodeIndices<'_> {
171        self.topology.node_indices()
172    }
173
174    fn edge_indices(&self) -> Self::EdgeIndices<'_> {
175        self.topology.edge_indices()
176    }
177
178    fn node_indices_copied(&self) -> Self::NodeIndicesCopied {
179        self.topology.node_indices_copied()
180    }
181
182    fn edge_indices_copied(&self) -> Self::EdgeIndicesCopied {
183        self.topology.edge_indices_copied()
184    }
185
186    fn contains_node_index(&self, node_index: Self::NodeIndex) -> bool {
187        self.topology.contains_node_index(node_index)
188    }
189
190    fn contains_edge_index(&self, edge_index: Self::EdgeIndex) -> bool {
191        self.topology.contains_edge_index(edge_index)
192    }
193
194    fn node_count(&self) -> usize {
195        self.topology.node_count()
196    }
197
198    fn edge_count(&self) -> usize {
199        self.topology.edge_count()
200    }
201
202    fn node_data(&self, node_id: Self::NodeIndex) -> &Self::NodeData {
203        self.topology.node_data(node_id)
204    }
205
206    fn edge_data(&self, edge_id: Self::EdgeIndex) -> &Self::EdgeData {
207        self.topology.edge_data(edge_id)
208    }
209
210    fn edge_endpoints(&self, edge_id: Self::EdgeIndex) -> Edge<Self::NodeIndex> {
211        self.topology.edge_endpoints(edge_id)
212    }
213}
214
215impl<Topology: MutableGraphContainer + StaticGraph> MutableGraphContainer
216    for NodeBigraphWrapper<Topology>
217{
218    fn node_data_mut(&mut self, node_id: Self::NodeIndex) -> &mut Self::NodeData {
219        self.topology.node_data_mut(node_id)
220    }
221
222    fn edge_data_mut(&mut self, edge_id: Self::EdgeIndex) -> &mut Self::EdgeData {
223        self.topology.edge_data_mut(edge_id)
224    }
225
226    fn add_node(&mut self, node_data: Self::NodeData) -> Self::NodeIndex {
227        self.binode_map.push(Self::OptionalNodeIndex::new_none());
228        self.topology.add_node(node_data)
229    }
230
231    fn add_edge(
232        &mut self,
233        from: Self::NodeIndex,
234        to: Self::NodeIndex,
235        edge_data: Self::EdgeData,
236    ) -> Self::EdgeIndex {
237        self.topology.add_edge(from, to, edge_data)
238    }
239
240    fn remove_node(&mut self, node_id: Self::NodeIndex) -> Option<Self::NodeData> {
241        if let Some(mirror_node_id) = self.mirror_node(node_id) {
242            self.binode_map[mirror_node_id.as_usize()] = Self::OptionalNodeIndex::new_none();
243        }
244
245        self.binode_map.remove(node_id.as_usize());
246        for mirror_node_id in &mut self.binode_map {
247            if let Some(mirror_node_usize) = mirror_node_id.as_usize() {
248                assert_ne!(mirror_node_usize, node_id.as_usize());
249                if mirror_node_usize > node_id.as_usize() {
250                    *mirror_node_id = (mirror_node_usize - 1).into();
251                }
252            }
253        }
254
255        self.topology.remove_node(node_id)
256    }
257
258    fn remove_nodes_sorted_slice(&mut self, node_ids: &[Self::NodeIndex]) {
259        debug_assert!(node_ids.windows(2).all(|w| w[0] < w[1]));
260        let mut decrement_map = Vec::new();
261        for (index, &node_id) in node_ids.iter().enumerate() {
262            // build map to decrement mirror nodes by the right amount
263            while decrement_map.len() < node_id.as_usize() {
264                decrement_map.push(index);
265            }
266
267            // remove mirror references of deleted nodes
268            if let Some(mirror_node_id) = self.mirror_node(node_id) {
269                self.binode_map[mirror_node_id.as_usize()] = Self::OptionalNodeIndex::new_none();
270            }
271        }
272
273        while decrement_map.len() < self.binode_map.len() {
274            decrement_map.push(node_ids.len());
275        }
276
277        // decrement mirror nodes to match new node indices
278        let mut index = 0;
279        for node_id in 0..self.binode_map.len() {
280            if let Some(remove_node_id) = node_ids.get(index) {
281                if remove_node_id.as_usize() == node_id {
282                    index += 1;
283                    continue;
284                }
285            }
286
287            let binode_id = self.binode_map[node_id]
288                .as_usize()
289                .map(|binode_id_usize| binode_id_usize - decrement_map[binode_id_usize])
290                .into();
291
292            self.binode_map[node_id - index] = binode_id;
293        }
294        self.binode_map.resize(
295            self.binode_map.len() - node_ids.len(),
296            Option::<usize>::None.into(),
297        );
298
299        self.topology.remove_nodes_sorted_slice(node_ids)
300    }
301
302    fn remove_edge(&mut self, edge_id: Self::EdgeIndex) -> Option<Self::EdgeData> {
303        self.topology.remove_edge(edge_id)
304    }
305
306    fn remove_edges_sorted(&mut self, edge_ids: &[Self::EdgeIndex]) {
307        self.topology.remove_edges_sorted(edge_ids)
308    }
309
310    fn clear(&mut self) {
311        self.topology.clear();
312        self.binode_map.clear();
313    }
314}
315
316impl<Topology: NavigableGraph> NavigableGraph for NodeBigraphWrapper<Topology> {
317    type OutNeighbors<'a>
318        = <Topology as NavigableGraph>::OutNeighbors<'a>
319    where
320        Self: 'a,
321        Topology: 'a;
322    type InNeighbors<'a>
323        = <Topology as NavigableGraph>::InNeighbors<'a>
324    where
325        Self: 'a,
326        Topology: 'a;
327    type EdgesBetween<'a>
328        = <Topology as NavigableGraph>::EdgesBetween<'a>
329    where
330        Self: 'a,
331        Topology: 'a;
332
333    fn out_neighbors(&self, node_id: Self::NodeIndex) -> Self::OutNeighbors<'_> {
334        self.topology.out_neighbors(node_id)
335    }
336
337    fn in_neighbors(&self, node_id: Self::NodeIndex) -> Self::InNeighbors<'_> {
338        self.topology.in_neighbors(node_id)
339    }
340
341    fn edges_between(
342        &self,
343        from_node_id: Self::NodeIndex,
344        to_node_id: Self::NodeIndex,
345    ) -> Self::EdgesBetween<'_> {
346        self.topology.edges_between(from_node_id, to_node_id)
347    }
348}
349
350impl<Topology: SubgraphBase> SubgraphBase for NodeBigraphWrapper<Topology> {
351    type RootGraph = Self;
352
353    fn root(&self) -> &Self::RootGraph {
354        self
355    }
356}
357
358impl<Topology: Default + GraphBase> Default for NodeBigraphWrapper<Topology> {
359    fn default() -> Self {
360        Self {
361            topology: Topology::default(),
362            binode_map: vec![],
363        }
364    }
365}
366
367impl<Topology: StaticGraph> StaticNodeCentricBigraph for NodeBigraphWrapper<Topology> {}
368
369impl<Topology: StaticGraph> StaticEdgeCentricBigraph for NodeBigraphWrapper<Topology> where
370    <Topology as GraphBase>::EdgeData: BidirectedData + Eq
371{
372}
373
374impl<Topology: DynamicGraph> DynamicNodeCentricBigraph for NodeBigraphWrapper<Topology>
375where
376    <Topology as GraphBase>::NodeData: BidirectedData,
377    <Topology as GraphBase>::EdgeData: Clone,
378{
379}
380
381impl<Topology: DynamicGraph> DynamicEdgeCentricBigraph for NodeBigraphWrapper<Topology> where
382    <Topology as GraphBase>::EdgeData: BidirectedData + Eq
383{
384}
385
386impl<Topology: GraphBase + PartialEq> PartialEq for NodeBigraphWrapper<Topology> {
387    fn eq(&self, other: &Self) -> bool {
388        self.topology == other.topology && self.binode_map == other.binode_map
389    }
390}
391
392impl<Topology: GraphBase + Eq> Eq for NodeBigraphWrapper<Topology> {}
393
394#[cfg(test)]
395mod tests {
396    use super::NodeBigraphWrapper;
397    use crate::interface::dynamic_bigraph::{DynamicBigraph, DynamicNodeCentricBigraph};
398    use crate::interface::static_bigraph::StaticEdgeCentricBigraph;
399    use crate::interface::{
400        static_bigraph::StaticBigraph, static_bigraph::StaticBigraphFromDigraph, BidirectedData,
401    };
402    use crate::traitgraph::interface::{ImmutableGraphContainer, MutableGraphContainer};
403    use traitgraph::implementation::petgraph_impl::PetGraph;
404    use traitgraph::index::OptionalGraphIndex;
405    use traitgraph::interface::NavigableGraph;
406
407    #[test]
408    fn test_bigraph_creation() {
409        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
410        struct NodeData(i32);
411        impl BidirectedData for NodeData {
412            fn mirror(&self) -> Self {
413                Self(if self.0 % 2 == 0 {
414                    self.0 + 1
415                } else {
416                    self.0 - 1
417                })
418            }
419        }
420
421        let mut graph = PetGraph::new();
422        let n1 = graph.add_node(NodeData(0));
423        let n2 = graph.add_node(NodeData(1));
424        let n3 = graph.add_node(NodeData(2));
425        let n4 = graph.add_node(NodeData(3));
426        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
427        let bigraph = NodeBigraphWrapper::new(graph);
428
429        debug_assert_eq!(Some(n2), bigraph.mirror_node(n1));
430        debug_assert_eq!(Some(n1), bigraph.mirror_node(n2));
431        debug_assert_eq!(Some(n4), bigraph.mirror_node(n3));
432        debug_assert_eq!(Some(n3), bigraph.mirror_node(n4));
433    }
434
435    #[test]
436    #[should_panic]
437    fn test_bigraph_creation_unmapped_node() {
438        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
439        struct NodeData(i32);
440        impl BidirectedData for NodeData {
441            fn mirror(&self) -> Self {
442                Self(if self.0 % 2 == 0 {
443                    self.0 + 1
444                } else {
445                    self.0 - 1
446                })
447            }
448        }
449
450        let mut graph = PetGraph::new();
451        let n1 = graph.add_node(NodeData(0));
452        let n2 = graph.add_node(NodeData(1));
453        graph.add_node(NodeData(2));
454        graph.add_node(NodeData(3));
455        graph.add_node(NodeData(4));
456        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
457        NodeBigraphWrapper::new(graph);
458    }
459
460    #[test]
461    #[should_panic]
462    fn test_bigraph_creation_wrongly_mapped_node() {
463        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
464        struct NodeData(i32);
465        impl BidirectedData for NodeData {
466            fn mirror(&self) -> Self {
467                Self(if self.0 == 4 {
468                    3
469                } else if self.0 % 2 == 0 {
470                    self.0 + 1
471                } else {
472                    self.0 - 1
473                })
474            }
475        }
476
477        let mut graph = PetGraph::new();
478        let n1 = graph.add_node(NodeData(0));
479        let n2 = graph.add_node(NodeData(1));
480        graph.add_node(NodeData(2));
481        graph.add_node(NodeData(3));
482        graph.add_node(NodeData(4));
483        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
484        NodeBigraphWrapper::new(graph);
485    }
486
487    #[test]
488    #[should_panic]
489    fn test_bigraph_creation_self_mapped_node_without_mirror() {
490        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
491        struct NodeData(i32);
492        impl BidirectedData for NodeData {
493            fn mirror(&self) -> Self {
494                Self(if self.0 == 4 {
495                    4
496                } else if self.0 % 2 == 0 {
497                    self.0 + 1
498                } else {
499                    self.0 - 1
500                })
501            }
502        }
503
504        let mut graph = PetGraph::new();
505        let n1 = graph.add_node(NodeData(0));
506        let n2 = graph.add_node(NodeData(1));
507        graph.add_node(NodeData(2));
508        graph.add_node(NodeData(3));
509        graph.add_node(NodeData(4));
510        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
511        NodeBigraphWrapper::new(graph);
512    }
513
514    #[test]
515    #[should_panic]
516    fn test_bigraph_creation_self_mapped_node_with_mirror() {
517        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
518        struct NodeData(i32);
519        impl BidirectedData for NodeData {
520            fn mirror(&self) -> Self {
521                Self(if self.0 == 4 {
522                    4
523                } else if self.0 % 2 == 0 {
524                    self.0 + 1
525                } else {
526                    self.0 - 1
527                })
528            }
529        }
530
531        let mut graph = PetGraph::new();
532        let n1 = graph.add_node(NodeData(0));
533        let n2 = graph.add_node(NodeData(1));
534        graph.add_node(NodeData(2));
535        graph.add_node(NodeData(3));
536        graph.add_node(NodeData(4));
537        graph.add_node(NodeData(5));
538        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
539        NodeBigraphWrapper::new(graph);
540    }
541
542    #[test]
543    fn test_bigraph_unchecked_creation() {
544        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
545        struct NodeData(i32);
546        impl BidirectedData for NodeData {
547            fn mirror(&self) -> Self {
548                Self(if self.0 % 2 == 0 {
549                    self.0 + 1
550                } else {
551                    self.0 - 1
552                })
553            }
554        }
555
556        let mut graph = PetGraph::new();
557        let n1 = graph.add_node(NodeData(0));
558        let n2 = graph.add_node(NodeData(1));
559        let n3 = graph.add_node(NodeData(2));
560        let n4 = graph.add_node(NodeData(3));
561        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
562        let bigraph = NodeBigraphWrapper::new_unchecked(graph);
563
564        debug_assert_eq!(Some(n2), bigraph.mirror_node(n1));
565        debug_assert_eq!(Some(n1), bigraph.mirror_node(n2));
566        debug_assert_eq!(Some(n4), bigraph.mirror_node(n3));
567        debug_assert_eq!(Some(n3), bigraph.mirror_node(n4));
568    }
569
570    #[test]
571    fn test_bigraph_unchecked_creation_unmapped_node() {
572        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
573        struct NodeData(i32);
574        impl BidirectedData for NodeData {
575            fn mirror(&self) -> Self {
576                Self(if self.0 % 2 == 0 {
577                    self.0 + 1
578                } else {
579                    self.0 - 1
580                })
581            }
582        }
583
584        let mut graph = PetGraph::new();
585        let n1 = graph.add_node(NodeData(0));
586        let n2 = graph.add_node(NodeData(1));
587        let n3 = graph.add_node(NodeData(2));
588        let n4 = graph.add_node(NodeData(3));
589        let n5 = graph.add_node(NodeData(4));
590        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
591        let bigraph = NodeBigraphWrapper::new_unchecked(graph);
592
593        debug_assert_eq!(Some(n2), bigraph.mirror_node(n1));
594        debug_assert_eq!(Some(n1), bigraph.mirror_node(n2));
595        debug_assert_eq!(Some(n4), bigraph.mirror_node(n3));
596        debug_assert_eq!(Some(n3), bigraph.mirror_node(n4));
597        debug_assert_eq!(None, bigraph.mirror_node(n5));
598    }
599
600    #[test]
601    #[should_panic]
602    fn test_bigraph_unchecked_creation_wrongly_mapped_node_at_end() {
603        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
604        struct NodeData(i32);
605        impl BidirectedData for NodeData {
606            fn mirror(&self) -> Self {
607                Self(if self.0 == 4 {
608                    3
609                } else if self.0 % 2 == 0 {
610                    self.0 + 1
611                } else {
612                    self.0 - 1
613                })
614            }
615        }
616
617        let mut graph = PetGraph::new();
618        let n1 = graph.add_node(NodeData(0));
619        let n2 = graph.add_node(NodeData(1));
620        graph.add_node(NodeData(2));
621        graph.add_node(NodeData(3));
622        graph.add_node(NodeData(4));
623        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
624        NodeBigraphWrapper::new_unchecked(graph);
625    }
626
627    #[test]
628    #[should_panic]
629    fn test_bigraph_unchecked_creation_wrongly_mapped_node_at_beginning() {
630        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
631        struct NodeData(i32);
632        impl BidirectedData for NodeData {
633            fn mirror(&self) -> Self {
634                Self(if self.0 == 4 {
635                    3
636                } else if self.0 % 2 == 0 {
637                    self.0 + 1
638                } else {
639                    self.0 - 1
640                })
641            }
642        }
643
644        let mut graph = PetGraph::new();
645        graph.add_node(NodeData(4));
646        let n1 = graph.add_node(NodeData(0));
647        let n2 = graph.add_node(NodeData(1));
648        graph.add_node(NodeData(2));
649        graph.add_node(NodeData(3));
650        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
651        NodeBigraphWrapper::new_unchecked(graph);
652    }
653
654    #[test]
655    #[should_panic]
656    fn test_bigraph_unchecked_creation_self_mapped_node_without_mirror() {
657        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
658        struct NodeData(i32);
659        impl BidirectedData for NodeData {
660            fn mirror(&self) -> Self {
661                Self(if self.0 == 4 {
662                    4
663                } else if self.0 % 2 == 0 {
664                    self.0 + 1
665                } else {
666                    self.0 - 1
667                })
668            }
669        }
670
671        let mut graph = PetGraph::new();
672        let n1 = graph.add_node(NodeData(0));
673        let n2 = graph.add_node(NodeData(1));
674        graph.add_node(NodeData(2));
675        graph.add_node(NodeData(3));
676        graph.add_node(NodeData(4));
677        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
678        NodeBigraphWrapper::new_unchecked(graph);
679    }
680
681    #[test]
682    #[should_panic]
683    fn test_bigraph_unchecked_creation_self_mapped_node_with_mirror() {
684        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
685        struct NodeData(i32);
686        impl BidirectedData for NodeData {
687            fn mirror(&self) -> Self {
688                Self(if self.0 == 4 {
689                    4
690                } else if self.0 % 2 == 0 {
691                    self.0 + 1
692                } else {
693                    self.0 - 1
694                })
695            }
696        }
697
698        let mut graph = PetGraph::new();
699        let n1 = graph.add_node(NodeData(0));
700        let n2 = graph.add_node(NodeData(1));
701        graph.add_node(NodeData(2));
702        graph.add_node(NodeData(3));
703        graph.add_node(NodeData(4));
704        graph.add_node(NodeData(5));
705        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
706        NodeBigraphWrapper::new_unchecked(graph);
707    }
708
709    #[test]
710    fn test_bigraph_verification() {
711        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
712        struct NodeData(i32);
713        impl BidirectedData for NodeData {
714            fn mirror(&self) -> Self {
715                Self(if self.0 % 2 == 0 {
716                    self.0 + 1
717                } else {
718                    self.0 - 1
719                })
720            }
721        }
722
723        let mut graph = PetGraph::new();
724        let n1 = graph.add_node(NodeData(0));
725        let n2 = graph.add_node(NodeData(1));
726        graph.add_node(NodeData(2));
727        graph.add_node(NodeData(3));
728        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
729        let bigraph = NodeBigraphWrapper::new(graph);
730        debug_assert!(bigraph.verify_node_pairing_without_self_mirrors());
731        debug_assert!(bigraph.verify_node_pairing());
732    }
733
734    #[test]
735    fn test_bigraph_verification_self_mapped_node() {
736        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
737        struct NodeData(i32);
738        impl BidirectedData for NodeData {
739            fn mirror(&self) -> Self {
740                Self(if self.0 % 2 == 0 {
741                    self.0 + 1
742                } else {
743                    self.0 - 1
744                })
745            }
746        }
747
748        let mut graph = PetGraph::new();
749        let n1 = graph.add_node(NodeData(0));
750        let n2 = graph.add_node(NodeData(1));
751        graph.add_node(NodeData(2));
752        graph.add_node(NodeData(3));
753        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
754        let mut bigraph = NodeBigraphWrapper::new(graph);
755        bigraph.topology.add_node(NodeData(4));
756        bigraph.binode_map.push(4usize.into());
757        debug_assert!(!bigraph.verify_node_pairing_without_self_mirrors());
758        debug_assert!(bigraph.verify_node_pairing());
759    }
760
761    #[test]
762    fn test_bigraph_verification_self_unmapped_node() {
763        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
764        struct NodeData(i32);
765        impl BidirectedData for NodeData {
766            fn mirror(&self) -> Self {
767                Self(if self.0 % 2 == 0 {
768                    self.0 + 1
769                } else {
770                    self.0 - 1
771                })
772            }
773        }
774
775        let mut graph = PetGraph::new();
776        let n1 = graph.add_node(NodeData(0));
777        let n2 = graph.add_node(NodeData(1));
778        graph.add_node(NodeData(2));
779        graph.add_node(NodeData(3));
780        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
781        let mut bigraph = NodeBigraphWrapper::new(graph);
782        bigraph.topology.add_node(NodeData(4));
783        bigraph.binode_map.push(OptionalGraphIndex::new_none());
784        debug_assert!(!bigraph.verify_node_pairing_without_self_mirrors());
785        debug_assert!(!bigraph.verify_node_pairing());
786    }
787
788    #[test]
789    fn test_bigraph_verification_wrongly_mapped_node() {
790        #[derive(Clone, Eq, PartialEq, Hash, Debug)]
791        struct NodeData(i32);
792        impl BidirectedData for NodeData {
793            fn mirror(&self) -> Self {
794                Self(if self.0 % 2 == 0 {
795                    self.0 + 1
796                } else {
797                    self.0 - 1
798                })
799            }
800        }
801
802        let mut graph = PetGraph::new();
803        let n1 = graph.add_node(NodeData(0));
804        let n2 = graph.add_node(NodeData(1));
805        graph.add_node(NodeData(2));
806        graph.add_node(NodeData(3));
807        graph.add_edge(n1, n2, ()); // Just to fix the EdgeData type parameter
808        let mut bigraph = NodeBigraphWrapper::new(graph);
809        bigraph.topology.add_node(NodeData(4));
810        bigraph.binode_map.push(3usize.into());
811        debug_assert!(!bigraph.verify_node_pairing_without_self_mirrors());
812        debug_assert!(!bigraph.verify_node_pairing());
813    }
814
815    #[test]
816    fn test_bigraph_add_mirror_nodes() {
817        #[derive(Eq, PartialEq, Debug, Hash, Clone)]
818        struct NodeData(u32);
819        impl BidirectedData for NodeData {
820            fn mirror(&self) -> Self {
821                Self(1000 - self.0)
822            }
823        }
824
825        let mut graph = PetGraph::new();
826        let n0 = graph.add_node(NodeData(0));
827        let n1 = graph.add_node(NodeData(1));
828        graph.add_node(NodeData(2));
829        graph.add_node(NodeData(3));
830        graph.add_node(NodeData(997));
831        graph.add_edge(n0, n1, ());
832        let mut graph = NodeBigraphWrapper::new_unchecked(graph);
833        debug_assert!(!graph.verify_node_pairing());
834        graph.add_mirror_nodes();
835        debug_assert!(graph.verify_node_pairing());
836        debug_assert_eq!(graph.node_count(), 8);
837    }
838
839    #[test]
840    fn test_bigraph_remove_node() {
841        #[derive(Eq, PartialEq, Debug, Hash, Clone)]
842        struct NodeData(u32);
843        impl BidirectedData for NodeData {
844            fn mirror(&self) -> Self {
845                Self(1000 - self.0)
846            }
847        }
848
849        let mut graph = NodeBigraphWrapper::new(PetGraph::new());
850        let n0 = graph.add_node(NodeData(0));
851        let n1 = graph.add_node(NodeData(1000));
852        graph.set_mirror_nodes(n0, n1);
853        let n2 = graph.add_node(NodeData(1));
854        let n3 = graph.add_node(NodeData(999));
855        graph.set_mirror_nodes(n2, n3);
856        let _e0 = graph.add_edge(n0, n2, ());
857        let _e1 = graph.add_edge(n3, n1, ());
858
859        assert!(graph.verify_node_pairing());
860        assert!(graph.verify_edge_mirror_property());
861
862        graph.remove_node(n0);
863
864        assert_eq!(graph.edge_count(), 1);
865        assert_eq!(graph.mirror_node(n0), None);
866        assert_eq!(graph.mirror_node(n1), Some(n2));
867        assert_eq!(graph.mirror_node(n2), Some(n1));
868
869        graph.remove_node(n0);
870
871        assert!(graph.verify_node_pairing());
872        assert!(graph.verify_edge_mirror_property());
873        assert_eq!(graph.edge_count(), 0);
874        assert_eq!(graph.mirror_node(n0), Some(n1));
875        assert_eq!(graph.mirror_node(n1), Some(n0));
876    }
877
878    #[test]
879    fn test_bigraph_remove_nodes() {
880        #[derive(Eq, PartialEq, Debug, Hash, Clone)]
881        struct NodeData(u32);
882        impl BidirectedData for NodeData {
883            fn mirror(&self) -> Self {
884                Self(1000 - self.0)
885            }
886        }
887
888        let mut graph = NodeBigraphWrapper::new(PetGraph::new());
889        for i in 0..100 {
890            graph.add_node(NodeData(i));
891        }
892        graph.add_mirror_nodes();
893
894        fn random(n: usize) -> usize {
895            // hopefully results in a distribution of edges that covers all possible edge cases
896            n.wrapping_mul(31)
897                .wrapping_add(n.wrapping_mul(97))
898                .wrapping_add(n / 31)
899                .wrapping_add(n / 97)
900                .wrapping_add(n)
901                .wrapping_add(n.count_zeros() as usize)
902        }
903
904        let mut n = 0;
905        while graph.edge_count() < 250 {
906            let n1 = (n % graph.node_count()).into();
907            n = random(n);
908            let n2 = (n % graph.node_count()).into();
909            n = random(n);
910
911            if !graph.contains_edge_between(n1, n2) {
912                graph.add_edge(n1, n2, ());
913            }
914        }
915        graph.add_node_centric_mirror_edges();
916
917        let mut g1 = graph.clone();
918        let mut g2 = graph.clone();
919        let remove: Vec<_> = [
920            0, 1, 2, 5, 7, 24, 35, 36, 37, 38, 39, 40, 77, 88, 99, 100, 101, 102, 133, 134, 135,
921            136, 188, 199,
922        ]
923        .into_iter()
924        .map(Into::into)
925        .collect();
926        g1.remove_nodes_sorted_slice(&remove);
927        for n in remove.into_iter().rev() {
928            g2.remove_node(n);
929        }
930        assert!(g1.eq(&g2), "g1: {:?}\ng2: {:?}", g1, g2);
931
932        let mut g1 = graph.clone();
933        let mut g2 = graph.clone();
934        let remove: Vec<_> = [
935            2, 5, 7, 24, 35, 36, 37, 38, 39, 40, 77, 88, 99, 100, 101, 102,
936        ]
937        .into_iter()
938        .map(Into::into)
939        .collect();
940        g1.remove_nodes_sorted_slice(&remove);
941        for n in remove.into_iter().rev() {
942            g2.remove_node(n);
943        }
944        assert!(g1.eq(&g2), "g1: {:?}\ng2: {:?}", g1, g2);
945    }
946}
bigraph/implementation/node_bigraph_wrapper.rs

bigraph/implementation/
node_bigraph_wrapper.rs
