1use alloc::vec::Vec;
5use core::{
6 cmp::Ordering,
7 fmt,
8 hash::{self, BuildHasher, Hash},
9 iter::{Copied, FromIterator},
10 marker::PhantomData,
11 mem,
12 ops::{Deref, Index, IndexMut},
13 slice::Iter,
14};
15
16use hashbrown::HashSet;
17use indexmap::{
18 map::{Iter as IndexMapIter, IterMut as IndexMapIterMut, Keys},
19 IndexMap,
20};
21
22use crate::{
23 data,
24 graph::{node_index, Graph},
25 visit, Directed, Direction, EdgeType, Incoming, IntoWeightedEdge, Outgoing, Undirected,
26};
27
28#[cfg(feature = "std")]
29use std::collections::hash_map::RandomState;
30
31#[cfg(feature = "rayon")]
32use {
33 indexmap::map::rayon::{ParIter, ParIterMut, ParKeys},
34 rayon::prelude::*,
35};
36
37pub type UnGraphMap<N, E, #[cfg(not(feature = "std"))] S, #[cfg(feature = "std")] S = RandomState> =
42 GraphMap<N, E, Undirected, S>;
43pub type DiGraphMap<N, E, #[cfg(not(feature = "std"))] S, #[cfg(feature = "std")] S = RandomState> =
48 GraphMap<N, E, Directed, S>;
49
50#[derive(Clone)]
76pub struct GraphMap<
77 N,
78 E,
79 Ty,
80 #[cfg(not(feature = "std"))] S,
81 #[cfg(feature = "std")] S = RandomState,
82> where
83 S: BuildHasher,
84{
85 nodes: IndexMap<N, Vec<(N, CompactDirection)>, S>,
86 edges: IndexMap<(N, N), E, S>,
87 ty: PhantomData<Ty>,
88}
89
90impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType, S: BuildHasher> fmt::Debug
91 for GraphMap<N, E, Ty, S>
92{
93 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
94 self.nodes.fmt(f)
95 }
96}
97
98pub trait NodeTrait: Copy + Ord + Hash {}
100impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
101
102#[derive(Copy, Clone, Debug, PartialEq)]
104enum CompactDirection {
105 Outgoing,
106 Incoming,
107}
108
109impl CompactDirection {
110 #[inline]
112 pub fn opposite(self) -> CompactDirection {
113 match self {
114 CompactDirection::Outgoing => CompactDirection::Incoming,
115 CompactDirection::Incoming => CompactDirection::Outgoing,
116 }
117 }
118}
119
120impl From<Direction> for CompactDirection {
121 fn from(d: Direction) -> Self {
122 match d {
123 Outgoing => CompactDirection::Outgoing,
124 Incoming => CompactDirection::Incoming,
125 }
126 }
127}
128
129impl From<CompactDirection> for Direction {
130 fn from(d: CompactDirection) -> Self {
131 match d {
132 CompactDirection::Outgoing => Outgoing,
133 CompactDirection::Incoming => Incoming,
134 }
135 }
136}
137
138impl PartialEq<Direction> for CompactDirection {
139 fn eq(&self, rhs: &Direction) -> bool {
140 (*self as usize) == (*rhs as usize)
141 }
142}
143
144#[cfg(feature = "serde-1")]
145impl<N, E, Ty, S> serde::Serialize for GraphMap<N, E, Ty, S>
146where
147 Ty: EdgeType,
148 N: NodeTrait + serde::Serialize,
149 E: serde::Serialize,
150 S: BuildHasher,
151 Self: Clone,
152{
153 fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
158 where
159 Ser: serde::Serializer,
160 {
161 let cloned_graph: GraphMap<N, E, Ty, S> = GraphMap::clone(self);
162 let equivalent_graph: Graph<N, E, Ty, u32> = cloned_graph.into_graph();
163 equivalent_graph.serialize(serializer)
164 }
165}
166
167#[cfg(feature = "serde-1")]
168impl<'de, N, E, Ty, S> serde::Deserialize<'de> for GraphMap<N, E, Ty, S>
169where
170 Ty: EdgeType,
171 N: NodeTrait + serde::Deserialize<'de>,
172 E: Clone + serde::Deserialize<'de>,
173 S: BuildHasher + Default,
174{
175 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
183 where
184 D: serde::Deserializer<'de>,
185 {
186 let equivalent_graph: Graph<N, E, Ty, u32> = Graph::deserialize(deserializer)?;
187 Ok(GraphMap::from_graph(equivalent_graph))
188 }
189}
190
191impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
192where
193 S: BuildHasher,
194{
195 pub fn new() -> Self
197 where
198 S: Default,
199 {
200 Self::default()
201 }
202
203 pub fn with_capacity(nodes: usize, edges: usize) -> Self
205 where
206 S: Default,
207 {
208 Self {
209 nodes: IndexMap::with_capacity_and_hasher(nodes, S::default()),
210 edges: IndexMap::with_capacity_and_hasher(edges, S::default()),
211 ty: PhantomData,
212 }
213 }
214
215 pub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Self
217 where
218 S: Clone,
219 {
220 Self {
221 nodes: IndexMap::with_capacity_and_hasher(nodes, hasher.clone()),
222 edges: IndexMap::with_capacity_and_hasher(edges, hasher),
223 ty: PhantomData,
224 }
225 }
226}
227
228impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
229where
230 N: NodeTrait,
231 Ty: EdgeType,
232 S: BuildHasher,
233{
234 pub fn capacity(&self) -> (usize, usize) {
236 (self.nodes.capacity(), self.edges.capacity())
237 }
238
239 #[inline]
241 fn edge_key(a: N, b: N) -> (N, N) {
242 if Ty::is_directed() || a <= b {
243 (a, b)
244 } else {
245 (b, a)
246 }
247 }
248
249 pub fn is_directed(&self) -> bool {
251 Ty::is_directed()
252 }
253
254 pub fn from_edges<I>(iterable: I) -> Self
274 where
275 I: IntoIterator,
276 I::Item: IntoWeightedEdge<E, NodeId = N>,
277 S: Default,
278 {
279 Self::from_iter(iterable)
280 }
281
282 pub fn node_count(&self) -> usize {
284 self.nodes.len()
285 }
286
287 pub fn edge_count(&self) -> usize {
289 self.edges.len()
290 }
291
292 pub fn clear(&mut self) {
294 self.nodes.clear();
295 self.edges.clear();
296 }
297
298 pub fn add_node(&mut self, n: N) -> N {
300 self.nodes.entry(n).or_default();
301 n
302 }
303
304 pub fn remove_node(&mut self, n: N) -> bool {
310 let links = match self.nodes.swap_remove(&n) {
311 None => return false,
312 Some(sus) => sus,
313 };
314 for (succ, dir) in links {
315 let edge = if dir == CompactDirection::Outgoing {
316 Self::edge_key(n, succ)
317 } else {
318 Self::edge_key(succ, n)
319 };
320 self.remove_single_edge(&succ, &n, dir.opposite());
322 self.edges.swap_remove(&edge);
324 }
325 true
326 }
327
328 pub fn contains_node(&self, n: N) -> bool {
330 self.nodes.contains_key(&n)
331 }
332
333 pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
355 if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) {
356 old
357 } else {
358 self.nodes
360 .entry(a)
361 .or_insert_with(|| Vec::with_capacity(1))
362 .push((b, CompactDirection::Outgoing));
363 if a != b {
364 self.nodes
366 .entry(b)
367 .or_insert_with(|| Vec::with_capacity(1))
368 .push((a, CompactDirection::Incoming));
369 }
370 None
371 }
372 }
373
374 fn remove_single_edge(&mut self, a: &N, b: &N, dir: CompactDirection) -> bool {
378 match self.nodes.get_mut(a) {
379 None => false,
380 Some(sus) => {
381 if Ty::is_directed() {
382 match sus.iter().position(|elt| elt == &(*b, dir)) {
383 Some(index) => {
384 sus.swap_remove(index);
385 true
386 }
387 None => false,
388 }
389 } else {
390 match sus.iter().position(|elt| &elt.0 == b) {
391 Some(index) => {
392 sus.swap_remove(index);
393 true
394 }
395 None => false,
396 }
397 }
398 }
399 }
400 }
401
402 pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
418 let exist1 = self.remove_single_edge(&a, &b, CompactDirection::Outgoing);
419 let exist2 = if a != b {
420 self.remove_single_edge(&b, &a, CompactDirection::Incoming)
421 } else {
422 exist1
423 };
424 let weight = self.edges.swap_remove(&Self::edge_key(a, b));
425 debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
426 weight
427 }
428
429 pub fn contains_edge(&self, a: N, b: N) -> bool {
431 self.edges.contains_key(&Self::edge_key(a, b))
432 }
433
434 pub fn nodes(&self) -> Nodes<'_, N> {
438 Nodes {
439 iter: self.nodes.keys().copied(),
440 }
441 }
442
443 #[cfg(feature = "rayon")]
447 pub fn par_nodes(&self) -> ParNodes<'_, N>
448 where
449 N: Send + Sync,
450 {
451 ParNodes {
452 iter: self.nodes.par_keys(),
453 }
454 }
455
456 pub fn neighbors(&self, a: N) -> Neighbors<'_, N, Ty> {
464 Neighbors {
465 iter: match self.nodes.get(&a) {
466 Some(neigh) => neigh.iter(),
467 None => [].iter(),
468 },
469 ty: self.ty,
470 }
471 }
472
473 pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<'_, N, Ty> {
484 NeighborsDirected {
485 iter: match self.nodes.get(&a) {
486 Some(neigh) => neigh.iter(),
487 None => [].iter(),
488 },
489 start_node: a,
490 dir,
491 ty: self.ty,
492 }
493 }
494
495 pub fn edges(&self, a: N) -> Edges<'_, N, E, Ty, S> {
504 Edges {
505 from: a,
506 iter: self.neighbors(a),
507 edges: &self.edges,
508 }
509 }
510
511 pub fn edges_directed(&self, a: N, dir: Direction) -> EdgesDirected<'_, N, E, Ty, S> {
524 EdgesDirected {
525 from: a,
526 iter: self.neighbors_directed(a, dir),
527 dir,
528 edges: &self.edges,
529 }
530 }
531
532 pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
535 self.edges.get(&Self::edge_key(a, b))
536 }
537
538 pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
541 self.edges.get_mut(&Self::edge_key(a, b))
542 }
543
544 pub fn all_edges(&self) -> AllEdges<'_, N, E, Ty> {
548 AllEdges {
549 inner: self.edges.iter(),
550 ty: self.ty,
551 }
552 }
553
554 pub fn all_edges_mut(&mut self) -> AllEdgesMut<'_, N, E, Ty> {
559 AllEdgesMut {
560 inner: self.edges.iter_mut(),
561 ty: self.ty,
562 }
563 }
564
565 #[cfg(feature = "rayon")]
570 pub fn par_all_edges(&self) -> ParAllEdges<'_, N, E, Ty>
571 where
572 N: Send + Sync,
573 E: Sync,
574 {
575 ParAllEdges {
576 inner: self.edges.par_iter(),
577 ty: PhantomData,
578 }
579 }
580
581 #[cfg(feature = "rayon")]
586 pub fn par_all_edges_mut(&mut self) -> ParAllEdgesMut<'_, N, E, Ty>
587 where
588 N: Send + Sync,
589 E: Send,
590 {
591 ParAllEdgesMut {
592 inner: self.edges.par_iter_mut(),
593 ty: PhantomData,
594 }
595 }
596
597 #[track_caller]
609 pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
610 where
611 Ix: crate::graph::IndexType,
612 {
613 let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
615 for (&node, _) in &self.nodes {
616 gr.add_node(node);
617 }
618 for ((a, b), edge_weight) in self.edges {
619 let ai = self.nodes.get_index_of(&a).unwrap();
620 let bi = self.nodes.get_index_of(&b).unwrap();
621 gr.add_edge(node_index(ai), node_index(bi), edge_weight);
622 }
623 gr
624 }
625
626 pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Self
634 where
635 Ix: crate::graph::IndexType,
636 E: Clone,
637 S: Default,
638 {
639 let mut new_graph: GraphMap<N, E, Ty, S> =
640 GraphMap::with_capacity(graph.node_count(), graph.edge_count());
641
642 for node in graph.raw_nodes() {
643 new_graph.add_node(node.weight);
644 }
645
646 for edge in graph.edge_indices() {
647 let (a, b) = graph.edge_endpoints(edge).unwrap();
648 new_graph.add_edge(
649 *graph.node_weight(a).unwrap(),
650 *graph.node_weight(b).unwrap(),
651 graph.edge_weight(edge).unwrap().clone(),
652 );
653 }
654
655 new_graph
656 }
657}
658
659impl<N, E, Ty, Item, S> FromIterator<Item> for GraphMap<N, E, Ty, S>
661where
662 Item: IntoWeightedEdge<E, NodeId = N>,
663 N: NodeTrait,
664 Ty: EdgeType,
665 S: BuildHasher + Default,
666{
667 fn from_iter<I>(iterable: I) -> Self
668 where
669 I: IntoIterator<Item = Item>,
670 {
671 let iter = iterable.into_iter();
672 let (low, _) = iter.size_hint();
673 let mut g = Self::with_capacity(0, low);
674 g.extend(iter);
675 g
676 }
677}
678
679impl<N, E, Ty, Item, S> Extend<Item> for GraphMap<N, E, Ty, S>
683where
684 Item: IntoWeightedEdge<E, NodeId = N>,
685 N: NodeTrait,
686 Ty: EdgeType,
687 S: BuildHasher,
688{
689 fn extend<I>(&mut self, iterable: I)
690 where
691 I: IntoIterator<Item = Item>,
692 {
693 let iter = iterable.into_iter();
694 let (low, _) = iter.size_hint();
695 self.edges.reserve(low);
696
697 for elt in iter {
698 let (source, target, weight) = elt.into_weighted_edge();
699 self.add_edge(source, target, weight);
700 }
701 }
702}
703
704iterator_wrap! {
705 impl (Iterator DoubleEndedIterator ExactSizeIterator) for
706 #[derive(Debug, Clone)]
707 struct Nodes <'a, N> where { N: 'a + NodeTrait }
708 item: N,
709 iter: Copied<Keys<'a, N, Vec<(N, CompactDirection)>>>,
710}
711
712#[derive(Debug, Clone)]
713pub struct Neighbors<'a, N, Ty = Undirected>
714where
715 N: 'a,
716 Ty: EdgeType,
717{
718 iter: Iter<'a, (N, CompactDirection)>,
719 ty: PhantomData<Ty>,
720}
721
722impl<N, Ty> Iterator for Neighbors<'_, N, Ty>
723where
724 N: NodeTrait,
725 Ty: EdgeType,
726{
727 type Item = N;
728 fn next(&mut self) -> Option<N> {
729 if Ty::is_directed() {
730 (&mut self.iter)
731 .filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None })
732 .next()
733 } else {
734 self.iter.next().map(|&(n, _)| n)
735 }
736 }
737 fn size_hint(&self) -> (usize, Option<usize>) {
738 let (lower, upper) = self.iter.size_hint();
739 if Ty::is_directed() {
740 (0, upper)
741 } else {
742 (lower, upper)
743 }
744 }
745}
746
747#[derive(Debug, Clone)]
748pub struct NeighborsDirected<'a, N, Ty>
749where
750 N: 'a,
751 Ty: EdgeType,
752{
753 iter: Iter<'a, (N, CompactDirection)>,
754 start_node: N,
755 dir: Direction,
756 ty: PhantomData<Ty>,
757}
758
759impl<N, Ty> Iterator for NeighborsDirected<'_, N, Ty>
760where
761 N: NodeTrait,
762 Ty: EdgeType,
763{
764 type Item = N;
765 fn next(&mut self) -> Option<N> {
766 if Ty::is_directed() {
767 let self_dir = self.dir;
768 let start_node = self.start_node;
769 (&mut self.iter)
770 .filter_map(move |&(n, dir)| {
771 if dir == self_dir || n == start_node {
772 Some(n)
773 } else {
774 None
775 }
776 })
777 .next()
778 } else {
779 self.iter.next().map(|&(n, _)| n)
780 }
781 }
782 fn size_hint(&self) -> (usize, Option<usize>) {
783 let (lower, upper) = self.iter.size_hint();
784 if Ty::is_directed() {
785 (0, upper)
786 } else {
787 (lower, upper)
788 }
789 }
790}
791
792#[derive(Debug, Clone)]
793pub struct Edges<
794 'a,
795 N,
796 E: 'a,
797 Ty,
798 #[cfg(not(feature = "std"))] S,
799 #[cfg(feature = "std")] S = RandomState,
800> where
801 N: 'a + NodeTrait,
802 Ty: EdgeType,
803 S: BuildHasher,
804{
805 from: N,
806 edges: &'a IndexMap<(N, N), E, S>,
807 iter: Neighbors<'a, N, Ty>,
808}
809
810impl<'a, N, E, Ty, S> Iterator for Edges<'a, N, E, Ty, S>
811where
812 N: 'a + NodeTrait,
813 E: 'a,
814 Ty: EdgeType,
815 S: BuildHasher,
816{
817 type Item = (N, N, &'a E);
818 fn next(&mut self) -> Option<Self::Item> {
819 self.iter.next().map(|b| {
820 let a = self.from;
821 match self.edges.get(&GraphMap::<N, E, Ty, S>::edge_key(a, b)) {
822 None => unreachable!(),
823 Some(edge) => (a, b, edge),
824 }
825 })
826 }
827 fn size_hint(&self) -> (usize, Option<usize>) {
828 self.iter.size_hint()
829 }
830}
831
832#[derive(Debug, Clone)]
833pub struct EdgesDirected<
834 'a,
835 N,
836 E: 'a,
837 Ty,
838 #[cfg(not(feature = "std"))] S,
839 #[cfg(feature = "std")] S = RandomState,
840> where
841 N: 'a + NodeTrait,
842 Ty: EdgeType,
843 S: BuildHasher,
844{
845 from: N,
846 dir: Direction,
847 edges: &'a IndexMap<(N, N), E, S>,
848 iter: NeighborsDirected<'a, N, Ty>,
849}
850
851impl<'a, N, E, Ty, S> Iterator for EdgesDirected<'a, N, E, Ty, S>
852where
853 N: 'a + NodeTrait,
854 E: 'a,
855 Ty: EdgeType,
856 S: BuildHasher,
857{
858 type Item = (N, N, &'a E);
859 fn next(&mut self) -> Option<Self::Item> {
860 self.iter.next().map(|mut b| {
861 let mut a = self.from;
862 if self.dir == Direction::Incoming {
863 mem::swap(&mut a, &mut b);
864 }
865 match self.edges.get(&GraphMap::<N, E, Ty, S>::edge_key(a, b)) {
866 None => unreachable!(),
867 Some(edge) => (a, b, edge),
868 }
869 })
870 }
871 fn size_hint(&self) -> (usize, Option<usize>) {
872 self.iter.size_hint()
873 }
874}
875
876#[derive(Debug, Clone)]
877pub struct AllEdges<'a, N, E: 'a, Ty>
878where
879 N: 'a + NodeTrait,
880{
881 inner: IndexMapIter<'a, (N, N), E>,
882 ty: PhantomData<Ty>,
883}
884
885impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
886where
887 N: 'a + NodeTrait,
888 E: 'a,
889 Ty: EdgeType,
890{
891 type Item = (N, N, &'a E);
892 fn next(&mut self) -> Option<Self::Item> {
893 self.inner.next().map(|(&(a, b), v)| (a, b, v))
894 }
895
896 fn size_hint(&self) -> (usize, Option<usize>) {
897 self.inner.size_hint()
898 }
899
900 fn count(self) -> usize {
901 self.inner.count()
902 }
903
904 fn nth(&mut self, n: usize) -> Option<Self::Item> {
905 self.inner
906 .nth(n)
907 .map(|(&(n1, n2), weight)| (n1, n2, weight))
908 }
909
910 fn last(self) -> Option<Self::Item> {
911 self.inner
912 .last()
913 .map(|(&(n1, n2), weight)| (n1, n2, weight))
914 }
915}
916
917impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
918where
919 N: 'a + NodeTrait,
920 E: 'a,
921 Ty: EdgeType,
922{
923 fn next_back(&mut self) -> Option<Self::Item> {
924 self.inner
925 .next_back()
926 .map(|(&(n1, n2), weight)| (n1, n2, weight))
927 }
928}
929
930pub struct AllEdgesMut<'a, N, E: 'a, Ty>
931where
932 N: 'a + NodeTrait,
933{
934 inner: IndexMapIterMut<'a, (N, N), E>, ty: PhantomData<Ty>,
936}
937
938impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty>
939where
940 N: 'a + NodeTrait,
941 E: 'a,
942 Ty: EdgeType,
943{
944 type Item = (N, N, &'a mut E);
945 fn next(&mut self) -> Option<Self::Item> {
946 self.inner
947 .next()
948 .map(|(&(n1, n2), weight)| (n1, n2, weight))
949 }
950
951 fn size_hint(&self) -> (usize, Option<usize>) {
952 self.inner.size_hint()
953 }
954
955 fn count(self) -> usize {
956 self.inner.count()
957 }
958
959 fn nth(&mut self, n: usize) -> Option<Self::Item> {
960 self.inner
961 .nth(n)
962 .map(|(&(n1, n2), weight)| (n1, n2, weight))
963 }
964
965 fn last(self) -> Option<Self::Item> {
966 self.inner
967 .last()
968 .map(|(&(n1, n2), weight)| (n1, n2, weight))
969 }
970}
971
972impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty>
973where
974 N: 'a + NodeTrait,
975 E: 'a,
976 Ty: EdgeType,
977{
978 fn next_back(&mut self) -> Option<Self::Item> {
979 self.inner
980 .next_back()
981 .map(|(&(n1, n2), weight)| (n1, n2, weight))
982 }
983}
984
985impl<N, E, Ty, S> Index<(N, N)> for GraphMap<N, E, Ty, S>
987where
988 N: NodeTrait,
989 Ty: EdgeType,
990 S: BuildHasher,
991{
992 type Output = E;
993 fn index(&self, index: (N, N)) -> &E {
994 let index = Self::edge_key(index.0, index.1);
995 self.edge_weight(index.0, index.1)
996 .expect("GraphMap::index: no such edge")
997 }
998}
999
1000impl<N, E, Ty, S> IndexMut<(N, N)> for GraphMap<N, E, Ty, S>
1002where
1003 N: NodeTrait,
1004 Ty: EdgeType,
1005 S: BuildHasher,
1006{
1007 fn index_mut(&mut self, index: (N, N)) -> &mut E {
1008 let index = Self::edge_key(index.0, index.1);
1009 self.edge_weight_mut(index.0, index.1)
1010 .expect("GraphMap::index: no such edge")
1011 }
1012}
1013
1014impl<N, E, Ty, S> Default for GraphMap<N, E, Ty, S>
1016where
1017 S: BuildHasher + Default,
1018{
1019 fn default() -> Self {
1020 GraphMap::with_capacity(0, 0)
1021 }
1022}
1023
1024pub struct Ptr<'b, T: 'b>(pub &'b T);
1031
1032impl<T> Copy for Ptr<'_, T> {}
1033impl<T> Clone for Ptr<'_, T> {
1034 fn clone(&self) -> Self {
1035 *self
1036 }
1037}
1038
1039fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
1040 a == b
1041}
1042
1043impl<'b, T> PartialEq for Ptr<'b, T> {
1044 fn eq(&self, other: &Ptr<'b, T>) -> bool {
1046 ptr_eq(self.0, other.0)
1047 }
1048}
1049
1050impl<'b, T> PartialOrd for Ptr<'b, T> {
1051 fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
1052 Some(self.cmp(other))
1053 }
1054}
1055
1056impl<'b, T> Ord for Ptr<'b, T> {
1057 fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
1059 let a: *const T = self.0;
1060 let b: *const T = other.0;
1061 a.cmp(&b)
1062 }
1063}
1064
1065impl<T> Deref for Ptr<'_, T> {
1066 type Target = T;
1067 fn deref(&self) -> &T {
1068 self.0
1069 }
1070}
1071
1072impl<T> Eq for Ptr<'_, T> {}
1073
1074impl<T> Hash for Ptr<'_, T> {
1075 fn hash<H: hash::Hasher>(&self, st: &mut H) {
1076 let ptr = (self.0) as *const T;
1077 ptr.hash(st)
1078 }
1079}
1080
1081impl<T: fmt::Debug> fmt::Debug for Ptr<'_, T> {
1082 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1083 self.0.fmt(f)
1084 }
1085}
1086
1087#[derive(Debug, Clone)]
1088pub struct NodeIdentifiers<'a, N, E: 'a, Ty>
1089where
1090 N: 'a + NodeTrait,
1091{
1092 iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
1093 ty: PhantomData<Ty>,
1094 edge_ty: PhantomData<E>,
1095}
1096
1097impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty>
1098where
1099 N: 'a + NodeTrait,
1100 E: 'a,
1101 Ty: EdgeType,
1102{
1103 type Item = N;
1104 fn next(&mut self) -> Option<Self::Item> {
1105 self.iter.next().map(|(&n, _)| n)
1106 }
1107 fn size_hint(&self) -> (usize, Option<usize>) {
1108 self.iter.size_hint()
1109 }
1110}
1111
1112#[derive(Debug, Clone)]
1113pub struct NodeReferences<'a, N, E: 'a, Ty>
1114where
1115 N: 'a + NodeTrait,
1116{
1117 iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
1118 ty: PhantomData<Ty>,
1119 edge_ty: PhantomData<E>,
1120}
1121
1122impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty>
1123where
1124 N: 'a + NodeTrait,
1125 E: 'a,
1126 Ty: EdgeType,
1127{
1128 type Item = (N, &'a N);
1129 fn next(&mut self) -> Option<Self::Item> {
1130 self.iter.next().map(|(n, _)| (*n, n))
1131 }
1132 fn size_hint(&self) -> (usize, Option<usize>) {
1133 self.iter.size_hint()
1134 }
1135}
1136
1137impl<N, E, Ty, S> visit::GraphBase for GraphMap<N, E, Ty, S>
1138where
1139 N: Copy + PartialEq,
1140 S: BuildHasher,
1141{
1142 type NodeId = N;
1143 type EdgeId = (N, N);
1144}
1145
1146impl<N, E, Ty, S> visit::Data for GraphMap<N, E, Ty, S>
1147where
1148 N: Copy + PartialEq,
1149 Ty: EdgeType,
1150 S: BuildHasher,
1151{
1152 type NodeWeight = N;
1153 type EdgeWeight = E;
1154}
1155
1156impl<N, E, Ty, S> visit::Visitable for GraphMap<N, E, Ty, S>
1157where
1158 N: Copy + Ord + Hash,
1159 Ty: EdgeType,
1160 S: BuildHasher,
1161{
1162 type Map = HashSet<N>;
1163 fn visit_map(&self) -> HashSet<N> {
1164 HashSet::with_capacity(self.node_count())
1165 }
1166 fn reset_map(&self, map: &mut Self::Map) {
1167 map.clear();
1168 }
1169}
1170
1171impl<N, E, Ty, S> visit::GraphProp for GraphMap<N, E, Ty, S>
1172where
1173 N: NodeTrait,
1174 Ty: EdgeType,
1175 S: BuildHasher,
1176{
1177 type EdgeType = Ty;
1178}
1179
1180impl<'a, N, E, Ty, S> visit::IntoNodeReferences for &'a GraphMap<N, E, Ty, S>
1181where
1182 N: NodeTrait,
1183 Ty: EdgeType,
1184 S: BuildHasher,
1185{
1186 type NodeRef = (N, &'a N);
1187 type NodeReferences = NodeReferences<'a, N, E, Ty>;
1188 fn node_references(self) -> Self::NodeReferences {
1189 NodeReferences {
1190 iter: self.nodes.iter(),
1191 ty: self.ty,
1192 edge_ty: PhantomData,
1193 }
1194 }
1195}
1196
1197impl<'a, N, E: 'a, Ty, S> visit::IntoNodeIdentifiers for &'a GraphMap<N, E, Ty, S>
1198where
1199 N: NodeTrait,
1200 Ty: EdgeType,
1201 S: BuildHasher,
1202{
1203 type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>;
1204
1205 fn node_identifiers(self) -> Self::NodeIdentifiers {
1206 NodeIdentifiers {
1207 iter: self.nodes.iter(),
1208 ty: self.ty,
1209 edge_ty: PhantomData,
1210 }
1211 }
1212}
1213
1214impl<N, E, Ty, S> visit::NodeCount for GraphMap<N, E, Ty, S>
1215where
1216 N: NodeTrait,
1217 Ty: EdgeType,
1218 S: BuildHasher,
1219{
1220 fn node_count(&self) -> usize {
1221 (*self).node_count()
1222 }
1223}
1224
1225impl<N, E, Ty, S> visit::NodeIndexable for GraphMap<N, E, Ty, S>
1226where
1227 N: NodeTrait,
1228 Ty: EdgeType,
1229 S: BuildHasher,
1230{
1231 fn node_bound(&self) -> usize {
1232 self.node_count()
1233 }
1234 fn to_index(&self, ix: Self::NodeId) -> usize {
1235 self.nodes.get_index_of(&ix).expect("node not found")
1236 }
1237 fn from_index(&self, ix: usize) -> Self::NodeId {
1238 assert!(
1239 ix < self.nodes.len(),
1240 "The requested index {ix} is out-of-bounds."
1241 );
1242 let (&key, _) = self.nodes.get_index(ix).unwrap();
1243 key
1244 }
1245}
1246
1247impl<N, E, Ty, S> visit::NodeCompactIndexable for GraphMap<N, E, Ty, S>
1248where
1249 N: NodeTrait,
1250 Ty: EdgeType,
1251 S: BuildHasher,
1252{
1253}
1254
1255impl<'a, N: 'a, E, Ty, S> visit::IntoNeighbors for &'a GraphMap<N, E, Ty, S>
1256where
1257 N: Copy + Ord + Hash,
1258 Ty: EdgeType,
1259 S: BuildHasher,
1260{
1261 type Neighbors = Neighbors<'a, N, Ty>;
1262 fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
1263 self.neighbors(n)
1264 }
1265}
1266
1267impl<'a, N: 'a, E, Ty, S> visit::IntoNeighborsDirected for &'a GraphMap<N, E, Ty, S>
1268where
1269 N: Copy + Ord + Hash,
1270 Ty: EdgeType,
1271 S: BuildHasher,
1272{
1273 type NeighborsDirected = NeighborsDirected<'a, N, Ty>;
1274 fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected {
1275 self.neighbors_directed(n, dir)
1276 }
1277}
1278
1279impl<N, E, Ty, S> visit::EdgeIndexable for GraphMap<N, E, Ty, S>
1280where
1281 N: NodeTrait,
1282 Ty: EdgeType,
1283 S: BuildHasher,
1284{
1285 fn edge_bound(&self) -> usize {
1286 self.edge_count()
1287 }
1288
1289 fn to_index(&self, ix: Self::EdgeId) -> usize {
1290 self.edges.get_index_of(&ix).expect("edge not found")
1291 }
1292
1293 fn from_index(&self, ix: usize) -> Self::EdgeId {
1294 assert!(
1295 ix < self.edges.len(),
1296 "The requested index {ix} is out-of-bounds."
1297 );
1298 let (&key, _) = self.edges.get_index(ix).unwrap();
1299 key
1300 }
1301}
1302
1303impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdges for &'a GraphMap<N, E, Ty, S>
1304where
1305 N: NodeTrait,
1306 Ty: EdgeType,
1307 S: BuildHasher,
1308{
1309 type Edges = Edges<'a, N, E, Ty, S>;
1310 fn edges(self, a: Self::NodeId) -> Self::Edges {
1311 self.edges(a)
1312 }
1313}
1314
1315impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgesDirected for &'a GraphMap<N, E, Ty, S>
1316where
1317 N: NodeTrait,
1318 Ty: EdgeType,
1319 S: BuildHasher,
1320{
1321 type EdgesDirected = EdgesDirected<'a, N, E, Ty, S>;
1322 fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
1323 self.edges_directed(a, dir)
1324 }
1325}
1326
1327impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgeReferences for &'a GraphMap<N, E, Ty, S>
1328where
1329 N: NodeTrait,
1330 Ty: EdgeType,
1331 S: BuildHasher,
1332{
1333 type EdgeRef = (N, N, &'a E);
1334 type EdgeReferences = AllEdges<'a, N, E, Ty>;
1335 fn edge_references(self) -> Self::EdgeReferences {
1336 self.all_edges()
1337 }
1338}
1339
1340impl<N, E, Ty, S> visit::EdgeCount for GraphMap<N, E, Ty, S>
1341where
1342 N: NodeTrait,
1343 Ty: EdgeType,
1344 S: BuildHasher,
1345{
1346 #[inline]
1347 fn edge_count(&self) -> usize {
1348 self.edge_count()
1349 }
1350}
1351
1352impl<N, E, Ty, S> visit::GetAdjacencyMatrix for GraphMap<N, E, Ty, S>
1354where
1355 N: Copy + Ord + Hash,
1356 Ty: EdgeType,
1357 S: BuildHasher,
1358{
1359 type AdjMatrix = ();
1360 #[inline]
1361 fn adjacency_matrix(&self) {}
1362 #[inline]
1363 fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
1364 self.contains_edge(a, b)
1365 }
1366}
1367
1368impl<N, E, Ty, S> data::DataMap for GraphMap<N, E, Ty, S>
1369where
1370 N: Copy + Ord + Hash,
1371 Ty: EdgeType,
1372 S: BuildHasher,
1373{
1374 fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
1375 self.edge_weight(id.0, id.1)
1376 }
1377
1378 fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
1379 self.nodes.get_key_value(&id).map(|(k, _)| k)
1381 }
1382}
1383
1384#[cfg(feature = "rayon")]
1386pub struct ParNodes<'a, N>
1387where
1388 N: NodeTrait + Send + Sync,
1389{
1390 iter: ParKeys<'a, N, Vec<(N, CompactDirection)>>,
1391}
1392
1393#[cfg(feature = "rayon")]
1394impl<N> ParallelIterator for ParNodes<'_, N>
1395where
1396 N: NodeTrait + Send + Sync,
1397{
1398 type Item = N;
1399
1400 fn drive_unindexed<C>(self, consumer: C) -> C::Result
1401 where
1402 C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
1403 {
1404 self.iter.copied().drive_unindexed(consumer)
1405 }
1406
1407 fn opt_len(&self) -> Option<usize> {
1408 self.iter.opt_len()
1409 }
1410}
1411
1412#[cfg(feature = "rayon")]
1413impl<N> IndexedParallelIterator for ParNodes<'_, N>
1414where
1415 N: NodeTrait + Send + Sync,
1416{
1417 fn drive<C>(self, consumer: C) -> C::Result
1418 where
1419 C: rayon::iter::plumbing::Consumer<Self::Item>,
1420 {
1421 self.iter.copied().drive(consumer)
1422 }
1423
1424 fn len(&self) -> usize {
1425 self.iter.len()
1426 }
1427
1428 fn with_producer<CB>(self, callback: CB) -> CB::Output
1429 where
1430 CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
1431 {
1432 self.iter.copied().with_producer(callback)
1433 }
1434}
1435
1436#[cfg(feature = "rayon")]
1438pub struct ParAllEdges<'a, N, E, Ty>
1439where
1440 N: NodeTrait + Send + Sync,
1441 E: Sync,
1442{
1443 inner: ParIter<'a, (N, N), E>,
1444 ty: PhantomData<fn(Ty)>,
1445}
1446
1447#[cfg(feature = "rayon")]
1448impl<'a, N, E, Ty> ParallelIterator for ParAllEdges<'a, N, E, Ty>
1449where
1450 N: NodeTrait + Send + Sync,
1451 E: Sync,
1452{
1453 type Item = (N, N, &'a E);
1454
1455 fn drive_unindexed<C>(self, c: C) -> C::Result
1456 where
1457 C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
1458 {
1459 self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
1460 }
1461
1462 fn opt_len(&self) -> Option<usize> {
1463 self.inner.opt_len()
1464 }
1465}
1466
1467#[cfg(feature = "rayon")]
1468impl<N, E, Ty> IndexedParallelIterator for ParAllEdges<'_, N, E, Ty>
1469where
1470 N: NodeTrait + Send + Sync,
1471 E: Sync,
1472{
1473 fn drive<C>(self, consumer: C) -> C::Result
1474 where
1475 C: rayon::iter::plumbing::Consumer<Self::Item>,
1476 {
1477 self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
1478 }
1479
1480 fn len(&self) -> usize {
1481 self.inner.len()
1482 }
1483
1484 fn with_producer<CB>(self, callback: CB) -> CB::Output
1485 where
1486 CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
1487 {
1488 self.inner
1489 .map(|(&(a, b), v)| (a, b, v))
1490 .with_producer(callback)
1491 }
1492}
1493
1494#[cfg(feature = "rayon")]
1496pub struct ParAllEdgesMut<'a, N, E: 'a, Ty>
1497where
1498 N: NodeTrait + Send + Sync,
1499 E: Send,
1500{
1501 inner: ParIterMut<'a, (N, N), E>,
1502 ty: PhantomData<fn(Ty)>,
1503}
1504
1505#[cfg(feature = "rayon")]
1506impl<'a, N, E, Ty> ParallelIterator for ParAllEdgesMut<'a, N, E, Ty>
1507where
1508 N: NodeTrait + Send + Sync,
1509 E: Send,
1510{
1511 type Item = (N, N, &'a mut E);
1512
1513 fn drive_unindexed<C>(self, c: C) -> C::Result
1514 where
1515 C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
1516 {
1517 self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
1518 }
1519
1520 fn opt_len(&self) -> Option<usize> {
1521 self.inner.opt_len()
1522 }
1523}
1524
1525#[cfg(feature = "rayon")]
1526impl<N, E, Ty> IndexedParallelIterator for ParAllEdgesMut<'_, N, E, Ty>
1527where
1528 N: NodeTrait + Send + Sync,
1529 E: Send,
1530{
1531 fn drive<C>(self, consumer: C) -> C::Result
1532 where
1533 C: rayon::iter::plumbing::Consumer<Self::Item>,
1534 {
1535 self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
1536 }
1537
1538 fn len(&self) -> usize {
1539 self.inner.len()
1540 }
1541
1542 fn with_producer<CB>(self, callback: CB) -> CB::Output
1543 where
1544 CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
1545 {
1546 self.inner
1547 .map(|(&(a, b), v)| (a, b, v))
1548 .with_producer(callback)
1549 }
1550}