diff --git a/src/graph.rs b/src/graph.rs
index f79720a..c704976 100644
--- a/src/graph.rs
+++ b/src/graph.rs
@@ -4,6 +4,7 @@
 use std::fmt;
 use std::iter;
 use std::marker::PhantomData;
+use std::mem::replace;
 use std::ops::{Index, IndexMut, Range};
 use std::slice;
 
@@ -404,8 +405,10 @@
         EdgeIndex,
         Graph2,
         Vector,
+        StableVector,
         Graph,
         GraphIface,
+        StableGraph,
     };
 
     pub trait PrivateBackend {
@@ -426,6 +429,17 @@
         type Ty = Ty;
         type Ix = Ix;
     }
+
+    impl<N, E, Ix, Ty> PrivateBackend for Graph2<N, E, Ty, Ix, StableVector>
+        where Ix: IndexType,
+              Ty: EdgeType,
+    {
+        type Repr = StableGraph<N, E, Ty, Ix>;
+        type N = N;
+        type E = E;
+        type Ty = Ty;
+        type Ix = Ix;
+    }
 }
 
 trait GraphIface {
@@ -499,6 +513,110 @@
     }
 }
 
+pub struct StableGraph<N, E, Ty = Directed, Ix = DefIndex>
+    where Ix: IndexType
+{
+    g: Graph<Option<N>, Option<E>, Ty, Ix>,
+    node_count: usize,
+    edge_count: usize,
+    free_node: NodeIndex<Ix>,
+    free_edge: EdgeIndex<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 {
+        try!(writeln!(f, "{:?}", self.g));
+        try!(writeln!(f, "free_node={:?}", self.free_node));
+        try!(writeln!(f, "free_edge={:?}", self.free_edge));
+        try!(writeln!(f, "node_count={:?}", self.node_count));
+        try!(writeln!(f, "edge_count={:?}", self.edge_count));
+        Ok(())
+    }
+}
+
+impl<N, E> StableGraph<N, E, Directed> {
+    /// Create a new `StableGraph` with directed edges.
+    pub fn new() -> Self {
+        Self::with_capacity(0, 0)
+    }
+}
+
+impl<N, E, Ty=Directed, Ix=DefIndex> StableGraph<N, E, Ty, Ix>
+    where Ty: EdgeType,
+          Ix: IndexType,
+{
+    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(),
+        }
+    }
+}
+
+impl<N, E, Ty, Ix> GraphIface for StableGraph<N, E, Ty, Ix>
+    where Ty: EdgeType,
+          Ix: IndexType,
+{
+    type N = N;
+    type E = E;
+    type Ty = Ty;
+    type Ix = Ix;
+
+    fn new() -> Self {
+        StableGraph::with_capacity(0, 0)
+    }
+
+    /// Return the current node and edge capacity of the graph.
+    fn capacity(&self) -> (usize, usize) {
+        self.g.capacity()
+    }
+
+    /*
+    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();
+    }
+    */
+
+    fn node_count(&self) -> usize {
+        self.node_count
+    }
+
+    fn edge_count(&self) -> usize {
+        self.edge_count
+    }
+
+    /// Whether the graph has directed edges or not.
+    #[inline]
+    fn is_directed(&self) -> bool {
+        Ty::is_directed()
+    }
+
+    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
+    }
+}
+
 impl<N, E> Graph<N, E, Directed>
 {
     /// Create a new `Graph` with directed edges.
@@ -1776,5 +1894,3 @@
 #[path = "stable.rs"]
 pub mod stable;
 
-use self::stable::StableGraph;
-