bellman-ford unit tests
Change-Id: I1b7b72874b78e4de0bf401aeff02ed79b7272408
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
index 0a36d77..2dc286c 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -20,6 +20,7 @@
import java.util.HashSet;
import java.util.Set;
+import static com.google.common.collect.ImmutableSet.of;
import static org.junit.Assert.assertEquals;
import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
@@ -73,5 +74,48 @@
printPaths(paths);
assertEquals("incorrect paths count", 6, paths.size());
}
+ @Test
+ public void testNegativeEdge() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, W3),
+ new TestEdge(A, C, W4),
+ new TestEdge(C, B, NW2),
+ new TestEdge(B, C, W2),
+ new TestEdge(A, D, W5),
+ new TestEdge(D, B, new TestDoubleWeight(-3))));
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weigher, 1).paths();
+ printPaths(paths);
+ assertEquals("incorrect path count", 1, paths.size());
+ assertEquals("incoreect path cost", new TestDoubleWeight(2), paths.iterator().next().cost());
+
+ executeSearch(graphSearch(), graph, A, B, weigher, 2, W2);
+ }
+
+ @Test
+ public void multipleNegatives() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, C, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(A, B, new TestDoubleWeight(-4)),
+ new TestEdge(A, C, new TestDoubleWeight(-3)),
+ new TestEdge(A, D, NW1),
+ new TestEdge(D, C, NW1)));
+ executeSearch(graphSearch(), graph, A, E, weigher, 2, NW1);
+ executeSinglePathSearch(graphSearch(), graph, A, E, weigher, 1, NW1);
+ executeSearch(graphSearch(), graph, B, C, weigher, 1, W1);
+ }
+
+ @Test
+ public void manualWeights() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C),
+ of(new TestEdge(A, B, new TestDoubleWeight(-3.3)),
+ new TestEdge(B, C, new TestDoubleWeight(1.3)),
+ new TestEdge(A, C, new TestDoubleWeight(-1.9)),
+ new TestEdge(B, C, new TestDoubleWeight(1.5))));
+ executeSearch(graphSearch(), graph, A, C, weigher, 1, new TestDoubleWeight(-2.0));
+ }
}