ONOS-5574: KShortestPathSearch mistakenly assumes every path has k edges
Change-Id: I9e99e95ee35f5bc4d4bdd285bf18666b6e58db0f
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 1b2a681..8e5442b 100644
--- a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
@@ -69,7 +69,7 @@
List<E> rootPathEdgeList = resultPaths.get(k - 1).edges().subList(0, i);
for (Path<V, E> path : resultPaths) {
- if (edgeListsAreEqual(rootPathEdgeList, path.edges().subList(0, i))) {
+ if (path.edges().size() >= i && edgeListsAreEqual(rootPathEdgeList, path.edges().subList(0, i))) {
modifiedWeighter.removedEdges.add(path.edges().get(i));
}
}
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 adf62b9..2b7c8d1 100644
--- a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
@@ -141,6 +141,68 @@
assertTrue("There are an unexpected number of paths.", result.paths().size() == 1);
}
+
+ @Test
+ public void testVariableLenPathsWithConstantLinkWeight() {
+
+ /*
+ * Test graph:
+ *
+ * +-+-+ +---+ +---+ +-+-+
+ * +--+ B +--+ C +-+ D +--+ E |
+ * | +-+-+ +---+ +---+ +-+-+
+ * | | |
+ * +-+-+ | +---+ +---+ +-+-+
+ * | A | +----+ F +-+ G +--+ H |
+ * +---+ +---+ +---+ +---+
+ */
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), of(
+ new TestEdge(A, B, 1),
+ new TestEdge(B, A, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, B, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, C, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(E, D, 1),
+ new TestEdge(E, H, 1),
+ new TestEdge(H, E, 1),
+ new TestEdge(H, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(G, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(F, B, 1),
+ new TestEdge(B, F, 1)
+ ));
+
+ weight = edge -> 1.0;
+
+ //Tests that there are only two paths between A and G and that they are returned in the correct order
+ result = kShortestPathsSearch.search(graph, A, G, weight, 5);
+
+ assertEquals("There are an unexpected number of paths.", 2, result.paths().size());
+
+ Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
+
+ List<TestEdge> correctEdgeList = Lists.newArrayList();
+ correctEdgeList.add(new TestEdge(A, B, 1));
+ correctEdgeList.add(new TestEdge(B, F, 1));
+ correctEdgeList.add(new TestEdge(F, G, 1));
+ assertTrue("The first path from A to G was incorrect.",
+ edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
+
+ correctEdgeList.clear();
+ correctEdgeList.add(new TestEdge(A, B, 1));
+ correctEdgeList.add(new TestEdge(B, C, 1));
+ correctEdgeList.add(new TestEdge(C, D, 1));
+ correctEdgeList.add(new TestEdge(D, E, 1));
+ correctEdgeList.add(new TestEdge(E, H, 1));
+ correctEdgeList.add(new TestEdge(H, G, 1));
+ assertTrue("The second path from A to G was incorrect.",
+ edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
+ }
+
+
private boolean edgeListsAreEqual(List<TestEdge> edgeListOne, List<TestEdge> edgeListTwo) {
if (edgeListOne.size() != edgeListTwo.size()) {
return false;
@@ -156,4 +218,4 @@
}
return true;
}
-}
\ No newline at end of file
+}