diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
new file mode 100644
index 0000000..d5b18fe
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
@@ -0,0 +1,46 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Base for all graph search tests.
+ */
+public abstract class AbstractGraphPathSearchTest extends GraphTest {
+
+    /**
+     * Creates a test-specific graph search to exercise.
+     *
+     * @return graph search
+     */
+    protected abstract AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch();
+
+    @Test(expected = IllegalArgumentException.class)
+    public void noSuchSourceArgument() {
+        graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
+                                                       of(new TestEdge(B, C, 1))),
+                             A, H, weight);
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void nullGraphArgument() {
+        graphSearch().search(null, A, H, weight);
+    }
+
+    @Test(expected = NullPointerException.class)
+    public void nullSourceArgument() {
+        graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
+                                                       of(new TestEdge(B, C, 1))),
+                             null, H, weight);
+    }
+
+    @Test
+    public void samenessThreshold() {
+        AbstractGraphPathSearch<TestVertex, TestEdge> search = graphSearch();
+        search.setSamenessThreshold(0.3);
+        assertEquals("incorrect threshold", 0.3, search.samenessThreshold(), 0.01);
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
deleted file mode 100644
index 00ba3da..0000000
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
+++ /dev/null
@@ -1,37 +0,0 @@
-package org.onlab.graph;
-
-import com.google.common.collect.ImmutableSet;
-import org.junit.Test;
-
-/**
- * Base for all graph search tests.
- */
-public abstract class AbstractGraphSearchTest extends GraphTest {
-
-    /**
-     * Creates a graph search to be tested.
-     *
-     * @return graph search
-     */
-    protected abstract GraphPathSearch<TestVertex, TestEdge> graphSearch();
-
-    @Test(expected = IllegalArgumentException.class)
-    public void badSource() {
-        graphSearch().search(new AdjacencyListsGraph<>(ImmutableSet.of(B, C),
-                                                       ImmutableSet.of(new TestEdge(B, C, 1))),
-                             A, H, weight);
-    }
-
-    @Test(expected = NullPointerException.class)
-    public void nullSource() {
-        graphSearch().search(new AdjacencyListsGraph<>(ImmutableSet.of(B, C),
-                                                       ImmutableSet.of(new TestEdge(B, C, 1))),
-                             null, H, weight);
-    }
-
-    @Test(expected = NullPointerException.class)
-    public void nullGraph() {
-        graphSearch().search(null, A, H, weight);
-    }
-
-}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
index e61583d..9105891 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
@@ -22,22 +22,9 @@
     private static final TestVertex G = new TestVertex("G");
 
     private final Set<TestEdge> edges =
-            ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 1),
-                            new TestEdge(B, C, 1), new TestEdge(C, D, 1),
-                            new TestEdge(D, A, 1));
-
-    @Test
-    public void basics() {
-        Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F);
-        AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges);
-        assertEquals("incorrect vertex count", 6, graph.getVertexes().size());
-        assertEquals("incorrect edge count", 5, graph.getEdges().size());
-
-        assertEquals("incorrect egress edge count", 2, graph.getEdgesFrom(A).size());
-        assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(A).size());
-        assertEquals("incorrect ingress edge count", 2, graph.getEdgesTo(C).size());
-        assertEquals("incorrect egress edge count", 1, graph.getEdgesFrom(C).size());
-    }
+            ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(B, C, 1),
+                            new TestEdge(C, D, 1), new TestEdge(D, A, 1),
+                            new TestEdge(B, D, 1));
 
     @Test
     public void equality() {
@@ -53,4 +40,18 @@
                 .addEqualityGroup(different)
                 .testEquals();
     }
+
+    @Test
+    public void basics() {
+        Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F);
+        AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges);
+        assertEquals("incorrect vertex count", 6, graph.getVertexes().size());
+        assertEquals("incorrect edge count", 5, graph.getEdges().size());
+
+        assertEquals("incorrect egress edge count", 1, graph.getEdgesFrom(A).size());
+        assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(A).size());
+        assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(C).size());
+        assertEquals("incorrect egress edge count", 2, graph.getEdgesFrom(B).size());
+        assertEquals("incorrect ingress edge count", 2, graph.getEdgesTo(D).size());
+    }
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
index ae45750..f9c752d 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -7,27 +7,28 @@
 import static org.junit.Assert.assertEquals;
 
 /**
- * Test of the BFS algorithm.
+ * Test of the BFS and similar path search algorithms.
  */
-public abstract class BreadthFirstSearchTest extends AbstractGraphSearchTest {
+public class BreadthFirstSearchTest extends AbstractGraphPathSearchTest {
 
     @Override
-    protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
-        return null; // new BreadthFirstSearch();
+    protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
+        return new BreadthFirstSearch<>();
     }
 
     @Test
-    public void basics() {
-        runBasics(3, 8.0, 7);
+    public void defaultGraphTest() {
+        executeDefaultTest(7, 3, 8.0);
     }
 
     @Test
-    public void defaultWeight() {
+    public void defaultHopCountWeight() {
         weight = null;
-        runBasics(3, 3.0, 7);
+        executeDefaultTest(7, 3, 3.0);
     }
 
-    protected void runBasics(int expectedLength, double expectedCost, int expectedPaths) {
+    // Executes the default test
+    protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) {
         g = new AdjacencyListsGraph<>(vertices(), edges());
 
         GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
@@ -37,12 +38,29 @@
         Path p = paths.iterator().next();
         assertEquals("incorrect src", A, p.src());
         assertEquals("incorrect dst", H, p.dst());
-        assertEquals("incorrect path length", expectedLength, p.edges().size());
-        assertEquals("incorrect path cost", expectedCost, p.cost(), 0.1);
+        assertEquals("incorrect path length", pathLength, p.edges().size());
+        assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
 
         paths = search.search(g, A, null, weight).paths();
         printPaths(paths);
-        assertEquals("incorrect paths count", expectedPaths, paths.size());
+        assertEquals("incorrect paths count", pathCount, paths.size());
+    }
+
+    // Executes the search and validates its results.
+    protected void executeSearch(GraphPathSearch<TestVertex, TestEdge> search,
+                                 Graph<TestVertex, TestEdge> graph,
+                                 TestVertex src, TestVertex dst,
+                                 EdgeWeight<TestVertex, TestEdge> weight,
+                                 int pathCount, double pathCost) {
+        GraphPathSearch.Result<TestVertex, TestEdge> result =
+                search.search(graph, src, dst, weight);
+        Set<Path<TestVertex, TestEdge>> paths = result.paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", pathCount, paths.size());
+        if (pathCount > 0) {
+            Path<TestVertex, TestEdge> path = paths.iterator().next();
+            assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+        }
     }
 
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
new file mode 100644
index 0000000..4245e9c
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
@@ -0,0 +1,99 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.Iterator;
+import java.util.List;
+
+import static com.google.common.collect.ImmutableList.of;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+/**
+ * Test of the default mutable path.
+ */
+public class DefaultMutablePathTest extends DefaultPathTest {
+
+    @Test
+    public void equality() {
+        DefaultPath<TestVertex, TestEdge> p1 =
+                new DefaultPath<>(of(new TestEdge(A, B, 1),
+                                     new TestEdge(B, C, 1)), 2.0);
+        DefaultPath<TestVertex, TestEdge> p2 =
+                new DefaultPath<>(of(new TestEdge(A, B, 1),
+                                     new TestEdge(B, D, 1)), 2.0);
+        new EqualsTester().addEqualityGroup(new DefaultMutablePath<>(p1),
+                                            new DefaultMutablePath<>(p1))
+                .addEqualityGroup(new DefaultMutablePath<>(p2))
+                .testEquals();
+    }
+
+    @Test
+    public void empty() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        assertNull("src should be null", p.src());
+        assertNull("dst should be null", p.dst());
+        assertEquals("incorrect edge count", 0, p.edges().size());
+        assertEquals("incorrect path cost", 0.0, p.cost(), 0.1);
+    }
+
+    @Test
+    public void pathCost() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        p.setCost(4);
+        assertEquals("incorrect path cost", 4.0, p.cost(), 0.1);
+    }
+
+    private void validatePath(Path<TestVertex, TestEdge> p,
+                              TestVertex src, TestVertex dst, int length) {
+        validatePath(p, src, dst, length, 0.0);
+    }
+
+    @Test
+    public void insertEdge() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        p.insertEdge(new TestEdge(B, C, 1));
+        p.insertEdge(new TestEdge(A, B, 1));
+        validatePath(p, A, C, 2);
+    }
+
+    @Test
+    public void appendEdge() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        p.appendEdge(new TestEdge(A, B, 1));
+        p.appendEdge(new TestEdge(B, C, 1));
+        validatePath(p, A, C, 2);
+    }
+
+    @Test
+    public void removeEdge() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        p.appendEdge(new TestEdge(A, B, 1));
+        p.appendEdge(new TestEdge(B, C, 1));
+        p.appendEdge(new TestEdge(C, C, 2));
+        p.appendEdge(new TestEdge(C, D, 1));
+        validatePath(p, A, D, 4);
+
+        p.removeEdge(new TestEdge(A, B, 1));
+        validatePath(p, B, D, 3);
+
+        p.removeEdge(new TestEdge(C, C, 2));
+        validatePath(p, B, D, 2);
+
+        p.removeEdge(new TestEdge(C, D, 1));
+        validatePath(p, B, C, 1);
+    }
+
+    @Test
+    public void toImmutable() {
+        MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
+        p.appendEdge(new TestEdge(A, B, 1));
+        p.appendEdge(new TestEdge(B, C, 1));
+        validatePath(p, A, C, 2);
+
+        assertEquals("immutables should equal", p.toImmutable(), p.toImmutable());
+        validatePath(p.toImmutable(), A, C, 2);
+    }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
new file mode 100644
index 0000000..dbdf57f
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
@@ -0,0 +1,44 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.List;
+
+import static com.google.common.collect.ImmutableList.of;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+/**
+ * Test of the default path.
+ */
+public class DefaultPathTest extends GraphTest {
+
+    @Test
+    public void equality() {
+        List<TestEdge> edges = of(new TestEdge(A, B, 1), new TestEdge(B, C, 1));
+        new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, 2.0),
+                                            new DefaultPath<>(edges, 2.0))
+                .addEqualityGroup(new DefaultPath<>(edges, 3.0))
+                .testEquals();
+    }
+
+    @Test
+    public void basics() {
+        Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B, 1),
+                                                            new TestEdge(B, C, 1)), 2.0);
+        validatePath(p, A, C, 2, 2.0);
+    }
+
+    // Validates the path against expected attributes
+    protected void validatePath(Path<TestVertex, TestEdge> p,
+                              TestVertex src, TestVertex dst,
+                              int length, double cost) {
+        assertEquals("incorrect path length", length, p.edges().size());
+        assertEquals("incorrect source", src, p.src());
+        assertEquals("incorrect destination", dst, p.dst());
+        assertEquals("incorrect path cost", cost, p.cost(), 0.1);
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index 5ee4caa..1731440 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -1,10 +1,10 @@
 package org.onlab.graph;
 
-import com.google.common.collect.ImmutableSet;
 import org.junit.Test;
 
 import java.util.Set;
 
+import static com.google.common.collect.ImmutableSet.of;
 import static org.junit.Assert.assertEquals;
 
 /**
@@ -13,30 +13,30 @@
 public class DijkstraGraphSearchTest extends BreadthFirstSearchTest {
 
     @Override
-    protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
+    protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
         return new DijkstraGraphSearch<>();
     }
 
     @Test
     @Override
-    public void basics() {
-        runBasics(5, 5.0, 7);
+    public void defaultGraphTest() {
+        executeDefaultTest(7, 5, 5.0);
     }
 
     @Test
-    public void defaultWeight() {
+    @Override
+    public void defaultHopCountWeight() {
         weight = null;
-        runBasics(3, 3.0, 10);
+        executeDefaultTest(10, 3, 3.0);
     }
 
     @Test
     public void noPath() {
-        g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D),
-                                      ImmutableSet.of(new TestEdge(A, B, 1),
-                                                      new TestEdge(B, A, 1),
-                                                      new TestEdge(C, D, 1),
-                                                      new TestEdge(D, C, 1)));
-
+        g = new AdjacencyListsGraph<>(of(A, B, C, D),
+                                      of(new TestEdge(A, B, 1),
+                                         new TestEdge(B, A, 1),
+                                         new TestEdge(C, D, 1),
+                                         new TestEdge(D, C, 1)));
         GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
         Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, B, weight).paths();
         printPaths(paths);
@@ -54,57 +54,41 @@
     }
 
     @Test
-    public void multiPath1() {
-        g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D),
-                                      ImmutableSet.of(new TestEdge(A, B, 1),
-                                                      new TestEdge(A, C, 1),
-                                                      new TestEdge(B, D, 1),
-                                                      new TestEdge(C, D, 1)));
-
-        GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, D, weight).paths();
-        printPaths(paths);
-        assertEquals("incorrect paths count", 2, paths.size());
-        assertEquals("incorrect path cost", 2.0, paths.iterator().next().cost(), 0.1);
+    public void simpleMultiplePath() {
+        g = new AdjacencyListsGraph<>(of(A, B, C, D),
+                                      of(new TestEdge(A, B, 1),
+                                         new TestEdge(A, C, 1),
+                                         new TestEdge(B, D, 1),
+                                         new TestEdge(C, D, 1)));
+        executeSearch(graphSearch(), g, A, D, weight, 2, 2.0);
     }
 
     @Test
-    public void multiPath2() {
-        g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D, E, F, G),
-                                      ImmutableSet.of(new TestEdge(A, B, 1),
-                                                      new TestEdge(A, C, 1),
-                                                      new TestEdge(B, D, 1),
-                                                      new TestEdge(C, D, 1),
-                                                      new TestEdge(D, E, 1),
-                                                      new TestEdge(D, F, 1),
-                                                      new TestEdge(E, G, 1),
-                                                      new TestEdge(F, G, 1),
-                                                      new TestEdge(A, G, 4)));
-
-        GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
-        GraphPathSearch.Result<TestVertex, TestEdge> gsr = gs.search(g, A, G, weight);
-        Set<Path<TestVertex, TestEdge>> paths = gsr.paths();
-        printPaths(paths);
-        assertEquals("incorrect paths count", 5, paths.size());
-        assertEquals("incorrect path cost", 4.0, paths.iterator().next().cost(), 0.1);
+    public void denseMultiplePath() {
+        g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
+                                      of(new TestEdge(A, B, 1),
+                                         new TestEdge(A, C, 1),
+                                         new TestEdge(B, D, 1),
+                                         new TestEdge(C, D, 1),
+                                         new TestEdge(D, E, 1),
+                                         new TestEdge(D, F, 1),
+                                         new TestEdge(E, G, 1),
+                                         new TestEdge(F, G, 1),
+                                         new TestEdge(A, G, 4)));
+        executeSearch(graphSearch(), g, A, G, weight, 5, 4.0);
     }
 
     @Test
-    public void multiPath3() {
-        g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D, E, F, G, H),
-                                      ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
-                                                      new TestEdge(B, D, 2), new TestEdge(B, C, 1),
-                                                      new TestEdge(B, E, 4), new TestEdge(C, E, 1),
-                                                      new TestEdge(D, H, 5), new TestEdge(D, E, 1),
-                                                      new TestEdge(E, F, 1), new TestEdge(F, D, 1),
-                                                      new TestEdge(F, G, 1), new TestEdge(F, H, 1),
-                                                      new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
-
-        GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, E, weight).paths();
-        printPaths(paths);
-        assertEquals("incorrect paths count", 3, paths.size());
-        assertEquals("incorrect path cost", 3.0, paths.iterator().next().cost(), 0.1);
+    public void dualEdgeMultiplePath() {
+        g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
+                                      of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
+                                         new TestEdge(B, D, 2), new TestEdge(B, C, 1),
+                                         new TestEdge(B, E, 4), new TestEdge(C, E, 1),
+                                         new TestEdge(D, H, 5), new TestEdge(D, E, 1),
+                                         new TestEdge(E, F, 1), new TestEdge(F, D, 1),
+                                         new TestEdge(F, G, 1), new TestEdge(F, H, 1),
+                                         new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
+        executeSearch(graphSearch(), g, A, E, weight, 3, 3.0);
     }
 
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
index bb91e03..fcfa51b 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -4,6 +4,8 @@
 
 import java.util.Set;
 
+import static com.google.common.collect.ImmutableSet.of;
+
 /**
  * Base class for various graph-related tests.
  */
@@ -35,16 +37,16 @@
     }
 
     protected Set<TestVertex> vertices() {
-        return ImmutableSet.of(A, B, C, D, E, F, G, H);
+        return of(A, B, C, D, E, F, G, H);
     }
 
     protected Set<TestEdge> edges() {
-        return ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
-                               new TestEdge(B, D, 2), new TestEdge(B, C, 1),
-                               new TestEdge(B, E, 4), new TestEdge(C, E, 1),
-                               new TestEdge(D, H, 5), new TestEdge(D, E, 1),
-                               new TestEdge(E, F, 1), new TestEdge(F, D, 1),
-                               new TestEdge(F, G, 1), new TestEdge(F, H, 1));
+        return of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
+                  new TestEdge(B, D, 2), new TestEdge(B, C, 1),
+                  new TestEdge(B, E, 4), new TestEdge(C, E, 1),
+                  new TestEdge(D, H, 5), new TestEdge(D, E, 1),
+                  new TestEdge(E, F, 1), new TestEdge(F, D, 1),
+                  new TestEdge(F, G, 1), new TestEdge(F, H, 1));
     }
 
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/HeapTest.java b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
index 0b1601d..85e44d8 100644
--- a/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
@@ -9,6 +9,7 @@
 import java.util.Comparator;
 import java.util.Iterator;
 
+import static com.google.common.collect.ImmutableList.of;
 import static org.junit.Assert.*;
 
 /**
@@ -17,25 +18,42 @@
 public class HeapTest {
 
     private ArrayList<Integer> data =
-            new ArrayList<>(ImmutableList.of(6, 4, 5, 9, 8, 3, 2, 1, 7, 0));
+            new ArrayList<>(of(6, 4, 5, 9, 8, 3, 2, 1, 7, 0));
 
-    private static final Comparator<Integer> ASCENDING = Ordering.natural().reverse();
-    private static final Comparator<Integer> DESCENDING = Ordering.natural();
+    private static final Comparator<Integer> MIN = Ordering.natural().reverse();
+    private static final Comparator<Integer> MAX = Ordering.natural();
 
     @Test
     public void equality() {
         new EqualsTester()
-                .addEqualityGroup(new Heap<>(data, ASCENDING),
-                                  new Heap<>(data, ASCENDING))
-                .addEqualityGroup(new Heap<>(data, DESCENDING))
+                .addEqualityGroup(new Heap<>(data, MIN),
+                                  new Heap<>(data, MIN))
+                .addEqualityGroup(new Heap<>(data, MAX))
                 .testEquals();
     }
 
     @Test
-    public void ascending() {
-        Heap<Integer> h = new Heap<>(data, ASCENDING);
+    public void empty() {
+        Heap<Integer> h = new Heap<>(new ArrayList<Integer>(), MIN);
+        assertTrue("should be empty", h.isEmpty());
+        assertEquals("incorrect size", 0, h.size());
+        assertNull("no item expected", h.extreme());
+        assertNull("no item expected", h.extractExtreme());
+    }
+
+    @Test
+    public void insert() {
+        Heap<Integer> h = new Heap<>(data, MIN);
         assertEquals("incorrect size", 10, h.size());
+        h.insert(3);
+        assertEquals("incorrect size", 11, h.size());
+    }
+
+    @Test
+    public void minQueue() {
+        Heap<Integer> h = new Heap<>(data, MIN);
         assertFalse("should not be empty", h.isEmpty());
+        assertEquals("incorrect size", 10, h.size());
         assertEquals("incorrect extreme", (Integer) 0, h.extreme());
 
         for (int i = 0, n = h.size(); i < n; i++) {
@@ -45,10 +63,10 @@
     }
 
     @Test
-    public void descending() {
-        Heap<Integer> h = new Heap<>(data, DESCENDING);
-        assertEquals("incorrect size", 10, h.size());
+    public void maxQueue() {
+        Heap<Integer> h = new Heap<>(data, MAX);
         assertFalse("should not be empty", h.isEmpty());
+        assertEquals("incorrect size", 10, h.size());
         assertEquals("incorrect extreme", (Integer) 9, h.extreme());
 
         for (int i = h.size(); i > 0; i--) {
@@ -58,29 +76,9 @@
     }
 
     @Test
-    public void empty() {
-        Heap<Integer> h = new Heap<>(new ArrayList<Integer>(), ASCENDING);
-        assertEquals("incorrect size", 0, h.size());
-        assertTrue("should be empty", h.isEmpty());
-        assertNull("no item expected", h.extreme());
-        assertNull("no item expected", h.extractExtreme());
-    }
-
-    @Test
-    public void insert() {
-        Heap<Integer> h = new Heap<>(data, ASCENDING);
-        assertEquals("incorrect size", 10, h.size());
-        h.insert(3);
-        assertEquals("incorrect size", 11, h.size());
-    }
-
-    @Test
     public void iterator() {
-        Heap<Integer> h = new Heap<>(data, ASCENDING);
-        Iterator<Integer> it = h.iterator();
-        while (it.hasNext()) {
-            int item = it.next();
-        }
+        Heap<Integer> h = new Heap<>(data, MIN);
+        assertTrue("should have next element", h.iterator().hasNext());
     }
 
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
index 855730a..225690c 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
@@ -2,6 +2,8 @@
 
 import java.util.Objects;
 
+import static com.google.common.base.Objects.toStringHelper;
+
 /**
  * Test edge.
  */
@@ -43,4 +45,11 @@
         }
         return false;
     }
+
+    @Override
+    public String toString() {
+        return toStringHelper(this).add("src", src()).add("dst", dst()).
+                add("weight", weight).toString();
+    }
+
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestVertex.java b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
index 2a1c7da..0cd8f2a 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
@@ -16,11 +16,6 @@
     }
 
     @Override
-    public String toString() {
-        return toStringHelper(this).add("name", name).toString();
-    }
-
-    @Override
     public int hashCode() {
         return Objects.hash(name);
     }
@@ -34,4 +29,9 @@
         return false;
     }
 
+    @Override
+    public String toString() {
+        return name;
+    }
+
 }