petgraph/
graphmap.rs

1//! `GraphMap<N, E, Ty>` is a graph datastructure where node values are mapping
2//! keys.
3
4#[cfg(feature = "std")]
5use std::{
6    cmp::Ordering,
7    fmt,
8    hash::{self, Hash},
9    iter::{Cloned, DoubleEndedIterator, FromIterator},
10    marker::PhantomData,
11    ops::{Deref, Index, IndexMut},
12    slice::Iter,
13};
14
15#[cfg(not(feature = "std"))]
16use core::{
17    cmp::Ordering,
18    fmt,
19    hash::{self, Hash},
20    iter::{Cloned, DoubleEndedIterator, FromIterator},
21    marker::PhantomData,
22    ops::{Deref, Index, IndexMut},
23    slice::Iter,
24};
25
26#[cfg(not(feature = "std"))]
27use alloc::vec::Vec;
28
29use indexmap::map::Keys;
30use indexmap::map::{Iter as IndexMapIter, IterMut as IndexMapIterMut};
31
32#[cfg(feature = "std")]
33type IndexMap<K, V> = indexmap::IndexMap<K, V>;
34
35#[cfg(not(feature = "std"))]
36type IndexMap<K, V> = indexmap::IndexMap<K, V, core::hash::BuildHasherDefault<twox_hash::XxHash64>>;
37
38use crate::{Directed, Direction, EdgeType, Incoming, Outgoing, Undirected};
39
40use crate::graph::node_index;
41use crate::graph::Graph;
42use crate::visit::{IntoEdgeReferences, IntoEdges, NodeCompactIndexable};
43use crate::visit::{IntoNodeIdentifiers, IntoNodeReferences, NodeCount, NodeIndexable};
44use crate::IntoWeightedEdge;
45
46/// A `GraphMap` with undirected edges.
47///
48/// For example, an edge between *1* and *2* is equivalent to an edge between
49/// *2* and *1*.
50pub type UnGraphMap<N, E> = GraphMap<N, E, Undirected>;
51/// A `GraphMap` with directed edges.
52///
53/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
54/// *1*.
55pub type DiGraphMap<N, E> = GraphMap<N, E, Directed>;
56
57/// `GraphMap<N, E, Ty>` is a graph datastructure using an associative array
58/// of its node weights `N`.
59///
60/// It uses an combined adjacency list and sparse adjacency matrix
61/// representation, using **O(|V| + |E|)** space, and allows testing for edge
62/// existence in constant time.
63///
64/// `GraphMap` is parameterized over:
65///
66/// - Associated data `N` for nodes and `E` for edges, called *weights*.
67/// - The node weight `N` must implement `Copy` and will be used as node
68/// identifier, duplicated into several places in the data structure.
69/// It must be suitable as a hash table key (implementing `Eq + Hash`).
70/// The node type must also implement `Ord` so that the implementation can
71/// order the pair (`a`, `b`) for an edge connecting any two nodes `a` and `b`.
72/// - `E` can be of arbitrary type.
73/// - Edge type `Ty` that determines whether the graph edges are directed or
74/// undirected.
75///
76/// You can use the type aliases `UnGraphMap` and `DiGraphMap` for convenience.
77///
78/// `GraphMap` does not allow parallel edges, but self loops are allowed.
79///
80/// Depends on crate feature `graphmap` (default).
81#[derive(Clone)]
82pub struct GraphMap<N, E, Ty> {
83    nodes: IndexMap<N, Vec<(N, CompactDirection)>>,
84    edges: IndexMap<(N, N), E>,
85    ty: PhantomData<Ty>,
86}
87
88impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType> fmt::Debug for GraphMap<N, E, Ty> {
89    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
90        self.nodes.fmt(f)
91    }
92}
93
94/// A trait group for `GraphMap`'s node identifier.
95pub trait NodeTrait: Copy + Ord + Hash {}
96impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
97
98// non-repr(usize) version of Direction
99#[derive(Copy, Clone, Debug, PartialEq)]
100enum CompactDirection {
101    Outgoing,
102    Incoming,
103}
104
105impl From<Direction> for CompactDirection {
106    fn from(d: Direction) -> Self {
107        match d {
108            Outgoing => CompactDirection::Outgoing,
109            Incoming => CompactDirection::Incoming,
110        }
111    }
112}
113
114impl PartialEq<Direction> for CompactDirection {
115    fn eq(&self, rhs: &Direction) -> bool {
116        (*self as usize) == (*rhs as usize)
117    }
118}
119
120impl<N, E, Ty> GraphMap<N, E, Ty>
121where
122    N: NodeTrait,
123    Ty: EdgeType,
124{
125    /// Create a new `GraphMap`
126    pub fn new() -> Self {
127        Self::default()
128    }
129
130    /// Create a new `GraphMap` with estimated capacity.
131    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
132        GraphMap {
133            nodes: {
134                #[cfg(feature = "std")] {
135                    IndexMap::with_capacity(nodes)
136                }
137                
138                #[cfg(not(feature = "std"))] {
139                    IndexMap::with_capacity_and_hasher(nodes, Default::default())
140                }
141            },
142            edges: {
143                #[cfg(feature = "std")] {
144                    IndexMap::with_capacity(edges)
145                }
146
147                #[cfg(not(feature = "std"))] {
148                    IndexMap::with_capacity_and_hasher(edges, Default::default())
149                }
150            },
151            ty: PhantomData,
152        }
153    }
154
155    /// Return the current node and edge capacity of the graph.
156    pub fn capacity(&self) -> (usize, usize) {
157        (self.nodes.capacity(), self.edges.capacity())
158    }
159
160    /// Use their natural order to map the node pair (a, b) to a canonical edge id.
161    #[inline]
162    fn edge_key(a: N, b: N) -> (N, N) {
163        if Ty::is_directed() || a <= b {
164            (a, b)
165        } else {
166            (b, a)
167        }
168    }
169
170    /// Whether the graph has directed edges.
171    pub fn is_directed(&self) -> bool {
172        Ty::is_directed()
173    }
174
175    /// Create a new `GraphMap` from an iterable of edges.
176    ///
177    /// Node values are taken directly from the list.
178    /// Edge weights `E` may either be specified in the list,
179    /// or they are filled with default values.
180    ///
181    /// Nodes are inserted automatically to match the edges.
182    ///
183    /// ```
184    /// use petgraph::graphmap::UnGraphMap;
185    ///
186    /// // Create a new undirected GraphMap.
187    /// // Use a type hint to have `()` be the edge weight type.
188    /// let gr = UnGraphMap::<_, ()>::from_edges(&[
189    ///     (0, 1), (0, 2), (0, 3),
190    ///     (1, 2), (1, 3),
191    ///     (2, 3),
192    /// ]);
193    /// ```
194    pub fn from_edges<I>(iterable: I) -> Self
195    where
196        I: IntoIterator,
197        I::Item: IntoWeightedEdge<E, NodeId = N>,
198    {
199        Self::from_iter(iterable)
200    }
201
202    /// Return the number of nodes in the graph.
203    pub fn node_count(&self) -> usize {
204        self.nodes.len()
205    }
206
207    /// Return the number of edges in the graph.
208    pub fn edge_count(&self) -> usize {
209        self.edges.len()
210    }
211
212    /// Remove all nodes and edges
213    pub fn clear(&mut self) {
214        self.nodes.clear();
215        self.edges.clear();
216    }
217
218    /// Add node `n` to the graph.
219    pub fn add_node(&mut self, n: N) -> N {
220        self.nodes.entry(n).or_insert(Vec::new());
221        n
222    }
223
224    /// Return `true` if node `n` was removed.
225    ///
226    /// Computes in **O(V)** time, due to the removal of edges with other nodes.
227    pub fn remove_node(&mut self, n: N) -> bool {
228        let links = match self.nodes.swap_remove(&n) {
229            None => return false,
230            Some(sus) => sus,
231        };
232        for (succ, _) in links {
233            // remove all successor links
234            self.remove_single_edge(&succ, &n, Incoming);
235            // Remove all edge values
236            self.edges.swap_remove(&Self::edge_key(n, succ));
237        }
238        true
239    }
240
241    /// Return `true` if the node is contained in the graph.
242    pub fn contains_node(&self, n: N) -> bool {
243        self.nodes.contains_key(&n)
244    }
245
246    /// Add an edge connecting `a` and `b` to the graph, with associated
247    /// data `weight`. For a directed graph, the edge is directed from `a`
248    /// to `b`.
249    ///
250    /// Inserts nodes `a` and/or `b` if they aren't already part of the graph.
251    ///
252    /// Return `None` if the edge did not previously exist, otherwise,
253    /// the associated data is updated and the old value is returned
254    /// as `Some(old_weight)`.
255    ///
256    /// ```
257    /// // Create a GraphMap with directed edges, and add one edge to it
258    /// use petgraph::graphmap::DiGraphMap;
259    ///
260    /// let mut g = DiGraphMap::new();
261    /// g.add_edge("x", "y", -1);
262    /// assert_eq!(g.node_count(), 2);
263    /// assert_eq!(g.edge_count(), 1);
264    /// assert!(g.contains_edge("x", "y"));
265    /// assert!(!g.contains_edge("y", "x"));
266    /// ```
267    pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
268        if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) {
269            old
270        } else {
271            // insert in the adjacency list if it's a new edge
272            self.nodes
273                .entry(a)
274                .or_insert_with(|| Vec::with_capacity(1))
275                .push((b, CompactDirection::Outgoing));
276            if a != b {
277                // self loops don't have the Incoming entry
278                self.nodes
279                    .entry(b)
280                    .or_insert_with(|| Vec::with_capacity(1))
281                    .push((a, CompactDirection::Incoming));
282            }
283            None
284        }
285    }
286
287    /// Remove edge relation from a to b
288    ///
289    /// Return `true` if it did exist.
290    fn remove_single_edge(&mut self, a: &N, b: &N, dir: Direction) -> bool {
291        match self.nodes.get_mut(a) {
292            None => false,
293            Some(sus) => {
294                if Ty::is_directed() {
295                    match sus
296                        .iter()
297                        .position(|elt| elt == &(*b, CompactDirection::from(dir)))
298                    {
299                        Some(index) => {
300                            sus.swap_remove(index);
301                            true
302                        }
303                        None => false,
304                    }
305                } else {
306                    match sus.iter().position(|elt| &elt.0 == b) {
307                        Some(index) => {
308                            sus.swap_remove(index);
309                            true
310                        }
311                        None => false,
312                    }
313                }
314            }
315        }
316    }
317
318    /// Remove edge from `a` to `b` from the graph and return the edge weight.
319    ///
320    /// Return `None` if the edge didn't exist.
321    ///
322    /// ```
323    /// // Create a GraphMap with undirected edges, and add and remove an edge.
324    /// use petgraph::graphmap::UnGraphMap;
325    ///
326    /// let mut g = UnGraphMap::new();
327    /// g.add_edge("x", "y", -1);
328    ///
329    /// let edge_data = g.remove_edge("y", "x");
330    /// assert_eq!(edge_data, Some(-1));
331    /// assert_eq!(g.edge_count(), 0);
332    /// ```
333    pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
334        let exist1 = self.remove_single_edge(&a, &b, Outgoing);
335        let exist2 = if a != b {
336            self.remove_single_edge(&b, &a, Incoming)
337        } else {
338            exist1
339        };
340        let weight = self.edges.remove(&Self::edge_key(a, b));
341        debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
342        weight
343    }
344
345    /// Return `true` if the edge connecting `a` with `b` is contained in the graph.
346    pub fn contains_edge(&self, a: N, b: N) -> bool {
347        self.edges.contains_key(&Self::edge_key(a, b))
348    }
349
350    /// Return an iterator over the nodes of the graph.
351    ///
352    /// Iterator element type is `N`.
353    pub fn nodes(&self) -> Nodes<N> {
354        Nodes {
355            iter: self.nodes.keys().cloned(),
356        }
357    }
358
359    /// Return an iterator of all nodes with an edge starting from `a`.
360    ///
361    /// - `Directed`: Outgoing edges from `a`.
362    /// - `Undirected`: All edges from or to `a`.
363    ///
364    /// Produces an empty iterator if the node doesn't exist.<br>
365    /// Iterator element type is `N`.
366    pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> {
367        Neighbors {
368            iter: match self.nodes.get(&a) {
369                Some(neigh) => neigh.iter(),
370                None => [].iter(),
371            },
372            ty: self.ty,
373        }
374    }
375
376    /// Return an iterator of all neighbors that have an edge between them and
377    /// `a`, in the specified direction.
378    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
379    ///
380    /// - `Directed`, `Outgoing`: All edges from `a`.
381    /// - `Directed`, `Incoming`: All edges to `a`.
382    /// - `Undirected`: All edges from or to `a`.
383    ///
384    /// Produces an empty iterator if the node doesn't exist.<br>
385    /// Iterator element type is `N`.
386    pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> {
387        NeighborsDirected {
388            iter: match self.nodes.get(&a) {
389                Some(neigh) => neigh.iter(),
390                None => [].iter(),
391            },
392            start_node: a,
393            dir,
394            ty: self.ty,
395        }
396    }
397
398    /// Return an iterator of target nodes with an edge starting from `a`,
399    /// paired with their respective edge weights.
400    ///
401    /// - `Directed`: Outgoing edges from `a`.
402    /// - `Undirected`: All edges from or to `a`.
403    ///
404    /// Produces an empty iterator if the node doesn't exist.<br>
405    /// Iterator element type is `(N, &E)`.
406    pub fn edges(&self, from: N) -> Edges<N, E, Ty> {
407        Edges {
408            from,
409            iter: self.neighbors(from),
410            edges: &self.edges,
411        }
412    }
413
414    /// Return a reference to the edge weight connecting `a` with `b`, or
415    /// `None` if the edge does not exist in the graph.
416    pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
417        self.edges.get(&Self::edge_key(a, b))
418    }
419
420    /// Return a mutable reference to the edge weight connecting `a` with `b`, or
421    /// `None` if the edge does not exist in the graph.
422    pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
423        self.edges.get_mut(&Self::edge_key(a, b))
424    }
425
426    /// Return an iterator over all edges of the graph with their weight in arbitrary order.
427    ///
428    /// Iterator element type is `(N, N, &E)`
429    pub fn all_edges(&self) -> AllEdges<N, E, Ty> {
430        AllEdges {
431            inner: self.edges.iter(),
432            ty: self.ty,
433        }
434    }
435
436    /// Return an iterator over all edges of the graph in arbitrary order, with a mutable reference
437    /// to their weight.
438    ///
439    /// Iterator element type is `(N, N, &mut E)`
440    pub fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty> {
441        AllEdgesMut {
442            inner: self.edges.iter_mut(),
443            ty: self.ty,
444        }
445    }
446
447    /// Return a `Graph` that corresponds to this `GraphMap`.
448    ///
449    /// 1. Note that node and edge indices in the `Graph` have nothing in common
450    ///    with the `GraphMap`s node weights `N`. The node weights `N` are used as
451    ///    node weights in the resulting `Graph`, too.
452    /// 2. Note that the index type is user-chosen.
453    ///
454    /// Computes in **O(|V| + |E|)** time (average).
455    ///
456    /// **Panics** if the number of nodes or edges does not fit with
457    /// the resulting graph's index type.
458    pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
459    where
460        Ix: crate::graph::IndexType,
461    {
462        // assuming two successive iterations of the same hashmap produce the same order
463        let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
464        for (&node, _) in &self.nodes {
465            gr.add_node(node);
466        }
467        for ((a, b), edge_weight) in self.edges {
468            let (ai, _, _) = self.nodes.get_full(&a).unwrap();
469            let (bi, _, _) = self.nodes.get_full(&b).unwrap();
470            gr.add_edge(node_index(ai), node_index(bi), edge_weight);
471        }
472        gr
473    }
474}
475
476/// Create a new `GraphMap` from an iterable of edges.
477impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<N, E, Ty>
478where
479    Item: IntoWeightedEdge<E, NodeId = N>,
480    N: NodeTrait,
481    Ty: EdgeType,
482{
483    fn from_iter<I>(iterable: I) -> Self
484    where
485        I: IntoIterator<Item = Item>,
486    {
487        let iter = iterable.into_iter();
488        let (low, _) = iter.size_hint();
489        let mut g = Self::with_capacity(0, low);
490        g.extend(iter);
491        g
492    }
493}
494
495/// Extend the graph from an iterable of edges.
496///
497/// Nodes are inserted automatically to match the edges.
498impl<N, E, Ty, Item> Extend<Item> for GraphMap<N, E, Ty>
499where
500    Item: IntoWeightedEdge<E, NodeId = N>,
501    N: NodeTrait,
502    Ty: EdgeType,
503{
504    fn extend<I>(&mut self, iterable: I)
505    where
506        I: IntoIterator<Item = Item>,
507    {
508        let iter = iterable.into_iter();
509        let (low, _) = iter.size_hint();
510        self.edges.reserve(low);
511
512        for elt in iter {
513            let (source, target, weight) = elt.into_weighted_edge();
514            self.add_edge(source, target, weight);
515        }
516    }
517}
518
519iterator_wrap! {
520    impl (Iterator DoubleEndedIterator ExactSizeIterator) for
521    struct Nodes <'a, N> where { N: 'a + NodeTrait }
522    item: N,
523    iter: Cloned<Keys<'a, N, Vec<(N, CompactDirection)>>>,
524}
525
526pub struct Neighbors<'a, N, Ty = Undirected>
527where
528    N: 'a,
529    Ty: EdgeType,
530{
531    iter: Iter<'a, (N, CompactDirection)>,
532    ty: PhantomData<Ty>,
533}
534
535impl<'a, N, Ty> Iterator for Neighbors<'a, N, Ty>
536where
537    N: NodeTrait,
538    Ty: EdgeType,
539{
540    type Item = N;
541    fn next(&mut self) -> Option<N> {
542        if Ty::is_directed() {
543            (&mut self.iter)
544                .filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None })
545                .next()
546        } else {
547            self.iter.next().map(|&(n, _)| n)
548        }
549    }
550}
551
552pub struct NeighborsDirected<'a, N, Ty>
553where
554    N: 'a,
555    Ty: EdgeType,
556{
557    iter: Iter<'a, (N, CompactDirection)>,
558    start_node: N,
559    dir: Direction,
560    ty: PhantomData<Ty>,
561}
562
563impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty>
564where
565    N: NodeTrait,
566    Ty: EdgeType,
567{
568    type Item = N;
569    fn next(&mut self) -> Option<N> {
570        if Ty::is_directed() {
571            let self_dir = self.dir;
572            let start_node = self.start_node;
573            (&mut self.iter)
574                .filter_map(move |&(n, dir)| {
575                    if dir == self_dir || n == start_node {
576                        Some(n)
577                    } else {
578                        None
579                    }
580                })
581                .next()
582        } else {
583            self.iter.next().map(|&(n, _)| n)
584        }
585    }
586}
587
588pub struct Edges<'a, N, E: 'a, Ty>
589where
590    N: 'a + NodeTrait,
591    Ty: EdgeType,
592{
593    from: N,
594    edges: &'a IndexMap<(N, N), E>,
595    iter: Neighbors<'a, N, Ty>,
596}
597
598impl<'a, N, E, Ty> Iterator for Edges<'a, N, E, Ty>
599where
600    N: 'a + NodeTrait,
601    E: 'a,
602    Ty: EdgeType,
603{
604    type Item = (N, N, &'a E);
605    fn next(&mut self) -> Option<Self::Item> {
606        match self.iter.next() {
607            None => None,
608            Some(b) => {
609                let a = self.from;
610                match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) {
611                    None => unreachable!(),
612                    Some(edge) => Some((a, b, edge)),
613                }
614            }
615        }
616    }
617}
618
619impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty>
620where
621    N: NodeTrait,
622    Ty: EdgeType,
623{
624    type EdgeRef = (N, N, &'a E);
625    type EdgeReferences = AllEdges<'a, N, E, Ty>;
626    fn edge_references(self) -> Self::EdgeReferences {
627        self.all_edges()
628    }
629}
630
631pub struct AllEdges<'a, N, E: 'a, Ty>
632where
633    N: 'a + NodeTrait,
634{
635    inner: IndexMapIter<'a, (N, N), E>,
636    ty: PhantomData<Ty>,
637}
638
639impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
640where
641    N: 'a + NodeTrait,
642    E: 'a,
643    Ty: EdgeType,
644{
645    type Item = (N, N, &'a E);
646    fn next(&mut self) -> Option<Self::Item> {
647        match self.inner.next() {
648            None => None,
649            Some((&(a, b), v)) => Some((a, b, v)),
650        }
651    }
652
653    fn size_hint(&self) -> (usize, Option<usize>) {
654        self.inner.size_hint()
655    }
656
657    fn count(self) -> usize {
658        self.inner.count()
659    }
660
661    fn nth(&mut self, n: usize) -> Option<Self::Item> {
662        self.inner
663            .nth(n)
664            .map(|(&(n1, n2), weight)| (n1, n2, weight))
665    }
666
667    fn last(self) -> Option<Self::Item> {
668        self.inner
669            .last()
670            .map(|(&(n1, n2), weight)| (n1, n2, weight))
671    }
672}
673
674impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
675where
676    N: 'a + NodeTrait,
677    E: 'a,
678    Ty: EdgeType,
679{
680    fn next_back(&mut self) -> Option<Self::Item> {
681        self.inner
682            .next_back()
683            .map(|(&(n1, n2), weight)| (n1, n2, weight))
684    }
685}
686
687pub struct AllEdgesMut<'a, N, E: 'a, Ty>
688where
689    N: 'a + NodeTrait,
690{
691    inner: IndexMapIterMut<'a, (N, N), E>,
692    ty: PhantomData<Ty>,
693}
694
695impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty>
696where
697    N: 'a + NodeTrait,
698    E: 'a,
699    Ty: EdgeType,
700{
701    type Item = (N, N, &'a mut E);
702    fn next(&mut self) -> Option<Self::Item> {
703        self.inner
704            .next()
705            .map(|(&(n1, n2), weight)| (n1, n2, weight))
706    }
707
708    fn size_hint(&self) -> (usize, Option<usize>) {
709        self.inner.size_hint()
710    }
711
712    fn count(self) -> usize {
713        self.inner.count()
714    }
715
716    fn nth(&mut self, n: usize) -> Option<Self::Item> {
717        self.inner
718            .nth(n)
719            .map(|(&(n1, n2), weight)| (n1, n2, weight))
720    }
721
722    fn last(self) -> Option<Self::Item> {
723        self.inner
724            .last()
725            .map(|(&(n1, n2), weight)| (n1, n2, weight))
726    }
727}
728
729impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty>
730where
731    N: 'a + NodeTrait,
732    E: 'a,
733    Ty: EdgeType,
734{
735    fn next_back(&mut self) -> Option<Self::Item> {
736        self.inner
737            .next_back()
738            .map(|(&(n1, n2), weight)| (n1, n2, weight))
739    }
740}
741
742impl<'a, N: 'a, E: 'a, Ty> IntoEdges for &'a GraphMap<N, E, Ty>
743where
744    N: NodeTrait,
745    Ty: EdgeType,
746{
747    type Edges = Edges<'a, N, E, Ty>;
748    fn edges(self, a: Self::NodeId) -> Self::Edges {
749        self.edges(a)
750    }
751}
752
753/// Index `GraphMap` by node pairs to access edge weights.
754impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty>
755where
756    N: NodeTrait,
757    Ty: EdgeType,
758{
759    type Output = E;
760    fn index(&self, index: (N, N)) -> &E {
761        let index = Self::edge_key(index.0, index.1);
762        self.edge_weight(index.0, index.1)
763            .expect("GraphMap::index: no such edge")
764    }
765}
766
767/// Index `GraphMap` by node pairs to access edge weights.
768impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty>
769where
770    N: NodeTrait,
771    Ty: EdgeType,
772{
773    fn index_mut(&mut self, index: (N, N)) -> &mut E {
774        let index = Self::edge_key(index.0, index.1);
775        self.edge_weight_mut(index.0, index.1)
776            .expect("GraphMap::index: no such edge")
777    }
778}
779
780/// Create a new empty `GraphMap`.
781impl<N, E, Ty> Default for GraphMap<N, E, Ty>
782where
783    N: NodeTrait,
784    Ty: EdgeType,
785{
786    fn default() -> Self {
787        GraphMap::with_capacity(0, 0)
788    }
789}
790
791/// A reference that is hashed and compared by its pointer value.
792///
793/// `Ptr` is used for certain configurations of `GraphMap`,
794/// in particular in the combination where the node type for
795/// `GraphMap` is something of type for example `Ptr(&Cell<T>)`,
796/// with the `Cell<T>` being `TypedArena` allocated.
797pub struct Ptr<'b, T: 'b>(pub &'b T);
798
799impl<'b, T> Copy for Ptr<'b, T> {}
800impl<'b, T> Clone for Ptr<'b, T> {
801    fn clone(&self) -> Self {
802        *self
803    }
804}
805
806fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
807    a == b
808}
809
810impl<'b, T> PartialEq for Ptr<'b, T> {
811    /// Ptr compares by pointer equality, i.e if they point to the same value
812    fn eq(&self, other: &Ptr<'b, T>) -> bool {
813        ptr_eq(self.0, other.0)
814    }
815}
816
817impl<'b, T> PartialOrd for Ptr<'b, T> {
818    fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
819        Some(self.cmp(other))
820    }
821}
822
823impl<'b, T> Ord for Ptr<'b, T> {
824    /// Ptr is ordered by pointer value, i.e. an arbitrary but stable and total order.
825    fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
826        let a: *const T = self.0;
827        let b: *const T = other.0;
828        a.cmp(&b)
829    }
830}
831
832impl<'b, T> Deref for Ptr<'b, T> {
833    type Target = T;
834    fn deref(&self) -> &T {
835        self.0
836    }
837}
838
839impl<'b, T> Eq for Ptr<'b, T> {}
840
841impl<'b, T> Hash for Ptr<'b, T> {
842    fn hash<H: hash::Hasher>(&self, st: &mut H) {
843        let ptr = (self.0) as *const T;
844        ptr.hash(st)
845    }
846}
847
848impl<'b, T: fmt::Debug> fmt::Debug for Ptr<'b, T> {
849    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
850        self.0.fmt(f)
851    }
852}
853
854impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty>
855where
856    N: NodeTrait,
857    Ty: EdgeType,
858{
859    type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>;
860
861    fn node_identifiers(self) -> Self::NodeIdentifiers {
862        NodeIdentifiers {
863            iter: self.nodes.iter(),
864            ty: self.ty,
865            edge_ty: PhantomData,
866        }
867    }
868}
869
870impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty>
871where
872    N: NodeTrait,
873    Ty: EdgeType,
874{
875    fn node_count(&self) -> usize {
876        (*self).node_count()
877    }
878}
879
880pub struct NodeIdentifiers<'a, N, E: 'a, Ty>
881where
882    N: 'a + NodeTrait,
883{
884    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
885    ty: PhantomData<Ty>,
886    edge_ty: PhantomData<E>,
887}
888
889impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty>
890where
891    N: 'a + NodeTrait,
892    E: 'a,
893    Ty: EdgeType,
894{
895    type Item = N;
896    fn next(&mut self) -> Option<Self::Item> {
897        self.iter.next().map(|(&n, _)| n)
898    }
899}
900
901impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty>
902where
903    N: NodeTrait,
904    Ty: EdgeType,
905{
906    type NodeRef = (N, &'a N);
907    type NodeReferences = NodeReferences<'a, N, E, Ty>;
908    fn node_references(self) -> Self::NodeReferences {
909        NodeReferences {
910            iter: self.nodes.iter(),
911            ty: self.ty,
912            edge_ty: PhantomData,
913        }
914    }
915}
916
917pub struct NodeReferences<'a, N, E: 'a, Ty>
918where
919    N: 'a + NodeTrait,
920{
921    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
922    ty: PhantomData<Ty>,
923    edge_ty: PhantomData<E>,
924}
925
926impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty>
927where
928    N: 'a + NodeTrait,
929    E: 'a,
930    Ty: EdgeType,
931{
932    type Item = (N, &'a N);
933    fn next(&mut self) -> Option<Self::Item> {
934        self.iter.next().map(|(n, _)| (*n, n))
935    }
936}
937
938impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty>
939where
940    N: NodeTrait,
941    Ty: EdgeType,
942{
943    fn node_bound(&self) -> usize {
944        self.node_count()
945    }
946    fn to_index(&self, ix: Self::NodeId) -> usize {
947        let (i, _, _) = self.nodes.get_full(&ix).unwrap();
948        i
949    }
950    fn from_index(&self, ix: usize) -> Self::NodeId {
951        let (&key, _) = self.nodes.get_index(ix).unwrap();
952        key
953    }
954}
955
956impl<N, E, Ty> NodeCompactIndexable for GraphMap<N, E, Ty>
957where
958    N: NodeTrait,
959    Ty: EdgeType,
960{
961}
petgraph/graphmap.rs

petgraph/
graphmap.rs
