ONOS-6229 KShortestPathsSearch bug fix
- KShortestPathsSearch cannot find other k-paths when the shortest path is 1 hop
Change-Id: I42d9952cc0fbc3e2fb2e3db44821a13fa0132137
diff --git a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
index 00bda43..67c9f6e 100644
--- a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
@@ -65,7 +65,7 @@
for (int k = 1; k < maxPaths; k++) {
- for (int i = 0; i < (resultPaths.get(k - 1).edges().size() - 1); i++) {
+ for (int i = 0; i < resultPaths.get(k - 1).edges().size(); i++) {
V spurNode = resultPaths.get(k - 1).edges().get(i).src();
List<E> rootPathEdgeList = resultPaths.get(k - 1).edges().subList(0, i);
@@ -88,7 +88,7 @@
spurPath.edges().forEach(totalPath::add);
//The following line must use the original weigher not the modified weigher because the modified
//weigher will count -1 values used for modifying the graph and return an inaccurate cost.
- potentialPaths.add(new DefaultPath<V, E>(totalPath,
+ potentialPaths.add(new DefaultPath<>(totalPath,
calculatePathCost(weigher, totalPath)));
}
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 d860928..0e15eb7 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -64,16 +64,49 @@
}
};
+ /**
+ * EdgeWeigher which only looks at hop count.
+ */
+ protected final EdgeWeigher<TestVertex, TestEdge> hopWeigher =
+ new EdgeWeigher<TestVertex, TestEdge>() {
+ @Override
+ public Weight weight(TestEdge edge) {
+ return W1;
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return ZW;
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return TestDoubleWeight.NON_VIABLE_WEIGHT;
+ }
+ };
+
protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) {
for (Path p : paths) {
System.out.println(p);
}
}
+ /**
+ * @return 8 vertices A to H.
+ */
protected Set<TestVertex> vertexes() {
return of(A, B, C, D, E, F, G, H);
}
+ /**
+ * <pre>
+ * A → B → D → H
+ * ↓ ↙ ↓ ↙ ↑ ↗
+ * C → E → F → G
+ * </pre>
+ * Note: not all edges have same weight, see method body for details.
+ * @return 12 edges illustrated as above.
+ */
protected Set<TestEdge> edges() {
return of(new TestEdge(A, B, W1),
new TestEdge(A, C, W3),
diff --git a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
index ed92be9..de0bc74 100644
--- a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
@@ -15,7 +15,9 @@
*/
package org.onlab.graph;
+import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
+
import org.junit.Before;
import org.junit.Test;
@@ -24,13 +26,15 @@
import java.util.Set;
import static com.google.common.collect.ImmutableSet.of;
+import static org.hamcrest.Matchers.is;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;
/**
* Class for test KshortestPathsSearch.
*/
-public class KShortestPathsSearchTest<V extends Vertex, E extends Edge<V>> extends GraphTest {
+public class KShortestPathsSearchTest extends GraphTest {
private KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>();
private GraphPathSearch.Result<TestVertex, TestEdge> result;
@@ -38,6 +42,7 @@
public void setUp() {
graph = new AdjacencyListsGraph<>(vertexes(), edges());
}
+
@Test
public void noPath() {
graph = new AdjacencyListsGraph<>(of(A, B, C, D),
@@ -56,7 +61,6 @@
//Tests that there is only a single path possible between A and B
graph = new AdjacencyListsGraph<>(vertexes(), edges());
this.result = kShortestPathsSearch.search(graph, A, B, weigher, 2);
- Iterator<Path<TestVertex, TestEdge>> itr = result.paths().iterator();
assertEquals("incorrect paths count", 1, result.paths().size());
List<TestEdge> correctEdgeList = Lists.newArrayList();
correctEdgeList.add(new TestEdge(A, B, W1));
@@ -65,6 +69,22 @@
}
@Test
+ public void testResultsAreOneHopPathPlusLongerOnes() {
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
+ this.result = kShortestPathsSearch.search(graph, B, D, hopWeigher, 42);
+ assertEquals("incorrect paths count", 3, result.paths().size());
+ assertThat("the shortest path size is 1 hop",
+ Iterables.get(result.paths(), 0).edges().size(),
+ is(1));
+ assertThat("the 2nd shortest path size is 3 hop",
+ Iterables.get(result.paths(), 1).edges().size(),
+ is(3));
+ assertThat("the 3rd shortest path size is 4 hop",
+ Iterables.get(result.paths(), 2).edges().size(),
+ is(4));
+ }
+
+ @Test
public void testTwoPath() {
//Tests that there are only two paths between A and C and that they are returned in the correct order
result = kShortestPathsSearch.search(graph, A, C, weigher, 3);
@@ -136,9 +156,9 @@
public void testLimitPathSetSize() {
//Checks to make sure that no more than K paths are returned
result = kShortestPathsSearch.search(graph, A, E, weigher, 3);
- assertTrue("There are an unexpected number of paths.", result.paths().size() == 3);
+ assertEquals("There are an unexpected number of paths.", 3, result.paths().size());
result = kShortestPathsSearch.search(graph, A, G, weigher, 1);
- assertTrue("There are an unexpected number of paths.", result.paths().size() == 1);
+ assertEquals("There are an unexpected number of paths.", 1, result.paths().size());
}