petgraph/
graphmap.rs

1//! `GraphMap<N, E, Ty>` is a graph datastructure where node values are mapping
2//! keys.
3
4use 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
37/// A `GraphMap` with undirected edges.
38///
39/// For example, an edge between *1* and *2* is equivalent to an edge between
40/// *2* and *1*.
41pub type UnGraphMap<N, E, #[cfg(not(feature = "std"))] S, #[cfg(feature = "std")] S = RandomState> =
42    GraphMap<N, E, Undirected, S>;
43/// A `GraphMap` with directed edges.
44///
45/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
46/// *1*.
47pub type DiGraphMap<N, E, #[cfg(not(feature = "std"))] S, #[cfg(feature = "std")] S = RandomState> =
48    GraphMap<N, E, Directed, S>;
49
50/// `GraphMap<N, E, Ty>` is a graph datastructure using an associative array
51/// of its node weights `N`.
52///
53/// It uses an combined adjacency list and sparse adjacency matrix
54/// representation, using **O(|V| + |E|)** space where V is the set of nodes
55/// and E is the set of edges, and allows testing for edge
56/// existence in constant time.
57///
58/// `GraphMap` is parameterized over:
59///
60/// - Associated data `N` for nodes and `E` for edges, called *weights*.
61/// - The node weight `N` must implement `Copy` and will be used as node
62///   identifier, duplicated into several places in the data structure.
63///   It must be suitable as a hash table key (implementing `Eq + Hash`).
64///   The node type must also implement `Ord` so that the implementation can
65///   order the pair (`a`, `b`) for an edge connecting any two nodes `a` and `b`.
66/// - `E` can be of arbitrary type.
67/// - Edge type `Ty` that determines whether the graph edges are directed or
68///   undirected.
69///
70/// You can use the type aliases `UnGraphMap` and `DiGraphMap` for convenience.
71///
72/// `GraphMap` does not allow parallel edges, but self loops are allowed.
73///
74/// Depends on crate feature `graphmap` (default).
75#[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
98/// A trait group for `GraphMap`'s node identifier.
99pub trait NodeTrait: Copy + Ord + Hash {}
100impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
101
102// non-repr(usize) version of Direction
103#[derive(Copy, Clone, Debug, PartialEq)]
104enum CompactDirection {
105    Outgoing,
106    Incoming,
107}
108
109impl CompactDirection {
110    /// Return the opposite `CompactDirection`.
111    #[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    /// Serializes the given `GraphMap` into the same format as the standard
154    /// `Graph`. Needs feature `serde-1`.
155    ///
156    /// Note: the graph has to be `Clone` for this to work.
157    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    /// Deserializes into a new `GraphMap` from the same format as the standard
176    /// `Graph`. Needs feature `serde-1`.
177    ///
178    /// **Warning**: When deserializing a graph that was not originally a `GraphMap`,
179    /// the restrictions from [`from_graph`](#method.from_graph) apply.
180    ///
181    /// Note: The edge weights have to be `Clone` for this to work.
182    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    /// Create a new `GraphMap`
196    pub fn new() -> Self
197    where
198        S: Default,
199    {
200        Self::default()
201    }
202
203    /// Create a new `GraphMap` with estimated capacity.
204    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    /// Create a new `GraphMap` with estimated capacity, and specified hasher.
216    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    /// Return the current node and edge capacity of the graph.
235    pub fn capacity(&self) -> (usize, usize) {
236        (self.nodes.capacity(), self.edges.capacity())
237    }
238
239    /// Use their natural order to map the node pair (a, b) to a canonical edge id.
240    #[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    /// Whether the graph has directed edges.
250    pub fn is_directed(&self) -> bool {
251        Ty::is_directed()
252    }
253
254    /// Create a new `GraphMap` from an iterable of edges.
255    ///
256    /// Node values are taken directly from the list.
257    /// Edge weights `E` may either be specified in the list,
258    /// or they are filled with default values.
259    ///
260    /// Nodes are inserted automatically to match the edges.
261    ///
262    /// ```
263    /// use petgraph::graphmap::UnGraphMap;
264    ///
265    /// // Create a new undirected GraphMap.
266    /// // Use a type hint to have `()` be the edge weight type.
267    /// let gr = UnGraphMap::<_, ()>::from_edges(&[
268    ///     (0, 1), (0, 2), (0, 3),
269    ///     (1, 2), (1, 3),
270    ///     (2, 3),
271    /// ]);
272    /// ```
273    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    /// Return the number of nodes in the graph.
283    pub fn node_count(&self) -> usize {
284        self.nodes.len()
285    }
286
287    /// Return the number of edges in the graph.
288    pub fn edge_count(&self) -> usize {
289        self.edges.len()
290    }
291
292    /// Remove all nodes and edges
293    pub fn clear(&mut self) {
294        self.nodes.clear();
295        self.edges.clear();
296    }
297
298    /// Add node `n` to the graph.
299    pub fn add_node(&mut self, n: N) -> N {
300        self.nodes.entry(n).or_default();
301        n
302    }
303
304    /// Remove node `n` from the graph.
305    ///
306    /// Return `true` if it did exist.
307    ///
308    /// Computes in **O(V)** time, due to the removal of edges with other nodes.
309    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            // remove all successor links
321            self.remove_single_edge(&succ, &n, dir.opposite());
322            // Remove all edge values
323            self.edges.swap_remove(&edge);
324        }
325        true
326    }
327
328    /// Return `true` if the node is contained in the graph.
329    pub fn contains_node(&self, n: N) -> bool {
330        self.nodes.contains_key(&n)
331    }
332
333    /// Add an edge connecting `a` and `b` to the graph, with associated
334    /// data `weight`. For a directed graph, the edge is directed from `a`
335    /// to `b`.
336    ///
337    /// Inserts nodes `a` and/or `b` if they aren't already part of the graph.
338    ///
339    /// Return `None` if the edge did not previously exist, otherwise,
340    /// the associated data is updated and the old value is returned
341    /// as `Some(old_weight)`.
342    ///
343    /// ```
344    /// // Create a GraphMap with directed edges, and add one edge to it
345    /// use petgraph::graphmap::DiGraphMap;
346    ///
347    /// let mut g = DiGraphMap::<_, _>::new();
348    /// g.add_edge("x", "y", -1);
349    /// assert_eq!(g.node_count(), 2);
350    /// assert_eq!(g.edge_count(), 1);
351    /// assert!(g.contains_edge("x", "y"));
352    /// assert!(!g.contains_edge("y", "x"));
353    /// ```
354    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            // insert in the adjacency list if it's a new edge
359            self.nodes
360                .entry(a)
361                .or_insert_with(|| Vec::with_capacity(1))
362                .push((b, CompactDirection::Outgoing));
363            if a != b {
364                // self loops don't have the Incoming entry
365                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    /// Remove edge relation from a to b
375    ///
376    /// Return `true` if it did exist.
377    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    /// Remove edge from `a` to `b` from the graph and return the edge weight.
403    ///
404    /// Return `None` if the edge didn't exist.
405    ///
406    /// ```
407    /// // Create a GraphMap with undirected edges, and add and remove an edge.
408    /// use petgraph::graphmap::UnGraphMap;
409    ///
410    /// let mut g = UnGraphMap::<_, _>::new();
411    /// g.add_edge("x", "y", -1);
412    ///
413    /// let edge_data = g.remove_edge("y", "x");
414    /// assert_eq!(edge_data, Some(-1));
415    /// assert_eq!(g.edge_count(), 0);
416    /// ```
417    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    /// Return `true` if the edge connecting `a` with `b` is contained in the graph.
430    pub fn contains_edge(&self, a: N, b: N) -> bool {
431        self.edges.contains_key(&Self::edge_key(a, b))
432    }
433
434    /// Return an iterator over the nodes of the graph.
435    ///
436    /// Iterator element type is `N`.
437    pub fn nodes(&self) -> Nodes<'_, N> {
438        Nodes {
439            iter: self.nodes.keys().copied(),
440        }
441    }
442
443    /// Return a parallel iterator over the nodes of the graph.
444    ///
445    /// Iterator element type is `N`.
446    #[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    /// Return an iterator of all nodes with an edge starting from `a`.
457    ///
458    /// - `Directed`: Outgoing edges from `a`.
459    /// - `Undirected`: All edges from or to `a`.
460    ///
461    /// Produces an empty iterator if the node doesn't exist.<br>
462    /// Iterator element type is `N`.
463    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    /// Return an iterator of all neighbors that have an edge between them and
474    /// `a`, in the specified direction.
475    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
476    ///
477    /// - `Directed`, `Outgoing`: All edges from `a`.
478    /// - `Directed`, `Incoming`: All edges to `a`.
479    /// - `Undirected`: All edges from or to `a`.
480    ///
481    /// Produces an empty iterator if the node doesn't exist.<br>
482    /// Iterator element type is `N`.
483    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    /// Return an iterator of target nodes with an edge starting from `a`,
496    /// paired with their respective edge weights.
497    ///
498    /// - `Directed`: Outgoing edges from `a`.
499    /// - `Undirected`: All edges from or to `a`.
500    ///
501    /// Produces an empty iterator if the node doesn't exist.<br>
502    /// Iterator element type is `(N, N, &E)`.
503    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    /// Return an iterator of target nodes with an edge starting from `a`,
512    /// paired with their respective edge weights.
513    ///
514    /// - `Directed`, `Outgoing`: All edges from `a`.
515    /// - `Directed`, `Incoming`: All edges to `a`.
516    /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
517    ///   edge.
518    /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
519    ///   edge.
520    ///
521    /// Produces an empty iterator if the node doesn't exist.<br>
522    /// Iterator element type is `(N, N, &E)`.
523    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    /// Return a reference to the edge weight connecting `a` with `b`, or
533    /// `None` if the edge does not exist in the graph.
534    pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
535        self.edges.get(&Self::edge_key(a, b))
536    }
537
538    /// Return a mutable reference to the edge weight connecting `a` with `b`, or
539    /// `None` if the edge does not exist in the graph.
540    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    /// Return an iterator over all edges of the graph with their weight in arbitrary order.
545    ///
546    /// Iterator element type is `(N, N, &E)`
547    pub fn all_edges(&self) -> AllEdges<'_, N, E, Ty> {
548        AllEdges {
549            inner: self.edges.iter(),
550            ty: self.ty,
551        }
552    }
553
554    /// Return an iterator over all edges of the graph in arbitrary order, with a mutable reference
555    /// to their weight.
556    ///
557    /// Iterator element type is `(N, N, &mut E)`
558    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    /// Return a parallel iterator over all edges of the graph with their weight in arbitrary
566    /// order.
567    ///
568    /// Iterator element type is `(N, N, &E)`
569    #[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    /// Return a parallel iterator over all edges of the graph in arbitrary order, with a mutable
582    /// reference to their weight.
583    ///
584    /// Iterator element type is `(N, N, &mut E)`
585    #[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    /// Return a `Graph` that corresponds to this `GraphMap`.
598    ///
599    /// 1. Note that node and edge indices in the `Graph` have nothing in common
600    ///    with the `GraphMap`s node weights `N`. The node weights `N` are used as
601    ///    node weights in the resulting `Graph`, too.
602    /// 2. Note that the index type is user-chosen.
603    ///
604    /// Computes in **O(|V| + |E|)** time (average) where V is the set of nodes and E is the set of edges.
605    ///
606    /// **Panics** if the number of nodes or edges does not fit with
607    /// the resulting graph's index type.
608    #[track_caller]
609    pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
610    where
611        Ix: crate::graph::IndexType,
612    {
613        // assuming two successive iterations of the same hashmap produce the same order
614        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    /// Creates a `GraphMap` that corresponds to the given `Graph`.
627    ///
628    /// **Warning**: Nodes with the same weight are merged and only the last parallel edge
629    /// is kept. Node and edge indices of the `Graph` are lost. Only use this function
630    /// if the node weights are distinct and there are no parallel edges.
631    ///
632    /// Computes in **O(|V| + |E|)** time (average).
633    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
659/// Create a new `GraphMap` from an iterable of edges.
660impl<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
679/// Extend the graph from an iterable of edges.
680///
681/// Nodes are inserted automatically to match the edges.
682impl<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>, // TODO: change to something that implements Debug + Clone?
935    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
985/// Index `GraphMap` by node pairs to access edge weights.
986impl<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
1000/// Index `GraphMap` by node pairs to access edge weights.
1001impl<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
1014/// Create a new empty `GraphMap`.
1015impl<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
1024/// A reference that is hashed and compared by its pointer value.
1025///
1026/// `Ptr` is used for certain configurations of `GraphMap`,
1027/// in particular in the combination where the node type for
1028/// `GraphMap` is something of type for example `Ptr(&Cell<T>)`,
1029/// with the `Cell<T>` being `TypedArena` allocated.
1030pub 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    /// Ptr compares by pointer equality, i.e if they point to the same value
1045    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    /// Ptr is ordered by pointer value, i.e. an arbitrary but stable and total order.
1058    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
1352/// The `GraphMap` keeps an adjacency matrix internally.
1353impl<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        // Technically `id` is already the weight for `GraphMap`, but since we need to return a reference, this is a O(1) borrowing alternative:
1380        self.nodes.get_key_value(&id).map(|(k, _)| k)
1381    }
1382}
1383
1384/// A [ParallelIterator] over this graph's nodes.
1385#[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/// A [ParallelIterator] over this graph's edges.
1437#[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/// A [ParallelIterator] over this graph's edges by mutable reference.
1495#[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}