petgraph/
graphmap.rs

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

petgraph/
graphmap.rs
