Added more unit tests for the graph utilities.
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
similarity index 98%
rename from utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
rename to utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index b3ebbdb..7dad767 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -15,7 +15,7 @@
* @param <V> vertex type
* @param <E> edge type
*/
-public abstract class AbstractPathSearch<V extends Vertex, E extends Edge<V>>
+public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
implements GraphPathSearch<V, E> {
private double samenessThreshold = 0.000000001;
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
new file mode 100644
index 0000000..66dd33a
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -0,0 +1,57 @@
+package org.onlab.graph;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Implementation of the BFS algorithm.
+ */
+public class BreadthFirstSearch<V extends Vertex, E extends Edge<V>>
+ extends AbstractGraphPathSearch<V, E> {
+
+ @Override
+ public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> ew) {
+ checkArguments(graph, src, dst);
+
+ // Prepare the graph result.
+ DefaultResult result = new DefaultResult(src, dst);
+
+ // Setup the starting frontier with the source as the sole vertex.
+ Set<V> frontier = new HashSet<>();
+ result.costs.put(src, 0.0);
+ frontier.add(src);
+
+ search: while (!frontier.isEmpty()) {
+ // Prepare the next frontier.
+ Set<V> next = new HashSet<>();
+
+ // Visit all vertexes in the current frontier.
+ for (V vertex : frontier) {
+ double cost = result.cost(vertex);
+
+ // Visit all egress edges of the current frontier vertex.
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ V nextVertex = edge.dst();
+ if (!result.hasCost(nextVertex)) {
+ // If this vertex has not been visited yet, update it.
+ result.updateVertex(nextVertex, edge,
+ cost + (ew == null ? 1.0 : ew.weight(edge)),
+ true);
+ // If we have reached our intended destination, bail.
+ if (nextVertex.equals(dst))
+ break search;
+ next.add(nextVertex);
+ }
+ }
+ }
+
+ // Promote the next frontier.
+ frontier = next;
+ }
+
+ // Finally, but the paths on the search result and return.
+ result.buildPaths();
+ return result;
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
index 0ef4f98..be7ad18 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -14,8 +14,6 @@
*/
public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> {
- private V src = null;
- private V dst = null;
private final List<E> edges = new ArrayList<>();
private double cost = 0.0;
@@ -32,20 +30,18 @@
*/
public DefaultMutablePath(Path<V, E> path) {
checkNotNull(path, "Path cannot be null");
- this.src = path.src();
- this.dst = path.dst();
this.cost = path.cost();
edges.addAll(path.edges());
}
@Override
public V src() {
- return src;
+ return edges.isEmpty() ? null : edges.get(0).src();
}
@Override
public V dst() {
- return dst;
+ return edges.isEmpty() ? null : edges.get(edges.size() - 1).dst();
}
@Override
@@ -69,28 +65,35 @@
}
@Override
+ public void insertEdge(E edge) {
+ checkNotNull(edge, "Edge cannot be null");
+ checkArgument(edges.isEmpty() || src().equals(edge.dst()),
+ "Edge destination must be the same as the current path source");
+ edges.add(0, edge);
+ }
+
+ @Override
public void appendEdge(E edge) {
checkNotNull(edge, "Edge cannot be null");
- checkArgument(edges.isEmpty() || dst.equals(edge.src()),
+ checkArgument(edges.isEmpty() || dst().equals(edge.src()),
"Edge source must be the same as the current path destination");
- dst = edge.dst();
edges.add(edge);
}
@Override
- public void insertEdge(E edge) {
- checkNotNull(edge, "Edge cannot be null");
- checkArgument(edges.isEmpty() || src.equals(edge.dst()),
- "Edge destination must be the same as the current path source");
- src = edge.src();
- edges.add(0, edge);
+ public void removeEdge(E edge) {
+ checkArgument(edge.src().equals(edge.dst()) ||
+ edges.indexOf(edge) == 0 ||
+ edges.lastIndexOf(edge) == edges.size() - 1,
+ "Edge must be at start or end of path, or it must be a cyclic edge");
+ edges.remove(edge);
}
@Override
public String toString() {
return com.google.common.base.Objects.toStringHelper(this)
- .add("src", src)
- .add("dst", dst)
+ .add("src", src())
+ .add("dst", dst())
.add("cost", cost)
.add("edges", edges)
.toString();
@@ -98,19 +101,17 @@
@Override
public int hashCode() {
- return Objects.hash(src, dst, edges, cost);
+ return Objects.hash(edges, cost);
}
@Override
public boolean equals(Object obj) {
if (obj instanceof DefaultMutablePath) {
final DefaultMutablePath other = (DefaultMutablePath) obj;
- return super.equals(obj) &&
- Objects.equals(this.src, other.src) &&
- Objects.equals(this.dst, other.dst) &&
- Objects.equals(this.cost, other.cost) &&
+ return Objects.equals(this.cost, other.cost) &&
Objects.equals(this.edges, other.edges);
}
return false;
}
+
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
index b0cd098..d7fc9e8a 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -73,8 +73,7 @@
public boolean equals(Object obj) {
if (obj instanceof DefaultPath) {
final DefaultPath other = (DefaultPath) obj;
- return super.equals(obj) &&
- Objects.equals(this.src, other.src) &&
+ return Objects.equals(this.src, other.src) &&
Objects.equals(this.dst, other.dst) &&
Objects.equals(this.cost, other.cost) &&
Objects.equals(this.edges, other.edges);
diff --git a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
index 9b27bd8..dc71859 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -9,7 +9,7 @@
* one, but all shortest paths between the source and destinations.
*/
public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>>
- extends AbstractPathSearch<V, E> {
+ extends AbstractGraphPathSearch<V, E> {
@Override
public Result<V, E> search(Graph<V, E> g, V src, V dst, EdgeWeight<V, E> ew) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
index c0a72c9..2d8420d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -22,6 +22,15 @@
void appendEdge(E edge);
/**
+ * Removes the specified edge. This edge must be either at the start or
+ * at the end of the path, or it must be a cyclic edge in order not to
+ * violate the contiguous path property.
+ *
+ * @param edge edge to be removed
+ */
+ void removeEdge(E edge);
+
+ /**
* Sets the total path cost as a unit-less double.
*
* @param cost new path cost
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;
+ }
+
}