Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 4726 insertions, 0 deletions

diff --git a/vendor/petgraph/src/graph_impl/frozen.rs b/vendor/petgraph/src/graph_impl/frozen.rs
new file mode 100644
index 000000000..1ba06d9d9
--- /dev/null
+++ b/vendor/petgraph/src/graph_impl/frozen.rs
@@ -0,0 +1,96 @@
+use std::ops::{Deref, Index, IndexMut};
+
+use super::Frozen;
+use crate::data::{DataMap, DataMapMut};
+use crate::graph::Graph;
+use crate::graph::{GraphIndex, IndexType};
+use crate::visit::{Data, GraphProp, IntoNeighborsDirected, IntoNodeIdentifiers, NodeIndexable};
+use crate::visit::{
+    GetAdjacencyMatrix, IntoEdges, IntoEdgesDirected, NodeCompactIndexable, NodeCount,
+};
+use crate::visit::{IntoEdgeReferences, IntoNeighbors, IntoNodeReferences, Visitable};
+use crate::{Direction, EdgeType};
+
+impl<'a, G> Frozen<'a, G> {
+    /// Create a new `Frozen` from a mutable reference to a graph.
+    pub fn new(gr: &'a mut G) -> Self {
+        Frozen(gr)
+    }
+}
+
+/// Deref allows transparent access to all shared reference (read-only)
+/// functionality in the underlying graph.
+impl<'a, G> Deref for Frozen<'a, G> {
+    type Target = G;
+    fn deref(&self) -> &G {
+        self.0
+    }
+}
+
+impl<'a, G, I> Index<I> for Frozen<'a, G>
+where
+    G: Index<I>,
+{
+    type Output = G::Output;
+    fn index(&self, i: I) -> &G::Output {
+        self.0.index(i)
+    }
+}
+
+impl<'a, G, I> IndexMut<I> for Frozen<'a, G>
+where
+    G: IndexMut<I>,
+{
+    fn index_mut(&mut self, i: I) -> &mut G::Output {
+        self.0.index_mut(i)
+    }
+}
+
+impl<'a, N, E, Ty, Ix> Frozen<'a, Graph<N, E, Ty, Ix>>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// Index the `Graph` by two indices, any combination of
+    /// node or edge indices is fine.
+    ///
+    /// **Panics** if the indices are equal or if they are out of bounds.
+    pub fn index_twice_mut<T, U>(
+        &mut self,
+        i: T,
+        j: U,
+    ) -> (
+        &mut <Graph<N, E, Ty, Ix> as Index<T>>::Output,
+        &mut <Graph<N, E, Ty, Ix> as Index<U>>::Output,
+    )
+    where
+        Graph<N, E, Ty, Ix>: IndexMut<T> + IndexMut<U>,
+        T: GraphIndex,
+        U: GraphIndex,
+    {
+        self.0.index_twice_mut(i, j)
+    }
+}
+
+macro_rules! access0 {
+    ($e:expr) => {
+        $e.0
+    };
+}
+
+Data! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+DataMap! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+DataMapMut! {delegate_impl [['a, G], G, Frozen<'a, G>, access0]}
+GetAdjacencyMatrix! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+IntoEdgeReferences! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoEdges! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoEdgesDirected! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoNeighbors! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoNeighborsDirected! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoNodeIdentifiers! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+IntoNodeReferences! {delegate_impl [['a, 'b, G], G, &'b Frozen<'a, G>, deref_twice]}
+NodeCompactIndexable! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+NodeCount! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+NodeIndexable! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+GraphProp! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
+Visitable! {delegate_impl [['a, G], G, Frozen<'a, G>, deref_twice]}
diff --git a/vendor/petgraph/src/graph_impl/mod.rs b/vendor/petgraph/src/graph_impl/mod.rs
new file mode 100644
index 000000000..9fb43b3c4
--- /dev/null
+++ b/vendor/petgraph/src/graph_impl/mod.rs
@@ -0,0 +1,2172 @@
+use std::cmp;
+use std::fmt;
+use std::hash::Hash;
+use std::iter;
+use std::marker::PhantomData;
+use std::mem::size_of;
+use std::ops::{Index, IndexMut, Range};
+use std::slice;
+
+use crate::{Directed, Direction, EdgeType, Incoming, IntoWeightedEdge, Outgoing, Undirected};
+
+use crate::iter_format::{DebugMap, IterFormatExt, NoPretty};
+
+use crate::util::enumerate;
+use crate::visit::EdgeRef;
+use crate::visit::{IntoEdges, IntoEdgesDirected, IntoNodeReferences};
+
+#[cfg(feature = "serde-1")]
+mod serialization;
+
+/// The default integer type for graph indices.
+/// `u32` is the default to reduce the size of the graph's data and improve
+/// performance in the common case.
+///
+/// Used for node and edge indices in `Graph` and `StableGraph`, used
+/// for node indices in `Csr`.
+pub type DefaultIx = u32;
+
+/// Trait for the unsigned integer type used for node and edge indices.
+///
+/// Marked `unsafe` because: the trait must faithfully preserve
+/// and convert index values.
+pub unsafe trait IndexType: Copy + Default + Hash + Ord + fmt::Debug + 'static {
+    fn new(x: usize) -> Self;
+    fn index(&self) -> usize;
+    fn max() -> Self;
+}
+
+unsafe impl IndexType for usize {
+    #[inline(always)]
+    fn new(x: usize) -> Self {
+        x
+    }
+    #[inline(always)]
+    fn index(&self) -> Self {
+        *self
+    }
+    #[inline(always)]
+    fn max() -> Self {
+        ::std::usize::MAX
+    }
+}
+
+unsafe impl IndexType for u32 {
+    #[inline(always)]
+    fn new(x: usize) -> Self {
+        x as u32
+    }
+    #[inline(always)]
+    fn index(&self) -> usize {
+        *self as usize
+    }
+    #[inline(always)]
+    fn max() -> Self {
+        ::std::u32::MAX
+    }
+}
+
+unsafe impl IndexType for u16 {
+    #[inline(always)]
+    fn new(x: usize) -> Self {
+        x as u16
+    }
+    #[inline(always)]
+    fn index(&self) -> usize {
+        *self as usize
+    }
+    #[inline(always)]
+    fn max() -> Self {
+        ::std::u16::MAX
+    }
+}
+
+unsafe impl IndexType for u8 {
+    #[inline(always)]
+    fn new(x: usize) -> Self {
+        x as u8
+    }
+    #[inline(always)]
+    fn index(&self) -> usize {
+        *self as usize
+    }
+    #[inline(always)]
+    fn max() -> Self {
+        ::std::u8::MAX
+    }
+}
+
+/// Node identifier.
+#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash)]
+pub struct NodeIndex<Ix = DefaultIx>(Ix);
+
+impl<Ix: IndexType> NodeIndex<Ix> {
+    #[inline]
+    pub fn new(x: usize) -> Self {
+        NodeIndex(IndexType::new(x))
+    }
+
+    #[inline]
+    pub fn index(self) -> usize {
+        self.0.index()
+    }
+
+    #[inline]
+    pub fn end() -> Self {
+        NodeIndex(IndexType::max())
+    }
+
+    fn _into_edge(self) -> EdgeIndex<Ix> {
+        EdgeIndex(self.0)
+    }
+}
+
+impl<Ix: IndexType> From<Ix> for NodeIndex<Ix> {
+    fn from(ix: Ix) -> Self {
+        NodeIndex(ix)
+    }
+}
+
+impl<Ix: fmt::Debug> fmt::Debug for NodeIndex<Ix> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "NodeIndex({:?})", self.0)
+    }
+}
+
+/// Short version of `NodeIndex::new`
+pub fn node_index<Ix: IndexType>(index: usize) -> NodeIndex<Ix> {
+    NodeIndex::new(index)
+}
+
+/// Short version of `EdgeIndex::new`
+pub fn edge_index<Ix: IndexType>(index: usize) -> EdgeIndex<Ix> {
+    EdgeIndex::new(index)
+}
+
+/// Edge identifier.
+#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash)]
+pub struct EdgeIndex<Ix = DefaultIx>(Ix);
+
+impl<Ix: IndexType> EdgeIndex<Ix> {
+    #[inline]
+    pub fn new(x: usize) -> Self {
+        EdgeIndex(IndexType::new(x))
+    }
+
+    #[inline]
+    pub fn index(self) -> usize {
+        self.0.index()
+    }
+
+    /// An invalid `EdgeIndex` used to denote absence of an edge, for example
+    /// to end an adjacency list.
+    #[inline]
+    pub fn end() -> Self {
+        EdgeIndex(IndexType::max())
+    }
+
+    fn _into_node(self) -> NodeIndex<Ix> {
+        NodeIndex(self.0)
+    }
+}
+
+impl<Ix: IndexType> From<Ix> for EdgeIndex<Ix> {
+    fn from(ix: Ix) -> Self {
+        EdgeIndex(ix)
+    }
+}
+
+impl<Ix: fmt::Debug> fmt::Debug for EdgeIndex<Ix> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "EdgeIndex({:?})", self.0)
+    }
+}
+/*
+ * FIXME: Use this impl again, when we don't need to add so many bounds
+impl<Ix: IndexType> fmt::Debug for EdgeIndex<Ix>
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        try!(write!(f, "EdgeIndex("));
+        if *self == EdgeIndex::end() {
+            try!(write!(f, "End"));
+        } else {
+            try!(write!(f, "{}", self.index()));
+        }
+        write!(f, ")")
+    }
+}
+*/
+
+const DIRECTIONS: [Direction; 2] = [Outgoing, Incoming];
+
+/// The graph's node type.
+#[derive(Debug)]
+pub struct Node<N, Ix = DefaultIx> {
+    /// Associated node data.
+    pub weight: N,
+    /// Next edge in outgoing and incoming edge lists.
+    next: [EdgeIndex<Ix>; 2],
+}
+
+impl<E, Ix> Clone for Node<E, Ix>
+where
+    E: Clone,
+    Ix: Copy,
+{
+    clone_fields!(Node, weight, next,);
+}
+
+impl<N, Ix: IndexType> Node<N, Ix> {
+    /// Accessor for data structure internals: the first edge in the given direction.
+    pub fn next_edge(&self, dir: Direction) -> EdgeIndex<Ix> {
+        self.next[dir.index()]
+    }
+}
+
+/// The graph's edge type.
+#[derive(Debug)]
+pub struct Edge<E, Ix = DefaultIx> {
+    /// Associated edge data.
+    pub weight: E,
+    /// Next edge in outgoing and incoming edge lists.
+    next: [EdgeIndex<Ix>; 2],
+    /// Start and End node index
+    node: [NodeIndex<Ix>; 2],
+}
+
+impl<E, Ix> Clone for Edge<E, Ix>
+where
+    E: Clone,
+    Ix: Copy,
+{
+    clone_fields!(Edge, weight, next, node,);
+}
+
+impl<E, Ix: IndexType> Edge<E, Ix> {
+    /// Accessor for data structure internals: the next edge for the given direction.
+    pub fn next_edge(&self, dir: Direction) -> EdgeIndex<Ix> {
+        self.next[dir.index()]
+    }
+
+    /// Return the source node index.
+    pub fn source(&self) -> NodeIndex<Ix> {
+        self.node[0]
+    }
+
+    /// Return the target node index.
+    pub fn target(&self) -> NodeIndex<Ix> {
+        self.node[1]
+    }
+}
+
+/// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation.
+///
+/// `Graph` is parameterized over:
+///
+/// - Associated data `N` for nodes and `E` for edges, called *weights*.
+///   The associated data can be of arbitrary type.
+/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
+/// - Index type `Ix`, which determines the maximum size of the graph.
+///
+/// The `Graph` is a regular Rust collection and is `Send` and `Sync` (as long
+/// as associated data `N` and `E` are).
+///
+/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert,
+/// efficient graph search and graph algorithms.
+/// It implements **O(e')** edge lookup and edge and node removals, where **e'**
+/// is some local measure of edge count.
+/// Based on the graph datastructure used in rustc.
+///
+/// Here's an example of building a graph with directed edges, and below
+/// an illustration of how it could be rendered with graphviz (see
+/// [`Dot`](../dot/struct.Dot.html)):
+///
+/// ```
+/// use petgraph::Graph;
+///
+/// let mut deps = Graph::<&str, &str>::new();
+/// let pg = deps.add_node("petgraph");
+/// let fb = deps.add_node("fixedbitset");
+/// let qc = deps.add_node("quickcheck");
+/// let rand = deps.add_node("rand");
+/// let libc = deps.add_node("libc");
+/// deps.extend_with_edges(&[
+///     (pg, fb), (pg, qc),
+///     (qc, rand), (rand, libc), (qc, libc),
+/// ]);
+/// ```
+///
+/// ![graph-example](https://bluss.github.io/ndarray/images/graph-example.svg)
+///
+/// ### Graph Indices
+///
+/// The graph maintains indices for nodes and edges, and node and edge
+/// weights may be accessed mutably. Indices range in a compact interval, for
+/// example for *n* nodes indices are 0 to *n* - 1 inclusive.
+///
+/// `NodeIndex` and `EdgeIndex` are types that act as references to nodes and edges,
+/// but these are only stable across certain operations:
+///
+/// * **Removing nodes or edges may shift other indices.** Removing a node will
+/// force the last node to shift its index to take its place. Similarly,
+/// removing an edge shifts the index of the last edge.
+/// * Adding nodes or edges keeps indices stable.
+///
+/// The `Ix` parameter is `u32` by default. The goal is that you can ignore this parameter
+/// completely unless you need a very big graph -- then you can use `usize`.
+///
+/// * The fact that the node and edge indices in the graph each are numbered in compact
+/// intervals (from 0 to *n* - 1 for *n* nodes) simplifies some graph algorithms.
+///
+/// * You can select graph index integer type after the size of the graph. A smaller
+/// size may have better performance.
+///
+/// * Using indices allows mutation while traversing the graph, see `Dfs`,
+/// and `.neighbors(a).detach()`.
+///
+/// * You can create several graphs using the equal node indices but with
+/// differing weights or differing edges.
+///
+/// * Indices don't allow as much compile time checking as references.
+///
+pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
+    nodes: Vec<Node<N, Ix>>,
+    edges: Vec<Edge<E, Ix>>,
+    ty: PhantomData<Ty>,
+}
+
+/// A `Graph` with directed edges.
+///
+/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
+/// *1*.
+pub type DiGraph<N, E, Ix = DefaultIx> = Graph<N, E, Directed, Ix>;
+
+/// A `Graph` with undirected edges.
+///
+/// For example, an edge between *1* and *2* is equivalent to an edge between
+/// *2* and *1*.
+pub type UnGraph<N, E, Ix = DefaultIx> = Graph<N, E, Undirected, Ix>;
+
+/// The resulting cloned graph has the same graph indices as `self`.
+impl<N, E, Ty, Ix: IndexType> Clone for Graph<N, E, Ty, Ix>
+where
+    N: Clone,
+    E: Clone,
+{
+    fn clone(&self) -> Self {
+        Graph {
+            nodes: self.nodes.clone(),
+            edges: self.edges.clone(),
+            ty: self.ty,
+        }
+    }
+
+    fn clone_from(&mut self, rhs: &Self) {
+        self.nodes.clone_from(&rhs.nodes);
+        self.edges.clone_from(&rhs.edges);
+        self.ty = rhs.ty;
+    }
+}
+
+impl<N, E, Ty, Ix> fmt::Debug for Graph<N, E, Ty, Ix>
+where
+    N: fmt::Debug,
+    E: fmt::Debug,
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let etype = if self.is_directed() {
+            "Directed"
+        } else {
+            "Undirected"
+        };
+        let mut fmt_struct = f.debug_struct("Graph");
+        fmt_struct.field("Ty", &etype);
+        fmt_struct.field("node_count", &self.node_count());
+        fmt_struct.field("edge_count", &self.edge_count());
+        if self.edge_count() > 0 {
+            fmt_struct.field(
+                "edges",
+                &self
+                    .edges
+                    .iter()
+                    .map(|e| NoPretty((e.source().index(), e.target().index())))
+                    .format(", "),
+            );
+        }
+        // skip weights if they are ZST!
+        if size_of::<N>() != 0 {
+            fmt_struct.field(
+                "node weights",
+                &DebugMap(|| self.nodes.iter().map(|n| &n.weight).enumerate()),
+            );
+        }
+        if size_of::<E>() != 0 {
+            fmt_struct.field(
+                "edge weights",
+                &DebugMap(|| self.edges.iter().map(|n| &n.weight).enumerate()),
+            );
+        }
+        fmt_struct.finish()
+    }
+}
+
+enum Pair<T> {
+    Both(T, T),
+    One(T),
+    None,
+}
+
+use std::cmp::max;
+
+/// Get mutable references at index `a` and `b`.
+fn index_twice<T>(slc: &mut [T], a: usize, b: usize) -> Pair<&mut T> {
+    if max(a, b) >= slc.len() {
+        Pair::None
+    } else if a == b {
+        Pair::One(&mut slc[max(a, b)])
+    } else {
+        // safe because a, b are in bounds and distinct
+        unsafe {
+            let ar = &mut *(slc.get_unchecked_mut(a) as *mut _);
+            let br = &mut *(slc.get_unchecked_mut(b) as *mut _);
+            Pair::Both(ar, br)
+        }
+    }
+}
+
+impl<N, E> Graph<N, E, Directed> {
+    /// Create a new `Graph` with directed edges.
+    ///
+    /// This is a convenience method. Use `Graph::with_capacity` or `Graph::default` for
+    /// a constructor that is generic in all the type parameters of `Graph`.
+    pub fn new() -> Self {
+        Graph {
+            nodes: Vec::new(),
+            edges: Vec::new(),
+            ty: PhantomData,
+        }
+    }
+}
+
+impl<N, E> Graph<N, E, Undirected> {
+    /// Create a new `Graph` with undirected edges.
+    ///
+    /// This is a convenience method. Use `Graph::with_capacity` or `Graph::default` for
+    /// a constructor that is generic in all the type parameters of `Graph`.
+    pub fn new_undirected() -> Self {
+        Graph {
+            nodes: Vec::new(),
+            edges: Vec::new(),
+            ty: PhantomData,
+        }
+    }
+}
+
+impl<N, E, Ty, Ix> Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// Create a new `Graph` with estimated capacity.
+    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
+        Graph {
+            nodes: Vec::with_capacity(nodes),
+            edges: Vec::with_capacity(edges),
+            ty: PhantomData,
+        }
+    }
+
+    /// Return the number of nodes (vertices) in the graph.
+    ///
+    /// Computes in **O(1)** time.
+    pub fn node_count(&self) -> usize {
+        self.nodes.len()
+    }
+
+    /// Return the number of edges in the graph.
+    ///
+    /// Computes in **O(1)** time.
+    pub fn edge_count(&self) -> usize {
+        self.edges.len()
+    }
+
+    /// Whether the graph has directed edges or not.
+    #[inline]
+    pub fn is_directed(&self) -> bool {
+        Ty::is_directed()
+    }
+
+    /// Add a node (also called vertex) with associated data `weight` to the graph.
+    ///
+    /// Computes in **O(1)** time.
+    ///
+    /// Return the index of the new node.
+    ///
+    /// **Panics** if the Graph is at the maximum number of nodes for its index
+    /// type (N/A if usize).
+    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
+        let node = Node {
+            weight,
+            next: [EdgeIndex::end(), EdgeIndex::end()],
+        };
+        let node_idx = NodeIndex::new(self.nodes.len());
+        // check for max capacity, except if we use usize
+        assert!(<Ix as IndexType>::max().index() == !0 || NodeIndex::end() != node_idx);
+        self.nodes.push(node);
+        node_idx
+    }
+
+    /// Access the weight for node `a`.
+    ///
+    /// Also available with indexing syntax: `&graph[a]`.
+    pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N> {
+        self.nodes.get(a.index()).map(|n| &n.weight)
+    }
+
+    /// Access the weight for node `a`, mutably.
+    ///
+    /// Also available with indexing syntax: `&mut graph[a]`.
+    pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N> {
+        self.nodes.get_mut(a.index()).map(|n| &mut n.weight)
+    }
+
+    /// Add an edge from `a` to `b` to the graph, with its associated
+    /// data `weight`.
+    ///
+    /// Return the index of the new edge.
+    ///
+    /// Computes in **O(1)** time.
+    ///
+    /// **Panics** if any of the nodes don't exist.<br>
+    /// **Panics** if the Graph is at the maximum number of edges for its index
+    /// type (N/A if usize).
+    ///
+    /// **Note:** `Graph` allows adding parallel (“duplicate”) edges. If you want
+    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
+    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
+        let edge_idx = EdgeIndex::new(self.edges.len());
+        assert!(<Ix as IndexType>::max().index() == !0 || EdgeIndex::end() != edge_idx);
+        let mut edge = Edge {
+            weight,
+            node: [a, b],
+            next: [EdgeIndex::end(); 2],
+        };
+        match index_twice(&mut self.nodes, a.index(), b.index()) {
+            Pair::None => panic!("Graph::add_edge: node indices out of bounds"),
+            Pair::One(an) => {
+                edge.next = an.next;
+                an.next[0] = edge_idx;
+                an.next[1] = edge_idx;
+            }
+            Pair::Both(an, bn) => {
+                // a and b are different indices
+                edge.next = [an.next[0], bn.next[1]];
+                an.next[0] = edge_idx;
+                bn.next[1] = edge_idx;
+            }
+        }
+        self.edges.push(edge);
+        edge_idx
+    }
+
+    /// Add or update an edge from `a` to `b`.
+    /// If the edge already exists, its weight is updated.
+    ///
+    /// Return the index of the affected edge.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    ///
+    /// **Panics** if any of the nodes don't exist.
+    pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
+        if let Some(ix) = self.find_edge(a, b) {
+            if let Some(ed) = self.edge_weight_mut(ix) {
+                *ed = weight;
+                return ix;
+            }
+        }
+        self.add_edge(a, b, weight)
+    }
+
+    /// Access the weight for edge `e`.
+    ///
+    /// Also available with indexing syntax: `&graph[e]`.
+    pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
+        self.edges.get(e.index()).map(|ed| &ed.weight)
+    }
+
+    /// Access the weight for edge `e`, mutably.
+    ///
+    /// Also available with indexing syntax: `&mut graph[e]`.
+    pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
+        self.edges.get_mut(e.index()).map(|ed| &mut ed.weight)
+    }
+
+    /// Access the source and target nodes for `e`.
+    pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
+        self.edges
+            .get(e.index())
+            .map(|ed| (ed.source(), ed.target()))
+    }
+
+    /// Remove `a` from the graph if it exists, and return its weight.
+    /// If it doesn't exist in the graph, return `None`.
+    ///
+    /// Apart from `a`, this invalidates the last node index in the graph
+    /// (that node will adopt the removed node index). Edge indices are
+    /// invalidated as they would be following the removal of each edge
+    /// with an endpoint in `a`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of affected
+    /// edges, including *n* calls to `.remove_edge()` where *n* is the number
+    /// of edges with an endpoint in `a`, and including the edges with an
+    /// endpoint in the displaced node.
+    pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N> {
+        self.nodes.get(a.index())?;
+        for d in &DIRECTIONS {
+            let k = d.index();
+
+            // Remove all edges from and to this node.
+            loop {
+                let next = self.nodes[a.index()].next[k];
+                if next == EdgeIndex::end() {
+                    break;
+                }
+                let ret = self.remove_edge(next);
+                debug_assert!(ret.is_some());
+                let _ = ret;
+            }
+        }
+
+        // Use swap_remove -- only the swapped-in node is going to change
+        // NodeIndex<Ix>, so we only have to walk its edges and update them.
+
+        let node = self.nodes.swap_remove(a.index());
+
+        // Find the edge lists of the node that had to relocate.
+        // It may be that no node had to relocate, then we are done already.
+        let swap_edges = match self.nodes.get(a.index()) {
+            None => return Some(node.weight),
+            Some(ed) => ed.next,
+        };
+
+        // The swapped element's old index
+        let old_index = NodeIndex::new(self.nodes.len());
+        let new_index = a;
+
+        // Adjust the starts of the out edges, and ends of the in edges.
+        for &d in &DIRECTIONS {
+            let k = d.index();
+            let mut edges = edges_walker_mut(&mut self.edges, swap_edges[k], d);
+            while let Some(curedge) = edges.next_edge() {
+                debug_assert!(curedge.node[k] == old_index);
+                curedge.node[k] = new_index;
+            }
+        }
+        Some(node.weight)
+    }
+
+    /// For edge `e` with endpoints `edge_node`, replace links to it,
+    /// with links to `edge_next`.
+    fn change_edge_links(
+        &mut self,
+        edge_node: [NodeIndex<Ix>; 2],
+        e: EdgeIndex<Ix>,
+        edge_next: [EdgeIndex<Ix>; 2],
+    ) {
+        for &d in &DIRECTIONS {
+            let k = d.index();
+            let node = match self.nodes.get_mut(edge_node[k].index()) {
+                Some(r) => r,
+                None => {
+                    debug_assert!(
+                        false,
+                        "Edge's endpoint dir={:?} index={:?} not found",
+                        d, edge_node[k]
+                    );
+                    return;
+                }
+            };
+            let fst = node.next[k];
+            if fst == e {
+                //println!("Updating first edge 0 for node {}, set to {}", edge_node[0], edge_next[0]);
+                node.next[k] = edge_next[k];
+            } else {
+                let mut edges = edges_walker_mut(&mut self.edges, fst, d);
+                while let Some(curedge) = edges.next_edge() {
+                    if curedge.next[k] == e {
+                        curedge.next[k] = edge_next[k];
+                        break; // the edge can only be present once in the list.
+                    }
+                }
+            }
+        }
+    }
+
+    /// Remove an edge and return its edge weight, or `None` if it didn't exist.
+    ///
+    /// Apart from `e`, this invalidates the last edge index in the graph
+    /// (that edge will adopt the removed edge index).
+    ///
+    /// Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for
+    /// the vertices of `e` and the vertices of another affected edge.
+    pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E> {
+        // every edge is part of two lists,
+        // outgoing and incoming edges.
+        // Remove it from both
+        let (edge_node, edge_next) = match self.edges.get(e.index()) {
+            None => return None,
+            Some(x) => (x.node, x.next),
+        };
+        // Remove the edge from its in and out lists by replacing it with
+        // a link to the next in the list.
+        self.change_edge_links(edge_node, e, edge_next);
+        self.remove_edge_adjust_indices(e)
+    }
+
+    fn remove_edge_adjust_indices(&mut self, e: EdgeIndex<Ix>) -> Option<E> {
+        // swap_remove the edge -- only the removed edge
+        // and the edge swapped into place are affected and need updating
+        // indices.
+        let edge = self.edges.swap_remove(e.index());
+        let swap = match self.edges.get(e.index()) {
+            // no elment needed to be swapped.
+            None => return Some(edge.weight),
+            Some(ed) => ed.node,
+        };
+        let swapped_e = EdgeIndex::new(self.edges.len());
+
+        // Update the edge lists by replacing links to the old index by references to the new
+        // edge index.
+        self.change_edge_links(swap, swapped_e, [e, e]);
+        Some(edge.weight)
+    }
+
+    /// Return an iterator of all nodes with an edge starting from `a`.
+    ///
+    /// - `Directed`: Outgoing edges from `a`.
+    /// - `Undirected`: All edges from or to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// Use [`.neighbors(a).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix> {
+        self.neighbors_directed(a, Outgoing)
+    }
+
+    /// Return an iterator of all neighbors that have an edge between them and
+    /// `a`, in the specified direction.
+    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
+    ///
+    /// - `Directed`, `Outgoing`: All edges from `a`.
+    /// - `Directed`, `Incoming`: All edges to `a`.
+    /// - `Undirected`: All edges from or to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// For a `Directed` graph, neighbors are listed in reverse order of their
+    /// addition to the graph, so the most recently added edge's neighbor is
+    /// listed first. The order in an `Undirected` graph is arbitrary.
+    ///
+    /// Use [`.neighbors_directed(a, dir).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    pub fn neighbors_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Neighbors<E, Ix> {
+        let mut iter = self.neighbors_undirected(a);
+        if self.is_directed() {
+            let k = dir.index();
+            iter.next[1 - k] = EdgeIndex::end();
+            iter.skip_start = NodeIndex::end();
+        }
+        iter
+    }
+
+    /// Return an iterator of all neighbors that have an edge between them and
+    /// `a`, in either direction.
+    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
+    ///
+    /// - `Directed` and `Undirected`: All edges from or to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// Use [`.neighbors_undirected(a).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    ///
+    pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix> {
+        Neighbors {
+            skip_start: a,
+            edges: &self.edges,
+            next: match self.nodes.get(a.index()) {
+                None => [EdgeIndex::end(), EdgeIndex::end()],
+                Some(n) => n.next,
+            },
+        }
+    }
+
+    /// Return an iterator of all edges of `a`.
+    ///
+    /// - `Directed`: Outgoing edges from `a`.
+    /// - `Undirected`: All edges connected to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
+        self.edges_directed(a, Outgoing)
+    }
+
+    /// Return an iterator of all edges of `a`, in the specified direction.
+    ///
+    /// - `Directed`, `Outgoing`: All edges from `a`.
+    /// - `Directed`, `Incoming`: All edges to `a`.
+    /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
+    ///   edge.
+    /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
+    ///   edge.
+    ///
+    /// Produces an empty iterator if the node `a` doesn't exist.<br>
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix> {
+        Edges {
+            skip_start: a,
+            edges: &self.edges,
+            direction: dir,
+            next: match self.nodes.get(a.index()) {
+                None => [EdgeIndex::end(), EdgeIndex::end()],
+                Some(n) => n.next,
+            },
+            ty: PhantomData,
+        }
+    }
+
+    /// Return an iterator over all the edges connecting `a` and `b`.
+    ///
+    /// - `Directed`: Outgoing edges from `a`.
+    /// - `Undirected`: All edges connected to `a`.
+    ///
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edges_connecting(
+        &self,
+        a: NodeIndex<Ix>,
+        b: NodeIndex<Ix>,
+    ) -> EdgesConnecting<E, Ty, Ix> {
+        EdgesConnecting {
+            target_node: b,
+            edges: self.edges_directed(a, Direction::Outgoing),
+            ty: PhantomData,
+        }
+    }
+
+    /// Lookup if there is an edge from `a` to `b`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
+        self.find_edge(a, b).is_some()
+    }
+
+    /// Lookup an edge from `a` to `b`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
+        if !self.is_directed() {
+            self.find_edge_undirected(a, b).map(|(ix, _)| ix)
+        } else {
+            match self.nodes.get(a.index()) {
+                None => None,
+                Some(node) => self.find_edge_directed_from_node(node, b),
+            }
+        }
+    }
+
+    fn find_edge_directed_from_node(
+        &self,
+        node: &Node<N, Ix>,
+        b: NodeIndex<Ix>,
+    ) -> Option<EdgeIndex<Ix>> {
+        let mut edix = node.next[0];
+        while let Some(edge) = self.edges.get(edix.index()) {
+            if edge.node[1] == b {
+                return Some(edix);
+            }
+            edix = edge.next[0];
+        }
+        None
+    }
+
+    /// Lookup an edge between `a` and `b`, in either direction.
+    ///
+    /// If the graph is undirected, then this is equivalent to `.find_edge()`.
+    ///
+    /// Return the edge index and its directionality, with `Outgoing` meaning
+    /// from `a` to `b` and `Incoming` the reverse,
+    /// or `None` if the edge does not exist.
+    pub fn find_edge_undirected(
+        &self,
+        a: NodeIndex<Ix>,
+        b: NodeIndex<Ix>,
+    ) -> Option<(EdgeIndex<Ix>, Direction)> {
+        match self.nodes.get(a.index()) {
+            None => None,
+            Some(node) => self.find_edge_undirected_from_node(node, b),
+        }
+    }
+
+    fn find_edge_undirected_from_node(
+        &self,
+        node: &Node<N, Ix>,
+        b: NodeIndex<Ix>,
+    ) -> Option<(EdgeIndex<Ix>, Direction)> {
+        for &d in &DIRECTIONS {
+            let k = d.index();
+            let mut edix = node.next[k];
+            while let Some(edge) = self.edges.get(edix.index()) {
+                if edge.node[1 - k] == b {
+                    return Some((edix, d));
+                }
+                edix = edge.next[k];
+            }
+        }
+        None
+    }
+
+    /// Return an iterator over either the nodes without edges to them
+    /// (`Incoming`) or from them (`Outgoing`).
+    ///
+    /// An *internal* node has both incoming and outgoing edges.
+    /// The nodes in `.externals(Incoming)` are the source nodes and
+    /// `.externals(Outgoing)` are the sinks of the graph.
+    ///
+    /// For a graph with undirected edges, both the sinks and the sources are
+    /// just the nodes without edges.
+    ///
+    /// The whole iteration computes in **O(|V|)** time.
+    pub fn externals(&self, dir: Direction) -> Externals<N, Ty, Ix> {
+        Externals {
+            iter: self.nodes.iter().enumerate(),
+            dir,
+            ty: PhantomData,
+        }
+    }
+
+    /// Return an iterator over the node indices of the graph.
+    ///
+    /// For example, in a rare case where a graph algorithm were not applicable,
+    /// the following code will iterate through all nodes to find a
+    /// specific index:
+    ///
+    /// ```
+    /// # use petgraph::Graph;
+    /// # let mut g = Graph::<&str, i32>::new();
+    /// # g.add_node("book");
+    /// let index = g.node_indices().find(|i| g[*i] == "book").unwrap();
+    /// ```
+    pub fn node_indices(&self) -> NodeIndices<Ix> {
+        NodeIndices {
+            r: 0..self.node_count(),
+            ty: PhantomData,
+        }
+    }
+
+    /// Return an iterator yielding mutable access to all node weights.
+    ///
+    /// The order in which weights are yielded matches the order of their
+    /// node indices.
+    pub fn node_weights_mut(&mut self) -> NodeWeightsMut<N, Ix> {
+        NodeWeightsMut {
+            nodes: self.nodes.iter_mut(),
+        }
+    }
+
+    /// Return an iterator over the edge indices of the graph
+    pub fn edge_indices(&self) -> EdgeIndices<Ix> {
+        EdgeIndices {
+            r: 0..self.edge_count(),
+            ty: PhantomData,
+        }
+    }
+
+    /// Create an iterator over all edges, in indexed order.
+    ///
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edge_references(&self) -> EdgeReferences<E, Ix> {
+        EdgeReferences {
+            iter: self.edges.iter().enumerate(),
+        }
+    }
+
+    /// Return an iterator yielding mutable access to all edge weights.
+    ///
+    /// The order in which weights are yielded matches the order of their
+    /// edge indices.
+    pub fn edge_weights_mut(&mut self) -> EdgeWeightsMut<E, Ix> {
+        EdgeWeightsMut {
+            edges: self.edges.iter_mut(),
+        }
+    }
+
+    // Remaining methods are of the more internal flavour, read-only access to
+    // the data structure's internals.
+
+    /// Access the internal node array.
+    pub fn raw_nodes(&self) -> &[Node<N, Ix>] {
+        &self.nodes
+    }
+
+    /// Access the internal edge array.
+    pub fn raw_edges(&self) -> &[Edge<E, Ix>] {
+        &self.edges
+    }
+
+    /// Convert the graph into a vector of Nodes and a vector of Edges
+    pub fn into_nodes_edges(self) -> (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>) {
+        (self.nodes, self.edges)
+    }
+
+    /// Accessor for data structure internals: the first edge in the given direction.
+    pub fn first_edge(&self, a: NodeIndex<Ix>, dir: Direction) -> Option<EdgeIndex<Ix>> {
+        match self.nodes.get(a.index()) {
+            None => None,
+            Some(node) => {
+                let edix = node.next[dir.index()];
+                if edix == EdgeIndex::end() {
+                    None
+                } else {
+                    Some(edix)
+                }
+            }
+        }
+    }
+
+    /// Accessor for data structure internals: the next edge for the given direction.
+    pub fn next_edge(&self, e: EdgeIndex<Ix>, dir: Direction) -> Option<EdgeIndex<Ix>> {
+        match self.edges.get(e.index()) {
+            None => None,
+            Some(node) => {
+                let edix = node.next[dir.index()];
+                if edix == EdgeIndex::end() {
+                    None
+                } else {
+                    Some(edix)
+                }
+            }
+        }
+    }
+
+    /// Index the `Graph` by two indices, any combination of
+    /// node or edge indices is fine.
+    ///
+    /// **Panics** if the indices are equal or if they are out of bounds.
+    ///
+    /// ```
+    /// use petgraph::{Graph, Incoming};
+    /// use petgraph::visit::Dfs;
+    ///
+    /// let mut gr = Graph::new();
+    /// let a = gr.add_node(0.);
+    /// let b = gr.add_node(0.);
+    /// let c = gr.add_node(0.);
+    /// gr.add_edge(a, b, 3.);
+    /// gr.add_edge(b, c, 2.);
+    /// gr.add_edge(c, b, 1.);
+    ///
+    /// // walk the graph and sum incoming edges into the node weight
+    /// let mut dfs = Dfs::new(&gr, a);
+    /// while let Some(node) = dfs.next(&gr) {
+    ///     // use a walker -- a detached neighbors iterator
+    ///     let mut edges = gr.neighbors_directed(node, Incoming).detach();
+    ///     while let Some(edge) = edges.next_edge(&gr) {
+    ///         let (nw, ew) = gr.index_twice_mut(node, edge);
+    ///         *nw += *ew;
+    ///     }
+    /// }
+    ///
+    /// // check the result
+    /// assert_eq!(gr[a], 0.);
+    /// assert_eq!(gr[b], 4.);
+    /// assert_eq!(gr[c], 2.);
+    /// ```
+    pub fn index_twice_mut<T, U>(
+        &mut self,
+        i: T,
+        j: U,
+    ) -> (
+        &mut <Self as Index<T>>::Output,
+        &mut <Self as Index<U>>::Output,
+    )
+    where
+        Self: IndexMut<T> + IndexMut<U>,
+        T: GraphIndex,
+        U: GraphIndex,
+    {
+        assert!(T::is_node_index() != U::is_node_index() || i.index() != j.index());
+
+        // Allow two mutable indexes here -- they are nonoverlapping
+        unsafe {
+            let self_mut = self as *mut _;
+            (
+                <Self as IndexMut<T>>::index_mut(&mut *self_mut, i),
+                <Self as IndexMut<U>>::index_mut(&mut *self_mut, j),
+            )
+        }
+    }
+
+    /// Reverse the direction of all edges
+    pub fn reverse(&mut self) {
+        // swap edge endpoints,
+        // edge incoming / outgoing lists,
+        // node incoming / outgoing lists
+        for edge in &mut self.edges {
+            edge.node.swap(0, 1);
+            edge.next.swap(0, 1);
+        }
+        for node in &mut self.nodes {
+            node.next.swap(0, 1);
+        }
+    }
+
+    /// Remove all nodes and edges
+    pub fn clear(&mut self) {
+        self.nodes.clear();
+        self.edges.clear();
+    }
+
+    /// Remove all edges
+    pub fn clear_edges(&mut self) {
+        self.edges.clear();
+        for node in &mut self.nodes {
+            node.next = [EdgeIndex::end(), EdgeIndex::end()];
+        }
+    }
+
+    /// Return the current node and edge capacity of the graph.
+    pub fn capacity(&self) -> (usize, usize) {
+        (self.nodes.capacity(), self.edges.capacity())
+    }
+
+    /// Reserves capacity for at least `additional` more nodes to be inserted in
+    /// the graph. Graph may reserve more space to avoid frequent reallocations.
+    ///
+    /// **Panics** if the new capacity overflows `usize`.
+    pub fn reserve_nodes(&mut self, additional: usize) {
+        self.nodes.reserve(additional);
+    }
+
+    /// Reserves capacity for at least `additional` more edges to be inserted in
+    /// the graph. Graph may reserve more space to avoid frequent reallocations.
+    ///
+    /// **Panics** if the new capacity overflows `usize`.
+    pub fn reserve_edges(&mut self, additional: usize) {
+        self.edges.reserve(additional);
+    }
+
+    /// Reserves the minimum capacity for exactly `additional` more nodes to be
+    /// inserted in the graph. Does nothing if the capacity is already
+    /// sufficient.
+    ///
+    /// Prefer `reserve_nodes` if future insertions are expected.
+    ///
+    /// **Panics** if the new capacity overflows `usize`.
+    pub fn reserve_exact_nodes(&mut self, additional: usize) {
+        self.nodes.reserve_exact(additional);
+    }
+
+    /// Reserves the minimum capacity for exactly `additional` more edges to be
+    /// inserted in the graph.
+    /// Does nothing if the capacity is already sufficient.
+    ///
+    /// Prefer `reserve_edges` if future insertions are expected.
+    ///
+    /// **Panics** if the new capacity overflows `usize`.
+    pub fn reserve_exact_edges(&mut self, additional: usize) {
+        self.edges.reserve_exact(additional);
+    }
+
+    /// Shrinks the capacity of the underlying nodes collection as much as possible.
+    pub fn shrink_to_fit_nodes(&mut self) {
+        self.nodes.shrink_to_fit();
+    }
+
+    /// Shrinks the capacity of the underlying edges collection as much as possible.
+    pub fn shrink_to_fit_edges(&mut self) {
+        self.edges.shrink_to_fit();
+    }
+
+    /// Shrinks the capacity of the graph as much as possible.
+    pub fn shrink_to_fit(&mut self) {
+        self.nodes.shrink_to_fit();
+        self.edges.shrink_to_fit();
+    }
+
+    /// Keep all nodes that return `true` from the `visit` closure,
+    /// remove the others.
+    ///
+    /// `visit` is provided a proxy reference to the graph, so that
+    /// the graph can be walked and associated data modified.
+    ///
+    /// The order nodes are visited is not specified.
+    pub fn retain_nodes<F>(&mut self, mut visit: F)
+    where
+        F: FnMut(Frozen<Self>, NodeIndex<Ix>) -> bool,
+    {
+        for index in self.node_indices().rev() {
+            if !visit(Frozen(self), index) {
+                let ret = self.remove_node(index);
+                debug_assert!(ret.is_some());
+                let _ = ret;
+            }
+        }
+    }
+
+    /// Keep all edges that return `true` from the `visit` closure,
+    /// remove the others.
+    ///
+    /// `visit` is provided a proxy reference to the graph, so that
+    /// the graph can be walked and associated data modified.
+    ///
+    /// The order edges are visited is not specified.
+    pub fn retain_edges<F>(&mut self, mut visit: F)
+    where
+        F: FnMut(Frozen<Self>, EdgeIndex<Ix>) -> bool,
+    {
+        for index in self.edge_indices().rev() {
+            if !visit(Frozen(self), index) {
+                let ret = self.remove_edge(index);
+                debug_assert!(ret.is_some());
+                let _ = ret;
+            }
+        }
+    }
+
+    /// Create a new `Graph` from an iterable of edges.
+    ///
+    /// Node weights `N` are set to default values.
+    /// Edge weights `E` may either be specified in the list,
+    /// or they are filled with default values.
+    ///
+    /// Nodes are inserted automatically to match the edges.
+    ///
+    /// ```
+    /// use petgraph::Graph;
+    ///
+    /// let gr = Graph::<(), i32>::from_edges(&[
+    ///     (0, 1), (0, 2), (0, 3),
+    ///     (1, 2), (1, 3),
+    ///     (2, 3),
+    /// ]);
+    /// ```
+    pub fn from_edges<I>(iterable: I) -> Self
+    where
+        I: IntoIterator,
+        I::Item: IntoWeightedEdge<E>,
+        <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+        N: Default,
+    {
+        let mut g = Self::with_capacity(0, 0);
+        g.extend_with_edges(iterable);
+        g
+    }
+
+    /// Extend the graph from an iterable of edges.
+    ///
+    /// Node weights `N` are set to default values.
+    /// Edge weights `E` may either be specified in the list,
+    /// or they are filled with default values.
+    ///
+    /// Nodes are inserted automatically to match the edges.
+    pub fn extend_with_edges<I>(&mut self, iterable: I)
+    where
+        I: IntoIterator,
+        I::Item: IntoWeightedEdge<E>,
+        <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+        N: Default,
+    {
+        let iter = iterable.into_iter();
+        let (low, _) = iter.size_hint();
+        self.edges.reserve(low);
+
+        for elt in iter {
+            let (source, target, weight) = elt.into_weighted_edge();
+            let (source, target) = (source.into(), target.into());
+            let nx = cmp::max(source, target);
+            while nx.index() >= self.node_count() {
+                self.add_node(N::default());
+            }
+            self.add_edge(source, target, weight);
+        }
+    }
+
+    /// Create a new `Graph` by mapping node and
+    /// edge weights to new values.
+    ///
+    /// The resulting graph has the same structure and the same
+    /// graph indices as `self`.
+    pub fn map<'a, F, G, N2, E2>(
+        &'a self,
+        mut node_map: F,
+        mut edge_map: G,
+    ) -> Graph<N2, E2, Ty, Ix>
+    where
+        F: FnMut(NodeIndex<Ix>, &'a N) -> N2,
+        G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,
+    {
+        let mut g = Graph::with_capacity(self.node_count(), self.edge_count());
+        g.nodes.extend(enumerate(&self.nodes).map(|(i, node)| Node {
+            weight: node_map(NodeIndex::new(i), &node.weight),
+            next: node.next,
+        }));
+        g.edges.extend(enumerate(&self.edges).map(|(i, edge)| Edge {
+            weight: edge_map(EdgeIndex::new(i), &edge.weight),
+            next: edge.next,
+            node: edge.node,
+        }));
+        g
+    }
+
+    /// Create a new `Graph` by mapping nodes and edges.
+    /// A node or edge may be mapped to `None` to exclude it from
+    /// the resulting graph.
+    ///
+    /// Nodes are mapped first with the `node_map` closure, then
+    /// `edge_map` is called for the edges that have not had any endpoint
+    /// removed.
+    ///
+    /// The resulting graph has the structure of a subgraph of the original graph.
+    /// If no nodes are removed, the resulting graph has compatible node
+    /// indices; if neither nodes nor edges are removed, the result has
+    /// the same graph indices as `self`.
+    pub fn filter_map<'a, F, G, N2, E2>(
+        &'a self,
+        mut node_map: F,
+        mut edge_map: G,
+    ) -> Graph<N2, E2, Ty, Ix>
+    where
+        F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>,
+        G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,
+    {
+        let mut g = Graph::with_capacity(0, 0);
+        // mapping from old node index to new node index, end represents removed.
+        let mut node_index_map = vec![NodeIndex::end(); self.node_count()];
+        for (i, node) in enumerate(&self.nodes) {
+            if let Some(nw) = node_map(NodeIndex::new(i), &node.weight) {
+                node_index_map[i] = g.add_node(nw);
+            }
+        }
+        for (i, edge) in enumerate(&self.edges) {
+            // skip edge if any endpoint was removed
+            let source = node_index_map[edge.source().index()];
+            let target = node_index_map[edge.target().index()];
+            if source != NodeIndex::end() && target != NodeIndex::end() {
+                if let Some(ew) = edge_map(EdgeIndex::new(i), &edge.weight) {
+                    g.add_edge(source, target, ew);
+                }
+            }
+        }
+        g
+    }
+
+    /// Convert the graph into either undirected or directed. No edge adjustments
+    /// are done, so you may want to go over the result to remove or add edges.
+    ///
+    /// Computes in **O(1)** time.
+    pub fn into_edge_type<NewTy>(self) -> Graph<N, E, NewTy, Ix>
+    where
+        NewTy: EdgeType,
+    {
+        Graph {
+            nodes: self.nodes,
+            edges: self.edges,
+            ty: PhantomData,
+        }
+    }
+
+    //
+    // internal methods
+    //
+    #[cfg(feature = "serde-1")]
+    /// Fix up node and edge links after deserialization
+    fn link_edges(&mut self) -> Result<(), NodeIndex<Ix>> {
+        for (edge_index, edge) in enumerate(&mut self.edges) {
+            let a = edge.source();
+            let b = edge.target();
+            let edge_idx = EdgeIndex::new(edge_index);
+            match index_twice(&mut self.nodes, a.index(), b.index()) {
+                Pair::None => return Err(if a > b { a } else { b }),
+                Pair::One(an) => {
+                    edge.next = an.next;
+                    an.next[0] = edge_idx;
+                    an.next[1] = edge_idx;
+                }
+                Pair::Both(an, bn) => {
+                    // a and b are different indices
+                    edge.next = [an.next[0], bn.next[1]];
+                    an.next[0] = edge_idx;
+                    bn.next[1] = edge_idx;
+                }
+            }
+        }
+        Ok(())
+    }
+}
+
+/// An iterator over either the nodes without edges to them or from them.
+pub struct Externals<'a, N: 'a, Ty, Ix: IndexType = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Node<N, Ix>>>,
+    dir: Direction,
+    ty: PhantomData<Ty>,
+}
+
+impl<'a, N: 'a, Ty, Ix> Iterator for Externals<'a, N, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Item = NodeIndex<Ix>;
+    fn next(&mut self) -> Option<NodeIndex<Ix>> {
+        let k = self.dir.index();
+        loop {
+            match self.iter.next() {
+                None => return None,
+                Some((index, node)) => {
+                    if node.next[k] == EdgeIndex::end()
+                        && (Ty::is_directed() || node.next[1 - k] == EdgeIndex::end())
+                    {
+                        return Some(NodeIndex::new(index));
+                    } else {
+                        continue;
+                    }
+                }
+            }
+        }
+    }
+}
+
+/// Iterator over the neighbors of a node.
+///
+/// Iterator element type is `NodeIndex<Ix>`.
+///
+/// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2] or
+/// [`.neighbors_undirected()`][3].
+///
+/// [1]: struct.Graph.html#method.neighbors
+/// [2]: struct.Graph.html#method.neighbors_directed
+/// [3]: struct.Graph.html#method.neighbors_undirected
+pub struct Neighbors<'a, E: 'a, Ix: 'a = DefaultIx> {
+    /// starting node to skip over
+    skip_start: NodeIndex<Ix>,
+    edges: &'a [Edge<E, Ix>],
+    next: [EdgeIndex<Ix>; 2],
+}
+
+impl<'a, E, Ix> Iterator for Neighbors<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = NodeIndex<Ix>;
+
+    fn next(&mut self) -> Option<NodeIndex<Ix>> {
+        // First any outgoing edges
+        match self.edges.get(self.next[0].index()) {
+            None => {}
+            Some(edge) => {
+                self.next[0] = edge.next[0];
+                return Some(edge.node[1]);
+            }
+        }
+        // Then incoming edges
+        // For an "undirected" iterator (traverse both incoming
+        // and outgoing edge lists), make sure we don't double
+        // count selfloops by skipping them in the incoming list.
+        while let Some(edge) = self.edges.get(self.next[1].index()) {
+            self.next[1] = edge.next[1];
+            if edge.node[0] != self.skip_start {
+                return Some(edge.node[0]);
+            }
+        }
+        None
+    }
+}
+
+impl<'a, E, Ix> Clone for Neighbors<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    clone_fields!(Neighbors, skip_start, edges, next,);
+}
+
+impl<'a, E, Ix> Neighbors<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    /// Return a “walker” object that can be used to step through the
+    /// neighbors and edges from the origin node.
+    ///
+    /// Note: The walker does not borrow from the graph, this is to allow mixing
+    /// edge walking with mutating the graph's weights.
+    pub fn detach(&self) -> WalkNeighbors<Ix> {
+        WalkNeighbors {
+            skip_start: self.skip_start,
+            next: self.next,
+        }
+    }
+}
+
+struct EdgesWalkerMut<'a, E: 'a, Ix: IndexType = DefaultIx> {
+    edges: &'a mut [Edge<E, Ix>],
+    next: EdgeIndex<Ix>,
+    dir: Direction,
+}
+
+fn edges_walker_mut<E, Ix>(
+    edges: &mut [Edge<E, Ix>],
+    next: EdgeIndex<Ix>,
+    dir: Direction,
+) -> EdgesWalkerMut<E, Ix>
+where
+    Ix: IndexType,
+{
+    EdgesWalkerMut { edges, next, dir }
+}
+
+impl<'a, E, Ix> EdgesWalkerMut<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    fn next_edge(&mut self) -> Option<&mut Edge<E, Ix>> {
+        self.next().map(|t| t.1)
+    }
+
+    fn next(&mut self) -> Option<(EdgeIndex<Ix>, &mut Edge<E, Ix>)> {
+        let this_index = self.next;
+        let k = self.dir.index();
+        match self.edges.get_mut(self.next.index()) {
+            None => None,
+            Some(edge) => {
+                self.next = edge.next[k];
+                Some((this_index, edge))
+            }
+        }
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoEdges for &'a Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Edges = Edges<'a, E, Ty, Ix>;
+    fn edges(self, a: Self::NodeId) -> Self::Edges {
+        self.edges(a)
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type EdgesDirected = Edges<'a, E, Ty, Ix>;
+    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
+        self.edges_directed(a, dir)
+    }
+}
+
+/// Iterator over the edges of from or to a node
+pub struct Edges<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// starting node to skip over
+    skip_start: NodeIndex<Ix>,
+    edges: &'a [Edge<E, Ix>],
+
+    /// Next edge to visit.
+    next: [EdgeIndex<Ix>; 2],
+
+    /// For directed graphs: the direction to iterate in
+    /// For undirected graphs: the direction of edges
+    direction: Direction,
+    ty: PhantomData<Ty>,
+}
+
+impl<'a, E, Ty, Ix> Iterator for Edges<'a, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Item = EdgeReference<'a, E, Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        //      type        direction    |    iterate over    reverse
+        //                               |
+        //    Directed      Outgoing     |      outgoing        no
+        //    Directed      Incoming     |      incoming        no
+        //   Undirected     Outgoing     |        both       incoming
+        //   Undirected     Incoming     |        both       outgoing
+
+        // For iterate_over, "both" is represented as None.
+        // For reverse, "no" is represented as None.
+        let (iterate_over, reverse) = if Ty::is_directed() {
+            (Some(self.direction), None)
+        } else {
+            (None, Some(self.direction.opposite()))
+        };
+
+        if iterate_over.unwrap_or(Outgoing) == Outgoing {
+            let i = self.next[0].index();
+            if let Some(Edge { node, weight, next }) = self.edges.get(i) {
+                self.next[0] = next[0];
+                return Some(EdgeReference {
+                    index: edge_index(i),
+                    node: if reverse == Some(Outgoing) {
+                        swap_pair(*node)
+                    } else {
+                        *node
+                    },
+                    weight,
+                });
+            }
+        }
+
+        if iterate_over.unwrap_or(Incoming) == Incoming {
+            while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
+                let edge_index = self.next[1];
+                self.next[1] = next[1];
+                // In any of the "both" situations, self-loops would be iterated over twice.
+                // Skip them here.
+                if iterate_over.is_none() && node[0] == self.skip_start {
+                    continue;
+                }
+
+                return Some(EdgeReference {
+                    index: edge_index,
+                    node: if reverse == Some(Incoming) {
+                        swap_pair(*node)
+                    } else {
+                        *node
+                    },
+                    weight,
+                });
+            }
+        }
+
+        None
+    }
+}
+
+/// Iterator over the multiple directed edges connecting a source node to a target node
+pub struct EdgesConnecting<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    target_node: NodeIndex<Ix>,
+    edges: Edges<'a, E, Ty, Ix>,
+    ty: PhantomData<Ty>,
+}
+
+impl<'a, E, Ty, Ix> Iterator for EdgesConnecting<'a, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Item = EdgeReference<'a, E, Ix>;
+
+    fn next(&mut self) -> Option<EdgeReference<'a, E, Ix>> {
+        while let Some(edge) = self.edges.next() {
+            if edge.node[1] == self.target_node {
+                return Some(edge);
+            }
+        }
+
+        None
+    }
+}
+
+fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
+    x.swap(0, 1);
+    x
+}
+
+impl<'a, E, Ty, Ix> Clone for Edges<'a, E, Ty, Ix>
+where
+    Ix: IndexType,
+    Ty: EdgeType,
+{
+    fn clone(&self) -> Self {
+        Edges {
+            skip_start: self.skip_start,
+            edges: self.edges,
+            next: self.next,
+            direction: self.direction,
+            ty: self.ty,
+        }
+    }
+}
+
+/// Iterator yielding mutable access to all node weights.
+pub struct NodeWeightsMut<'a, N: 'a, Ix: IndexType = DefaultIx> {
+    nodes: ::std::slice::IterMut<'a, Node<N, Ix>>,
+}
+
+impl<'a, N, Ix> Iterator for NodeWeightsMut<'a, N, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = &'a mut N;
+
+    fn next(&mut self) -> Option<&'a mut N> {
+        self.nodes.next().map(|node| &mut node.weight)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.nodes.size_hint()
+    }
+}
+
+/// Iterator yielding mutable access to all edge weights.
+pub struct EdgeWeightsMut<'a, E: 'a, Ix: IndexType = DefaultIx> {
+    edges: ::std::slice::IterMut<'a, Edge<E, Ix>>,
+}
+
+impl<'a, E, Ix> Iterator for EdgeWeightsMut<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = &'a mut E;
+
+    fn next(&mut self) -> Option<&'a mut E> {
+        self.edges.next().map(|edge| &mut edge.weight)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.edges.size_hint()
+    }
+}
+
+/// Index the `Graph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Output = N;
+    fn index(&self, index: NodeIndex<Ix>) -> &N {
+        &self.nodes[index.index()].weight
+    }
+}
+
+/// Index the `Graph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn index_mut(&mut self, index: NodeIndex<Ix>) -> &mut N {
+        &mut self.nodes[index.index()].weight
+    }
+}
+
+/// Index the `Graph` by `EdgeIndex` to access edge weights.
+///
+/// **Panics** if the edge doesn't exist.
+impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Output = E;
+    fn index(&self, index: EdgeIndex<Ix>) -> &E {
+        &self.edges[index.index()].weight
+    }
+}
+
+/// Index the `Graph` by `EdgeIndex` to access edge weights.
+///
+/// **Panics** if the edge doesn't exist.
+impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn index_mut(&mut self, index: EdgeIndex<Ix>) -> &mut E {
+        &mut self.edges[index.index()].weight
+    }
+}
+
+/// Create a new empty `Graph`.
+impl<N, E, Ty, Ix> Default for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn default() -> Self {
+        Self::with_capacity(0, 0)
+    }
+}
+
+/// A  `GraphIndex` is a node or edge index.
+pub trait GraphIndex: Copy {
+    #[doc(hidden)]
+    fn index(&self) -> usize;
+    #[doc(hidden)]
+    fn is_node_index() -> bool;
+}
+
+impl<Ix: IndexType> GraphIndex for NodeIndex<Ix> {
+    #[inline]
+    fn index(&self) -> usize {
+        NodeIndex::index(*self)
+    }
+    #[inline]
+    fn is_node_index() -> bool {
+        true
+    }
+}
+
+impl<Ix: IndexType> GraphIndex for EdgeIndex<Ix> {
+    #[inline]
+    fn index(&self) -> usize {
+        EdgeIndex::index(*self)
+    }
+    #[inline]
+    fn is_node_index() -> bool {
+        false
+    }
+}
+
+/// A “walker” object that can be used to step through the edge list of a node.
+///
+/// Created with [`.detach()`](struct.Neighbors.html#method.detach).
+///
+/// The walker does not borrow from the graph, so it lets you step through
+/// neighbors or incident edges while also mutating graph weights, as
+/// in the following example:
+///
+/// ```
+/// use petgraph::{Graph, Incoming};
+/// use petgraph::visit::Dfs;
+///
+/// let mut gr = Graph::new();
+/// let a = gr.add_node(0.);
+/// let b = gr.add_node(0.);
+/// let c = gr.add_node(0.);
+/// gr.add_edge(a, b, 3.);
+/// gr.add_edge(b, c, 2.);
+/// gr.add_edge(c, b, 1.);
+///
+/// // step through the graph and sum incoming edges into the node weight
+/// let mut dfs = Dfs::new(&gr, a);
+/// while let Some(node) = dfs.next(&gr) {
+///     // use a detached neighbors walker
+///     let mut edges = gr.neighbors_directed(node, Incoming).detach();
+///     while let Some(edge) = edges.next_edge(&gr) {
+///         gr[node] += gr[edge];
+///     }
+/// }
+///
+/// // check the result
+/// assert_eq!(gr[a], 0.);
+/// assert_eq!(gr[b], 4.);
+/// assert_eq!(gr[c], 2.);
+/// ```
+pub struct WalkNeighbors<Ix> {
+    skip_start: NodeIndex<Ix>,
+    next: [EdgeIndex<Ix>; 2],
+}
+
+impl<Ix> Clone for WalkNeighbors<Ix>
+where
+    Ix: IndexType,
+{
+    fn clone(&self) -> Self {
+        WalkNeighbors {
+            skip_start: self.skip_start,
+            next: self.next,
+        }
+    }
+}
+
+impl<Ix: IndexType> WalkNeighbors<Ix> {
+    /// Step to the next edge and its endpoint node in the walk for graph `g`.
+    ///
+    /// The next node indices are always the others than the starting point
+    /// where the `WalkNeighbors` value was created.
+    /// For an `Outgoing` walk, the target nodes,
+    /// for an `Incoming` walk, the source nodes of the edge.
+    pub fn next<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &Graph<N, E, Ty, Ix>,
+    ) -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)> {
+        // First any outgoing edges
+        match g.edges.get(self.next[0].index()) {
+            None => {}
+            Some(edge) => {
+                let ed = self.next[0];
+                self.next[0] = edge.next[0];
+                return Some((ed, edge.node[1]));
+            }
+        }
+        // Then incoming edges
+        // For an "undirected" iterator (traverse both incoming
+        // and outgoing edge lists), make sure we don't double
+        // count selfloops by skipping them in the incoming list.
+        while let Some(edge) = g.edges.get(self.next[1].index()) {
+            let ed = self.next[1];
+            self.next[1] = edge.next[1];
+            if edge.node[0] != self.skip_start {
+                return Some((ed, edge.node[0]));
+            }
+        }
+        None
+    }
+
+    pub fn next_node<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &Graph<N, E, Ty, Ix>,
+    ) -> Option<NodeIndex<Ix>> {
+        self.next(g).map(|t| t.1)
+    }
+
+    pub fn next_edge<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &Graph<N, E, Ty, Ix>,
+    ) -> Option<EdgeIndex<Ix>> {
+        self.next(g).map(|t| t.0)
+    }
+}
+
+/// Iterator over the node indices of a graph.
+#[derive(Clone, Debug)]
+pub struct NodeIndices<Ix = DefaultIx> {
+    r: Range<usize>,
+    ty: PhantomData<fn() -> Ix>,
+}
+
+impl<Ix: IndexType> Iterator for NodeIndices<Ix> {
+    type Item = NodeIndex<Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.r.next().map(node_index)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.r.size_hint()
+    }
+}
+
+impl<Ix: IndexType> DoubleEndedIterator for NodeIndices<Ix> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.r.next_back().map(node_index)
+    }
+}
+
+impl<Ix: IndexType> ExactSizeIterator for NodeIndices<Ix> {}
+
+/// Iterator over the edge indices of a graph.
+#[derive(Clone, Debug)]
+pub struct EdgeIndices<Ix = DefaultIx> {
+    r: Range<usize>,
+    ty: PhantomData<fn() -> Ix>,
+}
+
+impl<Ix: IndexType> Iterator for EdgeIndices<Ix> {
+    type Item = EdgeIndex<Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.r.next().map(edge_index)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.r.size_hint()
+    }
+}
+
+impl<Ix: IndexType> DoubleEndedIterator for EdgeIndices<Ix> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.r.next_back().map(edge_index)
+    }
+}
+
+impl<Ix: IndexType> ExactSizeIterator for EdgeIndices<Ix> {}
+
+/// Reference to a `Graph` edge.
+#[derive(Debug)]
+pub struct EdgeReference<'a, E: 'a, Ix = DefaultIx> {
+    index: EdgeIndex<Ix>,
+    node: [NodeIndex<Ix>; 2],
+    weight: &'a E,
+}
+
+impl<'a, E, Ix: IndexType> Clone for EdgeReference<'a, E, Ix> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<'a, E, Ix: IndexType> Copy for EdgeReference<'a, E, Ix> {}
+
+impl<'a, E, Ix: IndexType> PartialEq for EdgeReference<'a, E, Ix>
+where
+    E: PartialEq,
+{
+    fn eq(&self, rhs: &Self) -> bool {
+        self.index == rhs.index && self.weight == rhs.weight
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type NodeRef = (NodeIndex<Ix>, &'a N);
+    type NodeReferences = NodeReferences<'a, N, Ix>;
+    fn node_references(self) -> Self::NodeReferences {
+        NodeReferences {
+            iter: self.nodes.iter().enumerate(),
+        }
+    }
+}
+
+/// Iterator over all nodes of a graph.
+pub struct NodeReferences<'a, N: 'a, Ix: IndexType = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Node<N, Ix>>>,
+}
+
+impl<'a, N, Ix> Iterator for NodeReferences<'a, N, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = (NodeIndex<Ix>, &'a N);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter
+            .next()
+            .map(|(i, node)| (node_index(i), &node.weight))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, N, Ix> DoubleEndedIterator for NodeReferences<'a, N, Ix>
+where
+    Ix: IndexType,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter
+            .next_back()
+            .map(|(i, node)| (node_index(i), &node.weight))
+    }
+}
+
+impl<'a, N, Ix> ExactSizeIterator for NodeReferences<'a, N, Ix> where Ix: IndexType {}
+
+impl<'a, Ix, E> EdgeReference<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    /// Access the edge’s weight.
+    ///
+    /// **NOTE** that this method offers a longer lifetime
+    /// than the trait (unfortunately they don't match yet).
+    pub fn weight(&self) -> &'a E {
+        self.weight
+    }
+}
+
+impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type NodeId = NodeIndex<Ix>;
+    type EdgeId = EdgeIndex<Ix>;
+    type Weight = E;
+
+    fn source(&self) -> Self::NodeId {
+        self.node[0]
+    }
+    fn target(&self) -> Self::NodeId {
+        self.node[1]
+    }
+    fn weight(&self) -> &E {
+        self.weight
+    }
+    fn id(&self) -> Self::EdgeId {
+        self.index
+    }
+}
+
+/// Iterator over all edges of a graph.
+pub struct EdgeReferences<'a, E: 'a, Ix: IndexType = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Edge<E, Ix>>>,
+}
+
+impl<'a, E, Ix> Iterator for EdgeReferences<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = EdgeReference<'a, E, Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(|(i, edge)| EdgeReference {
+            index: edge_index(i),
+            node: edge.node,
+            weight: &edge.weight,
+        })
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, E, Ix> DoubleEndedIterator for EdgeReferences<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.next_back().map(|(i, edge)| EdgeReference {
+            index: edge_index(i),
+            node: edge.node,
+            weight: &edge.weight,
+        })
+    }
+}
+
+impl<'a, E, Ix> ExactSizeIterator for EdgeReferences<'a, E, Ix> where Ix: IndexType {}
+
+mod frozen;
+#[cfg(feature = "stable_graph")]
+pub mod stable_graph;
+
+/// `Frozen` is a graph wrapper.
+///
+/// The `Frozen` only allows shared access (read-only) to the
+/// underlying graph `G`, but it allows mutable access to its
+/// node and edge weights.
+///
+/// This is used to ensure immutability of the graph's structure
+/// while permitting weights to be both read and written.
+///
+/// See indexing implementations and the traits `Data` and `DataMap`
+/// for read-write access to the graph's weights.
+pub struct Frozen<'a, G: 'a>(&'a mut G);
diff --git a/vendor/petgraph/src/graph_impl/serialization.rs b/vendor/petgraph/src/graph_impl/serialization.rs
new file mode 100644
index 000000000..e108f3dd4
--- /dev/null
+++ b/vendor/petgraph/src/graph_impl/serialization.rs
@@ -0,0 +1,345 @@
+use serde::de::Error;
+
+use std::marker::PhantomData;
+
+use crate::prelude::*;
+
+use crate::graph::Node;
+use crate::graph::{Edge, IndexType};
+use crate::serde_utils::CollectSeqWithLength;
+use crate::serde_utils::MappedSequenceVisitor;
+use crate::serde_utils::{FromDeserialized, IntoSerializable};
+use crate::EdgeType;
+
+use super::{EdgeIndex, NodeIndex};
+use serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+/// Serialization representation for Graph
+/// Keep in sync with deserialization and StableGraph
+///
+/// The serialization format is as follows, in Pseudorust:
+///
+/// Graph {
+///     nodes: [N],
+///     node_holes: [NodeIndex<Ix>],
+///     edge_property: EdgeProperty,
+///     edges: [Option<(NodeIndex<Ix>, NodeIndex<Ix>, E)>]
+/// }
+///
+/// The same format is used by both Graph and StableGraph.
+///
+/// For graph there are restrictions:
+/// node_holes is always empty and edges are always Some
+///
+/// A stable graph serialization that obeys these restrictions
+/// (effectively, it has no interior vacancies) can de deserialized
+/// as a graph.
+///
+/// Node indices are serialized as integers and are fixed size for
+/// binary formats, so the Ix parameter matters there.
+#[derive(Serialize)]
+#[serde(rename = "Graph")]
+#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
+pub struct SerGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
+    #[serde(serialize_with = "ser_graph_nodes")]
+    nodes: &'a [Node<N, Ix>],
+    node_holes: &'a [NodeIndex<Ix>],
+    edge_property: EdgeProperty,
+    #[serde(serialize_with = "ser_graph_edges")]
+    edges: &'a [Edge<E, Ix>],
+}
+
+// Deserialization representation for Graph
+// Keep in sync with serialization and StableGraph
+#[derive(Deserialize)]
+#[serde(rename = "Graph")]
+#[serde(bound(
+    deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"
+))]
+pub struct DeserGraph<N, E, Ix> {
+    #[serde(deserialize_with = "deser_graph_nodes")]
+    nodes: Vec<Node<N, Ix>>,
+    #[serde(deserialize_with = "deser_graph_node_holes")]
+    #[allow(unused)]
+    #[serde(default = "Vec::new")]
+    node_holes: Vec<NodeIndex<Ix>>,
+    edge_property: EdgeProperty,
+    #[serde(deserialize_with = "deser_graph_edges")]
+    edges: Vec<Edge<E, Ix>>,
+}
+
+impl<Ix> Serialize for NodeIndex<Ix>
+where
+    Ix: IndexType + Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.0.serialize(serializer)
+    }
+}
+
+impl<'de, Ix> Deserialize<'de> for NodeIndex<Ix>
+where
+    Ix: IndexType + Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        Ok(NodeIndex(Ix::deserialize(deserializer)?))
+    }
+}
+
+impl<Ix> Serialize for EdgeIndex<Ix>
+where
+    Ix: IndexType + Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.0.serialize(serializer)
+    }
+}
+
+impl<'de, Ix> Deserialize<'de> for EdgeIndex<Ix>
+where
+    Ix: IndexType + Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        Ok(EdgeIndex(Ix::deserialize(deserializer)?))
+    }
+}
+
+#[derive(Serialize, Deserialize)]
+#[serde(rename_all = "lowercase")]
+#[derive(Debug)]
+pub enum EdgeProperty {
+    Undirected,
+    Directed,
+}
+
+impl EdgeProperty {
+    pub fn is_directed(&self) -> bool {
+        match *self {
+            EdgeProperty::Directed => true,
+            EdgeProperty::Undirected => false,
+        }
+    }
+}
+
+impl<Ty> From<PhantomData<Ty>> for EdgeProperty
+where
+    Ty: EdgeType,
+{
+    fn from(_: PhantomData<Ty>) -> Self {
+        if Ty::is_directed() {
+            EdgeProperty::Directed
+        } else {
+            EdgeProperty::Undirected
+        }
+    }
+}
+
+impl<Ty> FromDeserialized for PhantomData<Ty>
+where
+    Ty: EdgeType,
+{
+    type Input = EdgeProperty;
+    fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
+    where
+        E2: Error,
+    {
+        if input.is_directed() != Ty::is_directed() {
+            Err(E2::custom(format_args!(
+                "graph edge property mismatch, \
+                 expected {:?}, found {:?}",
+                EdgeProperty::from(PhantomData::<Ty>),
+                input
+            )))
+        } else {
+            Ok(PhantomData)
+        }
+    }
+}
+
+fn ser_graph_nodes<S, N, Ix>(nodes: &&[Node<N, Ix>], serializer: S) -> Result<S::Ok, S::Error>
+where
+    S: Serializer,
+    N: Serialize,
+    Ix: Serialize + IndexType,
+{
+    serializer.collect_seq_exact(nodes.iter().map(|node| &node.weight))
+}
+
+fn ser_graph_edges<S, E, Ix>(edges: &&[Edge<E, Ix>], serializer: S) -> Result<S::Ok, S::Error>
+where
+    S: Serializer,
+    E: Serialize,
+    Ix: Serialize + IndexType,
+{
+    serializer.collect_seq_exact(
+        edges
+            .iter()
+            .map(|edge| Some((edge.source(), edge.target(), &edge.weight))),
+    )
+}
+
+fn deser_graph_nodes<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Node<N, Ix>>, D::Error>
+where
+    D: Deserializer<'de>,
+    N: Deserialize<'de>,
+    Ix: IndexType + Deserialize<'de>,
+{
+    deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| {
+        Ok(Node {
+            weight: n,
+            next: [EdgeIndex::end(); 2],
+        })
+    }))
+}
+
+fn deser_graph_node_holes<'de, D, Ix>(deserializer: D) -> Result<Vec<NodeIndex<Ix>>, D::Error>
+where
+    D: Deserializer<'de>,
+    Ix: IndexType + Deserialize<'de>,
+{
+    deserializer.deserialize_seq(
+        MappedSequenceVisitor::<NodeIndex<Ix>, NodeIndex<Ix>, _>::new(|_| {
+            Err("Graph can not have holes in the node set, found non-empty node_holes")
+        }),
+    )
+}
+
+fn deser_graph_edges<'de, D, N, Ix>(deserializer: D) -> Result<Vec<Edge<N, Ix>>, D::Error>
+where
+    D: Deserializer<'de>,
+    N: Deserialize<'de>,
+    Ix: IndexType + Deserialize<'de>,
+{
+    deserializer.deserialize_seq(MappedSequenceVisitor::<
+        Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>,
+        _,
+        _,
+    >::new(|x| {
+        if let Some((i, j, w)) = x {
+            Ok(Edge {
+                weight: w,
+                node: [i, j],
+                next: [EdgeIndex::end(); 2],
+            })
+        } else {
+            Err("Graph can not have holes in the edge set, found None, expected edge")
+        }
+    }))
+}
+
+impl<'a, N, E, Ty, Ix> IntoSerializable for &'a Graph<N, E, Ty, Ix>
+where
+    Ix: IndexType,
+    Ty: EdgeType,
+{
+    type Output = SerGraph<'a, N, E, Ix>;
+    fn into_serializable(self) -> Self::Output {
+        SerGraph {
+            nodes: &self.nodes,
+            node_holes: &[],
+            edges: &self.edges,
+            edge_property: EdgeProperty::from(PhantomData::<Ty>),
+        }
+    }
+}
+
+/// Requires crate feature `"serde-1"`
+impl<N, E, Ty, Ix> Serialize for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType + Serialize,
+    N: Serialize,
+    E: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.into_serializable().serialize(serializer)
+    }
+}
+
+pub fn invalid_node_err<E>(node_index: usize, len: usize) -> E
+where
+    E: Error,
+{
+    E::custom(format_args!(
+        "invalid value: node index `{}` does not exist in graph \
+         with node bound {}",
+        node_index, len
+    ))
+}
+
+pub fn invalid_length_err<Ix, E>(node_or_edge: &str, len: usize) -> E
+where
+    E: Error,
+    Ix: IndexType,
+{
+    E::custom(format_args!(
+        "invalid size: graph {} count {} exceeds index type maximum {}",
+        node_or_edge,
+        len,
+        <Ix as IndexType>::max().index()
+    ))
+}
+
+impl<'a, N, E, Ty, Ix> FromDeserialized for Graph<N, E, Ty, Ix>
+where
+    Ix: IndexType,
+    Ty: EdgeType,
+{
+    type Input = DeserGraph<N, E, Ix>;
+    fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
+    where
+        E2: Error,
+    {
+        let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
+        let nodes = input.nodes;
+        let edges = input.edges;
+        if nodes.len() >= <Ix as IndexType>::max().index() {
+            Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
+        }
+
+        if edges.len() >= <Ix as IndexType>::max().index() {
+            Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
+        }
+
+        let mut gr = Graph {
+            nodes: nodes,
+            edges: edges,
+            ty: ty,
+        };
+        let nc = gr.node_count();
+        gr.link_edges()
+            .map_err(|i| invalid_node_err(i.index(), nc))?;
+        Ok(gr)
+    }
+}
+
+/// Requires crate feature `"serde-1"`
+impl<'de, N, E, Ty, Ix> Deserialize<'de> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType + Deserialize<'de>,
+    N: Deserialize<'de>,
+    E: Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        Self::from_deserialized(DeserGraph::deserialize(deserializer)?)
+    }
+}
diff --git a/vendor/petgraph/src/graph_impl/stable_graph/mod.rs b/vendor/petgraph/src/graph_impl/stable_graph/mod.rs
new file mode 100644
index 000000000..142aaebed
--- /dev/null
+++ b/vendor/petgraph/src/graph_impl/stable_graph/mod.rs
@@ -0,0 +1,1817 @@
+//! `StableGraph` keeps indices stable across removals.
+//!
+//! Depends on `feature = "stable_graph"`.
+//!
+
+use std::cmp;
+use std::fmt;
+use std::iter;
+use std::marker::PhantomData;
+use std::mem::replace;
+use std::mem::size_of;
+use std::ops::{Index, IndexMut};
+use std::slice;
+
+use crate::{Directed, Direction, EdgeType, Graph, Incoming, Outgoing, Undirected};
+
+use crate::iter_format::{DebugMap, IterFormatExt, NoPretty};
+use crate::iter_utils::IterUtilsExt;
+
+use super::{index_twice, Edge, Frozen, Node, Pair, DIRECTIONS};
+use crate::visit::{
+    EdgeRef, IntoEdgeReferences, IntoEdges, IntoEdgesDirected, IntoNodeReferences, NodeIndexable,
+};
+use crate::IntoWeightedEdge;
+
+// reexport those things that are shared with Graph
+#[doc(no_inline)]
+pub use crate::graph::{
+    edge_index, node_index, DefaultIx, EdgeIndex, GraphIndex, IndexType, NodeIndex,
+};
+
+use crate::util::enumerate;
+
+#[cfg(feature = "serde-1")]
+mod serialization;
+
+/// `StableGraph<N, E, Ty, Ix>` is a graph datastructure using an adjacency
+/// list representation.
+///
+/// The graph **does not invalidate** any unrelated node or edge indices when
+/// items are removed.
+///
+/// `StableGraph` is parameterized over:
+///
+/// - Associated data `N` for nodes and `E` for edges, also called *weights*.
+///   The associated data can be of arbitrary type.
+/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
+/// - Index type `Ix`, which determines the maximum size of the graph.
+///
+/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert
+/// and efficient graph search.
+///
+/// It implements **O(e')** edge lookup and edge and node removals, where **e'**
+/// is some local measure of edge count.
+///
+/// - Nodes and edges are each numbered in an interval from *0* to some number
+/// *m*, but *not all* indices in the range are valid, since gaps are formed
+/// by deletions.
+///
+/// - You can select graph index integer type after the size of the graph. A smaller
+/// size may have better performance.
+///
+/// - Using indices allows mutation while traversing the graph, see `Dfs`.
+///
+/// - The `StableGraph` is a regular rust collection and is `Send` and `Sync`
+/// (as long as associated data `N` and `E` are).
+///
+/// - Indices don't allow as much compile time checking as references.
+///
+/// Depends on crate feature `stable_graph` (default). *Stable Graph is still
+/// missing a few methods compared to Graph. You can contribute to help it
+/// achieve parity.*
+pub struct StableGraph<N, E, Ty = Directed, Ix = DefaultIx> {
+    g: Graph<Option<N>, Option<E>, Ty, Ix>,
+    node_count: usize,
+    edge_count: usize,
+
+    // node and edge free lists (both work the same way)
+    //
+    // free_node, if not NodeIndex::end(), points to a node index
+    // that is vacant (after a deletion).  The next item in the list is kept in
+    // that Node's Node.next[0] field. For Node, it's a node index stored
+    // in an EdgeIndex location, and the _into_edge()/_into_node() methods
+    // convert.
+    free_node: NodeIndex<Ix>,
+    free_edge: EdgeIndex<Ix>,
+}
+
+/// A `StableGraph` with directed edges.
+///
+/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
+/// *1*.
+pub type StableDiGraph<N, E, Ix = DefaultIx> = StableGraph<N, E, Directed, Ix>;
+
+/// A `StableGraph` with undirected edges.
+///
+/// For example, an edge between *1* and *2* is equivalent to an edge between
+/// *2* and *1*.
+pub type StableUnGraph<N, E, Ix = DefaultIx> = StableGraph<N, E, Undirected, Ix>;
+
+impl<N, E, Ty, Ix> fmt::Debug for StableGraph<N, E, Ty, Ix>
+where
+    N: fmt::Debug,
+    E: fmt::Debug,
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let etype = if self.is_directed() {
+            "Directed"
+        } else {
+            "Undirected"
+        };
+        let mut fmt_struct = f.debug_struct("StableGraph");
+        fmt_struct.field("Ty", &etype);
+        fmt_struct.field("node_count", &self.node_count);
+        fmt_struct.field("edge_count", &self.edge_count);
+        if self.g.edges.iter().any(|e| e.weight.is_some()) {
+            fmt_struct.field(
+                "edges",
+                &self
+                    .g
+                    .edges
+                    .iter()
+                    .filter(|e| e.weight.is_some())
+                    .map(|e| NoPretty((e.source().index(), e.target().index())))
+                    .format(", "),
+            );
+        }
+        // skip weights if they are ZST!
+        if size_of::<N>() != 0 {
+            fmt_struct.field(
+                "node weights",
+                &DebugMap(|| {
+                    self.g
+                        .nodes
+                        .iter()
+                        .map(|n| n.weight.as_ref())
+                        .enumerate()
+                        .filter_map(|(i, wo)| wo.map(move |w| (i, w)))
+                }),
+            );
+        }
+        if size_of::<E>() != 0 {
+            fmt_struct.field(
+                "edge weights",
+                &DebugMap(|| {
+                    self.g
+                        .edges
+                        .iter()
+                        .map(|n| n.weight.as_ref())
+                        .enumerate()
+                        .filter_map(|(i, wo)| wo.map(move |w| (i, w)))
+                }),
+            );
+        }
+        fmt_struct.field("free_node", &self.free_node);
+        fmt_struct.field("free_edge", &self.free_edge);
+        fmt_struct.finish()
+    }
+}
+
+impl<N, E> StableGraph<N, E, Directed> {
+    /// Create a new `StableGraph` with directed edges.
+    ///
+    /// This is a convenience method. See `StableGraph::with_capacity`
+    /// or `StableGraph::default` for a constructor that is generic in all the
+    /// type parameters of `StableGraph`.
+    pub fn new() -> Self {
+        Self::with_capacity(0, 0)
+    }
+}
+
+impl<N, E, Ty, Ix> StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// Create a new `StableGraph` with estimated capacity.
+    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
+        StableGraph {
+            g: Graph::with_capacity(nodes, edges),
+            node_count: 0,
+            edge_count: 0,
+            free_node: NodeIndex::end(),
+            free_edge: EdgeIndex::end(),
+        }
+    }
+
+    /// Return the current node and edge capacity of the graph.
+    pub fn capacity(&self) -> (usize, usize) {
+        self.g.capacity()
+    }
+
+    /// Remove all nodes and edges
+    pub fn clear(&mut self) {
+        self.node_count = 0;
+        self.edge_count = 0;
+        self.free_node = NodeIndex::end();
+        self.free_edge = EdgeIndex::end();
+        self.g.clear();
+    }
+
+    /// Remove all edges
+    pub fn clear_edges(&mut self) {
+        self.edge_count = 0;
+        self.free_edge = EdgeIndex::end();
+        self.g.edges.clear();
+        // clear edges without touching the free list
+        for node in &mut self.g.nodes {
+            if node.weight.is_some() {
+                node.next = [EdgeIndex::end(), EdgeIndex::end()];
+            }
+        }
+    }
+
+    /// Return the number of nodes (vertices) in the graph.
+    ///
+    /// Computes in **O(1)** time.
+    pub fn node_count(&self) -> usize {
+        self.node_count
+    }
+
+    /// Return the number of edges in the graph.
+    ///
+    /// Computes in **O(1)** time.
+    pub fn edge_count(&self) -> usize {
+        self.edge_count
+    }
+
+    /// Whether the graph has directed edges or not.
+    #[inline]
+    pub fn is_directed(&self) -> bool {
+        Ty::is_directed()
+    }
+
+    /// Add a node (also called vertex) with associated data `weight` to the graph.
+    ///
+    /// Computes in **O(1)** time.
+    ///
+    /// Return the index of the new node.
+    ///
+    /// **Panics** if the `StableGraph` is at the maximum number of nodes for
+    /// its index type.
+    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
+        let index = if self.free_node != NodeIndex::end() {
+            let node_idx = self.free_node;
+            let node_slot = &mut self.g.nodes[node_idx.index()];
+            let _old = replace(&mut node_slot.weight, Some(weight));
+            debug_assert!(_old.is_none());
+            self.free_node = node_slot.next[0]._into_node();
+            node_slot.next[0] = EdgeIndex::end();
+            node_idx
+        } else {
+            self.g.add_node(Some(weight))
+        };
+        self.node_count += 1;
+        index
+    }
+
+    /// free_node: Which free list to update for the vacancy
+    fn add_vacant_node(&mut self, free_node: &mut NodeIndex<Ix>) {
+        let node_idx = self.g.add_node(None);
+        // link the free list
+        let node_slot = &mut self.g.nodes[node_idx.index()];
+        node_slot.next[0] = free_node._into_edge();
+        *free_node = node_idx;
+    }
+
+    /// Remove `a` from the graph if it exists, and return its weight.
+    /// If it doesn't exist in the graph, return `None`.
+    ///
+    /// The node index `a` is invalidated, but none other.
+    /// Edge indices are invalidated as they would be following the removal of
+    /// each edge with an endpoint in `a`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of affected
+    /// edges, including *n* calls to `.remove_edge()` where *n* is the number
+    /// of edges with an endpoint in `a`.
+    pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N> {
+        let node_weight = self.g.nodes.get_mut(a.index())?.weight.take()?;
+        for d in &DIRECTIONS {
+            let k = d.index();
+
+            // Remove all edges from and to this node.
+            loop {
+                let next = self.g.nodes[a.index()].next[k];
+                if next == EdgeIndex::end() {
+                    break;
+                }
+                let ret = self.remove_edge(next);
+                debug_assert!(ret.is_some());
+                let _ = ret;
+            }
+        }
+
+        let node_slot = &mut self.g.nodes[a.index()];
+        //let node_weight = replace(&mut self.g.nodes[a.index()].weight, Entry::Empty(self.free_node));
+        //self.g.nodes[a.index()].next = [EdgeIndex::end(), EdgeIndex::end()];
+        node_slot.next = [self.free_node._into_edge(), EdgeIndex::end()];
+        self.free_node = a;
+        self.node_count -= 1;
+
+        Some(node_weight)
+    }
+
+    pub fn contains_node(&self, a: NodeIndex<Ix>) -> bool {
+        self.get_node(a).is_some()
+    }
+
+    // Return the Node if it is not vacant (non-None weight)
+    fn get_node(&self, a: NodeIndex<Ix>) -> Option<&Node<Option<N>, Ix>> {
+        self.g
+            .nodes
+            .get(a.index())
+            .and_then(|node| node.weight.as_ref().map(move |_| node))
+    }
+
+    /// Add an edge from `a` to `b` to the graph, with its associated
+    /// data `weight`.
+    ///
+    /// Return the index of the new edge.
+    ///
+    /// Computes in **O(1)** time.
+    ///
+    /// **Panics** if any of the nodes don't exist.<br>
+    /// **Panics** if the `StableGraph` is at the maximum number of edges for
+    /// its index type.
+    ///
+    /// **Note:** `StableGraph` allows adding parallel (“duplicate”) edges.
+    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
+        let edge_idx;
+        let mut new_edge = None::<Edge<_, _>>;
+        {
+            let edge: &mut Edge<_, _>;
+
+            if self.free_edge != EdgeIndex::end() {
+                edge_idx = self.free_edge;
+                edge = &mut self.g.edges[edge_idx.index()];
+                let _old = replace(&mut edge.weight, Some(weight));
+                debug_assert!(_old.is_none());
+                self.free_edge = edge.next[0];
+                edge.node = [a, b];
+            } else {
+                edge_idx = EdgeIndex::new(self.g.edges.len());
+                assert!(<Ix as IndexType>::max().index() == !0 || EdgeIndex::end() != edge_idx);
+                new_edge = Some(Edge {
+                    weight: Some(weight),
+                    node: [a, b],
+                    next: [EdgeIndex::end(); 2],
+                });
+                edge = new_edge.as_mut().unwrap();
+            }
+
+            let wrong_index = match index_twice(&mut self.g.nodes, a.index(), b.index()) {
+                Pair::None => Some(cmp::max(a.index(), b.index())),
+                Pair::One(an) => {
+                    if an.weight.is_none() {
+                        Some(a.index())
+                    } else {
+                        edge.next = an.next;
+                        an.next[0] = edge_idx;
+                        an.next[1] = edge_idx;
+                        None
+                    }
+                }
+                Pair::Both(an, bn) => {
+                    // a and b are different indices
+                    if an.weight.is_none() {
+                        Some(a.index())
+                    } else if bn.weight.is_none() {
+                        Some(b.index())
+                    } else {
+                        edge.next = [an.next[0], bn.next[1]];
+                        an.next[0] = edge_idx;
+                        bn.next[1] = edge_idx;
+                        None
+                    }
+                }
+            };
+            if let Some(i) = wrong_index {
+                panic!(
+                    "StableGraph::add_edge: node index {} is not a node in the graph",
+                    i
+                );
+            }
+            self.edge_count += 1;
+        }
+        if let Some(edge) = new_edge {
+            self.g.edges.push(edge);
+        }
+        edge_idx
+    }
+
+    /// free_edge: Which free list to update for the vacancy
+    fn add_vacant_edge(&mut self, free_edge: &mut EdgeIndex<Ix>) {
+        let edge_idx = EdgeIndex::new(self.g.edges.len());
+        debug_assert!(edge_idx != EdgeIndex::end());
+        let mut edge = Edge {
+            weight: None,
+            node: [NodeIndex::end(); 2],
+            next: [EdgeIndex::end(); 2],
+        };
+        edge.next[0] = *free_edge;
+        *free_edge = edge_idx;
+        self.g.edges.push(edge);
+    }
+
+    /// Add or update an edge from `a` to `b`.
+    /// If the edge already exists, its weight is updated.
+    ///
+    /// Return the index of the affected edge.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    ///
+    /// **Panics** if any of the nodes don't exist.
+    pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
+        if let Some(ix) = self.find_edge(a, b) {
+            self[ix] = weight;
+            return ix;
+        }
+        self.add_edge(a, b, weight)
+    }
+
+    /// Remove an edge and return its edge weight, or `None` if it didn't exist.
+    ///
+    /// Invalidates the edge index `e` but no other.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to the same endpoints as `e`.
+    pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E> {
+        // every edge is part of two lists,
+        // outgoing and incoming edges.
+        // Remove it from both
+        let (is_edge, edge_node, edge_next) = match self.g.edges.get(e.index()) {
+            None => return None,
+            Some(x) => (x.weight.is_some(), x.node, x.next),
+        };
+        if !is_edge {
+            return None;
+        }
+
+        // Remove the edge from its in and out lists by replacing it with
+        // a link to the next in the list.
+        self.g.change_edge_links(edge_node, e, edge_next);
+
+        // Clear the edge and put it in the free list
+        let edge = &mut self.g.edges[e.index()];
+        edge.next = [self.free_edge, EdgeIndex::end()];
+        edge.node = [NodeIndex::end(), NodeIndex::end()];
+        self.free_edge = e;
+        self.edge_count -= 1;
+        edge.weight.take()
+    }
+
+    /// Access the weight for node `a`.
+    ///
+    /// Also available with indexing syntax: `&graph[a]`.
+    pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N> {
+        match self.g.nodes.get(a.index()) {
+            Some(no) => no.weight.as_ref(),
+            None => None,
+        }
+    }
+
+    /// Access the weight for node `a`, mutably.
+    ///
+    /// Also available with indexing syntax: `&mut graph[a]`.
+    pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> Option<&mut N> {
+        match self.g.nodes.get_mut(a.index()) {
+            Some(no) => no.weight.as_mut(),
+            None => None,
+        }
+    }
+
+    /// Return an iterator yielding mutable access to all node weights.
+    ///
+    /// The order in which weights are yielded matches the order of their node
+    /// indices.
+    pub fn node_weights_mut(&mut self) -> impl Iterator<Item = &mut N> {
+        self.g
+            .node_weights_mut()
+            .flat_map(|maybe_node| maybe_node.iter_mut())
+    }
+
+    /// Return an iterator over the node indices of the graph
+    pub fn node_indices(&self) -> NodeIndices<N, Ix> {
+        NodeIndices {
+            iter: enumerate(self.raw_nodes()),
+        }
+    }
+
+    /// Access the weight for edge `e`.
+    ///
+    /// Also available with indexing syntax: `&graph[e]`.
+    pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
+        match self.g.edges.get(e.index()) {
+            Some(ed) => ed.weight.as_ref(),
+            None => None,
+        }
+    }
+
+    /// Access the weight for edge `e`, mutably
+    ///
+    /// Also available with indexing syntax: `&mut graph[e]`.
+    pub fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
+        match self.g.edges.get_mut(e.index()) {
+            Some(ed) => ed.weight.as_mut(),
+            None => None,
+        }
+    }
+
+    /// Return an iterator yielding mutable access to all edge weights.
+    ///
+    /// The order in which weights are yielded matches the order of their edge
+    /// indices.
+    pub fn edge_weights_mut(&mut self) -> impl Iterator<Item = &mut E> {
+        self.g
+            .edge_weights_mut()
+            .flat_map(|maybe_edge| maybe_edge.iter_mut())
+    }
+
+    /// Access the source and target nodes for `e`.
+    pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
+        match self.g.edges.get(e.index()) {
+            Some(ed) if ed.weight.is_some() => Some((ed.source(), ed.target())),
+            _otherwise => None,
+        }
+    }
+
+    /// Return an iterator over the edge indices of the graph
+    pub fn edge_indices(&self) -> EdgeIndices<E, Ix> {
+        EdgeIndices {
+            iter: enumerate(self.raw_edges()),
+        }
+    }
+
+    /// Lookup if there is an edge from `a` to `b`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
+        self.find_edge(a, b).is_some()
+    }
+
+    /// Lookup an edge from `a` to `b`.
+    ///
+    /// Computes in **O(e')** time, where **e'** is the number of edges
+    /// connected to `a` (and `b`, if the graph edges are undirected).
+    pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
+        if !self.is_directed() {
+            self.find_edge_undirected(a, b).map(|(ix, _)| ix)
+        } else {
+            match self.get_node(a) {
+                None => None,
+                Some(node) => self.g.find_edge_directed_from_node(node, b),
+            }
+        }
+    }
+
+    /// Lookup an edge between `a` and `b`, in either direction.
+    ///
+    /// If the graph is undirected, then this is equivalent to `.find_edge()`.
+    ///
+    /// Return the edge index and its directionality, with `Outgoing` meaning
+    /// from `a` to `b` and `Incoming` the reverse,
+    /// or `None` if the edge does not exist.
+    pub fn find_edge_undirected(
+        &self,
+        a: NodeIndex<Ix>,
+        b: NodeIndex<Ix>,
+    ) -> Option<(EdgeIndex<Ix>, Direction)> {
+        match self.get_node(a) {
+            None => None,
+            Some(node) => self.g.find_edge_undirected_from_node(node, b),
+        }
+    }
+
+    /// Return an iterator of all nodes with an edge starting from `a`.
+    ///
+    /// - `Directed`: Outgoing edges from `a`.
+    /// - `Undirected`: All edges connected to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// Use [`.neighbors(a).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix> {
+        self.neighbors_directed(a, Outgoing)
+    }
+
+    /// Return an iterator of all neighbors that have an edge between them and `a`,
+    /// in the specified direction.
+    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
+    ///
+    /// - `Directed`, `Outgoing`: All edges from `a`.
+    /// - `Directed`, `Incoming`: All edges to `a`.
+    /// - `Undirected`: All edges connected to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// Use [`.neighbors_directed(a, dir).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    pub fn neighbors_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Neighbors<E, Ix> {
+        let mut iter = self.neighbors_undirected(a);
+        if self.is_directed() {
+            let k = dir.index();
+            iter.next[1 - k] = EdgeIndex::end();
+            iter.skip_start = NodeIndex::end();
+        }
+        iter
+    }
+
+    /// Return an iterator of all neighbors that have an edge between them and `a`,
+    /// in either direction.
+    /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
+    ///
+    /// - `Directed` and `Undirected`: All edges connected to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `NodeIndex<Ix>`.
+    ///
+    /// Use [`.neighbors_undirected(a).detach()`][1] to get a neighbor walker that does
+    /// not borrow from the graph.
+    ///
+    /// [1]: struct.Neighbors.html#method.detach
+    pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<E, Ix> {
+        Neighbors {
+            skip_start: a,
+            edges: &self.g.edges,
+            next: match self.get_node(a) {
+                None => [EdgeIndex::end(), EdgeIndex::end()],
+                Some(n) => n.next,
+            },
+        }
+    }
+
+    /// Return an iterator of all edges of `a`.
+    ///
+    /// - `Directed`: Outgoing edges from `a`.
+    /// - `Undirected`: All edges connected to `a`.
+    ///
+    /// Produces an empty iterator if the node doesn't exist.<br>
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
+        self.edges_directed(a, Outgoing)
+    }
+
+    /// Return an iterator of all edges of `a`, in the specified direction.
+    ///
+    /// - `Directed`, `Outgoing`: All edges from `a`.
+    /// - `Directed`, `Incoming`: All edges to `a`.
+    /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
+    ///   edge.
+    /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
+    ///   edge.
+    ///
+    /// Produces an empty iterator if the node `a` doesn't exist.<br>
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    pub fn edges_directed(&self, a: NodeIndex<Ix>, dir: Direction) -> Edges<E, Ty, Ix> {
+        Edges {
+            skip_start: a,
+            edges: &self.g.edges,
+            direction: dir,
+            next: match self.get_node(a) {
+                None => [EdgeIndex::end(), EdgeIndex::end()],
+                Some(n) => n.next,
+            },
+            ty: PhantomData,
+        }
+    }
+
+    /// Return an iterator over either the nodes without edges to them
+    /// (`Incoming`) or from them (`Outgoing`).
+    ///
+    /// An *internal* node has both incoming and outgoing edges.
+    /// The nodes in `.externals(Incoming)` are the source nodes and
+    /// `.externals(Outgoing)` are the sinks of the graph.
+    ///
+    /// For a graph with undirected edges, both the sinks and the sources are
+    /// just the nodes without edges.
+    ///
+    /// The whole iteration computes in **O(|V|)** time.
+    pub fn externals(&self, dir: Direction) -> Externals<N, Ty, Ix> {
+        Externals {
+            iter: self.raw_nodes().iter().enumerate(),
+            dir,
+            ty: PhantomData,
+        }
+    }
+
+    /// Index the `StableGraph` by two indices, any combination of
+    /// node or edge indices is fine.
+    ///
+    /// **Panics** if the indices are equal or if they are out of bounds.
+    pub fn index_twice_mut<T, U>(
+        &mut self,
+        i: T,
+        j: U,
+    ) -> (
+        &mut <Self as Index<T>>::Output,
+        &mut <Self as Index<U>>::Output,
+    )
+    where
+        Self: IndexMut<T> + IndexMut<U>,
+        T: GraphIndex,
+        U: GraphIndex,
+    {
+        assert!(T::is_node_index() != U::is_node_index() || i.index() != j.index());
+
+        // Allow two mutable indexes here -- they are nonoverlapping
+        unsafe {
+            let self_mut = self as *mut _;
+            (
+                <Self as IndexMut<T>>::index_mut(&mut *self_mut, i),
+                <Self as IndexMut<U>>::index_mut(&mut *self_mut, j),
+            )
+        }
+    }
+
+    /// Keep all nodes that return `true` from the `visit` closure,
+    /// remove the others.
+    ///
+    /// `visit` is provided a proxy reference to the graph, so that
+    /// the graph can be walked and associated data modified.
+    ///
+    /// The order nodes are visited is not specified.
+    ///
+    /// The node indices of the removed nodes are invalidated, but none other.
+    /// Edge indices are invalidated as they would be following the removal of
+    /// each edge with an endpoint in a removed node.
+    ///
+    /// Computes in **O(n + e')** time, where **n** is the number of node indices and
+    ///  **e'** is the number of affected edges, including *n* calls to `.remove_edge()`
+    /// where *n* is the number of edges with an endpoint in a removed node.
+    pub fn retain_nodes<F>(&mut self, mut visit: F)
+    where
+        F: FnMut(Frozen<Self>, NodeIndex<Ix>) -> bool,
+    {
+        for i in 0..self.node_bound() {
+            let ix = node_index(i);
+            if self.contains_node(ix) && !visit(Frozen(self), ix) {
+                self.remove_node(ix);
+            }
+        }
+        self.check_free_lists();
+    }
+
+    /// Keep all edges that return `true` from the `visit` closure,
+    /// remove the others.
+    ///
+    /// `visit` is provided a proxy reference to the graph, so that
+    /// the graph can be walked and associated data modified.
+    ///
+    /// The order edges are visited is not specified.
+    ///
+    /// The edge indices of the removed edes are invalidated, but none other.
+    ///
+    /// Computes in **O(e'')** time, **e'** is the number of affected edges,
+    /// including the calls to `.remove_edge()` for each removed edge.
+    pub fn retain_edges<F>(&mut self, mut visit: F)
+    where
+        F: FnMut(Frozen<Self>, EdgeIndex<Ix>) -> bool,
+    {
+        for i in 0..self.edge_bound() {
+            let ix = edge_index(i);
+            if self.edge_weight(ix).is_some() && !visit(Frozen(self), ix) {
+                self.remove_edge(ix);
+            }
+        }
+        self.check_free_lists();
+    }
+
+    /// Create a new `StableGraph` from an iterable of edges.
+    ///
+    /// Node weights `N` are set to default values.
+    /// Edge weights `E` may either be specified in the list,
+    /// or they are filled with default values.
+    ///
+    /// Nodes are inserted automatically to match the edges.
+    ///
+    /// ```
+    /// use petgraph::stable_graph::StableGraph;
+    ///
+    /// let gr = StableGraph::<(), i32>::from_edges(&[
+    ///     (0, 1), (0, 2), (0, 3),
+    ///     (1, 2), (1, 3),
+    ///     (2, 3),
+    /// ]);
+    /// ```
+    pub fn from_edges<I>(iterable: I) -> Self
+    where
+        I: IntoIterator,
+        I::Item: IntoWeightedEdge<E>,
+        <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+        N: Default,
+    {
+        let mut g = Self::with_capacity(0, 0);
+        g.extend_with_edges(iterable);
+        g
+    }
+
+    /// Create a new `StableGraph` by mapping node and
+    /// edge weights to new values.
+    ///
+    /// The resulting graph has the same structure and the same
+    /// graph indices as `self`.
+    pub fn map<'a, F, G, N2, E2>(
+        &'a self,
+        mut node_map: F,
+        mut edge_map: G,
+    ) -> StableGraph<N2, E2, Ty, Ix>
+    where
+        F: FnMut(NodeIndex<Ix>, &'a N) -> N2,
+        G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,
+    {
+        let g = self.g.map(
+            move |i, w| w.as_ref().map(|w| node_map(i, w)),
+            move |i, w| w.as_ref().map(|w| edge_map(i, w)),
+        );
+        StableGraph {
+            g,
+            node_count: self.node_count,
+            edge_count: self.edge_count,
+            free_node: self.free_node,
+            free_edge: self.free_edge,
+        }
+    }
+
+    /// Create a new `StableGraph` by mapping nodes and edges.
+    /// A node or edge may be mapped to `None` to exclude it from
+    /// the resulting graph.
+    ///
+    /// Nodes are mapped first with the `node_map` closure, then
+    /// `edge_map` is called for the edges that have not had any endpoint
+    /// removed.
+    ///
+    /// The resulting graph has the structure of a subgraph of the original graph.
+    /// Nodes and edges that are not removed maintain their old node or edge
+    /// indices.
+    pub fn filter_map<'a, F, G, N2, E2>(
+        &'a self,
+        mut node_map: F,
+        mut edge_map: G,
+    ) -> StableGraph<N2, E2, Ty, Ix>
+    where
+        F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>,
+        G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,
+    {
+        let node_bound = self.node_bound();
+        let edge_bound = self.edge_bound();
+        let mut result_g = StableGraph::with_capacity(node_bound, edge_bound);
+        // use separate free lists so that
+        // add_node / add_edge below do not reuse the tombstones
+        let mut free_node = NodeIndex::end();
+        let mut free_edge = EdgeIndex::end();
+
+        // the stable graph keeps the node map itself
+
+        for (i, node) in enumerate(self.raw_nodes()) {
+            if i >= node_bound {
+                break;
+            }
+            if let Some(node_weight) = node.weight.as_ref() {
+                if let Some(new_weight) = node_map(NodeIndex::new(i), node_weight) {
+                    result_g.add_node(new_weight);
+                    continue;
+                }
+            }
+            result_g.add_vacant_node(&mut free_node);
+        }
+        for (i, edge) in enumerate(self.raw_edges()) {
+            if i >= edge_bound {
+                break;
+            }
+            let source = edge.source();
+            let target = edge.target();
+            if let Some(edge_weight) = edge.weight.as_ref() {
+                if result_g.contains_node(source) && result_g.contains_node(target) {
+                    if let Some(new_weight) = edge_map(EdgeIndex::new(i), edge_weight) {
+                        result_g.add_edge(source, target, new_weight);
+                        continue;
+                    }
+                }
+            }
+            result_g.add_vacant_edge(&mut free_edge);
+        }
+        result_g.free_node = free_node;
+        result_g.free_edge = free_edge;
+        result_g.check_free_lists();
+        result_g
+    }
+
+    /// Extend the graph from an iterable of edges.
+    ///
+    /// Node weights `N` are set to default values.
+    /// Edge weights `E` may either be specified in the list,
+    /// or they are filled with default values.
+    ///
+    /// Nodes are inserted automatically to match the edges.
+    pub fn extend_with_edges<I>(&mut self, iterable: I)
+    where
+        I: IntoIterator,
+        I::Item: IntoWeightedEdge<E>,
+        <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+        N: Default,
+    {
+        let iter = iterable.into_iter();
+
+        for elt in iter {
+            let (source, target, weight) = elt.into_weighted_edge();
+            let (source, target) = (source.into(), target.into());
+            let nx = cmp::max(source, target);
+            while nx.index() >= self.node_count() {
+                self.add_node(N::default());
+            }
+            self.add_edge(source, target, weight);
+        }
+    }
+
+    //
+    // internal methods
+    //
+    fn raw_nodes(&self) -> &[Node<Option<N>, Ix>] {
+        self.g.raw_nodes()
+    }
+
+    fn raw_edges(&self) -> &[Edge<Option<E>, Ix>] {
+        self.g.raw_edges()
+    }
+
+    fn edge_bound(&self) -> usize {
+        self.edge_references()
+            .next_back()
+            .map_or(0, |edge| edge.id().index() + 1)
+    }
+
+    #[cfg(feature = "serde-1")]
+    /// Fix up node and edge links after deserialization
+    fn link_edges(&mut self) -> Result<(), NodeIndex<Ix>> {
+        // set up free node list
+        self.node_count = 0;
+        self.edge_count = 0;
+        let mut free_node = NodeIndex::end();
+        for (node_index, node) in enumerate(&mut self.g.nodes) {
+            if node.weight.is_some() {
+                self.node_count += 1;
+            } else {
+                // free node
+                node.next = [free_node._into_edge(), EdgeIndex::end()];
+                free_node = NodeIndex::new(node_index);
+            }
+        }
+        self.free_node = free_node;
+
+        let mut free_edge = EdgeIndex::end();
+        for (edge_index, edge) in enumerate(&mut self.g.edges) {
+            if edge.weight.is_none() {
+                // free edge
+                edge.next = [free_edge, EdgeIndex::end()];
+                free_edge = EdgeIndex::new(edge_index);
+                continue;
+            }
+            let a = edge.source();
+            let b = edge.target();
+            let edge_idx = EdgeIndex::new(edge_index);
+            match index_twice(&mut self.g.nodes, a.index(), b.index()) {
+                Pair::None => return Err(if a > b { a } else { b }),
+                Pair::One(an) => {
+                    edge.next = an.next;
+                    an.next[0] = edge_idx;
+                    an.next[1] = edge_idx;
+                }
+                Pair::Both(an, bn) => {
+                    // a and b are different indices
+                    edge.next = [an.next[0], bn.next[1]];
+                    an.next[0] = edge_idx;
+                    bn.next[1] = edge_idx;
+                }
+            }
+            self.edge_count += 1;
+        }
+        self.free_edge = free_edge;
+        Ok(())
+    }
+
+    #[cfg(not(debug_assertions))]
+    fn check_free_lists(&self) {}
+    #[cfg(debug_assertions)]
+    // internal method to debug check the free lists (linked lists)
+    fn check_free_lists(&self) {
+        let mut free_node = self.free_node;
+        let mut free_node_len = 0;
+        while free_node != NodeIndex::end() {
+            if let Some(n) = self.g.nodes.get(free_node.index()) {
+                if n.weight.is_none() {
+                    free_node = n.next[0]._into_node();
+                    free_node_len += 1;
+                    continue;
+                }
+                debug_assert!(
+                    false,
+                    "Corrupt free list: pointing to existing {:?}",
+                    free_node.index()
+                );
+            }
+            debug_assert!(false, "Corrupt free list: missing {:?}", free_node.index());
+        }
+        debug_assert_eq!(self.node_count(), self.raw_nodes().len() - free_node_len);
+
+        let mut free_edge_len = 0;
+        let mut free_edge = self.free_edge;
+        while free_edge != EdgeIndex::end() {
+            if let Some(n) = self.g.edges.get(free_edge.index()) {
+                if n.weight.is_none() {
+                    free_edge = n.next[0];
+                    free_edge_len += 1;
+                    continue;
+                }
+                debug_assert!(
+                    false,
+                    "Corrupt free list: pointing to existing {:?}",
+                    free_node.index()
+                );
+            }
+            debug_assert!(false, "Corrupt free list: missing {:?}", free_edge.index());
+        }
+        debug_assert_eq!(self.edge_count(), self.raw_edges().len() - free_edge_len);
+    }
+}
+
+/// The resulting cloned graph has the same graph indices as `self`.
+impl<N, E, Ty, Ix: IndexType> Clone for StableGraph<N, E, Ty, Ix>
+where
+    N: Clone,
+    E: Clone,
+{
+    fn clone(&self) -> Self {
+        StableGraph {
+            g: self.g.clone(),
+            node_count: self.node_count,
+            edge_count: self.edge_count,
+            free_node: self.free_node,
+            free_edge: self.free_edge,
+        }
+    }
+
+    fn clone_from(&mut self, rhs: &Self) {
+        self.g.clone_from(&rhs.g);
+        self.node_count = rhs.node_count;
+        self.edge_count = rhs.edge_count;
+        self.free_node = rhs.free_node;
+        self.free_edge = rhs.free_edge;
+    }
+}
+
+/// Index the `StableGraph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Output = N;
+    fn index(&self, index: NodeIndex<Ix>) -> &N {
+        self.node_weight(index).unwrap()
+    }
+}
+
+/// Index the `StableGraph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn index_mut(&mut self, index: NodeIndex<Ix>) -> &mut N {
+        self.node_weight_mut(index).unwrap()
+    }
+}
+
+/// Index the `StableGraph` by `EdgeIndex` to access edge weights.
+///
+/// **Panics** if the edge doesn't exist.
+impl<N, E, Ty, Ix> Index<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Output = E;
+    fn index(&self, index: EdgeIndex<Ix>) -> &E {
+        self.edge_weight(index).unwrap()
+    }
+}
+
+/// Index the `StableGraph` by `EdgeIndex` to access edge weights.
+///
+/// **Panics** if the edge doesn't exist.
+impl<N, E, Ty, Ix> IndexMut<EdgeIndex<Ix>> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn index_mut(&mut self, index: EdgeIndex<Ix>) -> &mut E {
+        self.edge_weight_mut(index).unwrap()
+    }
+}
+
+/// Create a new empty `StableGraph`.
+impl<N, E, Ty, Ix> Default for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn default() -> Self {
+        Self::with_capacity(0, 0)
+    }
+}
+
+/// Convert a `Graph` into a `StableGraph`
+///
+/// Computes in **O(|V| + |E|)** time.
+///
+/// The resulting graph has the same node and edge indices as
+/// the original graph.
+impl<N, E, Ty, Ix> From<Graph<N, E, Ty, Ix>> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn from(g: Graph<N, E, Ty, Ix>) -> Self {
+        let nodes = g.nodes.into_iter().map(|e| Node {
+            weight: Some(e.weight),
+            next: e.next,
+        });
+        let edges = g.edges.into_iter().map(|e| Edge {
+            weight: Some(e.weight),
+            node: e.node,
+            next: e.next,
+        });
+        StableGraph {
+            node_count: nodes.len(),
+            edge_count: edges.len(),
+            g: Graph {
+                edges: edges.collect(),
+                nodes: nodes.collect(),
+                ty: g.ty,
+            },
+            free_node: NodeIndex::end(),
+            free_edge: EdgeIndex::end(),
+        }
+    }
+}
+
+/// Convert a `StableGraph` into a `Graph`
+///
+/// Computes in **O(|V| + |E|)** time.
+///
+/// This translates the stable graph into a graph with node and edge indices in
+/// a compact interval without holes (like `Graph`s always are).
+///
+/// Only if the stable graph had no vacancies after deletions (if node bound was
+/// equal to node count, and the same for edges), would the resulting graph have
+/// the same node and edge indices as the input.
+impl<N, E, Ty, Ix> From<StableGraph<N, E, Ty, Ix>> for Graph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    fn from(graph: StableGraph<N, E, Ty, Ix>) -> Self {
+        let mut result_g = Graph::with_capacity(graph.node_count(), graph.edge_count());
+        // mapping from old node index to new node index
+        let mut node_index_map = vec![NodeIndex::end(); graph.node_bound()];
+
+        for (i, node) in enumerate(graph.g.nodes) {
+            if let Some(nw) = node.weight {
+                node_index_map[i] = result_g.add_node(nw);
+            }
+        }
+        for edge in graph.g.edges {
+            let source_index = edge.source().index();
+            let target_index = edge.target().index();
+            if let Some(ew) = edge.weight {
+                let source = node_index_map[source_index];
+                let target = node_index_map[target_index];
+                debug_assert!(source != NodeIndex::end());
+                debug_assert!(target != NodeIndex::end());
+                result_g.add_edge(source, target, ew);
+            }
+        }
+        result_g
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type NodeRef = (NodeIndex<Ix>, &'a N);
+    type NodeReferences = NodeReferences<'a, N, Ix>;
+    fn node_references(self) -> Self::NodeReferences {
+        NodeReferences {
+            iter: enumerate(self.raw_nodes()),
+        }
+    }
+}
+
+/// Iterator over all nodes of a graph.
+pub struct NodeReferences<'a, N: 'a, Ix: IndexType = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Node<Option<N>, Ix>>>,
+}
+
+impl<'a, N, Ix> Iterator for NodeReferences<'a, N, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = (NodeIndex<Ix>, &'a N);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter
+            .ex_find_map(|(i, node)| node.weight.as_ref().map(move |w| (node_index(i), w)))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (_, hi) = self.iter.size_hint();
+        (0, hi)
+    }
+}
+
+impl<'a, N, Ix> DoubleEndedIterator for NodeReferences<'a, N, Ix>
+where
+    Ix: IndexType,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter
+            .ex_rfind_map(|(i, node)| node.weight.as_ref().map(move |w| (node_index(i), w)))
+    }
+}
+
+/// Reference to a `StableGraph` edge.
+#[derive(Debug)]
+pub struct EdgeReference<'a, E: 'a, Ix = DefaultIx> {
+    index: EdgeIndex<Ix>,
+    node: [NodeIndex<Ix>; 2],
+    weight: &'a E,
+}
+
+impl<'a, E, Ix: IndexType> Clone for EdgeReference<'a, E, Ix> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<'a, E, Ix: IndexType> Copy for EdgeReference<'a, E, Ix> {}
+
+impl<'a, E, Ix: IndexType> PartialEq for EdgeReference<'a, E, Ix>
+where
+    E: PartialEq,
+{
+    fn eq(&self, rhs: &Self) -> bool {
+        self.index == rhs.index && self.weight == rhs.weight
+    }
+}
+
+impl<'a, Ix, E> EdgeReference<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    /// Access the edge’s weight.
+    ///
+    /// **NOTE** that this method offers a longer lifetime
+    /// than the trait (unfortunately they don't match yet).
+    pub fn weight(&self) -> &'a E {
+        self.weight
+    }
+}
+
+impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type NodeId = NodeIndex<Ix>;
+    type EdgeId = EdgeIndex<Ix>;
+    type Weight = E;
+
+    fn source(&self) -> Self::NodeId {
+        self.node[0]
+    }
+    fn target(&self) -> Self::NodeId {
+        self.node[1]
+    }
+    fn weight(&self) -> &E {
+        self.weight
+    }
+    fn id(&self) -> Self::EdgeId {
+        self.index
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoEdges for &'a StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Edges = Edges<'a, E, Ty, Ix>;
+    fn edges(self, a: Self::NodeId) -> Self::Edges {
+        self.edges(a)
+    }
+}
+
+impl<'a, N, E, Ty, Ix> IntoEdgesDirected for &'a StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type EdgesDirected = Edges<'a, E, Ty, Ix>;
+    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
+        self.edges_directed(a, dir)
+    }
+}
+
+/// Iterator over the edges of from or to a node
+pub struct Edges<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// starting node to skip over
+    skip_start: NodeIndex<Ix>,
+    edges: &'a [Edge<Option<E>, Ix>],
+
+    /// Next edge to visit.
+    next: [EdgeIndex<Ix>; 2],
+
+    /// For directed graphs: the direction to iterate in
+    /// For undirected graphs: the direction of edges
+    direction: Direction,
+    ty: PhantomData<Ty>,
+}
+
+impl<'a, E, Ty, Ix> Iterator for Edges<'a, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Item = EdgeReference<'a, E, Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        //      type        direction    |    iterate over    reverse
+        //                               |
+        //    Directed      Outgoing     |      outgoing        no
+        //    Directed      Incoming     |      incoming        no
+        //   Undirected     Outgoing     |        both       incoming
+        //   Undirected     Incoming     |        both       outgoing
+
+        // For iterate_over, "both" is represented as None.
+        // For reverse, "no" is represented as None.
+        let (iterate_over, reverse) = if Ty::is_directed() {
+            (Some(self.direction), None)
+        } else {
+            (None, Some(self.direction.opposite()))
+        };
+
+        if iterate_over.unwrap_or(Outgoing) == Outgoing {
+            let i = self.next[0].index();
+            if let Some(Edge {
+                node,
+                weight: Some(weight),
+                next,
+            }) = self.edges.get(i)
+            {
+                self.next[0] = next[0];
+                return Some(EdgeReference {
+                    index: edge_index(i),
+                    node: if reverse == Some(Outgoing) {
+                        swap_pair(*node)
+                    } else {
+                        *node
+                    },
+                    weight,
+                });
+            }
+        }
+
+        if iterate_over.unwrap_or(Incoming) == Incoming {
+            while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
+                debug_assert!(weight.is_some());
+                let edge_index = self.next[1];
+                self.next[1] = next[1];
+                // In any of the "both" situations, self-loops would be iterated over twice.
+                // Skip them here.
+                if iterate_over.is_none() && node[0] == self.skip_start {
+                    continue;
+                }
+
+                return Some(EdgeReference {
+                    index: edge_index,
+                    node: if reverse == Some(Incoming) {
+                        swap_pair(*node)
+                    } else {
+                        *node
+                    },
+                    weight: weight.as_ref().unwrap(),
+                });
+            }
+        }
+
+        None
+    }
+}
+
+fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
+    x.swap(0, 1);
+    x
+}
+
+impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type EdgeRef = EdgeReference<'a, E, Ix>;
+    type EdgeReferences = EdgeReferences<'a, E, Ix>;
+
+    /// Create an iterator over all edges in the graph, in indexed order.
+    ///
+    /// Iterator element type is `EdgeReference<E, Ix>`.
+    fn edge_references(self) -> Self::EdgeReferences {
+        EdgeReferences {
+            iter: self.g.edges.iter().enumerate(),
+        }
+    }
+}
+
+/// Iterator over all edges of a graph.
+pub struct EdgeReferences<'a, E: 'a, Ix: 'a = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Edge<Option<E>, Ix>>>,
+}
+
+impl<'a, E, Ix> Iterator for EdgeReferences<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = EdgeReference<'a, E, Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.ex_find_map(|(i, edge)| {
+            edge.weight.as_ref().map(move |weight| EdgeReference {
+                index: edge_index(i),
+                node: edge.node,
+                weight,
+            })
+        })
+    }
+}
+
+impl<'a, E, Ix> DoubleEndedIterator for EdgeReferences<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.ex_rfind_map(|(i, edge)| {
+            edge.weight.as_ref().map(move |weight| EdgeReference {
+                index: edge_index(i),
+                node: edge.node,
+                weight,
+            })
+        })
+    }
+}
+
+/// An iterator over either the nodes without edges to them or from them.
+pub struct Externals<'a, N: 'a, Ty, Ix: IndexType = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Node<Option<N>, Ix>>>,
+    dir: Direction,
+    ty: PhantomData<Ty>,
+}
+
+impl<'a, N: 'a, Ty, Ix> Iterator for Externals<'a, N, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    type Item = NodeIndex<Ix>;
+    fn next(&mut self) -> Option<NodeIndex<Ix>> {
+        let k = self.dir.index();
+        loop {
+            match self.iter.next() {
+                None => return None,
+                Some((index, node)) => {
+                    if node.weight.is_some()
+                        && node.next[k] == EdgeIndex::end()
+                        && (Ty::is_directed() || node.next[1 - k] == EdgeIndex::end())
+                    {
+                        return Some(NodeIndex::new(index));
+                    } else {
+                        continue;
+                    }
+                }
+            }
+        }
+    }
+}
+
+/// Iterator over the neighbors of a node.
+///
+/// Iterator element type is `NodeIndex`.
+pub struct Neighbors<'a, E: 'a, Ix: 'a = DefaultIx> {
+    /// starting node to skip over
+    skip_start: NodeIndex<Ix>,
+    edges: &'a [Edge<Option<E>, Ix>],
+    next: [EdgeIndex<Ix>; 2],
+}
+
+impl<'a, E, Ix> Neighbors<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    /// Return a “walker” object that can be used to step through the
+    /// neighbors and edges from the origin node.
+    ///
+    /// Note: The walker does not borrow from the graph, this is to allow mixing
+    /// edge walking with mutating the graph's weights.
+    pub fn detach(&self) -> WalkNeighbors<Ix> {
+        WalkNeighbors {
+            inner: super::WalkNeighbors {
+                skip_start: self.skip_start,
+                next: self.next,
+            },
+        }
+    }
+}
+
+impl<'a, E, Ix> Iterator for Neighbors<'a, E, Ix>
+where
+    Ix: IndexType,
+{
+    type Item = NodeIndex<Ix>;
+
+    fn next(&mut self) -> Option<NodeIndex<Ix>> {
+        // First any outgoing edges
+        match self.edges.get(self.next[0].index()) {
+            None => {}
+            Some(edge) => {
+                debug_assert!(edge.weight.is_some());
+                self.next[0] = edge.next[0];
+                return Some(edge.node[1]);
+            }
+        }
+        // Then incoming edges
+        // For an "undirected" iterator (traverse both incoming
+        // and outgoing edge lists), make sure we don't double
+        // count selfloops by skipping them in the incoming list.
+        while let Some(edge) = self.edges.get(self.next[1].index()) {
+            debug_assert!(edge.weight.is_some());
+            self.next[1] = edge.next[1];
+            if edge.node[0] != self.skip_start {
+                return Some(edge.node[0]);
+            }
+        }
+        None
+    }
+}
+
+/// A “walker” object that can be used to step through the edge list of a node.
+///
+/// See [*.detach()*](struct.Neighbors.html#method.detach) for more information.
+///
+/// The walker does not borrow from the graph, so it lets you step through
+/// neighbors or incident edges while also mutating graph weights, as
+/// in the following example:
+///
+/// ```
+/// use petgraph::visit::Dfs;
+/// use petgraph::Incoming;
+/// use petgraph::stable_graph::StableGraph;
+///
+/// let mut gr = StableGraph::new();
+/// let a = gr.add_node(0.);
+/// let b = gr.add_node(0.);
+/// let c = gr.add_node(0.);
+/// gr.add_edge(a, b, 3.);
+/// gr.add_edge(b, c, 2.);
+/// gr.add_edge(c, b, 1.);
+///
+/// // step through the graph and sum incoming edges into the node weight
+/// let mut dfs = Dfs::new(&gr, a);
+/// while let Some(node) = dfs.next(&gr) {
+///     // use a detached neighbors walker
+///     let mut edges = gr.neighbors_directed(node, Incoming).detach();
+///     while let Some(edge) = edges.next_edge(&gr) {
+///         gr[node] += gr[edge];
+///     }
+/// }
+///
+/// // check the result
+/// assert_eq!(gr[a], 0.);
+/// assert_eq!(gr[b], 4.);
+/// assert_eq!(gr[c], 2.);
+/// ```
+pub struct WalkNeighbors<Ix> {
+    inner: super::WalkNeighbors<Ix>,
+}
+
+impl<Ix: IndexType> Clone for WalkNeighbors<Ix> {
+    clone_fields!(WalkNeighbors, inner);
+}
+
+impl<Ix: IndexType> WalkNeighbors<Ix> {
+    /// Step to the next edge and its endpoint node in the walk for graph `g`.
+    ///
+    /// The next node indices are always the others than the starting point
+    /// where the `WalkNeighbors` value was created.
+    /// For an `Outgoing` walk, the target nodes,
+    /// for an `Incoming` walk, the source nodes of the edge.
+    pub fn next<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &StableGraph<N, E, Ty, Ix>,
+    ) -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)> {
+        self.inner.next(&g.g)
+    }
+
+    pub fn next_node<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &StableGraph<N, E, Ty, Ix>,
+    ) -> Option<NodeIndex<Ix>> {
+        self.next(g).map(|t| t.1)
+    }
+
+    pub fn next_edge<N, E, Ty: EdgeType>(
+        &mut self,
+        g: &StableGraph<N, E, Ty, Ix>,
+    ) -> Option<EdgeIndex<Ix>> {
+        self.next(g).map(|t| t.0)
+    }
+}
+
+/// Iterator over the node indices of a graph.
+pub struct NodeIndices<'a, N: 'a, Ix: 'a = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Node<Option<N>, Ix>>>,
+}
+
+impl<'a, N, Ix: IndexType> Iterator for NodeIndices<'a, N, Ix> {
+    type Item = NodeIndex<Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.ex_find_map(|(i, node)| {
+            if node.weight.is_some() {
+                Some(node_index(i))
+            } else {
+                None
+            }
+        })
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (_, hi) = self.iter.size_hint();
+        (0, hi)
+    }
+}
+
+impl<'a, N, Ix: IndexType> DoubleEndedIterator for NodeIndices<'a, N, Ix> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.ex_rfind_map(|(i, node)| {
+            if node.weight.is_some() {
+                Some(node_index(i))
+            } else {
+                None
+            }
+        })
+    }
+}
+
+impl<N, E, Ty, Ix> NodeIndexable for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType,
+{
+    /// Return an upper bound of the node indices in the graph
+    fn node_bound(&self) -> usize {
+        self.node_indices().next_back().map_or(0, |i| i.index() + 1)
+    }
+    fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
+        ix.index()
+    }
+    fn from_index(&self, ix: usize) -> Self::NodeId {
+        NodeIndex::new(ix)
+    }
+}
+
+/// Iterator over the edge indices of a graph.
+pub struct EdgeIndices<'a, E: 'a, Ix: 'a = DefaultIx> {
+    iter: iter::Enumerate<slice::Iter<'a, Edge<Option<E>, Ix>>>,
+}
+
+impl<'a, E, Ix: IndexType> Iterator for EdgeIndices<'a, E, Ix> {
+    type Item = EdgeIndex<Ix>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.ex_find_map(|(i, node)| {
+            if node.weight.is_some() {
+                Some(edge_index(i))
+            } else {
+                None
+            }
+        })
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (_, hi) = self.iter.size_hint();
+        (0, hi)
+    }
+}
+
+impl<'a, E, Ix: IndexType> DoubleEndedIterator for EdgeIndices<'a, E, Ix> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.iter.ex_rfind_map(|(i, node)| {
+            if node.weight.is_some() {
+                Some(edge_index(i))
+            } else {
+                None
+            }
+        })
+    }
+}
+
+#[test]
+fn stable_graph() {
+    let mut gr = StableGraph::<_, _>::with_capacity(0, 0);
+    let a = gr.add_node(0);
+    let b = gr.add_node(1);
+    let c = gr.add_node(2);
+    let _ed = gr.add_edge(a, b, 1);
+    println!("{:?}", gr);
+    gr.remove_node(b);
+    println!("{:?}", gr);
+    let d = gr.add_node(3);
+    println!("{:?}", gr);
+    gr.check_free_lists();
+    gr.remove_node(a);
+    gr.check_free_lists();
+    gr.remove_node(c);
+    gr.check_free_lists();
+    println!("{:?}", gr);
+    gr.add_edge(d, d, 2);
+    println!("{:?}", gr);
+
+    let e = gr.add_node(4);
+    gr.add_edge(d, e, 3);
+    println!("{:?}", gr);
+    for neigh in gr.neighbors(d) {
+        println!("edge {:?} -> {:?}", d, neigh);
+    }
+    gr.check_free_lists();
+}
+
+#[test]
+fn dfs() {
+    use crate::visit::Dfs;
+
+    let mut gr = StableGraph::<_, _>::with_capacity(0, 0);
+    let a = gr.add_node("a");
+    let b = gr.add_node("b");
+    let c = gr.add_node("c");
+    let d = gr.add_node("d");
+    gr.add_edge(a, b, 1);
+    gr.add_edge(a, c, 2);
+    gr.add_edge(b, c, 3);
+    gr.add_edge(b, d, 4);
+    gr.add_edge(c, d, 5);
+    gr.add_edge(d, b, 6);
+    gr.add_edge(c, b, 7);
+    println!("{:?}", gr);
+
+    let mut dfs = Dfs::new(&gr, a);
+    while let Some(next) = dfs.next(&gr) {
+        println!("dfs visit => {:?}, weight={:?}", next, &gr[next]);
+    }
+}
+
+#[test]
+fn test_retain_nodes() {
+    let mut gr = StableGraph::<_, _>::with_capacity(6, 6);
+    let a = gr.add_node("a");
+    let f = gr.add_node("f");
+    let b = gr.add_node("b");
+    let c = gr.add_node("c");
+    let d = gr.add_node("d");
+    let e = gr.add_node("e");
+    gr.add_edge(a, b, 1);
+    gr.add_edge(a, c, 2);
+    gr.add_edge(b, c, 3);
+    gr.add_edge(b, d, 4);
+    gr.add_edge(c, d, 5);
+    gr.add_edge(d, b, 6);
+    gr.add_edge(c, b, 7);
+    gr.add_edge(d, e, 8);
+    gr.remove_node(f);
+
+    assert_eq!(gr.node_count(), 5);
+    assert_eq!(gr.edge_count(), 8);
+    gr.retain_nodes(|frozen_gr, ix| frozen_gr[ix] >= "c");
+    assert_eq!(gr.node_count(), 3);
+    assert_eq!(gr.edge_count(), 2);
+
+    gr.check_free_lists();
+}
diff --git a/vendor/petgraph/src/graph_impl/stable_graph/serialization.rs b/vendor/petgraph/src/graph_impl/stable_graph/serialization.rs
new file mode 100644
index 000000000..c24ca636b
--- /dev/null
+++ b/vendor/petgraph/src/graph_impl/stable_graph/serialization.rs
@@ -0,0 +1,296 @@
+use serde::de::Error;
+use serde::{Deserialize, Deserializer, Serialize, Serializer};
+
+use std::marker::PhantomData;
+
+use crate::prelude::*;
+
+use crate::graph::Node;
+use crate::graph::{Edge, IndexType};
+use crate::serde_utils::CollectSeqWithLength;
+use crate::serde_utils::MappedSequenceVisitor;
+use crate::serde_utils::{FromDeserialized, IntoSerializable};
+use crate::stable_graph::StableGraph;
+use crate::util::rev;
+use crate::visit::NodeIndexable;
+use crate::EdgeType;
+
+use super::super::serialization::{invalid_length_err, invalid_node_err, EdgeProperty};
+
+// Serialization representation for StableGraph
+// Keep in sync with deserialization and Graph
+#[derive(Serialize)]
+#[serde(rename = "Graph")]
+#[serde(bound(serialize = "N: Serialize, E: Serialize, Ix: IndexType + Serialize"))]
+pub struct SerStableGraph<'a, N: 'a, E: 'a, Ix: 'a + IndexType> {
+    nodes: Somes<&'a [Node<Option<N>, Ix>]>,
+    node_holes: Holes<&'a [Node<Option<N>, Ix>]>,
+    edge_property: EdgeProperty,
+    #[serde(serialize_with = "ser_stable_graph_edges")]
+    edges: &'a [Edge<Option<E>, Ix>],
+}
+
+// Deserialization representation for StableGraph
+// Keep in sync with serialization and Graph
+#[derive(Deserialize)]
+#[serde(rename = "Graph")]
+#[serde(bound(
+    deserialize = "N: Deserialize<'de>, E: Deserialize<'de>, Ix: IndexType + Deserialize<'de>"
+))]
+pub struct DeserStableGraph<N, E, Ix> {
+    #[serde(deserialize_with = "deser_stable_graph_nodes")]
+    nodes: Vec<Node<Option<N>, Ix>>,
+    #[serde(default = "Vec::new")]
+    node_holes: Vec<NodeIndex<Ix>>,
+    edge_property: EdgeProperty,
+    #[serde(deserialize_with = "deser_stable_graph_edges")]
+    edges: Vec<Edge<Option<E>, Ix>>,
+}
+
+/// `Somes` are the present node weights N, with known length.
+struct Somes<T>(usize, T);
+
+impl<'a, N, Ix> Serialize for Somes<&'a [Node<Option<N>, Ix>]>
+where
+    N: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        serializer.collect_seq_with_length(
+            self.0,
+            self.1.iter().filter_map(|node| node.weight.as_ref()),
+        )
+    }
+}
+
+/// Holes are the node indices of vacancies, with known length
+struct Holes<T>(usize, T);
+
+impl<'a, N, Ix> Serialize for Holes<&'a [Node<Option<N>, Ix>]>
+where
+    Ix: Serialize + IndexType,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        serializer.collect_seq_with_length(
+            self.0,
+            self.1.iter().enumerate().filter_map(|(i, node)| {
+                if node.weight.is_none() {
+                    Some(NodeIndex::<Ix>::new(i))
+                } else {
+                    None
+                }
+            }),
+        )
+    }
+}
+
+fn ser_stable_graph_edges<S, E, Ix>(
+    edges: &&[Edge<Option<E>, Ix>],
+    serializer: S,
+) -> Result<S::Ok, S::Error>
+where
+    S: Serializer,
+    E: Serialize,
+    Ix: Serialize + IndexType,
+{
+    serializer.collect_seq_exact(edges.iter().map(|edge| {
+        edge.weight
+            .as_ref()
+            .map(|w| (edge.source(), edge.target(), w))
+    }))
+}
+
+fn deser_stable_graph_nodes<'de, D, N, Ix>(
+    deserializer: D,
+) -> Result<Vec<Node<Option<N>, Ix>>, D::Error>
+where
+    D: Deserializer<'de>,
+    N: Deserialize<'de>,
+    Ix: IndexType + Deserialize<'de>,
+{
+    deserializer.deserialize_seq(MappedSequenceVisitor::new(|n| {
+        Ok(Node {
+            weight: Some(n),
+            next: [EdgeIndex::end(); 2],
+        })
+    }))
+}
+
+fn deser_stable_graph_edges<'de, D, N, Ix>(
+    deserializer: D,
+) -> Result<Vec<Edge<Option<N>, Ix>>, D::Error>
+where
+    D: Deserializer<'de>,
+    N: Deserialize<'de>,
+    Ix: IndexType + Deserialize<'de>,
+{
+    deserializer.deserialize_seq(MappedSequenceVisitor::<
+        Option<(NodeIndex<Ix>, NodeIndex<Ix>, N)>,
+        _,
+        _,
+    >::new(|x| {
+        if let Some((i, j, w)) = x {
+            Ok(Edge {
+                weight: Some(w),
+                node: [i, j],
+                next: [EdgeIndex::end(); 2],
+            })
+        } else {
+            Ok(Edge {
+                weight: None,
+                node: [NodeIndex::end(); 2],
+                next: [EdgeIndex::end(); 2],
+            })
+        }
+    }))
+}
+
+impl<'a, N, E, Ty, Ix> IntoSerializable for &'a StableGraph<N, E, Ty, Ix>
+where
+    Ix: IndexType,
+    Ty: EdgeType,
+{
+    type Output = SerStableGraph<'a, N, E, Ix>;
+    fn into_serializable(self) -> Self::Output {
+        let nodes = &self.raw_nodes()[..self.node_bound()];
+        let node_count = self.node_count();
+        let hole_count = nodes.len() - node_count;
+        let edges = &self.raw_edges()[..self.edge_bound()];
+        SerStableGraph {
+            nodes: Somes(node_count, nodes),
+            node_holes: Holes(hole_count, nodes),
+            edges: edges,
+            edge_property: EdgeProperty::from(PhantomData::<Ty>),
+        }
+    }
+}
+
+/// Requires crate feature `"serde-1"`
+impl<N, E, Ty, Ix> Serialize for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType + Serialize,
+    N: Serialize,
+    E: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.into_serializable().serialize(serializer)
+    }
+}
+
+impl<'a, N, E, Ty, Ix> FromDeserialized for StableGraph<N, E, Ty, Ix>
+where
+    Ix: IndexType,
+    Ty: EdgeType,
+{
+    type Input = DeserStableGraph<N, E, Ix>;
+    fn from_deserialized<E2>(input: Self::Input) -> Result<Self, E2>
+    where
+        E2: Error,
+    {
+        let ty = PhantomData::<Ty>::from_deserialized(input.edge_property)?;
+        let mut nodes = input.nodes;
+        let node_holes = input.node_holes;
+        let edges = input.edges;
+        if edges.len() >= <Ix as IndexType>::max().index() {
+            Err(invalid_length_err::<Ix, _>("edge", edges.len()))?
+        }
+
+        // insert Nones for each hole
+        let mut offset = node_holes.len();
+        let node_bound = node_holes.len() + nodes.len();
+        for hole_pos in rev(node_holes) {
+            offset -= 1;
+            if hole_pos.index() >= node_bound {
+                Err(invalid_node_err(hole_pos.index(), node_bound))?;
+            }
+            let insert_pos = hole_pos.index() - offset;
+            nodes.insert(
+                insert_pos,
+                Node {
+                    weight: None,
+                    next: [EdgeIndex::end(); 2],
+                },
+            );
+        }
+
+        if nodes.len() >= <Ix as IndexType>::max().index() {
+            Err(invalid_length_err::<Ix, _>("node", nodes.len()))?
+        }
+
+        let node_bound = nodes.len();
+        let mut sgr = StableGraph {
+            g: Graph {
+                nodes: nodes,
+                edges: edges,
+                ty: ty,
+            },
+            node_count: 0,
+            edge_count: 0,
+            free_edge: EdgeIndex::end(),
+            free_node: NodeIndex::end(),
+        };
+        sgr.link_edges()
+            .map_err(|i| invalid_node_err(i.index(), node_bound))?;
+        Ok(sgr)
+    }
+}
+
+/// Requires crate feature `"serde-1"`
+impl<'de, N, E, Ty, Ix> Deserialize<'de> for StableGraph<N, E, Ty, Ix>
+where
+    Ty: EdgeType,
+    Ix: IndexType + Deserialize<'de>,
+    N: Deserialize<'de>,
+    E: Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        Self::from_deserialized(DeserStableGraph::deserialize(deserializer)?)
+    }
+}
+
+#[test]
+fn test_from_deserialized_with_holes() {
+    use crate::graph::node_index;
+    use crate::stable_graph::StableUnGraph;
+    use itertools::assert_equal;
+    use serde::de::value::Error as SerdeError;
+
+    let input = DeserStableGraph::<_, (), u32> {
+        nodes: vec![
+            Node {
+                weight: Some(1),
+                next: [EdgeIndex::end(); 2],
+            },
+            Node {
+                weight: Some(4),
+                next: [EdgeIndex::end(); 2],
+            },
+            Node {
+                weight: Some(5),
+                next: [EdgeIndex::end(); 2],
+            },
+        ],
+        node_holes: vec![node_index(0), node_index(2), node_index(3), node_index(6)],
+        edges: vec![],
+        edge_property: EdgeProperty::Undirected,
+    };
+    let graph = StableUnGraph::from_deserialized::<SerdeError>(input).unwrap();
+
+    assert_eq!(graph.node_count(), 3);
+    assert_equal(
+        graph.raw_nodes().iter().map(|n| n.weight.as_ref().cloned()),
+        vec![None, Some(1), None, None, Some(4), Some(5), None],
+    );
+}