Added edge case unit tests for Dijkstra search
Change-Id: Ie707c52140f3d417cc74ee9e3aa39275a1df6d84
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 cfd0a4b..7edf8b4 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -15,10 +15,13 @@
*/
package org.onlab.graph;
+import org.junit.Rule;
import org.junit.Test;
+import org.junit.rules.ExpectedException;
import java.text.DecimalFormat;
import java.util.HashSet;
+import java.util.NoSuchElementException;
import java.util.Set;
import static com.google.common.collect.ImmutableSet.of;
@@ -47,13 +50,16 @@
executeDefaultTest(10, 3, new ScalarWeight(3.0));
}
+ @Rule
+ public final ExpectedException exception = ExpectedException.none();
+
@Test
public void noPath() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, W1),
- new TestEdge(B, A, W1),
- new TestEdge(C, D, W1),
- new TestEdge(D, C, W1)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, A, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, C, W1)));
GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weigher, 1).paths();
printPaths(paths);
@@ -71,28 +77,76 @@
}
@Test
+ public void exceptions() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, W2),
+ new TestEdge(B, A, W1),
+ new TestEdge(A, A, W3),
+ new TestEdge(A, C, NW1),
+ new TestEdge(C, D, W3)));
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS).paths();
+ printPaths(paths);
+ assertEquals("Incorrect path count", 0, paths.size());
+
+ paths = gs.search(graph, A, A, weigher, 5).paths();
+ exception.expect(NoSuchElementException.class);
+ paths.iterator().next().cost();
+ }
+
+ @Test
+ public void noEdges() {
+ graph = new AdjacencyListsGraph<>(vertexes(), of());
+ for (TestVertex v: vertexes()) {
+ executeSearch(graphSearch(), graph, v, null, weigher, 0, new TestDoubleWeight(0));
+ }
+
+ }
+
+ @Test
public void simpleMultiplePath() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, W1),
- new TestEdge(A, C, W1),
- new TestEdge(B, D, W1),
- new TestEdge(C, D, W1)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W1),
+ new TestEdge(B, D, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(A, E, ZW),
+ new TestEdge(E, F, NW1),
+ new TestEdge(F, B, ZW)));
executeSearch(graphSearch(), graph, A, D, weigher, 2, W2);
executeSinglePathSearch(graphSearch(), graph, A, D, weigher, 1, W2);
+
+ executeSearch(graphSearch(), graph, A, B, weigher, 1, W1);
+ executeSearch(graphSearch(), graph, D, A, weigher, 0, null);
+ }
+
+
+ @Test
+ public void manualDoubleWeights() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(new TestEdge(A, B, new TestDoubleWeight(1.5)),
+ new TestEdge(B, D, new TestDoubleWeight(3.5)),
+ new TestEdge(A, C, new TestDoubleWeight(2.2)),
+ new TestEdge(C, E, new TestDoubleWeight(1.1)),
+ new TestEdge(E, D, new TestDoubleWeight(1.7)),
+ new TestEdge(A, D, new TestDoubleWeight(5.0))));
+ executeSearch(graphSearch(), graph, A, D, weigher, 3, new TestDoubleWeight(5.0));
+ executeSinglePathSearch(graphSearch(), graph, A, D, weigher, 1, W5);
}
@Test
public void denseMultiplePath() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
- of(new TestEdge(A, B, W1),
- new TestEdge(A, C, W1),
- new TestEdge(B, D, W1),
- new TestEdge(C, D, W1),
- new TestEdge(D, E, W1),
- new TestEdge(D, F, W1),
- new TestEdge(E, G, W1),
- new TestEdge(F, G, W1),
- new TestEdge(A, G, W4)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W1),
+ new TestEdge(B, D, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(D, F, W1),
+ new TestEdge(E, G, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(A, G, W4)));
executeSearch(graphSearch(), graph, A, G, weigher, 5, W4);
executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, W4);
}
@@ -100,55 +154,51 @@
@Test
public void dualEdgeMultiplePath() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
- of(new TestEdge(A, B, W1),
- new TestEdge(A, C, W3),
- new TestEdge(B, D, W2),
- new TestEdge(B, C, W1),
- new TestEdge(B, E, W4),
- new TestEdge(C, E, W1),
- new TestEdge(D, H, W5),
- new TestEdge(D, E, W1),
- new TestEdge(E, F, W1),
- new TestEdge(F, D, W1),
- new TestEdge(F, G, W1),
- new TestEdge(F, H, W1),
- new TestEdge(A, E, W3),
- new TestEdge(B, D, W1)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W3),
+ new TestEdge(B, D, W2),
+ new TestEdge(B, C, W1),
+ new TestEdge(B, E, W4),
+ new TestEdge(C, E, W1),
+ new TestEdge(D, H, W5),
+ new TestEdge(D, E, W1),
+ new TestEdge(E, F, W1),
+ new TestEdge(F, D, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(F, H, W1),
+ new TestEdge(A, E, W3),
+ new TestEdge(B, D, W1)));
executeSearch(graphSearch(), graph, A, E, weigher, 3, W3);
executeSinglePathSearch(graphSearch(), graph, A, E, weigher, 1, W3);
+
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> pathF = gs.search(graph, A, F, weigher, GraphPathSearch.ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> pathE = gs.search(graph, A, E, weigher, GraphPathSearch.ALL_PATHS).paths();
+ assertEquals(0, pathF.size() - pathE.size());
+ assertEquals(new TestDoubleWeight(1.0),
+ pathF.iterator().next().cost().subtract(pathE.iterator().next().cost()));
}
@Test
public void negativeWeights() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
- of(new TestEdge(A, B, W1),
- new TestEdge(A, C, NW1),
- new TestEdge(B, D, W1),
- new TestEdge(D, A, NW2),
- new TestEdge(C, D, W1),
- new TestEdge(D, E, W1),
- new TestEdge(D, F, W1),
- new TestEdge(E, G, W1),
- new TestEdge(F, G, W1),
- new TestEdge(G, A, NW5),
- new TestEdge(A, G, W4)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, NW1),
+ new TestEdge(B, D, W1),
+ new TestEdge(D, A, NW2),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(D, F, W1),
+ new TestEdge(E, G, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(G, A, NW5),
+ new TestEdge(A, G, W4)));
executeSearch(graphSearch(), graph, A, G, weigher, 3, new TestDoubleWeight(4.0));
executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, new TestDoubleWeight(4.0));
}
- public void disconnectedPerf() {
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- disconnected();
- }
+ @Test
public void disconnected() {
Set<TestVertex> vertexes = new HashSet<>();
for (int i = 0; i < 200; i++) {
@@ -166,4 +216,4 @@
System.out.println("Compute cost is " + fmt.format(end - start) + " nanos");
}
-}
+}
\ No newline at end of file