Added graph-related utility code.
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;
+ }
+
+}