MatrixGraph: allow specifying the index type `Ix`
diff --git a/src/matrix_graph.rs b/src/matrix_graph.rs
index e3624e0..1e57e56 100644
--- a/src/matrix_graph.rs
+++ b/src/matrix_graph.rs
@@ -1,4 +1,4 @@
-//! `MatrixGraph<N, E, Ty, Null>` is a graph datastructure backed by an adjacency matrix.
+//! `MatrixGraph<N, E, Ty, NullN, NullE, Ix>` is a graph datastructure backed by an adjacency matrix.
 
 use std::marker::PhantomData;
 use std::ops::{Index, IndexMut};
@@ -45,10 +45,10 @@
 // The following types are used to control the max size of the adjacency matrix. Since the maximum
 // size of the matrix vector's is the square of the maximum number of nodes, the number of nodes
 // should be reasonably picked.
-type Ix = u16;
+type DefaultIx = u16;
 
 /// Node identifier.
-pub type NodeIndex = GraphNodeIndex<Ix>;
+pub type NodeIndex<Ix=DefaultIx> = GraphNodeIndex<Ix>;
 
 mod private {
     pub trait Sealed {}
@@ -182,10 +182,9 @@
 not_zero_impls!(i8, i16, i32, i64, isize);
 not_zero_impls!(f32, f64);
 
-/// Short version of `NodeIndex::new`
+/// Short version of `NodeIndex::new` (with Ix = `DefaultIx`)
 #[inline]
 pub fn node_index(ax: usize) -> NodeIndex {
-    debug_assert!(ax.index() <= Ix::max_value() as usize);
     NodeIndex::new(ax)
 }
 
@@ -200,6 +199,7 @@
 /// - Nullable type `Null`, which denotes the edges' presence (defaults to `Option<E>`). You may
 ///   specify [`NotZero<E>`](struct.NotZero.html) if you want to use a sentinel value (such as 0)
 ///   to mark the absence of an edge.
+/// - Index type `Ix` that sets the maximum size for the graph (defaults to `DefaultIx`).
 ///
 /// The graph uses **O(|V^2|)** space, with fast edge insertion & amortized node insertion, as well
 /// as efficient graph search and graph algorithms on dense graphs.
@@ -208,44 +208,41 @@
 /// matrix is stored. Since the backing array stores edge weights, it is recommended to box large
 /// edge weights.
 #[derive(Clone)]
-pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped=E> = Option<E>> {
+pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped=E> = Option<E>, Ix = DefaultIx> {
     node_adjacencies: Vec<Null>,
     node_capacity: usize,
     nodes: IdStorage<N>,
     nb_edges: usize,
     ty: PhantomData<Ty>,
+    ix: PhantomData<Ix>,
 }
 
 /// A `MatrixGraph` with directed edges.
-pub type DiMatrix<N, E, Null = Option<E>> = MatrixGraph<N, E, Directed, Null>;
+pub type DiMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Directed, Null, Ix>;
 
 /// A `MatrixGraph` with undirected edges.
-pub type UnMatrix<N, E, Null = Option<E>> = MatrixGraph<N, E, Undirected, Null>;
+pub type UnMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Undirected, Null, Ix>;
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> MatrixGraph<N, E, Ty, Null, Ix> {
     /// Create a new `MatrixGraph` with estimated capacity for nodes.
     pub fn with_nodes(nodes: usize) -> Self {
-        let mut m = MatrixGraph {
+        let mut m = Self {
             node_adjacencies: vec![],
             node_capacity: 0,
             nodes: IdStorage::with_capacity(nodes),
             nb_edges: 0,
             ty: PhantomData,
+            ix: PhantomData,
         };
 
-        m.extend_capacity_to(nodes);
+        debug_assert!(nodes <= <Ix as IndexType>::max().index());
+        m.extend_capacity_for_node(NodeIndex::new(nodes));
 
         m
     }
 
     #[inline]
-    fn extend_capacity_to(&mut self, min_node_index: usize) {
-        debug_assert!(min_node_index <= Ix::max_value() as usize);
-        self.node_capacity = extend_linearized_matrix::<Ty, _>(&mut self.node_adjacencies, self.node_capacity, min_node_index);
-    }
-
-    #[inline]
-    fn to_edge_position(&self, a: NodeIndex, b: NodeIndex) -> usize {
+    fn to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize {
         to_linearized_matrix_position::<Ty>(a.index(), b.index(), self.node_capacity)
     }
 
@@ -287,8 +284,8 @@
     /// Return the index of the new node.
     ///
     /// **Panics** if the MatrixGraph is at the maximum number of nodes for its index type.
-    pub fn add_node(&mut self, weight: N) -> NodeIndex {
-        node_index(self.nodes.add(weight))
+    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
+        NodeIndex::new(self.nodes.add(weight))
     }
 
     /// Remove `a` from the graph.
@@ -296,7 +293,7 @@
     /// Computes in **O(V)** time, due to the removal of edges with other nodes.
     ///
     /// **Panics** if the node `a` does not exist.
-    pub fn remove_node(&mut self, a: NodeIndex) -> N {
+    pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N {
         macro_rules! node_ids {
             () => {
                 self.node_identifiers()
@@ -325,6 +322,19 @@
         self.nodes.remove(a.index())
     }
 
+    #[inline]
+    fn extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>) {
+        self.node_capacity = extend_linearized_matrix::<Ty, _>(&mut self.node_adjacencies, self.node_capacity, min_node.index());
+    }
+
+    #[inline]
+    fn extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) {
+        let min_node = cmp::max(a, b);
+        if min_node.index() >= self.node_capacity {
+            self.extend_capacity_for_node(min_node);
+        }
+    }
+
     /// Update the edge from `a` to `b` to the graph, with its associated data `weight`.
     ///
     /// Return the previous data, if any.
@@ -333,11 +343,8 @@
     /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
     ///
     /// **Panics** if any of the nodes don't exist.
-    pub fn update_edge(&mut self, a: NodeIndex, b: NodeIndex, weight: E) -> Option<E> {
-        let min_node_index = cmp::max(a.index(), b.index());
-        if min_node_index >= self.node_capacity {
-            self.extend_capacity_to(min_node_index);
-        }
+    pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E> {
+        self.extend_capacity_for_edge(a, b);
 
         let p = self.to_edge_position(a, b);
         let old_weight = mem::replace(&mut self.node_adjacencies[p], Null::new(weight));
@@ -360,7 +367,7 @@
     ///
     /// **Note:** `MatrixGraph` does not allow 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, b: NodeIndex, weight: E) {
+    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) {
         let old_edge_id = self.update_edge(a, b, weight);
         assert!(old_edge_id.is_none());
     }
@@ -369,7 +376,7 @@
     ///
     /// **Panics** if any of the nodes don't exist.
     /// **Panics** if no edge exists between `a` and `b`.
-    pub fn remove_edge(&mut self, a: NodeIndex, b: NodeIndex) -> E {
+    pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E {
         let p = self.to_edge_position(a, b);
         let old_weight = mem::replace(&mut self.node_adjacencies[p], Default::default()).into().unwrap();
         let old_weight: Option<_> = old_weight.into();
@@ -380,7 +387,7 @@
     /// Return true if there is an edge between `a` and `b`.
     ///
     /// **Panics** if any of the nodes don't exist.
-    pub fn has_edge(&self, a: NodeIndex, b: NodeIndex) -> bool {
+    pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
         let p = self.to_edge_position(a, b);
         !self.node_adjacencies[p].is_null()
     }
@@ -390,7 +397,7 @@
     /// Also available with indexing syntax: `&graph[a]`.
     ///
     /// **Panics** if the node doesn't exist.
-    pub fn node_weight(&self, a: NodeIndex) -> &N {
+    pub fn node_weight(&self, a: NodeIndex<Ix>) -> &N {
         &self.nodes[a.index()]
     }
 
@@ -399,7 +406,7 @@
     /// Also available with indexing syntax: `&mut graph[a]`.
     ///
     /// **Panics** if the node doesn't exist.
-    pub fn node_weight_mut(&mut self, a: NodeIndex) -> &mut N {
+    pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N {
         &mut self.nodes[a.index()]
     }
 
@@ -408,7 +415,7 @@
     /// Also available with indexing syntax: `&graph[e]`.
     ///
     /// **Panics** if no edge exists between `a` and `b`.
-    pub fn edge_weight(&self, a: NodeIndex, b: NodeIndex) -> &E {
+    pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E {
         let p = self.to_edge_position(a, b);
         self.node_adjacencies[p].as_ref().unwrap()
     }
@@ -418,7 +425,7 @@
     /// Also available with indexing syntax: `&mut graph[e]`.
     ///
     /// **Panics** if no edge exists between `a` and `b`.
-    pub fn edge_weight_mut(&mut self, a: NodeIndex, b: NodeIndex) -> &mut E {
+    pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E {
         let p = self.to_edge_position(a, b);
         self.node_adjacencies[p].as_mut().unwrap()
     }
@@ -430,7 +437,7 @@
     ///
     /// Produces an empty iterator if the node doesn't exist.<br>
     /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
-    pub fn neighbors(&self, a: NodeIndex) -> Neighbors<Ty, Null> {
+    pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix> {
         Neighbors(Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity))
     }
 
@@ -441,7 +448,7 @@
     ///
     /// Produces an empty iterator if the node doesn't exist.<br>
     /// Iterator element type is [`Edges<E, Ix>`](../graph/struct.Edges.html).
-    pub fn edges(&self, a: NodeIndex) -> Edges<Ty, Null> {
+    pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix> {
         Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity)
     }
 
@@ -465,7 +472,7 @@
     pub fn from_edges<I>(iterable: I) -> Self
         where I: IntoIterator,
               I::Item: IntoWeightedEdge<E>,
-              <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex>,
+              <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
               N: Default,
     {
         let mut g = Self::default();
@@ -483,7 +490,7 @@
     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>,
+              <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
               N: Default,
     {
         for elt in iterable {
@@ -498,7 +505,7 @@
     }
 }
 
-impl<N, E, Null: Nullable<Wrapped=E>> MatrixGraph<N, E, Directed, Null> {
+impl<N, E, Null: Nullable<Wrapped=E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix> {
     /// 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)*.
@@ -509,7 +516,7 @@
     ///
     /// Produces an empty iterator if the node doesn't exist.<br>
     /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
-    pub fn neighbors_directed(&self, a: NodeIndex, d: Direction) -> Neighbors<Directed, Null> {
+    pub fn neighbors_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Neighbors<Directed, Null, Ix> {
         if d == Outgoing {
             self.neighbors(a)
         } else {
@@ -525,7 +532,7 @@
     ///
     /// Produces an empty iterator if the node `a` doesn't exist.<br>
     /// Iterator element type is [`EdgeReference<E, Ix>`](../graph/struct.EdgeReference.html).
-    pub fn edges_directed(&self, a: NodeIndex, d: Direction) -> Edges<Directed, Null> {
+    pub fn edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix> {
         if d == Outgoing {
             self.edges(a)
         } else {
@@ -540,13 +547,22 @@
 ///
 /// [1]: ../visit/trait.IntoNodeIdentifiers.html#tymethod.node_identifiers
 /// [2]: struct.MatrixGraph.html
-pub struct NodeIdentifiers<'a>(IdIterator<'a>);
+pub struct NodeIdentifiers<'a, Ix> {
+    iter: IdIterator<'a>,
+    ix: PhantomData<Ix>,
+}
 
-impl<'a> Iterator for NodeIdentifiers<'a> {
-    type Item = NodeIndex;
+impl<'a, Ix: IndexType> NodeIdentifiers<'a, Ix> {
+    fn new(iter: IdIterator<'a>) -> Self {
+        Self { iter, ix: PhantomData }
+    }
+}
+
+impl<'a, Ix: IndexType> Iterator for NodeIdentifiers<'a, Ix> {
+    type Item = NodeIndex<Ix>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.0.next().map(node_index)
+        self.iter.next().map(NodeIndex::new)
     }
 }
 
@@ -556,26 +572,27 @@
 ///
 /// [1]: ../visit/trait.IntoNodeReferences.html#tymethod.node_references
 /// [2]: struct.MatrixGraph.html
-pub struct NodeReferences<'a, N: 'a> {
+pub struct NodeReferences<'a, N: 'a, Ix> {
     nodes: &'a IdStorage<N>,
     iter: IdIterator<'a>,
+    ix: PhantomData<Ix>,
 }
 
-impl<'a, N: 'a> NodeReferences<'a, N> {
+impl<'a, N: 'a, Ix> NodeReferences<'a, N, Ix> {
     fn new(nodes: &'a IdStorage<N>) -> Self {
         NodeReferences {
             nodes: nodes,
             iter: nodes.iter_ids(),
+            ix: PhantomData,
         }
     }
 }
 
-impl<'a, N: 'a> Iterator for NodeReferences<'a, N> {
-    type Item = (NodeIndex, &'a N);
+impl<'a, N: 'a, Ix: IndexType> Iterator for NodeReferences<'a, N, Ix> {
+    type Item = (NodeIndex<Ix>, &'a N);
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.iter.next()
-            .map(|i| (node_index(i), &self.nodes[i]))
+        self.iter.next().map(|i| (NodeIndex::new(i), &self.nodes[i]))
     }
 }
 
@@ -585,27 +602,29 @@
 ///
 /// [1]: ../visit/trait.IntoEdgeReferences.html#tymethod.edge_references
 /// [2]: struct.MatrixGraph.html
-pub struct EdgeReferences<'a, Ty: EdgeType, Null: 'a + Nullable> {
+pub struct EdgeReferences<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
     row: usize,
     column: usize,
     node_adjacencies: &'a [Null],
     node_capacity: usize,
     ty: PhantomData<Ty>,
+    ix: PhantomData<Ix>,
 }
 
-impl<'a, Ty: EdgeType, Null: 'a + Nullable> EdgeReferences<'a, Ty, Null> {
+impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> EdgeReferences<'a, Ty, Null, Ix> {
     fn new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
         EdgeReferences {
             row: 0, column: 0,
             node_adjacencies: node_adjacencies,
             node_capacity: node_capacity,
             ty: PhantomData,
+            ix: PhantomData,
         }
     }
 }
 
-impl<'a, Ty: EdgeType, Null: Nullable> Iterator for EdgeReferences<'a, Ty, Null> {
-    type Item = (NodeIndex, NodeIndex, &'a Null::Wrapped);
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for EdgeReferences<'a, Ty, Null, Ix> {
+    type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
 
     fn next(&mut self) -> Option<Self::Item> {
         loop {
@@ -627,7 +646,7 @@
 
             let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
             if let Some(e) = self.node_adjacencies[p].as_ref() {
-                return Some((node_index(row), node_index(column), e));
+                return Some((NodeIndex::new(row), NodeIndex::new(column), e));
             }
         }
     }
@@ -641,10 +660,10 @@
 ///
 /// [1]: struct.MatrixGraph.html#method.neighbors
 /// [2]: struct.MatrixGraph.html#method.neighbors_directed
-pub struct Neighbors<'a, Ty: EdgeType, Null: 'a + Nullable>(Edges<'a, Ty, Null>);
+pub struct Neighbors<'a, Ty: EdgeType, Null: 'a + Nullable, Ix>(Edges<'a, Ty, Null, Ix>);
 
-impl<'a, Ty: EdgeType, Null: Nullable> Iterator for Neighbors<'a, Ty, Null> {
-    type Item = NodeIndex;
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> {
+    type Item = NodeIndex<Ix>;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.0.next().map(|(_, b, _)| b)
@@ -662,16 +681,17 @@
 ///
 /// [1]: struct.MatrixGraph.html#method.edges
 /// [2]: struct.MatrixGraph.html#method.edges_directed
-pub struct Edges<'a, Ty: EdgeType, Null: 'a + Nullable> {
+pub struct Edges<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
     iter_direction: NeighborIterDirection,
     node_adjacencies: &'a [Null],
     node_capacity: usize,
     row: usize,
     column: usize,
     ty: PhantomData<Ty>,
+    ix: PhantomData<Ix>,
 }
 
-impl<'a, Ty: EdgeType, Null: 'a + Nullable> Edges<'a, Ty, Null> {
+impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> Edges<'a, Ty, Null, Ix> {
     fn on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
         Edges {
             iter_direction: NeighborIterDirection::Columns,
@@ -680,6 +700,7 @@
             row: row,
             column: 0,
             ty: PhantomData,
+            ix: PhantomData,
         }
     }
 
@@ -691,12 +712,13 @@
             row: 0,
             column: column,
             ty: PhantomData,
+            ix: PhantomData,
         }
     }
 }
 
-impl<'a, Ty: EdgeType, Null: Nullable> Iterator for Edges<'a, Ty, Null> {
-    type Item = (NodeIndex, NodeIndex, &'a Null::Wrapped);
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> {
+    type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
 
     fn next(&mut self) -> Option<Self::Item> {
         use self::NeighborIterDirection::*;
@@ -719,7 +741,7 @@
                     Columns => (row, column),
                 };
 
-                return Some((node_index(a), node_index(b), e));
+                return Some((NodeIndex::new(a), NodeIndex::new(b), e));
             }
         }
     }
@@ -910,7 +932,7 @@
 }
 
 /// Create a new empty `MatrixGraph`.
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Default for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Default for MatrixGraph<N, E, Ty, Null, Ix> {
     fn default() -> Self {
         Self::with_nodes(0)
     }
@@ -939,10 +961,10 @@
 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
 ///
 /// **Panics** if the node doesn't exist.
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Index<NodeIndex> for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Index<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix> {
     type Output = N;
 
-    fn index(&self, ax: NodeIndex) -> &N {
+    fn index(&self, ax: NodeIndex<Ix>) -> &N {
         self.node_weight(ax)
     }
 }
@@ -950,13 +972,13 @@
 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
 ///
 /// **Panics** if the node doesn't exist.
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> IndexMut<NodeIndex> for MatrixGraph<N, E, Ty, Null> {
-    fn index_mut(&mut self, ax: NodeIndex) -> &mut N {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IndexMut<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix> {
+    fn index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N {
         self.node_weight_mut(ax)
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> NodeCount for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix> {
     fn node_count(&self) -> usize {
         MatrixGraph::node_count(self)
     }
@@ -967,10 +989,10 @@
 /// Also available with indexing syntax: `&graph[e]`.
 ///
 /// **Panics** if no edge exists between `a` and `b`.
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Index<(NodeIndex, NodeIndex)> for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix> {
     type Output = E;
 
-    fn index(&self, (ax, bx): (NodeIndex, NodeIndex)) -> &E {
+    fn index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E {
         self.edge_weight(ax, bx)
     }
 }
@@ -980,24 +1002,24 @@
 /// Also available with indexing syntax: `&mut graph[e]`.
 ///
 /// **Panics** if no edge exists between `a` and `b`.
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> IndexMut<(NodeIndex, NodeIndex)> for MatrixGraph<N, E, Ty, Null> {
-    fn index_mut(&mut self, (ax, bx): (NodeIndex, NodeIndex)) -> &mut E {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix> {
+    fn index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E {
         self.edge_weight_mut(ax, bx)
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix> {
     type AdjMatrix = ();
 
     fn adjacency_matrix(&self) -> Self::AdjMatrix {
     }
 
-    fn is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex, b: NodeIndex) -> bool {
+    fn is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
         MatrixGraph::has_edge(self, a, b)
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Visitable for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Visitable for MatrixGraph<N, E, Ty, Null, Ix> {
     type Map = FixedBitSet;
 
     fn visit_map(&self) -> FixedBitSet {
@@ -1010,83 +1032,85 @@
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> GraphBase for MatrixGraph<N, E, Ty, Null> {
-    type NodeId = NodeIndex;
-    type EdgeId = (NodeIndex, NodeIndex);
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix> {
+    type NodeId = NodeIndex<Ix>;
+    type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>);
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> GraphProp for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix> {
     type EdgeType = Ty;
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Data for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Data for MatrixGraph<N, E, Ty, Null, Ix> {
     type NodeWeight = N;
     type EdgeWeight = E;
 }
 
-impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null> {
-    type NodeIdentifiers = NodeIdentifiers<'a>;
+impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+    type NodeIdentifiers = NodeIdentifiers<'a, Ix>;
 
     fn node_identifiers(self) -> Self::NodeIdentifiers {
-        NodeIdentifiers(self.nodes.iter_ids())
+        NodeIdentifiers::new(self.nodes.iter_ids())
     }
 }
 
-impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null> {
-    type Neighbors = Neighbors<'a, Ty, Null>;
+impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+    type Neighbors = Neighbors<'a, Ty, Null, Ix>;
 
-    fn neighbors(self, a: NodeIndex) -> Self::Neighbors {
+    fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
         MatrixGraph::neighbors(self, a)
     }
 }
 
-impl<'a, N, E: 'a, Null: Nullable<Wrapped=E>> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null> {
-    type NeighborsDirected = Neighbors<'a, Directed, Null>;
+impl<'a, N, E: 'a, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix> {
+    type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>;
 
-    fn neighbors_directed(self, a: NodeIndex, d: Direction) -> Self::NeighborsDirected {
+    fn neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected {
         MatrixGraph::neighbors_directed(self, a, d)
     }
 }
 
-impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null> {
-    type NodeRef = (NodeIndex, &'a N);
-    type NodeReferences = NodeReferences<'a, N>;
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+    type NodeRef = (NodeIndex<Ix>, &'a N);
+    type NodeReferences = NodeReferences<'a, N, Ix>;
     fn node_references(self) -> Self::NodeReferences {
         NodeReferences::new(&self.nodes)
     }
 }
 
-impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null> {
-    type EdgeRef = (NodeIndex, NodeIndex, &'a E);
-    type EdgeReferences = EdgeReferences<'a, Ty, Null>;
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+    type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E);
+    type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>;
     fn edge_references(self) -> Self::EdgeReferences {
         EdgeReferences::new(&self.node_adjacencies, self.node_capacity)
     }
 }
 
-impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> IntoEdges for &'a MatrixGraph<N, E, Ty, Null> {
-    type Edges = Edges<'a, Ty, Null>;
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoEdges for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+    type Edges = Edges<'a, Ty, Null, Ix>;
     fn edges(self, a: Self::NodeId) -> Self::Edges {
         MatrixGraph::edges(self, a)
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> NodeIndexable for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeIndexable for MatrixGraph<N, E, Ty, Null, Ix> {
     fn node_bound(&self) -> usize {
         self.node_count()
     }
-    fn to_index(&self, ix: NodeIndex) -> usize {
+
+    fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
         ix.index()
     }
+
     fn from_index(&self, ix: usize) -> Self::NodeId {
-        node_index(ix)
+        NodeIndex::new(ix)
     }
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> NodeCompactIndexable for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeCompactIndexable for MatrixGraph<N, E, Ty, Null, Ix> {
 }
 
-impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>> Build for MatrixGraph<N, E, Ty, Null> {
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Build for MatrixGraph<N, E, Ty, Null, Ix> {
     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
         self.add_node(weight)
     }
@@ -1126,7 +1150,7 @@
     }
 
     #[test]
-    fn test_with_capacity() {
+    fn test_with_nodes() {
         let g = MatrixGraph::<i32, i32>::with_nodes(10);
         assert_eq!(g.node_count(), 0);
         assert_eq!(g.edge_count(), 0);