diff --git a/Cargo.toml b/Cargo.toml
index 47d07f5..a733dfa 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -27,29 +27,31 @@
 
 [dependencies]
 fixedbitset = { version = "0.1.4" }
-quickcheck = { optional = true, version = "0.4", default-features = false }
-ordermap = { version = "0.3.0", optional = true }
+quickcheck = { optional = true, version = "0.7.1", default-features = false }
+indexmap = { version = "1.0.2", optional = true }
 serde = { version = "1.0", optional = true }
 serde_derive = { version = "1.0", optional = true }
+rand = { version = "0.5.5", optional = true }
 
 [dev-dependencies]
-rand = "0.3"
+rand = "0.5.5"
 odds = { version = "0.2.19" }
 defmac = "0.1"
 itertools = { version = "0.7.0", default-features = false }
 
 [features]
 default = ["graphmap", "stable_graph"]
-graphmap = ["ordermap"]
+graphmap = ["indexmap"]
 serde-1 = ["serde", "serde_derive"]
 stable_graph = []
+check = ["quickcheck", "rand"]
 
 # For unstable features
 generate = []
 unstable = ["generate"]
 
 # feature flags for testing use only
-all = ["unstable", "quickcheck", "stable_graph", "graphmap"]
+all = ["unstable", "check", "stable_graph", "graphmap"]
 
 [workspace]
 members = ["serialization-tests"]
diff --git a/README.rst b/README.rst
index a428db6..383a709 100644
--- a/README.rst
+++ b/README.rst
@@ -198,7 +198,7 @@
   - ``GraphMap`` can now have directed edges. ``GraphMap::new`` is now generic
     in the edge type. ``DiGraphMap`` and ``UnGraphMap`` are new type aliases.
   - Add type aliases ``DiGraph, UnGraph, StableDiGraph, StableUnGraph``
-  - ``GraphMap`` is based on the ordermap crate. Deterministic iteration
+  - ``GraphMap`` is based on the indexmap crate. Deterministic iteration
     order, faster iteration, no side tables needed to convert to ``Graph``.
   - Improved docs for a lot of types and functions.
   - Add graph visitor ``DfsPostOrder``
@@ -308,7 +308,7 @@
   - Add Graph::capacity(), GraphMap::capacity()
   - Fix bug in Graph::reverse()
   - Graph and GraphMap have `quickcheck::Arbitrary` implementations,
-    if optional feature `quickcheck` is enabled.
+    if optional feature `check` is enabled.
 
 - 0.1.16
 
diff --git a/serialization-tests/Cargo.toml b/serialization-tests/Cargo.toml
index 8837c0d..54491db 100644
--- a/serialization-tests/Cargo.toml
+++ b/serialization-tests/Cargo.toml
@@ -14,11 +14,11 @@
 
 
 [dependencies]
-petgraph = { path = "..", features = ["serde-1", "quickcheck"] }
+petgraph = { path = "..", features = ["serde-1", "check"] }
 itertools = { version = "0.6.2" }
 
 [dev-dependencies]
 serde_json = "1.0"
-quickcheck = { version = "0.4", default-features = false }
-bincode = { version = "0.9" }
+quickcheck = { version = "0.7.1", default-features = false }
+bincode = "1.0.1"
 defmac = "0.1"
diff --git a/serialization-tests/tests/serialization.rs b/serialization-tests/tests/serialization.rs
index 069304f..a82ff88 100644
--- a/serialization-tests/tests/serialization.rs
+++ b/serialization-tests/tests/serialization.rs
@@ -352,7 +352,7 @@
 
 
 // bincode macros
-defmac!(encode ref g => bincode::serialize(g, bincode::Infinite).unwrap());
+defmac!(encode ref g => bincode::serialize(g).unwrap());
 defmac!(decode ref data => bincode::deserialize(data).unwrap());
 defmac!(recode ref g => decode!(encode!(g)));
 
diff --git a/src/graphmap.rs b/src/graphmap.rs
index 945abe0..6b6cab4 100644
--- a/src/graphmap.rs
+++ b/src/graphmap.rs
@@ -14,11 +14,11 @@
 use std::ops::{Index, IndexMut, Deref};
 use std::iter::FromIterator;
 use std::marker::PhantomData;
-use ordermap::OrderMap;
-use ordermap::{
-    Iter as OrderMapIter, IterMut as OrderMapIterMut
+use indexmap::IndexMap;
+use indexmap::map::{
+    Iter as IndexMapIter, IterMut as IndexMapIterMut
 };
-use ordermap::Keys;
+use indexmap::map::Keys;
 
 use {
     EdgeType,
@@ -72,8 +72,8 @@
 /// Depends on crate feature `graphmap` (default).
 #[derive(Clone)]
 pub struct GraphMap<N, E, Ty> {
-    nodes: OrderMap<N, Vec<(N, CompactDirection)>>,
-    edges: OrderMap<(N, N), E>,
+    nodes: IndexMap<N, Vec<(N, CompactDirection)>>,
+    edges: IndexMap<(N, N), E>,
     ty: PhantomData<Ty>,
 }
 
@@ -121,8 +121,8 @@
     /// Create a new `GraphMap` with estimated capacity.
     pub fn with_capacity(nodes: usize, edges: usize) -> Self {
         GraphMap {
-            nodes: OrderMap::with_capacity(nodes),
-            edges: OrderMap::with_capacity(edges),
+            nodes: IndexMap::with_capacity(nodes),
+            edges: IndexMap::with_capacity(edges),
             ty: PhantomData,
         }
     }
@@ -559,7 +559,7 @@
           Ty: EdgeType
 {
     from: N,
-    edges: &'a OrderMap<(N, N), E>,
+    edges: &'a IndexMap<(N, N), E>,
     iter: Neighbors<'a, N, Ty>,
 }
 
@@ -596,7 +596,7 @@
 }
 
 pub struct AllEdges<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
-    inner: OrderMapIter<'a, (N, N), E>,
+    inner: IndexMapIter<'a, (N, N), E>,
     ty: PhantomData<Ty>,
 }
 
@@ -640,7 +640,7 @@
 }
 
 pub struct AllEdgesMut<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
-    inner: OrderMapIterMut<'a, (N, N), E>,
+    inner: IndexMapIterMut<'a, (N, N), E>,
     ty: PhantomData<Ty>,
 }
 
@@ -815,7 +815,7 @@
 }
 
 pub struct NodeIdentifiers<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
-    iter: OrderMapIter<'a, N, Vec<(N, CompactDirection)>>,
+    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
     ty: PhantomData<Ty>,
     edge_ty: PhantomData<E>,
 }
@@ -847,7 +847,7 @@
 }
 
 pub struct NodeReferences<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
-    iter: OrderMapIter<'a, N, Vec<(N, CompactDirection)>>,
+    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
     ty: PhantomData<Ty>,
     edge_ty: PhantomData<E>,
 }
diff --git a/src/lib.rs b/src/lib.rs
index 6523894..7554774 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -19,7 +19,7 @@
 
 extern crate fixedbitset;
 #[cfg(feature = "graphmap")]
-extern crate ordermap;
+extern crate indexmap;
 
 #[cfg(feature = "serde-1")]
 extern crate serde;
diff --git a/src/quickcheck.rs b/src/quickcheck.rs
index 18d40c7..0b0ed35 100644
--- a/src/quickcheck.rs
+++ b/src/quickcheck.rs
@@ -1,6 +1,7 @@
 extern crate quickcheck;
-
+extern crate rand;
 use self::quickcheck::{Gen, Arbitrary};
+use self::rand::Rng;
 
 use {
     Graph,
diff --git a/tests/unionfind.rs b/tests/unionfind.rs
index f5e2bcf..ba3bdc5 100644
--- a/tests/unionfind.rs
+++ b/tests/unionfind.rs
@@ -1,7 +1,7 @@
 extern crate rand;
 extern crate petgraph;
 
-use rand::{Rng, thread_rng, ChaChaRng};
+use rand::{Rng, thread_rng, ChaChaRng, SeedableRng};
 use std::collections::HashSet;
 use petgraph::unionfind::UnionFind;
 
@@ -36,7 +36,7 @@
 #[test]
 fn uf_rand() {
     let n = 1 << 14;
-    let mut rng: ChaChaRng = thread_rng().gen();
+    let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
     let mut u = UnionFind::new(n);
     for _ in 0..100 {
         let a = rng.gen_range(0, n);
@@ -50,7 +50,7 @@
 #[test]
 fn uf_u8() {
     let n = 256;
-    let mut rng: ChaChaRng = thread_rng().gen();
+    let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
     let mut u = UnionFind::<u8>::new(n);
     for _ in 0..(n * 8) {
         let a = rng.gen();