petgraph/graph_impl/
mod.rs

1use std::cmp;
2use std::fmt;
3use std::hash::Hash;
4use std::iter;
5use std::marker::PhantomData;
6use std::mem::size_of;
7use std::ops::{Index, IndexMut, Range};
8use std::slice;
9
10use {
11    Direction, Outgoing, Incoming,
12    Undirected,
13    Directed,
14    EdgeType,
15    IntoWeightedEdge,
16};
17
18use iter_format::{
19    IterFormatExt,
20    NoPretty,
21    DebugMap,
22};
23
24use visit::EdgeRef;
25use visit::{IntoNodeReferences, IntoEdges, IntoEdgesDirected};
26use util::enumerate;
27
28#[cfg(feature = "serde-1")]
29mod serialization;
30
31
32/// The default integer type for graph indices.
33/// `u32` is the default to reduce the size of the graph's data and improve
34/// performance in the common case.
35///
36/// Used for node and edge indices in `Graph` and `StableGraph`, used
37/// for node indices in `Csr`.
38pub type DefaultIx = u32;
39
40/// Trait for the unsigned integer type used for node and edge indices.
41///
42/// Marked `unsafe` because: the trait must faithfully preseve
43/// and convert index values.
44pub unsafe trait IndexType : Copy + Default + Hash + Ord + fmt::Debug + 'static
45{
46    fn new(x: usize) -> Self;
47    fn index(&self) -> usize;
48    fn max() -> Self;
49}
50
51unsafe impl IndexType for usize {
52    #[inline(always)]
53    fn new(x: usize) -> Self { x }
54    #[inline(always)]
55    fn index(&self) -> Self { *self }
56    #[inline(always)]
57    fn max() -> Self { ::std::usize::MAX }
58}
59
60unsafe impl IndexType for u32 {
61    #[inline(always)]
62    fn new(x: usize) -> Self { x as u32 }
63    #[inline(always)]
64    fn index(&self) -> usize { *self as usize }
65    #[inline(always)]
66    fn max() -> Self { ::std::u32::MAX }
67}
68
69unsafe impl IndexType for u16 {
70    #[inline(always)]
71    fn new(x: usize) -> Self { x as u16 }
72    #[inline(always)]
73    fn index(&self) -> usize { *self as usize }
74    #[inline(always)]
75    fn max() -> Self { ::std::u16::MAX }
76}
77
78unsafe impl IndexType for u8 {
79    #[inline(always)]
80    fn new(x: usize) -> Self { x as u8 }
81    #[inline(always)]
82    fn index(&self) -> usize { *self as usize }
83    #[inline(always)]
84    fn max() -> Self { ::std::u8::MAX }
85}
86
87/// Node identifier.
88#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash)]
89pub struct NodeIndex<Ix=DefaultIx>(Ix);
90
91impl<Ix: IndexType> NodeIndex<Ix>
92{
93    #[inline]
94    pub fn new(x: usize) -> Self {
95        NodeIndex(IndexType::new(x))
96    }
97
98    #[inline]
99    pub fn index(self) -> usize
100    {
101        self.0.index()
102    }
103
104    #[inline]
105    pub fn end() -> Self
106    {
107        NodeIndex(IndexType::max())
108    }
109
110    fn _into_edge(self) -> EdgeIndex<Ix> {
111        EdgeIndex(self.0)
112    }
113}
114
115impl<Ix: IndexType> From<Ix> for NodeIndex<Ix> {
116    fn from(ix: Ix) -> Self { NodeIndex(ix) }
117}
118
119impl<Ix: fmt::Debug> fmt::Debug for NodeIndex<Ix>
120{
121    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122        write!(f, "NodeIndex({:?})", self.0)
123    }
124}
125
126/// Short version of `NodeIndex::new`
127pub fn node_index<Ix: IndexType>(index: usize) -> NodeIndex<Ix> { NodeIndex::new(index) }
128
129/// Short version of `EdgeIndex::new`
130pub fn edge_index<Ix: IndexType>(index: usize) -> EdgeIndex<Ix> { EdgeIndex::new(index) }
131
132/// Edge identifier.
133#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash)]
134pub struct EdgeIndex<Ix=DefaultIx>(Ix);
135
136impl<Ix: IndexType> EdgeIndex<Ix>
137{
138    #[inline]
139    pub fn new(x: usize) -> Self {
140        EdgeIndex(IndexType::new(x))
141    }
142
143    #[inline]
144    pub fn index(self) -> usize
145    {
146        self.0.index()
147    }
148
149    /// An invalid `EdgeIndex` used to denote absence of an edge, for example
150    /// to end an adjacency list.
151    #[inline]
152    pub fn end() -> Self {
153        EdgeIndex(IndexType::max())
154    }
155
156    fn _into_node(self) -> NodeIndex<Ix> {
157        NodeIndex(self.0)
158    }
159}
160
161impl<Ix: fmt::Debug> fmt::Debug for EdgeIndex<Ix>
162{
163    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
164        write!(f, "EdgeIndex({:?})", self.0)
165    }
166}
167/*
168 * FIXME: Use this impl again, when we don't need to add so many bounds
169impl<Ix: IndexType> fmt::Debug for EdgeIndex<Ix>
170{
171    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
172        try!(write!(f, "EdgeIndex("));
173        if *self == EdgeIndex::end() {
174            try!(write!(f, "End"));
175        } else {
176            try!(write!(f, "{}", self.index()));
177        }
178        write!(f, ")")
179    }
180}
181*/
182
183const DIRECTIONS: [Direction; 2] = [Outgoing, Incoming];
184
185/// The graph's node type.
186#[derive(Debug)]
187pub struct Node<N, Ix = DefaultIx> {
188    /// Associated node data.
189    pub weight: N,
190    /// Next edge in outgoing and incoming edge lists.
191    next: [EdgeIndex<Ix>; 2],
192}
193
194impl<E, Ix> Clone for Node<E, Ix> where E: Clone, Ix: Copy {
195    clone_fields!(Node,
196                  weight,
197                  next,
198                  );
199}
200
201
202impl<N, Ix: IndexType> Node<N, Ix>
203{
204    /// Accessor for data structure internals: the first edge in the given direction.
205    pub fn next_edge(&self, dir: Direction) -> EdgeIndex<Ix>
206    {
207        self.next[dir.index()]
208    }
209}
210
211
212/// The graph's edge type.
213#[derive(Debug)]
214pub struct Edge<E, Ix = DefaultIx> {
215    /// Associated edge data.
216    pub weight: E,
217    /// Next edge in outgoing and incoming edge lists.
218    next: [EdgeIndex<Ix>; 2],
219    /// Start and End node index
220    node: [NodeIndex<Ix>; 2],
221}
222
223impl<E, Ix> Clone for Edge<E, Ix> where E: Clone, Ix: Copy {
224    clone_fields!(Edge,
225                  weight,
226                  next,
227                  node,
228                  );
229}
230
231impl<E, Ix: IndexType> Edge<E, Ix>
232{
233    /// Accessor for data structure internals: the next edge for the given direction.
234    pub fn next_edge(&self, dir: Direction) -> EdgeIndex<Ix>
235    {
236        self.next[dir.index()]
237    }
238
239    /// Return the source node index.
240    pub fn source(&self) -> NodeIndex<Ix>
241    {
242        self.node[0]
243    }
244
245    /// Return the target node index.
246    pub fn target(&self) -> NodeIndex<Ix>
247    {
248        self.node[1]
249    }
250}
251
252/// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation.
253///
254/// `Graph` is parameterized over:
255///
256/// - Associated data `N` for nodes and `E` for edges, called *weights*.
257///   The associated data can be of arbitrary type.
258/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
259/// - Index type `Ix`, which determines the maximum size of the graph.
260///
261/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert,
262/// efficient graph search and graph algorithms.
263/// It implements **O(e')** edge lookup and edge and node removals, where **e'**
264/// is some local measure of edge count.
265/// Based on the graph datastructure used in rustc.
266///
267/// Here's an example of building a graph with directed edges, and below
268/// an illustration of how it could be rendered with graphviz (see
269/// [`Dot`](../dot/struct.Dot.html)):
270///
271/// ```
272/// use petgraph::Graph;
273///
274/// let mut deps = Graph::<&str, &str>::new();
275/// let pg = deps.add_node("petgraph");
276/// let fb = deps.add_node("fixedbitset");
277/// let qc = deps.add_node("quickcheck");
278/// let rand = deps.add_node("rand");
279/// let libc = deps.add_node("libc");
280/// deps.extend_with_edges(&[
281///     (pg, fb), (pg, qc),
282///     (qc, rand), (rand, libc), (qc, libc),
283/// ]);
284/// ```
285///
286/// ![graph-example](https://bluss.github.io/ndarray/images/graph-example.svg)
287///
288/// ### Graph Indices
289///
290/// The graph maintains indices for nodes and edges, and node and edge
291/// weights may be accessed mutably. Indices range in a compact interval, for
292/// example for *n* nodes indices are 0 to *n* - 1 inclusive.
293///
294/// `NodeIndex` and `EdgeIndex` are types that act as references to nodes and edges,
295/// but these are only stable across certain operations.
296/// **Adding nodes or edges keeps indices stable.
297/// Removing nodes or edges may shift other indices.**
298/// Removing a node will force the last node to shift its index to
299/// take its place. Similarly, removing an edge shifts the index of the last edge.
300///
301/// The `Ix` parameter is `u32` by default. The goal is that you can ignore this parameter
302/// completely unless you need a very big graph -- then you can use `usize`.
303///
304/// ### Pros and Cons of Indices
305///
306/// * The fact that the node and edge indices in the graph each are numbered in compact
307/// intervals (from 0 to *n* - 1 for *n* nodes) simplifies some graph algorithms.
308///
309/// * You can select graph index integer type after the size of the graph. A smaller
310/// size may have better performance.
311///
312/// * Using indices allows mutation while traversing the graph, see `Dfs`,
313/// and `.neighbors(a).detach()`.
314///
315/// * You can create several graphs using the equal node indices but with
316/// differing weights or differing edges.
317///
318/// * The `Graph` is a regular rust collection and is `Send` and `Sync` (as long
319/// as associated data `N` and `E` are).
320///
321/// * Some indices shift during node or edge removal, so that is a drawback
322/// of removing elements. Indices don't allow as much compile time checking as
323/// references.
324///
325pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
326    nodes: Vec<Node<N, Ix>>,
327    edges: Vec<Edge<E, Ix>>,
328    ty: PhantomData<Ty>,
329}
330
331/// A `Graph` with directed edges.
332///
333/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
334/// *1*.
335pub type DiGraph<N, E, Ix = DefaultIx> = Graph<N, E, Directed, Ix>;
336
337/// A `Graph` with undirected edges.
338///
339/// For example, an edge between *1* and *2* is equivalent to an edge between
340/// *2* and *1*.
341pub type UnGraph<N, E, Ix = DefaultIx> = Graph<N, E, Undirected, Ix>;
342
343
344/// The resulting cloned graph has the same graph indices as `self`.
345impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix>
346    where N: Clone, E: Clone,
347{
348    fn clone(&self) -> Self {
349        Graph {
350            nodes: self.nodes.clone(),
351            edges: self.edges.clone(),
352            ty: self.ty,
353        }
354    }
355
356    fn clone_from(&mut self, rhs: &Self) {
357        self.nodes.clone_from(&rhs.nodes);
358        self.edges.clone_from(&rhs.edges);
359        self.ty = rhs.ty;
360    }
361}
362
363impl<N, E, Ty, Ix> fmt::Debug for Graph<N, E, Ty, Ix>
364    where N: fmt::Debug,
365          E: fmt::Debug,
366          Ty: EdgeType,
367          Ix: IndexType,
368{
369    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
370        let etype = if self.is_directed() { "Directed" } else { "Undirected" };
371        let mut fmt_struct = f.debug_struct("Graph");
372        fmt_struct.field("Ty", &etype);
373        fmt_struct.field("node_count", &self.node_count());
374        fmt_struct.field("edge_count", &self.edge_count());
375        if self.edge_count() > 0 {
376            fmt_struct.field("edges",
377                 &self.edges
378                     .iter()
379                     .map(|e| NoPretty((e.source().index(), e.target().index())))
380                     .format(", "));
381        }
382        // skip weights if they are ZST!
383        if size_of::<N>() != 0 {
384            fmt_struct.field("node weights", &DebugMap(|| self.nodes.iter()
385                             .map(|n| &n.weight)
386                             .enumerate()));
387        }
388        if size_of::<E>() != 0 {
389            fmt_struct.field("edge weights", &DebugMap(|| self.edges.iter()
390                             .map(|n| &n.weight)
391                             .enumerate()));
392        }
393        fmt_struct.finish()
394    }
395}
396
397enum Pair<T> {
398    Both(T, T),
399    One(T),
400    None,
401}
402
403use std::cmp::max;
404
405/// Get mutable references at index `a` and `b`.
406fn index_twice<T>(slc: &mut [T], a: usize, b: usize) -> Pair<&mut T> {
407    if max(a, b) >= slc.len() {
408        Pair::None
409    } else if a == b {
410        Pair::One(&mut slc[max(a, b)])
411    } else {
412        // safe because a, b are in bounds and distinct
413        unsafe {
414            let ar = &mut *(slc.get_unchecked_mut(a) as *mut _);
415            let br = &mut *(slc.get_unchecked_mut(b) as *mut _);
416            Pair::Both(ar, br)
417        }
418    }
419}
420
421impl<N, E> Graph<N, E, Directed>
422{
423    /// Create a new `Graph` with directed edges.
424    ///
425    /// This is a convenience method. Use `Graph::with_capacity` or `Graph::default` for
426    /// a constructor that is generic in all the type parameters of `Graph`.
427    pub fn new() -> Self
428    {
429        Graph{nodes: Vec::new(), edges: Vec::new(),
430              ty: PhantomData}
431    }
432}
433
434impl<N, E> Graph<N, E, Undirected>
435{
436    /// Create a new `Graph` with undirected edges.
437    ///
438    /// This is a convenience method. Use `Graph::with_capacity` or `Graph::default` for
439    /// a constructor that is generic in all the type parameters of `Graph`.
440    pub fn new_undirected() -> Self
441    {
442        Graph{nodes: Vec::new(), edges: Vec::new(),
443              ty: PhantomData}
444    }
445}
446
447impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix>
448    where Ty: EdgeType,
449          Ix: IndexType,
450{
451    /// Create a new `Graph` with estimated capacity.
452    pub fn with_capacity(nodes: usize, edges: usize) -> Self
453    {
454        Graph{nodes: Vec::with_capacity(nodes), edges: Vec::with_capacity(edges),
455              ty: PhantomData}
456    }
457
458    /// Return the number of nodes (vertices) in the graph.
459    ///
460    /// Computes in **O(1)** time.
461    pub fn node_count(&self) -> usize
462    {
463        self.nodes.len()
464    }
465
466    /// Return the number of edges in the graph.
467    ///
468    /// Computes in **O(1)** time.
469    pub fn edge_count(&self) -> usize
470    {
471        self.edges.len()
472    }
473
474    /// Whether the graph has directed edges or not.
475    #[inline]
476    pub fn is_directed(&self) -> bool
477    {
478        Ty::is_directed()
479    }
480
481    /// Add a node (also called vertex) with associated data `weight` to the graph.
482    ///
483    /// Computes in **O(1)** time.
484    ///
485    /// Return the index of the new node.
486    ///
487    /// **Panics** if the Graph is at the maximum number of nodes for its index
488    /// type (N/A if usize).
489    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>
490    {
491        let node = Node{weight: weight, next: [EdgeIndex::end(), EdgeIndex::end()]};
492        let node_idx = NodeIndex::new(self.nodes.len());
493        // check for max capacity, except if we use usize
494        assert!(<Ix as IndexType>::max().index() == !0 || NodeIndex::end() != node_idx);
495        self.nodes.push(node);
496        node_idx
497    }
498
499    /// Access the weight for node `a`.
500    ///
501    /// Also available with indexing syntax: `&graph[a]`.
502    pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>
503    {
504        self.nodes.get(a.index()).map(|n| &n.weight)
505    }
506
507    /// Access the weight for node `a`, mutably.
508    ///
509    /// Also available with indexing syntax: `&mut graph[a]`.
510    pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N>
511    {
512        self.nodes.get_mut(a.index()).map(|n| &mut n.weight)
513    }
514
515    /// Add an edge from `a` to `b` to the graph, with its associated
516    /// data `weight`.
517    ///
518    /// Return the index of the new edge.
519    ///
520    /// Computes in **O(1)** time.
521    ///
522    /// **Panics** if any of the nodes don't exist.<br>
523    /// **Panics** if the Graph is at the maximum number of edges for its index
524    /// type (N/A if usize).
525    ///
526    /// **Note:** `Graph` allows adding parallel (“duplicate”) edges. If you want
527    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
528    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix>
529    {
530        let edge_idx = EdgeIndex::new(self.edges.len());
531        assert!(<Ix as IndexType>::max().index() == !0 || EdgeIndex::end() != edge_idx);
532        let mut edge = Edge {
533            weight: weight,
534            node: [a, b],
535            next: [EdgeIndex::end(); 2],
536        };
537        match index_twice(&mut self.nodes, a.index(), b.index()) {
538            Pair::None => panic!("Graph::add_edge: node indices out of bounds"),
539            Pair::One(an) => {
540                edge.next = an.next;
541                an.next[0] = edge_idx;
542                an.next[1] = edge_idx;
543            }
544            Pair::Both(an, bn) => {
545                // a and b are different indices
546                edge.next = [an.next[0], bn.next[1]];
547                an.next[0] = edge_idx;
548                bn.next[1] = edge_idx;
549            }
550        }
551        self.edges.push(edge);
552        edge_idx
553    }
554
555    /// Add or update an edge from `a` to `b`.
556    /// If the edge already exists, its weight is updated.
557    ///
558    /// Return the index of the affected edge.
559    ///
560    /// Computes in **O(e')** time, where **e'** is the number of edges
561    /// connected to `a` (and `b`, if the graph edges are undirected).
562    ///
563    /// **Panics** if any of the nodes don't exist.
564    pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix>
565    {
566        if let Some(ix) = self.find_edge(a, b) {
567            if let Some(ed) = self.edge_weight_mut(ix) {
568                *ed = weight;
569                return ix;
570            }
571        }
572        self.add_edge(a, b, weight)
573    }
574
575    /// Access the weight for edge `e`.
576    ///
577    /// Also available with indexing syntax: `&graph[e]`.
578    pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>
579    {
580        self.edges.get(e.index()).map(|ed| &ed.weight)
581    }
582
583    /// Access the weight for edge `e`, mutably.
584    ///
585    /// Also available with indexing syntax: `&mut graph[e]`.
586    pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E>
587    {
588        self.edges.get_mut(e.index()).map(|ed| &mut ed.weight)
589    }
590
591    /// Access the source and target nodes for `e`.
592    pub fn edge_endpoints(&self, e: EdgeIndex<Ix>)
593        -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>
594    {
595        self.edges.get(e.index()).map(|ed| (ed.source(), ed.target()))
596    }
597
598    /// Remove `a` from the graph if it exists, and return its weight.
599    /// If it doesn't exist in the graph, return `None`.
600    ///
601    /// Apart from `a`, this invalidates the last node index in the graph
602    /// (that node will adopt the removed node index). Edge indices are
603    /// invalidated as they would be following the removal of each edge
604    /// with an endpoint in `a`.
605    ///
606    /// Computes in **O(e')** time, where **e'** is the number of affected
607    /// edges, including *n* calls to `.remove_edge()` where *n* is the number
608    /// of edges with an endpoint in `a`, and including the edges with an
609    /// endpoint in the displaced node.
610    pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N>
611    {
612        if self.nodes.get(a.index()).is_none() {
613            return None
614        }
615        for d in &DIRECTIONS {
616            let k = d.index();
617
618            // Remove all edges from and to this node.
619            loop {
620                let next = self.nodes[a.index()].next[k];
621                if next == EdgeIndex::end() {
622                    break
623                }
624                let ret = self.remove_edge(next);
625                debug_assert!(ret.is_some());
626                let _ = ret;
627            }
628        }
629
630        // Use swap_remove -- only the swapped-in node is going to change
631        // NodeIndex<Ix>, so we only have to walk its edges and update them.
632
633        let node = self.nodes.swap_remove(a.index());
634
635        // Find the edge lists of the node that had to relocate.
636        // It may be that no node had to relocate, then we are done already.
637        let swap_edges = match self.nodes.get(a.index()) {
638            None => return Some(node.weight),
639            Some(ed) => ed.next,
640        };
641
642        // The swapped element's old index
643        let old_index = NodeIndex::new(self.nodes.len());
644        let new_index = a;
645
646        // Adjust the starts of the out edges, and ends of the in edges.
647        for &d in &DIRECTIONS {
648            let k = d.index();
649            let mut edges = edges_walker_mut(&mut self.edges, swap_edges[k], d);
650            while let Some(curedge) = edges.next_edge() {
651                debug_assert!(curedge.node[k] == old_index);
652                curedge.node[k] = new_index;
653            }
654        }
655        Some(node.weight)
656    }
657
658    /// For edge `e` with endpoints `edge_node`, replace links to it,
659    /// with links to `edge_next`.
660    fn change_edge_links(&mut self, edge_node: [NodeIndex<Ix>; 2], e: EdgeIndex<Ix>,
661                         edge_next: [EdgeIndex<Ix>; 2])
662    {
663        for &d in &DIRECTIONS {
664            let k = d.index();
665            let node = match self.nodes.get_mut(edge_node[k].index()) {
666                Some(r) => r,
667                None => {
668                    debug_assert!(false, "Edge's endpoint dir={:?} index={:?} not found",
669                                  d, edge_node[k]);
670                    return
671                }
672            };
673            let fst = node.next[k];
674            if fst == e {
675                //println!("Updating first edge 0 for node {}, set to {}", edge_node[0], edge_next[0]);
676                node.next[k] = edge_next[k];
677            } else {
678                let mut edges = edges_walker_mut(&mut self.edges, fst, d);
679                while let Some(curedge) = edges.next_edge() {
680                    if curedge.next[k] == e {
681                        curedge.next[k] = edge_next[k];
682                        break; // the edge can only be present once in the list.
683                    }
684                }
685            }
686        }
687    }
688
689    /// Remove an edge and return its edge weight, or `None` if it didn't exist.
690    ///
691    /// Apart from `e`, this invalidates the last edge index in the graph
692    /// (that edge will adopt the removed edge index).
693    ///
694    /// Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for
695    /// the vertices of `e` and the vertices of another affected edge.
696    pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E>
697    {
698        // every edge is part of two lists,
699        // outgoing and incoming edges.
700        // Remove it from both
701        let (edge_node, edge_next) = match self.edges.get(e.index()) {
702            None => return None,
703            Some(x) => (x.node, x.next),
704        };
705        // Remove the edge from its in and out lists by replacing it with
706        // a link to the next in the list.
707        self.change_edge_links(edge_node, e, edge_next);
708        self.remove_edge_adjust_indices(e)
709    }
710
711    fn remove_edge_adjust_indices(&mut self, e: EdgeIndex<Ix>) -> Option<E>
712    {
713        // swap_remove the edge -- only the removed edge
714        // and the edge swapped into place are affected and need updating
715        // indices.
716        let edge = self.edges.swap_remove(e.index());
717        let swap = match self.edges.get(e.index()) {
718            // no elment needed to be swapped.
719            None => return Some(edge.weight),
720            Some(ed) => ed.node,
721        };
722        let swapped_e = EdgeIndex::new(self.edges.len());
723
724        // Update the edge lists by replacing links to the old index by references to the new
725        // edge index.
726        self.change_edge_links(swap, swapped_e, [e, e]);
727        Some(edge.weight)
728    }
729
730    /// Return an iterator of all nodes with an edge starting from `a`.
731    ///
732    /// - `Directed`: Outgoing edges from `a`.
733    /// - `Undirected`: All edges from or to `a`.
734    ///
735    /// Produces an empty iterator if the node doesn't exist.<br>
736    /// Iterator element type is `NodeIndex<Ix>`.
737    ///
738    /// Use [`.neighbors(a).detach()`][1] to get a neighbor walker that does
739    /// not borrow from the graph.
740    ///
741    /// [1]: struct.Neighbors.html#method.detach
742    pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>
743    {
744        self.neighbors_directed(a, Outgoing)
745    }
746
747    /// Return an iterator of all neighbors that have an edge between them and
748    /// `a`, in the specified direction.
749    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
750    ///
751    /// - `Directed`, `Outgoing`: All edges from `a`.
752    /// - `Directed`, `Incoming`: All edges to `a`.
753    /// - `Undirected`: All edges from or to `a`.
754    ///
755    /// Produces an empty iterator if the node doesn't exist.<br>
756    /// Iterator element type is `NodeIndex<Ix>`.
757    ///
758    /// For a `Directed` graph, neighbors are listed in reverse order of their
759    /// addition to the graph, so the most recently added edge's neighbor is
760    /// listed first. The order in an `Undirected` graph is arbitrary.
761    ///
762    /// Use [`.neighbors_directed(a, dir).detach()`][1] to get a neighbor walker that does
763    /// not borrow from the graph.
764    ///
765    /// [1]: struct.Neighbors.html#method.detach
766    pub fn neighbors_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Neighbors<E, Ix>
767    {
768        let mut iter = self.neighbors_undirected(a);
769        if self.is_directed() {
770            let k = dir.index();
771            iter.next[1 - k] = EdgeIndex::end();
772            iter.skip_start = NodeIndex::end();
773        }
774        iter
775    }
776
777    /// Return an iterator of all neighbors that have an edge between them and
778    /// `a`, in either direction.
779    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
780    ///
781    /// - `Directed` and `Undirected`: All edges from or to `a`.
782    ///
783    /// Produces an empty iterator if the node doesn't exist.<br>
784    /// Iterator element type is `NodeIndex<Ix>`.
785    ///
786    /// Use [`.neighbors_undirected(a).detach()`][1] to get a neighbor walker that does
787    /// not borrow from the graph.
788    ///
789    /// [1]: struct.Neighbors.html#method.detach
790    ///
791    pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix>
792    {
793        Neighbors {
794            skip_start: a,
795            edges: &self.edges,
796            next: match self.nodes.get(a.index()) {
797                None => [EdgeIndex::end(), EdgeIndex::end()],
798                Some(n) => n.next,
799            }
800        }
801    }
802
803    /// Return an iterator of all edges of `a`.
804    ///
805    /// - `Directed`: Outgoing edges from `a`.
806    /// - `Undirected`: All edges connected to `a`.
807    ///
808    /// Produces an empty iterator if the node doesn't exist.<br>
809    /// Iterator element type is `EdgeReference<E, Ix>`.
810    pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
811        self.edges_directed(a, Outgoing)
812    }
813
814    /// Return an iterator of all edges of `a`, in the specified direction.
815    ///
816    /// - `Directed`, `Outgoing`: All edges from `a`.
817    /// - `Directed`, `Incoming`: All edges to `a`.
818    /// - `Undirected`: All edges connected to `a`.
819    ///
820    /// Produces an empty iterator if the node `a` doesn't exist.<br>
821    /// Iterator element type is `EdgeReference<E, Ix>`.
822    pub fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix>
823    {
824        let mut iter = self.edges_undirected(a);
825        if self.is_directed() {
826            iter.direction = Some(dir);
827        }
828        if self.is_directed() && dir == Incoming {
829            iter.next.swap(0, 1);
830        }
831        iter
832    }
833
834    /// Return an iterator over all edges connected to `a`.
835    ///
836    /// - `Directed` and `Undirected`: All edges connected to `a`.
837    ///
838    /// Produces an empty iterator if the node `a` doesn't exist.<br>
839    /// Iterator element type is `EdgeReference<E, Ix>`.
840    fn edges_undirected(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
841        Edges {
842            skip_start: a,
843            edges: &self.edges,
844            direction: None,
845            next: match self.nodes.get(a.index()) {
846                None => [EdgeIndex::end(), EdgeIndex::end()],
847                Some(n) => n.next,
848            },
849            ty: PhantomData,
850        }
851    }
852
853    /// Lookup if there is an edge from `a` to `b`.
854    ///
855    /// Computes in **O(e')** time, where **e'** is the number of edges
856    /// connected to `a` (and `b`, if the graph edges are undirected).
857    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
858        self.find_edge(a, b).is_some()
859    }
860
861    /// Lookup an edge from `a` to `b`.
862    ///
863    /// Computes in **O(e')** time, where **e'** is the number of edges
864    /// connected to `a` (and `b`, if the graph edges are undirected).
865    pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>>
866    {
867        if !self.is_directed() {
868            self.find_edge_undirected(a, b).map(|(ix, _)| ix)
869        } else {
870            match self.nodes.get(a.index()) {
871                None => None,
872                Some(node) => self.find_edge_directed_from_node(node, b)
873            }
874        }
875    }
876
877    fn find_edge_directed_from_node(&self, node: &Node<N, Ix>, b: NodeIndex<Ix>)
878        -> Option<EdgeIndex<Ix>>
879    {
880        let mut edix = node.next[0];
881        while let Some(edge) = self.edges.get(edix.index()) {
882            if edge.node[1] == b {
883                return Some(edix)
884            }
885            edix = edge.next[0];
886        }
887        None
888    }
889
890    /// Lookup an edge between `a` and `b`, in either direction.
891    ///
892    /// If the graph is undirected, then this is equivalent to `.find_edge()`.
893    ///
894    /// Return the edge index and its directionality, with `Outgoing` meaning
895    /// from `a` to `b` and `Incoming` the reverse,
896    /// or `None` if the edge does not exist.
897    pub fn find_edge_undirected(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<(EdgeIndex<Ix>, Direction)>
898    {
899        match self.nodes.get(a.index()) {
900            None => None,
901            Some(node) => self.find_edge_undirected_from_node(node, b),
902        }
903    }
904
905    fn find_edge_undirected_from_node(&self, node: &Node<N, Ix>, b: NodeIndex<Ix>)
906        -> Option<(EdgeIndex<Ix>, Direction)>
907    {
908        for &d in &DIRECTIONS {
909            let k = d.index();
910            let mut edix = node.next[k];
911            while let Some(edge) = self.edges.get(edix.index()) {
912                if edge.node[1 - k] == b {
913                    return Some((edix, d))
914                }
915                edix = edge.next[k];
916            }
917        }
918        None
919    }
920
921    /// Return an iterator over either the nodes without edges to them
922    /// (`Incoming`) or from them (`Outgoing`).
923    ///
924    /// An *internal* node has both incoming and outgoing edges.
925    /// The nodes in `.externals(Incoming)` are the source nodes and
926    /// `.externals(Outgoing)` are the sinks of the graph.
927    ///
928    /// For a graph with undirected edges, both the sinks and the sources are
929    /// just the nodes without edges.
930    ///
931    /// The whole iteration computes in **O(|V|)** time.
932    pub fn externals(&self, dir: Direction) -> Externals<N, Ty, Ix>
933    {
934        Externals{iter: self.nodes.iter().enumerate(), dir: dir, ty: PhantomData}
935    }
936
937    /// Return an iterator over the node indices of the graph
938    pub fn node_indices(&self) -> NodeIndices<Ix> {
939        NodeIndices { r: 0..self.node_count(), ty: PhantomData }
940    }
941
942    /// Return an iterator yielding mutable access to all node weights.
943    ///
944    /// The order in which weights are yielded matches the order of their
945    /// node indices.
946    pub fn node_weights_mut(&mut self) -> NodeWeightsMut<N, Ix>
947    {
948        NodeWeightsMut { nodes: self.nodes.iter_mut() }
949    }
950
951    /// Return an iterator over the edge indices of the graph
952    pub fn edge_indices(&self) -> EdgeIndices<Ix> {
953        EdgeIndices { r: 0..self.edge_count(), ty: PhantomData }
954    }
955
956    /// Create an iterator over all edges, in indexed order.
957    ///
958    /// Iterator element type is `EdgeReference<E, Ix>`.
959    pub fn edge_references(&self) -> EdgeReferences<E, Ix> {
960        EdgeReferences {
961            iter: self.edges.iter().enumerate()
962        }
963    }
964
965    /// Return an iterator yielding mutable access to all edge weights.
966    ///
967    /// The order in which weights are yielded matches the order of their
968    /// edge indices.
969    pub fn edge_weights_mut(&mut self) -> EdgeWeightsMut<E, Ix>
970    {
971        EdgeWeightsMut { edges: self.edges.iter_mut() }
972    }
973
974    // Remaining methods are of the more internal flavour, read-only access to
975    // the data structure's internals.
976
977    /// Access the internal node array.
978    pub fn raw_nodes(&self) -> &[Node<N, Ix>]
979    {
980        &self.nodes
981    }
982
983    /// Access the internal edge array.
984    pub fn raw_edges(&self) -> &[Edge<E, Ix>]
985    {
986        &self.edges
987    }
988
989    /// Convert the graph into a vector of Nodes and a vector of Edges
990    pub fn into_nodes_edges(self) -> (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>) {
991        (self.nodes, self.edges)
992    }
993
994    /// Accessor for data structure internals: the first edge in the given direction.
995    pub fn first_edge(&self, a: NodeIndex<Ix>, dir: Direction) -> Option<EdgeIndex<Ix>>
996    {
997        match self.nodes.get(a.index()) {
998            None => None,
999            Some(node) => {
1000                let edix = node.next[dir.index()];
1001                if edix == EdgeIndex::end() {
1002                    None
1003                } else { Some(edix) }
1004            }
1005        }
1006    }
1007
1008    /// Accessor for data structure internals: the next edge for the given direction.
1009    pub fn next_edge(&self, e: EdgeIndex<Ix>, dir: Direction) -> Option<EdgeIndex<Ix>>
1010    {
1011        match self.edges.get(e.index()) {
1012            None => None,
1013            Some(node) => {
1014                let edix = node.next[dir.index()];
1015                if edix == EdgeIndex::end() {
1016                    None
1017                } else { Some(edix) }
1018            }
1019        }
1020    }
1021
1022    /// Index the `Graph` by two indices, any combination of
1023    /// node or edge indices is fine.
1024    ///
1025    /// **Panics** if the indices are equal or if they are out of bounds.
1026    ///
1027    /// ```
1028    /// use petgraph::{Graph, Incoming};
1029    /// use petgraph::visit::Dfs;
1030    ///
1031    /// let mut gr = Graph::new();
1032    /// let a = gr.add_node(0.);
1033    /// let b = gr.add_node(0.);
1034    /// let c = gr.add_node(0.);
1035    /// gr.add_edge(a, b, 3.);
1036    /// gr.add_edge(b, c, 2.);
1037    /// gr.add_edge(c, b, 1.);
1038    ///
1039    /// // walk the graph and sum incoming edges into the node weight
1040    /// let mut dfs = Dfs::new(&gr, a);
1041    /// while let Some(node) = dfs.next(&gr) {
1042    ///     // use a walker -- a detached neighbors iterator
1043    ///     let mut edges = gr.neighbors_directed(node, Incoming).detach();
1044    ///     while let Some(edge) = edges.next_edge(&gr) {
1045    ///         let (nw, ew) = gr.index_twice_mut(node, edge);
1046    ///         *nw += *ew;
1047    ///     }
1048    /// }
1049    ///
1050    /// // check the result
1051    /// assert_eq!(gr[a], 0.);
1052    /// assert_eq!(gr[b], 4.);
1053    /// assert_eq!(gr[c], 2.);
1054    /// ```
1055    pub fn index_twice_mut<T, U>(&mut self, i: T, j: U)
1056        -> (&mut <Self as Index<T>>::Output,
1057            &mut <Self as Index<U>>::Output)
1058        where Self: IndexMut<T> + IndexMut<U>,
1059              T: GraphIndex,
1060              U: GraphIndex,
1061    {
1062        assert!(T::is_node_index() != U::is_node_index() ||
1063                i.index() != j.index());
1064
1065        // Allow two mutable indexes here -- they are nonoverlapping
1066        unsafe {
1067            let self_mut = self as *mut _;
1068            (<Self as IndexMut<T>>::index_mut(&mut *self_mut, i),
1069             <Self as IndexMut<U>>::index_mut(&mut *self_mut, j))
1070        }
1071    }
1072
1073    /// Reverse the direction of all edges
1074    pub fn reverse(&mut self) {
1075        // swap edge endpoints,
1076        // edge incoming / outgoing lists,
1077        // node incoming / outgoing lists
1078        for edge in &mut self.edges {
1079            edge.node.swap(0, 1);
1080            edge.next.swap(0, 1);
1081        }
1082        for node in &mut self.nodes {
1083            node.next.swap(0, 1);
1084        }
1085    }
1086
1087    /// Remove all nodes and edges
1088    pub fn clear(&mut self) {
1089        self.nodes.clear();
1090        self.edges.clear();
1091    }
1092
1093    /// Remove all edges
1094    pub fn clear_edges(&mut self) {
1095        self.edges.clear();
1096        for node in &mut self.nodes {
1097            node.next = [EdgeIndex::end(), EdgeIndex::end()];
1098        }
1099    }
1100
1101    /// Return the current node and edge capacity of the graph.
1102    pub fn capacity(&self) -> (usize, usize) {
1103        (self.nodes.capacity(), self.edges.capacity())
1104    }
1105
1106    /// Reserves capacity for at least `additional` more nodes to be inserted in
1107    /// the graph. Graph may reserve more space to avoid frequent reallocations.
1108    ///
1109    /// **Panics** if the new capacity overflows `usize`.
1110    pub fn reserve_nodes(&mut self, additional: usize) {
1111        self.nodes.reserve(additional);
1112    }
1113
1114    /// Reserves capacity for at least `additional` more edges to be inserted in
1115    /// the graph. Graph may reserve more space to avoid frequent reallocations.
1116    ///
1117    /// **Panics** if the new capacity overflows `usize`.
1118    pub fn reserve_edges(&mut self, additional: usize) {
1119        self.edges.reserve(additional);
1120    }
1121
1122    /// Reserves the minimum capacity for exactly `additional` more nodes to be
1123    /// inserted in the graph. Does nothing if the capacity is already
1124    /// sufficient.
1125    ///
1126    /// Prefer `reserve_nodes` if future insertions are expected.
1127    ///
1128    /// **Panics** if the new capacity overflows `usize`.
1129    pub fn reserve_exact_nodes(&mut self, additional: usize) {
1130        self.nodes.reserve_exact(additional);
1131    }
1132
1133    /// Reserves the minimum capacity for exactly `additional` more edges to be
1134    /// inserted in the graph.
1135    /// Does nothing if the capacity is already sufficient.
1136    ///
1137    /// Prefer `reserve_edges` if future insertions are expected.
1138    ///
1139    /// **Panics** if the new capacity overflows `usize`.
1140    pub fn reserve_exact_edges(&mut self, additional: usize) {
1141        self.edges.reserve_exact(additional);
1142    }
1143
1144    /// Shrinks the capacity of the underlying nodes collection as much as possible.
1145    pub fn shrink_to_fit_nodes(&mut self) {
1146        self.nodes.shrink_to_fit();
1147    }
1148
1149    /// Shrinks the capacity of the underlying edges collection as much as possible.
1150    pub fn shrink_to_fit_edges(&mut self) {
1151        self.edges.shrink_to_fit();
1152    }
1153
1154    /// Shrinks the capacity of the graph as much as possible.
1155    pub fn shrink_to_fit(&mut self) {
1156        self.nodes.shrink_to_fit();
1157        self.edges.shrink_to_fit();
1158    }
1159
1160    /// Keep all nodes that return `true` from the `visit` closure,
1161    /// remove the others.
1162    ///
1163    /// `visit` is provided a proxy reference to the graph, so that
1164    /// the graph can be walked and associated data modified.
1165    ///
1166    /// The order nodes are visited is not specified.
1167    pub fn retain_nodes<F>(&mut self, mut visit: F)
1168        where F: FnMut(Frozen<Self>, NodeIndex<Ix>) -> bool
1169    {
1170        for index in self.node_indices().rev() {
1171            if !visit(Frozen(self), index) {
1172                let ret = self.remove_node(index);
1173                debug_assert!(ret.is_some());
1174                let _ = ret;
1175            }
1176        }
1177    }
1178
1179    /// Keep all edges that return `true` from the `visit` closure,
1180    /// remove the others.
1181    ///
1182    /// `visit` is provided a proxy reference to the graph, so that
1183    /// the graph can be walked and associated data modified.
1184    ///
1185    /// The order edges are visited is not specified.
1186    pub fn retain_edges<F>(&mut self, mut visit: F)
1187        where F: FnMut(Frozen<Self>, EdgeIndex<Ix>) -> bool
1188    {
1189        for index in self.edge_indices().rev() {
1190            if !visit(Frozen(self), index) {
1191                let ret = self.remove_edge(index);
1192                debug_assert!(ret.is_some());
1193                let _ = ret;
1194            }
1195        }
1196    }
1197
1198
1199    /// Create a new `Graph` from an iterable of edges.
1200    ///
1201    /// Node weights `N` are set to default values.
1202    /// Edge weights `E` may either be specified in the list,
1203    /// or they are filled with default values.
1204    ///
1205    /// Nodes are inserted automatically to match the edges.
1206    ///
1207    /// ```
1208    /// use petgraph::Graph;
1209    ///
1210    /// let gr = Graph::<(), i32>::from_edges(&[
1211    ///     (0, 1), (0, 2), (0, 3),
1212    ///     (1, 2), (1, 3),
1213    ///     (2, 3),
1214    /// ]);
1215    /// ```
1216    pub fn from_edges<I>(iterable: I) -> Self
1217        where I: IntoIterator,
1218              I::Item: IntoWeightedEdge<E>,
1219              <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
1220              N: Default,
1221    {
1222        let mut g = Self::with_capacity(0, 0);
1223        g.extend_with_edges(iterable);
1224        g
1225    }
1226
1227    /// Extend the graph from an iterable of edges.
1228    ///
1229    /// Node weights `N` are set to default values.
1230    /// Edge weights `E` may either be specified in the list,
1231    /// or they are filled with default values.
1232    ///
1233    /// Nodes are inserted automatically to match the edges.
1234    pub fn extend_with_edges<I>(&mut self, iterable: I)
1235        where I: IntoIterator,
1236              I::Item: IntoWeightedEdge<E>,
1237              <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
1238              N: Default,
1239    {
1240        let iter = iterable.into_iter();
1241        let (low, _) = iter.size_hint();
1242        self.edges.reserve(low);
1243
1244        for elt in iter {
1245            let (source, target, weight) = elt.into_weighted_edge();
1246            let (source, target) = (source.into(), target.into());
1247            let nx = cmp::max(source, target);
1248            while nx.index() >= self.node_count() {
1249                self.add_node(N::default());
1250            }
1251            self.add_edge(source, target, weight);
1252        }
1253    }
1254
1255
1256    /// Create a new `Graph` by mapping node and
1257    /// edge weights to new values.
1258    ///
1259    /// The resulting graph has the same structure and the same
1260    /// graph indices as `self`.
1261    pub fn map<'a, F, G, N2, E2>(&'a self, mut node_map: F, mut edge_map: G)
1262        -> Graph<N2, E2, Ty, Ix>
1263        where F: FnMut(NodeIndex<Ix>, &'a N) -> N2,
1264              G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,
1265    {
1266        let mut g = Graph::with_capacity(self.node_count(), self.edge_count());
1267        g.nodes.extend(enumerate(&self.nodes).map(|(i, node)|
1268            Node {
1269                weight: node_map(NodeIndex::new(i), &node.weight),
1270                next: node.next,
1271            }));
1272        g.edges.extend(enumerate(&self.edges).map(|(i, edge)| 
1273            Edge {
1274                weight: edge_map(EdgeIndex::new(i), &edge.weight),
1275                next: edge.next,
1276                node: edge.node,
1277            }));
1278        g
1279    }
1280
1281    /// Create a new `Graph` by mapping nodes and edges.
1282    /// A node or edge may be mapped to `None` to exclude it from
1283    /// the resulting graph.
1284    ///
1285    /// Nodes are mapped first with the `node_map` closure, then
1286    /// `edge_map` is called for the edges that have not had any endpoint
1287    /// removed.
1288    ///
1289    /// The resulting graph has the structure of a subgraph of the original graph.
1290    /// If no nodes are removed, the resulting graph has compatible node
1291    /// indices; if neither nodes nor edges are removed, the result has
1292    /// the same graph indices as `self`.
1293    pub fn filter_map<'a, F, G, N2, E2>(&'a self, mut node_map: F, mut edge_map: G)
1294        -> Graph<N2, E2, Ty, Ix>
1295        where F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>,
1296              G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,
1297    {
1298        let mut g = Graph::with_capacity(0, 0);
1299        // mapping from old node index to new node index, end represents removed.
1300        let mut node_index_map = vec![NodeIndex::end(); self.node_count()];
1301        for (i, node) in enumerate(&self.nodes) {
1302            if let Some(nw) = node_map(NodeIndex::new(i), &node.weight) {
1303                node_index_map[i] = g.add_node(nw);
1304            }
1305        }
1306        for (i, edge) in enumerate(&self.edges) {
1307            // skip edge if any endpoint was removed
1308            let source = node_index_map[edge.source().index()];
1309            let target = node_index_map[edge.target().index()];
1310            if source != NodeIndex::end() && target != NodeIndex::end() {
1311                if let Some(ew) = edge_map(EdgeIndex::new(i), &edge.weight) {
1312                    g.add_edge(source, target, ew);
1313                }
1314            }
1315        }
1316        g
1317    }
1318
1319    /// Convert the graph into either undirected or directed. No edge adjustments
1320    /// are done, so you may want to go over the result to remove or add edges.
1321    ///
1322    /// Computes in **O(1)** time.
1323    pub fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix> where
1324        NewTy: EdgeType
1325    {
1326        Graph{nodes: self.nodes, edges: self.edges,
1327              ty: PhantomData}
1328    }
1329
1330
1331    //
1332    // internal methods
1333    //
1334    #[cfg(feature = "serde-1")]
1335    /// Fix up node and edge links after deserialization
1336    fn link_edges(&mut self) -> Result<(), NodeIndex<Ix>> {
1337        for (edge_index, edge) in enumerate(&mut self.edges) {
1338            let a = edge.source();
1339            let b = edge.target();
1340            let edge_idx = EdgeIndex::new(edge_index);
1341            match index_twice(&mut self.nodes, a.index(), b.index()) {
1342                Pair::None => return Err(if a > b { a } else { b }),
1343                Pair::One(an) => {
1344                    edge.next = an.next;
1345                    an.next[0] = edge_idx;
1346                    an.next[1] = edge_idx;
1347                }
1348                Pair::Both(an, bn) => {
1349                    // a and b are different indices
1350                    edge.next = [an.next[0], bn.next[1]];
1351                    an.next[0] = edge_idx;
1352                    bn.next[1] = edge_idx;
1353                }
1354            }
1355        }
1356        Ok(())
1357    }
1358}
1359
1360/// An iterator over either the nodes without edges to them or from them.
1361pub struct Externals<'a, N: 'a, Ty, Ix: IndexType = DefaultIx> {
1362    iter: iter::Enumerate<slice::Iter<'a, Node<N, Ix>>>,
1363    dir: Direction,
1364    ty: PhantomData<Ty>,
1365}
1366
1367impl<'a, N: 'a, Ty, Ix> Iterator for Externals<'a, N, Ty, Ix> where
1368    Ty: EdgeType,
1369    Ix: IndexType,
1370{
1371    type Item = NodeIndex<Ix>;
1372    fn next(&mut self) -> Option<NodeIndex<Ix>>
1373    {
1374        let k = self.dir.index();
1375        loop {
1376            match self.iter.next() {
1377                None => return None,
1378                Some((index, node)) => {
1379                    if node.next[k] == EdgeIndex::end() &&
1380                        (Ty::is_directed() ||
1381                         node.next[1-k] == EdgeIndex::end()) {
1382                        return Some(NodeIndex::new(index))
1383                    } else {
1384                        continue
1385                    }
1386                },
1387            }
1388        }
1389    }
1390}
1391
1392/// Iterator over the neighbors of a node.
1393///
1394/// Iterator element type is `NodeIndex<Ix>`.
1395///
1396/// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2] or
1397/// [`.neighbors_undirected()`][3].
1398///
1399/// [1]: struct.Graph.html#method.neighbors
1400/// [2]: struct.Graph.html#method.neighbors_directed
1401/// [3]: struct.Graph.html#method.neighbors_undirected
1402pub struct Neighbors<'a, E: 'a, Ix: 'a = DefaultIx>
1403{
1404    /// starting node to skip over
1405    skip_start: NodeIndex<Ix>,
1406    edges: &'a [Edge<E, Ix>],
1407    next: [EdgeIndex<Ix>; 2],
1408}
1409
1410impl<'a, E, Ix> Iterator for Neighbors<'a, E, Ix> where
1411    Ix: IndexType,
1412{
1413    type Item = NodeIndex<Ix>;
1414
1415    fn next(&mut self) -> Option<NodeIndex<Ix>> {
1416        // First any outgoing edges
1417        match self.edges.get(self.next[0].index()) {
1418            None => {}
1419            Some(edge) => {
1420                self.next[0] = edge.next[0];
1421                return Some(edge.node[1]);
1422            }
1423        }
1424        // Then incoming edges
1425        // For an "undirected" iterator (traverse both incoming
1426        // and outgoing edge lists), make sure we don't double
1427        // count selfloops by skipping them in the incoming list.
1428        while let Some(edge) = self.edges.get(self.next[1].index()) {
1429            self.next[1] = edge.next[1];
1430            if edge.node[0] != self.skip_start {
1431                return Some(edge.node[0]);
1432            }
1433        }
1434        None
1435    }
1436}
1437
1438
1439impl<'a, E, Ix> Clone for Neighbors<'a, E, Ix>
1440    where Ix: IndexType,
1441{
1442    clone_fields!(Neighbors,
1443                  skip_start,
1444                  edges,
1445                  next,
1446                  );
1447}
1448
1449impl<'a, E, Ix> Neighbors<'a, E, Ix>
1450    where Ix: IndexType,
1451{
1452    /// Return a “walker” object that can be used to step through the
1453    /// neighbors and edges from the origin node.
1454    ///
1455    /// Note: The walker does not borrow from the graph, this is to allow mixing
1456    /// edge walking with mutating the graph's weights.
1457    pub fn detach(&self) -> WalkNeighbors<Ix> {
1458        WalkNeighbors {
1459            skip_start: self.skip_start,
1460            next: self.next
1461        }
1462    }
1463}
1464
1465struct EdgesWalkerMut<'a, E: 'a, Ix: IndexType = DefaultIx> {
1466    edges: &'a mut [Edge<E, Ix>],
1467    next: EdgeIndex<Ix>,
1468    dir: Direction,
1469}
1470
1471fn edges_walker_mut<E, Ix>(edges: &mut [Edge<E, Ix>], next: EdgeIndex<Ix>, dir: Direction)
1472    -> EdgesWalkerMut<E, Ix>
1473    where Ix: IndexType,
1474{
1475    EdgesWalkerMut {
1476        edges: edges,
1477        next: next,
1478        dir: dir
1479    }
1480}
1481
1482impl<'a, E, Ix> EdgesWalkerMut<'a, E, Ix> where
1483    Ix: IndexType,
1484{
1485    fn next_edge(&mut self) -> Option<&mut Edge<E, Ix>> {
1486        self.next().map(|t| t.1)
1487    }
1488
1489    fn next(&mut self) -> Option<(EdgeIndex<Ix>, &mut Edge<E, Ix>)> {
1490        let this_index = self.next;
1491        let k = self.dir.index();
1492        match self.edges.get_mut(self.next.index()) {
1493            None => None,
1494            Some(edge) => {
1495                self.next = edge.next[k];
1496                Some((this_index, edge))
1497            }
1498        }
1499    }
1500}
1501
1502
1503impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix>
1504    where Ty: EdgeType,
1505          Ix: IndexType,
1506{
1507    type Edges = Edges<'a, E, Ty, Ix>;
1508    fn edges(self, a: Self::NodeId) -> Self::Edges {
1509        self.edges(a)
1510    }
1511}
1512
1513impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>
1514    where Ty: EdgeType,
1515          Ix: IndexType,
1516{
1517    type EdgesDirected = Edges<'a, E, Ty, Ix>;
1518    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
1519        self.edges_directed(a, dir)
1520    }
1521}
1522
1523
1524/// Iterator over the edges of from or to a node
1525pub struct Edges<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
1526    where Ty: EdgeType,
1527          Ix: IndexType,
1528{
1529    /// starting node to skip over
1530    skip_start: NodeIndex<Ix>,
1531    edges: &'a [Edge<E, Ix>],
1532
1533    /// Next edge to visit.
1534    /// If we are only following one direction, we only use next[0] regardless.
1535    next: [EdgeIndex<Ix>; 2],
1536
1537    /// Which direction to follow
1538    /// None: Both,
1539    /// Some(d): d if Directed, Both if Undirected
1540    direction: Option<Direction>,
1541    ty: PhantomData<Ty>,
1542}
1543
1544impl<'a, E, Ty, Ix> Iterator for Edges<'a, E, Ty, Ix>
1545    where Ty: EdgeType,
1546          Ix: IndexType,
1547{
1548    type Item = EdgeReference<'a, E, Ix>;
1549
1550    fn next(&mut self) -> Option<Self::Item> {
1551        // First the outgoing or incoming edges (directionality)
1552        let k = self.direction.unwrap_or(Outgoing).index();
1553        let i = self.next[0].index();
1554        match self.edges.get(i) {
1555            None => {}
1556            Some(&Edge { ref node, ref weight, ref next }) => {
1557                self.next[0] = next[k];
1558                return Some(EdgeReference {
1559                    index: edge_index(i),
1560                    node: *node,
1561                    weight: weight,
1562                });
1563            }
1564        }
1565        // Stop here if we only follow one direction
1566        if self.direction.is_some() {
1567            return None;
1568        }
1569        // Then incoming edges
1570        // For an "undirected" iterator (traverse both incoming
1571        // and outgoing edge lists), make sure we don't double
1572        // count selfloops by skipping them in the incoming list.
1573
1574        // We reach here if self.direction was None or Outgoing.
1575        debug_assert_eq!(k, 0);
1576        while let Some(edge) = self.edges.get(self.next[1].index()) {
1577            let i = self.next[1].index();
1578            self.next[1] = edge.next[1];
1579            if edge.node[0] != self.skip_start {
1580                return Some(EdgeReference {
1581                    index: edge_index(i),
1582                    node: swap_pair(edge.node),
1583                    weight: &edge.weight,
1584                });
1585            }
1586        }
1587        None
1588    }
1589}
1590
1591fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
1592    x.swap(0, 1);
1593    x
1594}
1595
1596impl<'a, E, Ty, Ix> Clone for Edges<'a, E, Ty, Ix>
1597    where Ix: IndexType,
1598          Ty: EdgeType,
1599{
1600    fn clone(&self) -> Self {
1601        Edges {
1602            skip_start: self.skip_start,
1603            edges: self.edges,
1604            next: self.next,
1605            direction: self.direction,
1606            ty: self.ty,
1607        }
1608    }
1609}
1610
1611/// Iterator yielding mutable access to all node weights.
1612pub struct NodeWeightsMut<'a, N: 'a, Ix: IndexType = DefaultIx> {
1613    nodes: ::std::slice::IterMut<'a, Node<N, Ix>>,
1614}
1615
1616impl<'a, N, Ix> Iterator for NodeWeightsMut<'a, N, Ix> where
1617    Ix: IndexType,
1618{
1619    type Item = &'a mut N;
1620
1621    fn next(&mut self) -> Option<&'a mut N> {
1622        self.nodes.next().map(|node| &mut node.weight)
1623    }
1624
1625    fn size_hint(&self) -> (usize, Option<usize>) {
1626        self.nodes.size_hint()
1627    }
1628}
1629
1630/// Iterator yielding mutable access to all edge weights.
1631pub struct EdgeWeightsMut<'a, E: 'a, Ix: IndexType = DefaultIx> {
1632    edges: ::std::slice::IterMut<'a, Edge<E, Ix>>,
1633}
1634
1635impl<'a, E, Ix> Iterator for EdgeWeightsMut<'a, E, Ix> where
1636    Ix: IndexType,
1637{
1638    type Item = &'a mut E;
1639
1640    fn next(&mut self) -> Option<&'a mut E> {
1641        self.edges.next().map(|edge| &mut edge.weight)
1642    }
1643
1644    fn size_hint(&self) -> (usize, Option<usize>) {
1645        self.edges.size_hint()
1646    }
1647}
1648
1649/// Index the `Graph` by `NodeIndex` to access node weights.
1650///
1651/// **Panics** if the node doesn't exist.
1652impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
1653    Ty: EdgeType,
1654    Ix: IndexType,
1655{
1656    type Output = N;
1657    fn index(&self, index: NodeIndex<Ix>) -> &N {
1658        &self.nodes[index.index()].weight
1659    }
1660}
1661
1662/// Index the `Graph` by `NodeIndex` to access node weights.
1663///
1664/// **Panics** if the node doesn't exist.
1665impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix> where
1666    Ty: EdgeType,
1667    Ix: IndexType,
1668{
1669    fn index_mut(&mut self, index: NodeIndex<Ix>) -> &mut N {
1670        &mut self.nodes[index.index()].weight
1671    }
1672
1673}
1674
1675/// Index the `Graph` by `EdgeIndex` to access edge weights.
1676///
1677/// **Panics** if the edge doesn't exist.
1678impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
1679    Ty: EdgeType,
1680    Ix: IndexType,
1681{
1682    type Output = E;
1683    fn index(&self, index: EdgeIndex<Ix>) -> &E {
1684        &self.edges[index.index()].weight
1685    }
1686}
1687
1688/// Index the `Graph` by `EdgeIndex` to access edge weights.
1689///
1690/// **Panics** if the edge doesn't exist.
1691impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix> where
1692    Ty: EdgeType,
1693    Ix: IndexType,
1694{
1695    fn index_mut(&mut self, index: EdgeIndex<Ix>) -> &mut E {
1696        &mut self.edges[index.index()].weight
1697    }
1698}
1699
1700/// Create a new empty `Graph`.
1701impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix>
1702    where Ty: EdgeType,
1703          Ix: IndexType,
1704{
1705    fn default() -> Self { Self::with_capacity(0, 0) }
1706}
1707
1708/// A  `GraphIndex` is a node or edge index.
1709pub trait GraphIndex : Copy {
1710    #[doc(hidden)]
1711    fn index(&self) -> usize;
1712    #[doc(hidden)]
1713    fn is_node_index() -> bool;
1714}
1715
1716impl<Ix: IndexType> GraphIndex for NodeIndex<Ix> {
1717    #[inline]
1718    fn index(&self) -> usize { NodeIndex::index(*self) }
1719    #[inline]
1720    fn is_node_index() -> bool { true }
1721}
1722
1723impl<Ix: IndexType> GraphIndex for EdgeIndex<Ix> {
1724    #[inline]
1725    fn index(&self) -> usize { EdgeIndex::index(*self) }
1726    #[inline]
1727    fn is_node_index() -> bool { false }
1728}
1729
1730/// A “walker” object that can be used to step through the edge list of a node.
1731///
1732/// Created with [`.detach()`](struct.Neighbors.html#method.detach).
1733///
1734/// The walker does not borrow from the graph, so it lets you step through
1735/// neighbors or incident edges while also mutating graph weights, as
1736/// in the following example:
1737///
1738/// ```
1739/// use petgraph::{Graph, Incoming};
1740/// use petgraph::visit::Dfs;
1741///
1742/// let mut gr = Graph::new();
1743/// let a = gr.add_node(0.);
1744/// let b = gr.add_node(0.);
1745/// let c = gr.add_node(0.);
1746/// gr.add_edge(a, b, 3.);
1747/// gr.add_edge(b, c, 2.);
1748/// gr.add_edge(c, b, 1.);
1749///
1750/// // step through the graph and sum incoming edges into the node weight
1751/// let mut dfs = Dfs::new(&gr, a);
1752/// while let Some(node) = dfs.next(&gr) {
1753///     // use a detached neighbors walker
1754///     let mut edges = gr.neighbors_directed(node, Incoming).detach();
1755///     while let Some(edge) = edges.next_edge(&gr) {
1756///         gr[node] += gr[edge];
1757///     }
1758/// }
1759///
1760/// // check the result
1761/// assert_eq!(gr[a], 0.);
1762/// assert_eq!(gr[b], 4.);
1763/// assert_eq!(gr[c], 2.);
1764/// ```
1765pub struct WalkNeighbors<Ix> {
1766    skip_start: NodeIndex<Ix>,
1767    next: [EdgeIndex<Ix>; 2],
1768}
1769
1770impl<Ix> Clone for WalkNeighbors<Ix>
1771    where Ix: IndexType,
1772{
1773    fn clone(&self) -> Self {
1774        WalkNeighbors {
1775            skip_start: self.skip_start,
1776            next: self.next,
1777        }
1778    }
1779}
1780
1781impl<Ix: IndexType> WalkNeighbors<Ix> {
1782    /// Step to the next edge and its endpoint node in the walk for graph `g`.
1783    ///
1784    /// The next node indices are always the others than the starting point
1785    /// where the `WalkNeighbors` value was created.
1786    /// For an `Outgoing` walk, the target nodes,
1787    /// for an `Incoming` walk, the source nodes of the edge.
1788    pub fn next<N, E, Ty: EdgeType>(&mut self, g: &Graph<N, E, Ty, Ix>)
1789        -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)> {
1790        // First any outgoing edges
1791        match g.edges.get(self.next[0].index()) {
1792            None => {}
1793            Some(edge) => {
1794                let ed = self.next[0];
1795                self.next[0] = edge.next[0];
1796                return Some((ed, edge.node[1]));
1797            }
1798        }
1799        // Then incoming edges
1800        // For an "undirected" iterator (traverse both incoming
1801        // and outgoing edge lists), make sure we don't double
1802        // count selfloops by skipping them in the incoming list.
1803        while let Some(edge) = g.edges.get(self.next[1].index()) {
1804            let ed = self.next[1];
1805            self.next[1] = edge.next[1];
1806            if edge.node[0] != self.skip_start {
1807                return Some((ed, edge.node[0]));
1808            }
1809        }
1810        None
1811    }
1812
1813    pub fn next_node<N, E, Ty: EdgeType>(&mut self, g: &Graph<N, E, Ty, Ix>)
1814        -> Option<NodeIndex<Ix>>
1815    {
1816        self.next(g).map(|t| t.1)
1817    }
1818
1819    pub fn next_edge<N, E, Ty: EdgeType>(&mut self, g: &Graph<N, E, Ty, Ix>)
1820        -> Option<EdgeIndex<Ix>>
1821    {
1822        self.next(g).map(|t| t.0)
1823    }
1824}
1825
1826/// Iterator over the node indices of a graph.
1827#[derive(Clone, Debug)]
1828pub struct NodeIndices<Ix = DefaultIx> {
1829    r: Range<usize>,
1830    ty: PhantomData<fn() -> Ix>,
1831}
1832
1833impl<Ix: IndexType> Iterator for NodeIndices<Ix> {
1834    type Item = NodeIndex<Ix>;
1835
1836    fn next(&mut self) -> Option<Self::Item> {
1837        self.r.next().map(node_index)
1838    }
1839
1840    fn size_hint(&self) -> (usize, Option<usize>) {
1841        self.r.size_hint()
1842    }
1843}
1844
1845impl<Ix: IndexType> DoubleEndedIterator for NodeIndices<Ix> {
1846    fn next_back(&mut self) -> Option<Self::Item> {
1847        self.r.next_back().map(node_index)
1848    }
1849}
1850
1851impl<Ix: IndexType> ExactSizeIterator for NodeIndices<Ix> {}
1852
1853/// Iterator over the edge indices of a graph.
1854#[derive(Clone, Debug)]
1855pub struct EdgeIndices<Ix = DefaultIx> {
1856    r: Range<usize>,
1857    ty: PhantomData<fn() -> Ix>,
1858}
1859
1860impl<Ix: IndexType> Iterator for EdgeIndices<Ix> {
1861    type Item = EdgeIndex<Ix>;
1862
1863    fn next(&mut self) -> Option<Self::Item> {
1864        self.r.next().map(edge_index)
1865    }
1866
1867    fn size_hint(&self) -> (usize, Option<usize>) {
1868        self.r.size_hint()
1869    }
1870}
1871
1872impl<Ix: IndexType> DoubleEndedIterator for EdgeIndices<Ix> {
1873    fn next_back(&mut self) -> Option<Self::Item> {
1874        self.r.next_back().map(edge_index)
1875    }
1876}
1877
1878impl<Ix: IndexType> ExactSizeIterator for EdgeIndices<Ix> {}
1879
1880/// Reference to a `Graph` edge.
1881#[derive(Debug)]
1882pub struct EdgeReference<'a, E: 'a, Ix = DefaultIx> {
1883    index: EdgeIndex<Ix>,
1884    node: [NodeIndex<Ix>; 2],
1885    weight: &'a E,
1886}
1887
1888impl<'a, E, Ix: IndexType> Clone for EdgeReference<'a, E, Ix> {
1889    fn clone(&self) -> Self {
1890        *self
1891    }
1892}
1893
1894impl<'a, E, Ix: IndexType> Copy for EdgeReference<'a, E, Ix> { }
1895
1896impl<'a, E, Ix: IndexType> PartialEq for EdgeReference<'a, E, Ix>
1897    where E: PartialEq,
1898{
1899    fn eq(&self, rhs: &Self) -> bool {
1900        self.index == rhs.index && self.weight == rhs.weight
1901    }
1902}
1903
1904impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix>
1905    where Ty: EdgeType,
1906          Ix: IndexType,
1907{
1908    type NodeRef = (NodeIndex<Ix>, &'a N);
1909    type NodeReferences = NodeReferences<'a, N, Ix>;
1910    fn node_references(self) -> Self::NodeReferences {
1911        NodeReferences {
1912            iter: self.nodes.iter().enumerate()
1913        }
1914    }
1915}
1916
1917/// Iterator over all nodes of a graph.
1918pub struct NodeReferences<'a, N: 'a, Ix: IndexType = DefaultIx> {
1919    iter: iter::Enumerate<slice::Iter<'a, Node<N, Ix>>>,
1920}
1921
1922impl<'a, N, Ix> Iterator for NodeReferences<'a, N, Ix>
1923    where Ix: IndexType
1924{
1925    type Item = (NodeIndex<Ix>, &'a N);
1926
1927    fn next(&mut self) -> Option<Self::Item> {
1928        self.iter.next().map(|(i, node)| 
1929            (node_index(i), &node.weight)
1930        )
1931    }
1932
1933    fn size_hint(&self) -> (usize, Option<usize>) {
1934        self.iter.size_hint()
1935    }
1936}
1937
1938impl<'a, N, Ix> DoubleEndedIterator for NodeReferences<'a, N, Ix>
1939    where Ix: IndexType
1940{
1941    fn next_back(&mut self) -> Option<Self::Item> {
1942        self.iter.next_back().map(|(i, node)|
1943            (node_index(i), &node.weight)
1944        )
1945    }
1946}
1947
1948impl<'a, N, Ix> ExactSizeIterator for NodeReferences<'a, N, Ix>
1949    where Ix: IndexType
1950{ }
1951
1952impl<'a, Ix, E> EdgeReference<'a, E, Ix>
1953    where Ix: IndexType,
1954{
1955    /// Access the edge’s weight.
1956    ///
1957    /// **NOTE** that this method offers a longer lifetime
1958    /// than the trait (unfortunately they don't match yet).
1959    pub fn weight(&self) -> &'a E { self.weight }
1960}
1961
1962impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
1963    where Ix: IndexType,
1964{
1965    type NodeId = NodeIndex<Ix>;
1966    type EdgeId = EdgeIndex<Ix>;
1967    type Weight = E;
1968
1969    fn source(&self) -> Self::NodeId { self.node[0] }
1970    fn target(&self) -> Self::NodeId { self.node[1] }
1971    fn weight(&self) -> &E { self.weight }
1972    fn id(&self) -> Self::EdgeId { self.index }
1973}
1974
1975
1976/// Iterator over all edges of a graph.
1977pub struct EdgeReferences<'a, E: 'a, Ix: IndexType = DefaultIx> {
1978    iter: iter::Enumerate<slice::Iter<'a, Edge<E, Ix>>>,
1979}
1980
1981impl<'a, E, Ix> Iterator for EdgeReferences<'a, E, Ix>
1982    where Ix: IndexType
1983{
1984    type Item = EdgeReference<'a, E, Ix>;
1985
1986    fn next(&mut self) -> Option<Self::Item> {
1987        self.iter.next().map(|(i, edge)| 
1988            EdgeReference {
1989                index: edge_index(i),
1990                node: edge.node,
1991                weight: &edge.weight,
1992            }
1993        )
1994    }
1995
1996    fn size_hint(&self) -> (usize, Option<usize>) {
1997        self.iter.size_hint()
1998    }
1999}
2000
2001impl<'a, E, Ix> DoubleEndedIterator for EdgeReferences<'a, E, Ix>
2002    where Ix: IndexType
2003{
2004    fn next_back(&mut self) -> Option<Self::Item> {
2005        self.iter.next_back().map(|(i, edge)|
2006            EdgeReference {
2007                index: edge_index(i),
2008                node: edge.node,
2009                weight: &edge.weight,
2010            }
2011        )
2012    }
2013}
2014
2015impl<'a, E, Ix> ExactSizeIterator for EdgeReferences<'a, E, Ix>
2016    where Ix: IndexType
2017{}
2018
2019#[cfg(feature = "stable_graph")]
2020pub mod stable_graph;
2021mod frozen;
2022
2023/// `Frozen` is a graph wrapper.
2024///
2025/// The `Frozen` only allows shared access (read-only) to the
2026/// underlying graph `G`, but it allows mutable access to its
2027/// node and edge weights.
2028///
2029/// This is used to ensure immutability of the graph's structure
2030/// while permitting weights to be both read and written.
2031///
2032/// See indexing implementations and the traits `Data` and `DataMap`
2033/// for read-write access to the graph's weights.
2034pub struct Frozen<'a, G: 'a>(&'a mut G);
2035
petgraph/graph_impl/mod.rs

petgraph/graph_impl/
mod.rs
