diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
new file mode 100644
index 0000000..4384a66
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
@@ -0,0 +1,22 @@
+package org.onlab.graph;
+
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+/**
+ * Test of the base edge implementation.
+ */
+public class AbstractEdgeTest {
+
+    @Test
+    public void equality() {
+        TestVertex v1 = new TestVertex("1");
+        TestVertex v2 = new TestVertex("2");
+        new EqualsTester()
+                .addEqualityGroup(new TestEdge(v1, v2, 1),
+                                  new TestEdge(v1, v2, 1))
+                .addEqualityGroup(new TestEdge(v2, v1, 1))
+                .testEquals();
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
new file mode 100644
index 0000000..00ba3da
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
@@ -0,0 +1,37 @@
+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
new file mode 100644
index 0000000..e61583d
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
@@ -0,0 +1,56 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Tests of the graph implementation.
+ */
+public class AdjacencyListsGraphTest {
+
+    private static final TestVertex A = new TestVertex("A");
+    private static final TestVertex B = new TestVertex("B");
+    private static final TestVertex C = new TestVertex("C");
+    private static final TestVertex D = new TestVertex("D");
+    private static final TestVertex E = new TestVertex("E");
+    private static final TestVertex F = new TestVertex("F");
+    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());
+    }
+
+    @Test
+    public void equality() {
+        Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F);
+        Set<TestVertex> vertexes2 = ImmutableSet.of(A, B, C, D, E, F, G);
+
+        AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges);
+        AdjacencyListsGraph<TestVertex, TestEdge> same = new AdjacencyListsGraph<>(vertexes, edges);
+        AdjacencyListsGraph<TestVertex, TestEdge> different = new AdjacencyListsGraph<>(vertexes2, edges);
+
+        new EqualsTester()
+                .addEqualityGroup(graph, same)
+                .addEqualityGroup(different)
+                .testEquals();
+    }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
new file mode 100644
index 0000000..ae45750
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -0,0 +1,48 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the BFS algorithm.
+ */
+public abstract class BreadthFirstSearchTest extends AbstractGraphSearchTest {
+
+    @Override
+    protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
+        return null; // new BreadthFirstSearch();
+    }
+
+    @Test
+    public void basics() {
+        runBasics(3, 8.0, 7);
+    }
+
+    @Test
+    public void defaultWeight() {
+        weight = null;
+        runBasics(3, 3.0, 7);
+    }
+
+    protected void runBasics(int expectedLength, double expectedCost, int expectedPaths) {
+        g = new AdjacencyListsGraph<>(vertices(), edges());
+
+        GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+        assertEquals("incorrect paths count", 1, paths.size());
+
+        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);
+
+        paths = search.search(g, A, null, weight).paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", expectedPaths, paths.size());
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
new file mode 100644
index 0000000..5ee4caa
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -0,0 +1,110 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the Dijkstra algorithm.
+ */
+public class DijkstraGraphSearchTest extends BreadthFirstSearchTest {
+
+    @Override
+    protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
+        return new DijkstraGraphSearch<>();
+    }
+
+    @Test
+    @Override
+    public void basics() {
+        runBasics(5, 5.0, 7);
+    }
+
+    @Test
+    public void defaultWeight() {
+        weight = null;
+        runBasics(3, 3.0, 10);
+    }
+
+    @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)));
+
+        GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+        Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, B, weight).paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", 1, paths.size());
+        assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+
+        paths = gs.search(g, A, D, weight).paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", 0, paths.size());
+
+        paths = gs.search(g, A, null, weight).paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", 1, paths.size());
+        assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+    }
+
+    @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);
+    }
+
+    @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);
+    }
+
+    @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);
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
new file mode 100644
index 0000000..bb91e03
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -0,0 +1,50 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.Set;
+
+/**
+ * Base class for various graph-related tests.
+ */
+public class GraphTest {
+
+    static final TestVertex A = new TestVertex("A");
+    static final TestVertex B = new TestVertex("B");
+    static final TestVertex C = new TestVertex("C");
+    static final TestVertex D = new TestVertex("D");
+    static final TestVertex E = new TestVertex("E");
+    static final TestVertex F = new TestVertex("F");
+    static final TestVertex G = new TestVertex("G");
+    static final TestVertex H = new TestVertex("H");
+
+    protected Graph<TestVertex, TestEdge> g;
+
+    protected EdgeWeight<TestVertex, TestEdge> weight =
+            new EdgeWeight<TestVertex, TestEdge>() {
+        @Override
+        public double weight(TestEdge edge) {
+            return edge.weight();
+        }
+    };
+
+    protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) {
+        for (Path p : paths) {
+            System.out.println(p);
+        }
+    }
+
+    protected Set<TestVertex> vertices() {
+        return ImmutableSet.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));
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/HeapTest.java b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
new file mode 100644
index 0000000..0b1601d
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
@@ -0,0 +1,86 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Ordering;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+
+import static org.junit.Assert.*;
+
+/**
+ * Heap data structure tests.
+ */
+public class HeapTest {
+
+    private ArrayList<Integer> data =
+            new ArrayList<>(ImmutableList.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();
+
+    @Test
+    public void equality() {
+        new EqualsTester()
+                .addEqualityGroup(new Heap<>(data, ASCENDING),
+                                  new Heap<>(data, ASCENDING))
+                .addEqualityGroup(new Heap<>(data, DESCENDING))
+                .testEquals();
+    }
+
+    @Test
+    public void ascending() {
+        Heap<Integer> h = new Heap<>(data, ASCENDING);
+        assertEquals("incorrect size", 10, h.size());
+        assertFalse("should not be empty", h.isEmpty());
+        assertEquals("incorrect extreme", (Integer) 0, h.extreme());
+
+        for (int i = 0, n = h.size(); i < n; i++) {
+            assertEquals("incorrect element", (Integer) i, h.extractExtreme());
+        }
+        assertTrue("should be empty", h.isEmpty());
+    }
+
+    @Test
+    public void descending() {
+        Heap<Integer> h = new Heap<>(data, DESCENDING);
+        assertEquals("incorrect size", 10, h.size());
+        assertFalse("should not be empty", h.isEmpty());
+        assertEquals("incorrect extreme", (Integer) 9, h.extreme());
+
+        for (int i = h.size(); i > 0; i--) {
+            assertEquals("incorrect element", (Integer) (i - 1), h.extractExtreme());
+        }
+        assertTrue("should be empty", h.isEmpty());
+    }
+
+    @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();
+        }
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
new file mode 100644
index 0000000..855730a
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
@@ -0,0 +1,46 @@
+package org.onlab.graph;
+
+import java.util.Objects;
+
+/**
+ * Test edge.
+ */
+public class TestEdge extends AbstractEdge<TestVertex> {
+
+    private final double weight;
+
+    /**
+     * Creates a new edge between the specified source and destination vertexes.
+     *
+     * @param src    source vertex
+     * @param dst    destination vertex
+     * @param weight edge weight
+     */
+    public TestEdge(TestVertex src, TestVertex dst, double weight) {
+        super(src, dst);
+        this.weight = weight;
+    }
+
+    /**
+     * Returns the edge weight.
+     *
+     * @return edge weight
+     */
+    public double weight() {
+        return weight;
+    }
+
+    @Override
+    public int hashCode() {
+        return 31 * super.hashCode() + Objects.hash(weight);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof TestEdge) {
+            final TestEdge other = (TestEdge) obj;
+            return super.equals(obj) && Objects.equals(this.weight, other.weight);
+        }
+        return false;
+    }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestVertex.java b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
new file mode 100644
index 0000000..2a1c7da
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
@@ -0,0 +1,37 @@
+package org.onlab.graph;
+
+import java.util.Objects;
+
+import static com.google.common.base.Objects.toStringHelper;
+
+/**
+ * Test vertex.
+ */
+public class TestVertex implements Vertex {
+
+    private final String name;
+
+    public TestVertex(String name) {
+        this.name = name;
+    }
+
+    @Override
+    public String toString() {
+        return toStringHelper(this).add("name", name).toString();
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(name);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof TestVertex) {
+            final TestVertex other = (TestVertex) obj;
+            return Objects.equals(this.name, other.name);
+        }
+        return false;
+    }
+
+}