Lazy k-Shortest paths search
Change-Id: Ibebbe904c31c8c73e097035ae4486333b38ce2a8
diff --git a/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java b/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java
new file mode 100644
index 0000000..5039c51
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/LazyKShortestPathsSearch.java
@@ -0,0 +1,217 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onlab.graph;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static java.util.Spliterators.spliteratorUnknownSize;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.Set;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+import com.google.common.collect.ComparisonChain;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+
+/**
+ * Lazily runs K shortest paths algorithm on a provided directed graph.
+ */
+public class LazyKShortestPathsSearch<V extends Vertex, E extends Edge<V>> {
+
+ private final Comparator<Path<V, E>> pathComparator = new PathComparator();
+
+ private final GraphPathSearch<V, E> shortest = new DijkstraGraphSearch<>();
+
+ /**
+ * Searches the specified graph for paths between vertices.
+ *
+ * @param graph graph to be searched
+ * @param src source vertex
+ * @param dst destination vertex
+ * @param weigher edge-weigher
+ * @return Stream of shortest paths
+ */
+ public Stream<Path<V, E>> lazyPathSearch(Graph<V, E> graph,
+ V src, V dst,
+ EdgeWeigher<V, E> weigher) {
+
+ Iterator<Path<V, E>> it = new ShortestPathIterator(graph, src, dst, weigher);
+
+ return StreamSupport.stream(spliteratorUnknownSize(it,
+ Spliterator.ORDERED |
+ Spliterator.DISTINCT |
+ Spliterator.NONNULL |
+ Spliterator.IMMUTABLE),
+ false);
+ }
+
+ /**
+ * Iterator returning shortest paths, searched incrementally on each next() call.
+ */
+ private final class ShortestPathIterator implements Iterator<Path<V, E>> {
+
+ final Graph<V, E> graph;
+ final V src;
+ final V dst;
+ final EdgeWeigher<V, E> weigher;
+
+ final InnerEdgeWeigher maskingWeigher;
+
+ final List<Path<V, E>> resultPaths = new ArrayList<>(); // A
+ final Queue<Path<V, E>> potentialPaths = new PriorityQueue<>(pathComparator); // B
+
+ Path<V, E> next;
+
+ ShortestPathIterator(Graph<V, E> graph,
+ V src, V dst,
+ EdgeWeigher<V, E> weigher) {
+ this.graph = checkNotNull(graph);
+ this.src = checkNotNull(src);
+ this.dst = checkNotNull(dst);
+ this.weigher = checkNotNull(weigher);
+
+ maskingWeigher = new InnerEdgeWeigher(weigher);
+ next = shortest.search(graph, src, dst, weigher, 1)
+ .paths().stream().findFirst().orElse(null);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ @Override
+ public Path<V, E> next() {
+ if (next == null) {
+ throw new NoSuchElementException("No more path between " + src + "-" + dst);
+ }
+
+ // lastPath: the path to return at the end of this call
+ Path<V, E> lastPath = next;
+ resultPaths.add(lastPath);
+
+ /// following is basically Yen's k-shortest path algorithm
+
+ // start searching for next path
+ for (int i = 0; i < lastPath.edges().size(); i++) {
+ V spurNode = lastPath.edges().get(i).src();
+ List<E> rootPathEdgeList = lastPath.edges().subList(0, i);
+
+ for (Path<V, E> path : resultPaths) {
+ if (path.edges().size() >= i &&
+ rootPathEdgeList.equals(path.edges().subList(0, i))) {
+ maskingWeigher.excluded.add(path.edges().get(i));
+ }
+ }
+
+ // Effectively remove all root path nodes other than spurNode
+ rootPathEdgeList.forEach(edge -> {
+ maskingWeigher.excluded.addAll(graph.getEdgesFrom(edge.src()));
+ maskingWeigher.excluded.addAll(graph.getEdgesTo(edge.src()));
+ });
+
+ shortest.search(graph, spurNode, dst, maskingWeigher, 1)
+ .paths().stream().findAny().ifPresent(spurPath -> {
+ List<E> totalPath = ImmutableList.<E>builder()
+ .addAll(rootPathEdgeList)
+ .addAll(spurPath.edges())
+ .build();
+ potentialPaths.add(path(totalPath));
+ });
+
+ // Restore all removed paths and nodes
+ maskingWeigher.excluded.clear();
+ }
+
+ if (potentialPaths.isEmpty()) {
+ next = null;
+ } else {
+ next = potentialPaths.poll();
+ }
+
+ return lastPath;
+ }
+
+ private Path<V, E> path(List<E> edges) {
+ //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.
+ return new DefaultPath<>(edges, calculatePathCost(weigher, edges));
+ }
+
+ private Weight calculatePathCost(EdgeWeigher<V, E> weighter, List<E> edges) {
+ Weight totalCost = weighter.getInitialWeight();
+ for (E edge : edges) {
+ totalCost = totalCost.merge(weighter.weight(edge));
+ }
+ return totalCost;
+ }
+ }
+
+ /**
+ * EdgeWeigher which excludes specified edges from path computation.
+ */
+ private final class InnerEdgeWeigher implements EdgeWeigher<V, E> {
+
+ private final Set<E> excluded = Sets.newConcurrentHashSet();
+ private final EdgeWeigher<V, E> weigher;
+
+ private InnerEdgeWeigher(EdgeWeigher<V, E> weigher) {
+ this.weigher = weigher;
+ }
+
+ @Override
+ public Weight weight(E edge) {
+ if (excluded.contains(edge)) {
+ return weigher.getNonViableWeight();
+ }
+ return weigher.weight(edge);
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return weigher.getInitialWeight();
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return weigher.getNonViableWeight();
+ }
+ }
+
+ /**
+ * Provides a comparator to order the set of paths.
+ * Compare by cost, then by hop count.
+ */
+ private final class PathComparator implements Comparator<Path<V, E>> {
+
+ @Override
+ public int compare(Path<V, E> pathOne, Path<V, E> pathTwo) {
+ return ComparisonChain.start()
+ .compare(pathOne.cost(), pathTwo.cost())
+ .compare(pathOne.edges().size(), pathTwo.edges().size())
+ .result();
+ }
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/LazyKShortestPathsSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/LazyKShortestPathsSearchTest.java
new file mode 100644
index 0000000..a0a175f
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/LazyKShortestPathsSearchTest.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onlab.graph;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.hamcrest.Matchers.containsInAnyOrder;
+import static org.junit.Assert.*;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import com.google.common.collect.ImmutableList;
+
+public class LazyKShortestPathsSearchTest extends GraphTest {
+
+ LazyKShortestPathsSearch<TestVertex, TestEdge> sut;
+
+ @Before
+ public void setUp() {
+ sut = new LazyKShortestPathsSearch<>();
+ }
+
+ @Test
+ public void noPath() {
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B),
+ new TestEdge(B, A),
+ new TestEdge(C, D),
+ new TestEdge(D, C)));
+ Stream<Path<TestVertex, TestEdge>> result = sut.lazyPathSearch(graph, A, D, weigher);
+ assertEquals("There should not be any paths.", 0, result.count());
+ }
+
+ @Test
+ public void fourPath() {
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
+ Stream<Path<TestVertex, TestEdge>> result = sut.lazyPathSearch(graph, A, E, weigher);
+ List<Path<TestVertex, TestEdge>> rList = result.limit(42).collect(Collectors.toList());
+
+ assertEquals("There are an unexpected number of paths.", 4, rList.size());
+
+ // The shortest path
+ List<TestEdge> expectedEdges = new ArrayList<>();
+ expectedEdges.add(new TestEdge(A, B, W1));
+ expectedEdges.add(new TestEdge(B, C, W1));
+ expectedEdges.add(new TestEdge(C, E, W1));
+
+ assertEquals("The first path from A to E was incorrect.",
+ expectedEdges, rList.get(0).edges());
+ assertEquals(W3, rList.get(0).cost());
+
+
+ // There are two paths of equal cost as next shortest path
+ expectedEdges.clear();
+ expectedEdges.add(new TestEdge(A, C, W3));
+ expectedEdges.add(new TestEdge(C, E, W1));
+
+ List<TestEdge> alternateEdges = new ArrayList<>();
+ alternateEdges.add(new TestEdge(A, B, W1));
+ alternateEdges.add(new TestEdge(B, D, W2));
+ alternateEdges.add(new TestEdge(D, E, W1));
+
+ assertThat(ImmutableList.of(rList.get(1).edges(), rList.get(2).edges()),
+ containsInAnyOrder(expectedEdges, alternateEdges));
+ assertEquals(W4, rList.get(1).cost());
+ assertEquals(W4, rList.get(2).cost());
+
+
+ // last shortest path
+ expectedEdges.clear();
+ expectedEdges.add(new TestEdge(A, B, W1));
+ expectedEdges.add(new TestEdge(B, E, W4));
+
+ assertEquals("The fourth path rom A to E was incorrect",
+ expectedEdges, rList.get(3).edges());
+ assertEquals(W5, rList.get(3).cost());
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
index d0fa7fc..361c87f 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
@@ -81,4 +81,9 @@
public boolean isNegative() {
return value < 0;
}
+
+ @Override
+ public String toString() {
+ return String.valueOf(value);
+ }
}