petgraph/
graphmap.rs

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

petgraph/
graphmap.rs
