bit_gossip/prim.rs
1//! graph implementations using primitive data types.
2//!
3//! If you know the maximum number of nodes is less than or equal to 16, 32, 64, or 128, use the corresponding graph type.
4//! If you think the number of nodes will exceed 128, use the general [Graph](crate::graph::Graph) implementation.
5//!
6//! Computing paths with these is over 3x faster than using the general [Graph](crate::graph::Graph) implementation.
7//! See [Benchmarks](https://github.com/PoOnesNerfect/bit_gossip#benchmarks) for more details.
8//!
9//! <br>
10//!
11//! **Panics** in debug mode if the number of nodes exceeds the maximum number of nodes for the graph type.
12//!
13//! In release mode, it will saturate at the maximum number of nodes.
14//!
15//! # Example
16//!
17//! ## Basic Usage
18//!
19//! ```sh
20//! 0 -- 1 -- 2 -- 3
21//! | | |
22//! 4 -- 5 -- 6 -- 7
23//! | | |
24//! 8 -- 9 -- 10 - 11
25//! ```
26//!
27//! ```
28//! use bit_gossip::Graph16;
29//!
30//! // Initialize a builder with 12 nodes
31//! let mut builder = Graph16::builder(12);
32//!
33//! // Connect the nodes
34//! for i in 0..12u8 {
35//! if i % 4 != 3 {
36//! builder.connect(i, i + 1);
37//! }
38//! if i < 8 {
39//! builder.connect(i, i + 4);
40//! }
41//! }
42//! builder.disconnect(1, 5);
43//! builder.disconnect(5, 9);
44//!
45//! // Build the graph
46//! let graph = builder.build();
47//!
48//! // Check the shortest path from 0 to 9
49//! assert_eq!(graph.neighbor_to(0, 9), Some(4));
50//! assert_eq!(graph.neighbor_to(4, 9), Some(8));
51//! assert_eq!(graph.neighbor_to(8, 9), Some(9));
52//!
53//! // Both 1 and 4 can reach 11 in the shortest path.
54//! assert_eq!(graph.neighbors_to(0, 11).collect::<Vec<_>>(), vec![1, 4]);
55//!
56//! // Get the path from 0 to 5
57//! assert_eq!(graph.path_to(0, 5).collect::<Vec<_>>(), vec![0, 4, 5]);
58//! ```
59//!
60//! ## Do not exceed the maximum number of nodes for the graph type.
61//!
62//! ```should_panic
63//! use bit_gossip::Graph16;
64//!
65//! // This will panic in debug mode,
66//! // and saturate at 16 in release mode
67//! let mut builder = Graph16::builder(17);
68//! ```
69
70use crate::edge_id;
71use paste::paste;
72use std::{collections::HashMap, fmt::Debug};
73
74// macros were about 2x faster than using generics
75macro_rules! impl_prim {
76 ($node_bits:ty, $node_id:ty, $num:expr) => {
77 paste! {
78 #[doc = "Graph implementation using `" $node_bits "` as the node bits storage."]
79 ///
80 #[doc = "Number of nodes must be equal or lower than " $num "."]
81 ///
82 /// <br>
83 ///
84 /// **panics** in debug mode if given number of nodes exceeds
85 #[doc = $num "."]
86 ///
87 /// In release mode, it will saturate at the maximum number of nodes.
88 #[derive(Debug, Clone)]
89 pub struct [< Graph $num >] {
90 pub nodes: [<Nodes $num>],
91 pub edges: HashMap<($node_id, $node_id), $node_bits>,
92 }
93
94 impl [< Graph $num >] {
95 #[doc = "Create a new Graph" $num " with the given number of nodes."]
96 ///
97 #[doc = "Number of nodes must be equal or lower than " $num "."]
98 ///
99 /// <br>
100 ///
101 /// **panics** in debug mode if given number of nodes exceeds
102 #[doc = $num "."]
103 ///
104 /// In release mode, it will saturate at the maximum number of nodes.
105 pub fn builder(nodes_len: usize) -> [<Graph $num Builder>] {
106 debug_assert!(nodes_len <= $num, "Number of nodes must be equal or lower than {}", $num);
107
108 [<Graph $num Builder>]::new(nodes_len.min($num))
109 }
110
111 /// Converts this graph into a builder.
112 ///
113 /// This is useful if you want to update the graph,
114 /// like resizing nodes or adding/removing edges.
115 ///
116 /// Then you can build the graph again.
117 pub fn into_builder(self) -> [<Graph $num Builder>] {
118 [<Graph $num Builder>] {
119 nodes: self.nodes,
120 edge_masks: [<Edges $num>] { inner: self.edges.iter().map(|(k, _)| (*k, 0)).collect() },
121 edges: [<Edges $num>] { inner: self.edges },
122 }
123 }
124
125 /// Given a current node and a destination node,
126 /// return the first neighboring node that is the shortest path to the destination node.
127 ///
128 /// This operation is very fast as all paths for all nodes are precomputed.
129 ///
130 /// `None` is returned when:
131 /// - `curr` and `dest` are the same node
132 /// - `curr` has no path to `dest`
133 ///
134 /// **Note:** In case there are multiple neighboring nodes that lead to the destination node,
135 /// the first one found will be returned. The same node will be returned for the same input.
136 /// However, the order of the nodes is not guaranteed.
137 ///
138 /// You can use [neighbor_to_with](Self::neighbor_to_with) to filter matching neighbors,
139 /// or [neighbors_to](Self::neighbors_to) to get all neighboring nodes.
140 #[inline]
141 pub fn neighbor_to(&self, curr: $node_id, dest: $node_id) -> Option<$node_id> {
142 self.neighbors_to(curr, dest).next()
143 }
144
145 /// Given a current node and a destination node, and a filter function,
146 /// return the neighboring node of current that is the shortest path to the destination node.
147 ///
148 /// Same as `self.neighbors_to(curr, dest).find(f)`
149 ///
150 /// This may be useful if you want some custom behavior when choosing the next node.
151 ///
152 /// **Ex)** In a game, you might want to randomize which path to take when there are multiple shortest paths.
153 ///
154 /// `None` is returned when:
155 /// - `curr` and `dest` are the same node
156 /// - `curr` has no path to `dest`
157 /// - The filter function returns `false` for all neighboring nodes
158 #[inline]
159 pub fn neighbor_to_with(
160 &self,
161 curr: $node_id,
162 dest: $node_id,
163 f: impl Fn($node_id) -> bool,
164 ) -> Option<$node_id> {
165 self.neighbors_to(curr, dest).find(|&n| f(n))
166 }
167
168 /// Given a current node and a destination node,
169 /// return all neighboring nodes of current that are shortest paths to the destination node.
170 ///
171 /// The nodes will be returned in the same order for the same inputs. However, the ordering of the nodes is not guaranteed.
172 #[inline]
173 pub fn neighbors_to(&self, curr: $node_id, dest: $node_id) -> [<NextNodesIter $num>]<'_> {
174 [<NextNodesIter $num>] {
175 graph: self,
176 neighbors: self.nodes.neighbors(curr),
177 curr,
178 dest,
179 }
180 }
181
182 /// Given a current node and a destination node,
183 /// return a path from the current node to the destination node.
184 ///
185 /// The path is a list of node IDs, starting with current node and ending at the destination node.
186 ///
187 /// This is same as calling `.neighbor_to` repeatedly until the destination node is reached.
188 ///
189 /// If there is no path, the list will be empty.
190 #[inline]
191 pub fn path_to(&self, curr: $node_id, dest: $node_id) -> [<PathIter $num>]<'_> {
192 [<PathIter $num>] {
193 map: self,
194 curr,
195 dest,
196 init: false,
197 }
198 }
199
200 /// Check if there is a path from the current node to the destination node.
201 #[inline]
202 pub fn path_exists(&self, curr: $node_id, dest: $node_id) -> bool {
203 self.neighbor_to(curr, dest).is_some()
204 }
205
206 /// Return a list of all neighboring nodes of the given node.
207 #[inline]
208 pub fn neighbors(&self, node: $node_id) -> impl Iterator<Item = $node_id> + '_ {
209 self.nodes.neighbors(node)
210 }
211
212 /// Return the number of nodes in this graph.
213 #[inline]
214 pub fn nodes_len(&self) -> usize {
215 self.nodes.len()
216 }
217
218 /// Return the number of edges in this graph.
219 #[inline]
220 pub fn edges_len(&self) -> usize {
221 self.edges.len()
222 }
223 }
224
225 /// Iterator that returns a path from the current node to the destination node.
226 #[derive(Debug)]
227 pub struct [<PathIter $num>]<'a> {
228 map: &'a [<Graph $num>],
229 curr: $node_id,
230 dest: $node_id,
231 init: bool,
232 }
233
234 impl Iterator for [<PathIter $num>]<'_> {
235 type Item = $node_id;
236
237 fn next(&mut self) -> Option<Self::Item> {
238 if !self.init {
239 self.init = true;
240 return Some(self.curr);
241 }
242
243 let Some(next) = self.map.neighbor_to(self.curr, self.dest) else {
244 return None;
245 };
246
247 self.curr = next;
248
249 Some(next)
250 }
251 }
252
253 /// Iterator that iterates neighboring nodes which are the shortest paths to the destination node.
254 #[derive(Debug)]
255 pub struct [<NextNodesIter $num>]<'a> {
256 graph: &'a [<Graph $num>],
257 curr: $node_id,
258 dest: $node_id,
259 neighbors: [<NodeBits $num Iter>],
260 }
261
262 impl Iterator for [<NextNodesIter $num>]<'_> {
263 type Item = $node_id;
264
265 fn next(&mut self) -> Option<Self::Item> {
266 if self.curr == self.dest {
267 return None;
268 }
269
270 while let Some(neighbor) = self.neighbors.next() {
271 let bit = self.graph.edges.get(&edge_id(self.curr, neighbor))? & 1 << self.dest > 0;
272 let bit = if self.curr > neighbor { !bit } else { bit };
273
274 if bit {
275 return Some(neighbor);
276 }
277 }
278
279 None
280 }
281 }
282
283 #[doc = "Builder for [Graph" $num "]"]
284 #[derive(Debug, Clone)]
285 pub struct [<Graph $num Builder>] {
286 pub nodes: [<Nodes $num>],
287
288 /// key: edge_id
289 /// value: for each bit, if this edge is the shortest path
290 /// to that bit location's node, bit is set to 1
291 pub edges: [<Edges $num>],
292
293 /// key: edge_id
294 /// value: for each edge, bit is set to 1 if the node is computed for this edge
295 pub edge_masks: [<Edges $num>],
296 }
297
298 impl [<Graph $num Builder>] {
299 #[doc = "Create a new [Graph" $num "] with the given number of nodes."]
300 ///
301 #[doc = "Number of nodes must be equal or lower than " $num "."]
302 ///
303 /// <br>
304 ///
305 /// **panics** in debug mode if given number of nodes exceeds
306 #[doc = $num "."]
307 ///
308 /// In release mode, it will saturate at the maximum number of nodes.
309 pub fn new(nodes_len: usize) -> Self {
310 Self {
311 nodes: [<Nodes $num>]::new(nodes_len),
312 edges: [<Edges $num>]::new(),
313 edge_masks: [<Edges $num>]::new(),
314 }
315 }
316
317 /// Resize the graph to the given number of nodes.
318 ///
319 /// All edges that are connected to nodes that are removed will also be removed.
320 pub fn resize(&mut self, new_len: u8) {
321 let should_truncate = new_len < self.nodes.len() as u8;
322
323 self.nodes.resize(new_len as usize);
324
325 if should_truncate {
326 self.edges.truncate(new_len);
327 self.edge_masks.truncate(new_len);
328 }
329 }
330
331 /// Add a edge between node_a and node_b
332 pub fn connect(&mut self, a: $node_id, b: $node_id) {
333 // if the edge already exists, return
334 if !self.nodes.connect(a, b) {
335 return;
336 }
337
338 let a_bit = 1 << a;
339 let b_bit = 1 << b;
340
341 let mut val = b_bit;
342
343 // edge value is flipped to b -> a, which means from node b's perspective, this edge is:
344 // - gets further away from b
345 // - shortest path to a
346 // - gets further away from all other nodes
347 if a > b {
348 val = a_bit;
349 }
350
351 let ab = edge_id(a, b);
352
353 self.edges.insert(ab, val);
354 self.edge_masks.insert(ab, a_bit | b_bit);
355 }
356
357 /// Remove edge between node_a and node_b
358 pub fn disconnect(&mut self, a: $node_id, b: $node_id) {
359 // if the edge doesn't exist, return
360 if self.nodes.disconnect(a, b) {
361 return;
362 }
363
364 let ab = edge_id(a, b);
365
366 if self.edges.inner.remove(&ab).is_some() {
367 self.edge_masks.inner.remove(&ab);
368 }
369 }
370
371 /// Build the graph.
372 ///
373 /// Consumes the builder, processes all shortest paths for all nodes,
374 #[doc = "and returns [Graph" $num "]."]
375 pub fn build(self) -> [< Graph $num >] {
376 let Self {
377 nodes,
378 mut edges,
379 mut edge_masks,
380 } = self;
381
382 // (neighbors at current depth, neighbors at previous depths)
383 let mut neighbors_at_depth: Vec<($node_bits, $node_bits)> =
384 nodes.inner.iter().enumerate().map(|(i, e)| (*e, 1 << i)).collect();
385
386 let mut active_neighbors_mask: $node_bits = 0;
387
388 // each rooom's bit is set to 1 if all its edges are done computed
389 let mut done_mask: $node_bits = 0;
390
391 // Temporary storage for upserts
392 // so we don't have to allocate every iteration
393 // (edge_val, mask, computed_mask)
394 let mut upserts: Vec<($node_bits, $node_bits, $node_bits)> = Vec::new();
395
396 let last_node_bit = 1 << (nodes.inner.len() - 1);
397 let full_mask: $node_bits = last_node_bit | (last_node_bit - 1);
398
399 // setup
400 for (a, a_neighbors) in &nodes {
401 let a_neighbors_len = a_neighbors.len() as usize;
402
403 // clear upserts
404 upserts.fill((0, 0, 0));
405 if upserts.len() < a_neighbors_len {
406 upserts.resize(a_neighbors_len, (0, 0, 0));
407 }
408
409 // for each edge in this node
410 // set the value for a and b's node as 1
411 for (i, b) in a_neighbors.enumerate() {
412 let b_bit = 1 << b;
413
414 let mut val = b_bit;
415
416 // edge value is flipped to b -> a, which means from node b's perspective, this edge is:
417 // - gets further away from b
418 // - shortest path to a
419 // - gets further away from all other nodes
420 if a > b {
421 val = 0;
422 }
423
424 // for all other edges in this node, set the value for this node bit as 0
425 for (j, c) in a_neighbors.clone().enumerate() {
426 if i == j {
427 continue;
428 }
429
430 // if both b and c are in the same corner (tl or br)
431 // flip the bit
432 let upsert = if (a > b) == (a > c) {
433 !val & b_bit
434 } else {
435 val & b_bit
436 };
437
438 let vals = &mut upserts[j];
439 vals.0 |= upsert;
440 vals.1 |= b_bit;
441 }
442 }
443
444 // apply computed values
445 for (i, b) in a_neighbors.enumerate() {
446 let ab = edge_id(a, b);
447
448 let (upsert, computed, _) = upserts[i];
449
450 if computed != 0 {
451 if upsert != 0 {
452 edges.insert(ab, upsert);
453 }
454 edge_masks.insert(ab, computed);
455 }
456 }
457 }
458
459 'outer: while done_mask != full_mask {
460 // iterate through all undone nodes
461 for a in [<node_bits_ $num _iter>](full_mask ^ done_mask) {
462 let a_bit = 1 << a;
463 let a_neighbors = nodes.neighbors(a);
464 let a_neighbors_len = a_neighbors.len() as usize;
465
466 // clear upserts
467 upserts.fill((0, 0, 0));
468 if upserts.len() < a_neighbors_len {
469 upserts.resize(a_neighbors_len, (0, 0, 0));
470 }
471
472 // collect all nodes that need to update their neighbors to next depth
473 let mut a_active_neighbors_mask = 0;
474
475 // are all edges computed for this node?
476 let mut all_edges_done = true;
477
478 // get all neighbors' masks
479 // so we can just reuse it
480 for (i, b) in a_neighbors.enumerate() {
481 let mask = edge_masks.get(edge_id(a, b)).unwrap();
482 upserts[i].2 = mask;
483
484 if mask != full_mask {
485 all_edges_done = false;
486 }
487 }
488
489 if all_edges_done {
490 done_mask |= a_bit;
491
492 continue;
493 }
494
495 for (i, b) in a_neighbors.enumerate() {
496 // neighbors' bits to gossip from edge a->b to other edges
497 let neighbors_mask = neighbors_at_depth.get(b as usize).unwrap().0 & !a_bit;
498
499 // if no neighbors to gossip at this depth, skip
500 if neighbors_mask == 0 {
501 continue;
502 }
503
504 a_active_neighbors_mask |= 1 << b;
505
506 let ab = edge_id(a, b);
507
508 let val = edges.get(ab).unwrap();
509
510 // gossip to other edges about its neighbors at current depth
511 for (j, c) in a_neighbors.enumerate() {
512 // skip if same neighbor
513 if i == j {
514 continue;
515 }
516
517 let mask_ac = upserts[j].2;
518 if mask_ac == full_mask {
519 continue;
520 }
521 all_edges_done = false;
522
523 // dont set bits that are already computed
524 let compute_mask = neighbors_mask & !mask_ac;
525
526 // if all bits are already computed, skip
527 if compute_mask == 0 {
528 continue;
529 }
530
531 // if both b and c are in the same corner (tl or br)
532 // flip the bit
533 let upsert = if (a > b) == (a > c) { !val } else { val } & compute_mask;
534
535 let vals = &mut upserts[j];
536 vals.0 |= upsert;
537 vals.1 |= compute_mask;
538 }
539 }
540
541 // if all edges are computed or none of a's neighbors are active,
542 // then a is done
543 if all_edges_done || a_active_neighbors_mask == 0 {
544 done_mask |= a_bit;
545 } else {
546 for (i, b) in a_neighbors.enumerate() {
547 let ab = edge_id(a, b);
548
549 let (upsert, computed, _) = upserts[i];
550
551 if computed != 0 {
552 if upsert != 0 {
553 edges.insert(ab, upsert);
554 }
555 edge_masks.insert(ab, computed);
556 }
557 }
558 }
559
560 // if all nodes are done, return true
561 if done_mask == full_mask {
562 break 'outer;
563 }
564
565 active_neighbors_mask |= a_active_neighbors_mask;
566 }
567
568 // iterate through active neighbors that were colleted this iteration
569 // and get the next layer of neighbors for each node.
570 // if new_neighbors is 0, then all neighbors are computed.
571 for a in [<node_bits_ $num _iter>](active_neighbors_mask) {
572 let a_usize = a as usize;
573 let (a_neighbors_at_depth, mut prev_neighbors) = neighbors_at_depth[a_usize];
574
575 if a_neighbors_at_depth == 0 {
576 continue;
577 }
578
579 let mut new_neighbors = 0;
580 for b in [<node_bits_ $num _iter>](a_neighbors_at_depth) {
581 new_neighbors |= nodes.neighbors(b).node_bits;
582 }
583
584 // add previous neighbors to computed
585 prev_neighbors |= a_neighbors_at_depth;
586
587 // new neighbors at this depth without the previous neighbors
588 new_neighbors &= !prev_neighbors;
589 neighbors_at_depth[a_usize] = (new_neighbors, prev_neighbors);
590 }
591
592 active_neighbors_mask = 0;
593 }
594
595 [< Graph $num >] {
596 nodes,
597 edges: edges.inner,
598 }
599 }
600 }
601
602 /// Map of nodes and their neighbors.
603 #[doc = "value: " $node_bits " with neighbors' bit locations set to `true`"]
604 #[derive(Debug, Clone)]
605 pub struct [<Nodes $num>] {
606 pub inner: Vec<$node_bits>,
607 }
608
609 impl [<Nodes $num>] {
610 pub fn new(nodes_len: usize) -> Self {
611 Self {
612 inner: vec![0; nodes_len],
613 }
614 }
615
616 /// Get the neighboring nodes
617 #[inline]
618 pub fn neighbors(&self, node: $node_id) -> [<NodeBits $num Iter>] {
619 [<node_bits_ $num _iter>](self.inner[node as usize])
620 }
621
622 /// Add a edge between node_a and node_b
623 /// If the edge was not added, return false
624 pub fn connect(&mut self, a: $node_id, b: $node_id) -> bool {
625 if a == b {
626 return false;
627 }
628
629 let b_bit = 1 << b;
630
631 self.inner[a as usize] |= b_bit;
632 self.inner[b as usize] |= 1 << a;
633
634 true
635 }
636
637 /// Remove a edge between node_a and node_b
638 /// If the edge was not removed, return false
639 pub fn disconnect(&mut self, a: $node_id, b: $node_id) -> bool {
640 if a == b {
641 return false;
642 }
643
644 let b_bit = 1 << b;
645
646 self.inner[a as usize] &= !b_bit;
647 self.inner[b as usize] &= !(1 << a);
648
649 true
650 }
651
652 #[inline]
653 pub fn edge_count(&self, node: $node_id) -> u32 {
654 self.inner[node as usize].count_ones()
655 }
656
657 #[inline]
658 pub fn len(&self) -> usize {
659 self.inner.len()
660 }
661
662 #[inline]
663 pub fn resize(&mut self, new_len: usize) {
664 self.inner.resize(new_len, 0);
665 }
666 }
667
668 /// Map of edges and bits indicating if the edge is the shortest path to the node.
669 #[derive(Debug, Clone)]
670 pub struct [<Edges $num>] {
671 /// key: edge_id
672 ///
673 /// value: for each bit, if this edge is the shortest path
674 /// to that bit location's node, bit is set to 1
675 inner: HashMap<($node_id, $node_id), $node_bits>,
676 }
677
678 impl [<Edges $num>] {
679 fn new() -> Self {
680 Self {
681 inner: HashMap::new(),
682 }
683 }
684
685 #[inline]
686 pub fn get(&self, edge_id: ($node_id, $node_id)) -> Option<$node_bits> {
687 self.inner.get(&edge_id).cloned()
688 }
689
690 #[inline]
691 pub fn insert(&mut self, edge_id: ($node_id, $node_id), val: $node_bits) {
692 if let Some(edge) = self.inner.get_mut(&edge_id) {
693 *edge |= val;
694 } else {
695 self.inner.insert(edge_id, val);
696 }
697 }
698
699 /// Truncate the edges to the given length of nodes.
700 pub fn truncate(&mut self, nodes_len: u8) {
701 let keys_to_remove = self
702 .inner
703 .keys()
704 .filter(|&(a, b)| *a >= nodes_len || *b >= nodes_len)
705 .cloned()
706 .collect::<Vec<_>>();
707
708 for key in keys_to_remove {
709 self.inner.remove(&key);
710 }
711
712 for edge in self.inner.values_mut() {
713 *edge &= (1 << nodes_len) - 1;
714 }
715 }
716 }
717
718 impl<'a> IntoIterator for &'a [<Nodes $num>] {
719 type Item = ($node_id, [<NodeBits $num Iter>]);
720 type IntoIter = [<Neighbors $num Iter>]<'a>;
721
722 fn into_iter(self) -> Self::IntoIter {
723 [<Neighbors $num Iter>] {
724 neighbors: self,
725 node: 0,
726 }
727 }
728 }
729
730 /// Iterator that iterates through all nodes and their neighbors.
731 pub struct [<Neighbors $num Iter>]<'a> {
732 neighbors: &'a [<Nodes $num>],
733 node: $node_id,
734 }
735
736 impl<'a> Iterator for [<Neighbors $num Iter>]<'a> {
737 type Item = ($node_id, [<NodeBits $num Iter>]);
738
739 fn next(&mut self) -> Option<Self::Item> {
740 let node = self.node;
741
742 if node as usize >= self.neighbors.len() {
743 return None;
744 }
745
746 self.node += 1;
747 self.neighbors
748 .inner
749 .get(node as usize)
750 .map(|connected| (node, [<node_bits_ $num _iter>](*connected)))
751 }
752 }
753
754 fn [<node_bits_ $num _iter>](node_bits: $node_bits) -> [<NodeBits $num Iter>] {
755 [<NodeBits $num Iter>] { node_bits }
756 }
757
758 /// Given a value with bits set to 1 at existing nodes' indices,
759 /// iterate through the node indices
760 #[derive(Clone, Copy)]
761 pub struct [<NodeBits $num Iter>] {
762 node_bits: $node_bits,
763 }
764
765 impl Debug for [<NodeBits $num Iter>] {
766 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
767 write!(f, "{:016b}", self.node_bits)
768 }
769 }
770
771 impl [<NodeBits $num Iter>] {
772 pub fn without(self, node: $node_id) -> Self {
773 Self {
774 node_bits: self.node_bits & !(1 << node),
775 }
776 }
777
778 #[inline]
779 pub fn len(&self) -> u32 {
780 self.node_bits.count_ones()
781 }
782 }
783
784 impl Iterator for [<NodeBits $num Iter>] {
785 type Item = $node_id;
786
787 fn next(&mut self) -> Option<Self::Item> {
788 if self.node_bits == 0 {
789 return None;
790 }
791
792 // index of the next connected edge
793 let node = self.node_bits.trailing_zeros();
794
795 // remove the connected edge from the node_bits
796 self.node_bits &= !(1 << node);
797
798 Some(node as $node_id)
799 }
800 }
801 }
802 };
803}
804impl_prim!(u16, u8, 16);
805impl_prim!(u32, u8, 32);
806impl_prim!(u64, u8, 64);
807impl_prim!(u128, u8, 128);
808
809#[cfg(test)]
810mod tests {
811 use super::*;
812
813 #[test]
814 fn test_graph_16() {
815 pub const NODES_X_LEN: usize = 4;
816 pub const NODES_Y_LEN: usize = 4;
817 pub const NODES_LEN: usize = NODES_X_LEN * NODES_Y_LEN;
818
819 let mut builder = Graph16Builder::new(NODES_LEN);
820
821 // place a edge between every adjacent node
822 for y in 0..NODES_Y_LEN {
823 for x in 0..NODES_X_LEN {
824 let node_id = y * NODES_X_LEN + x;
825
826 if x > 0 {
827 let a = (node_id - 1) as u8;
828 let b = node_id as u8;
829 builder.connect(a, b);
830 }
831
832 if y > 0 {
833 let a = node_id as u8;
834 let b = (node_id - NODES_X_LEN) as u8;
835 builder.connect(a, b);
836 }
837 }
838 }
839
840 let now = std::time::Instant::now();
841 let _graph = builder.build();
842 println!("Time: {:?}", now.elapsed());
843 }
844
845 #[test]
846 fn test_graph_32() {
847 pub const NODES_X_LEN: usize = 4;
848 pub const NODES_Y_LEN: usize = 8;
849 pub const NODES_LEN: usize = NODES_X_LEN * NODES_Y_LEN;
850
851 let mut builder = Graph32Builder::new(NODES_LEN);
852
853 // place a edge between every adjacent node
854 for y in 0..NODES_Y_LEN {
855 for x in 0..NODES_X_LEN {
856 let node_id = y * NODES_X_LEN + x;
857
858 if x > 0 {
859 let a = (node_id - 1) as u8;
860 let b = node_id as u8;
861 builder.connect(a, b);
862 }
863
864 if y > 0 {
865 let a = node_id as u8;
866 let b = (node_id - NODES_X_LEN) as u8;
867 builder.connect(a, b);
868 }
869 }
870 }
871
872 let now = std::time::Instant::now();
873 let _graph = builder.build();
874 println!("Time: {:?}", now.elapsed());
875 }
876
877 #[test]
878 fn test_graph_64() {
879 pub const NODES_X_LEN: usize = 8;
880 pub const NODES_Y_LEN: usize = 8;
881 pub const NODES_LEN: usize = NODES_X_LEN * NODES_Y_LEN;
882
883 let mut builder = Graph64Builder::new(NODES_LEN);
884
885 // place a edge between every adjacent node
886 for y in 0..NODES_Y_LEN {
887 for x in 0..NODES_X_LEN {
888 let node_id = y * NODES_X_LEN + x;
889
890 if x > 0 {
891 let a = (node_id - 1) as u8;
892 let b = node_id as u8;
893 builder.connect(a, b);
894 }
895
896 if y > 0 {
897 let a = node_id as u8;
898 let b = (node_id - NODES_X_LEN) as u8;
899 builder.connect(a, b);
900 }
901 }
902 }
903
904 let now = std::time::Instant::now();
905 let _graph = builder.build();
906 println!("Time: {:?}", now.elapsed());
907 }
908
909 #[test]
910 fn test_graph_128() {
911 pub const NODES_X_LEN: usize = 8;
912 pub const NODES_Y_LEN: usize = 16;
913 pub const NODES_LEN: usize = NODES_X_LEN * NODES_Y_LEN;
914
915 let mut builder = Graph128Builder::new(NODES_LEN);
916
917 // place a edge between every adjacent node
918 for y in 0..NODES_Y_LEN {
919 for x in 0..NODES_X_LEN {
920 let node_id = y * NODES_X_LEN + x;
921
922 if x > 0 {
923 let a = (node_id - 1) as u8;
924 let b = node_id as u8;
925 builder.connect(a, b);
926 }
927
928 if y > 0 {
929 let a = node_id as u8;
930 let b = (node_id - NODES_X_LEN) as u8;
931 builder.connect(a, b);
932 }
933 }
934 }
935
936 let now = std::time::Instant::now();
937 let _graph = builder.build();
938 println!("Time: {:?}", now.elapsed());
939 }
940}