ONOS-6225 Expose k-shortest path search as part of TopologyService.
Change-Id: Idf812a707aba0b972fcfbde871c624dfc86b6e1b
diff --git a/core/common/src/main/java/org/onosproject/common/DefaultTopology.java b/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
index 53bebb6..dd2f3a9 100644
--- a/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
+++ b/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
@@ -27,12 +27,15 @@
import org.onlab.graph.DisjointPathPair;
import org.onlab.graph.GraphPathSearch;
import org.onlab.graph.GraphPathSearch.Result;
+import org.onlab.graph.KShortestPathsSearch;
+import org.onlab.graph.LazyKShortestPathsSearch;
import org.onlab.graph.ScalarWeight;
import org.onlab.graph.SrlgGraphSearch;
import org.onlab.graph.SuurballeGraphSearch;
import org.onlab.graph.TarjanGraphSearch;
import org.onlab.graph.TarjanGraphSearch.SccResult;
import org.onlab.graph.Weight;
+import org.onlab.util.GuavaCollectors;
import org.onosproject.net.AbstractModel;
import org.onosproject.net.ConnectPoint;
import org.onosproject.net.DefaultDisjointPath;
@@ -62,6 +65,7 @@
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
+import java.util.stream.Stream;
import static com.google.common.base.MoreObjects.toStringHelper;
import static com.google.common.base.Preconditions.checkArgument;
@@ -86,6 +90,11 @@
new TarjanGraphSearch<>();
private static final SuurballeGraphSearch<TopologyVertex, TopologyEdge> SUURBALLE =
new SuurballeGraphSearch<>();
+ private static final KShortestPathsSearch<TopologyVertex, TopologyEdge> KSHORTEST =
+ new KShortestPathsSearch<>();
+ private static final LazyKShortestPathsSearch<TopologyVertex, TopologyEdge> LAZY_KSHORTEST =
+ new LazyKShortestPathsSearch<>();
+
private static LinkWeigher defaultLinkWeigher = null;
private static GraphPathSearch<TopologyVertex, TopologyEdge> defaultGraphPathSearch = null;
@@ -387,7 +396,88 @@
}
/**
- * /**
+ * Computes on-demand the k-shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param maxPaths maximum number of paths (k)
+ * @return set of k-shortest paths
+ */
+ public Set<Path> getKShortestPaths(DeviceId src, DeviceId dst,
+ int maxPaths) {
+
+ return getKShortestPaths(src, dst, linkWeight(), maxPaths);
+ }
+
+ /**
+ * Computes on-demand the k-shortest paths between source and
+ * destination devices.
+ *
+ * The first {@code maxPaths} paths will be returned
+ * in ascending order according to the provided {@code weigher}
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weigher link weight function
+ * @param maxPaths maximum number of paths (k)
+ * @return set of k-shortest paths
+ */
+ public Set<Path> getKShortestPaths(DeviceId src, DeviceId dst,
+ LinkWeigher weigher,
+ int maxPaths) {
+ DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+ DefaultTopologyVertex dstV = new DefaultTopologyVertex(dst);
+ Set<TopologyVertex> vertices = graph.getVertexes();
+ if (!vertices.contains(srcV) || !vertices.contains(dstV)) {
+ // src or dst not part of the current graph
+ return ImmutableSet.of();
+ }
+
+ return KSHORTEST.search(graph, srcV, dstV, weigher, maxPaths)
+ .paths().stream()
+ .map(this::networkPath)
+ .collect(GuavaCollectors.toImmutableSet());
+ }
+
+ /**
+ * Lazily computes on-demand the k-shortest paths between source and
+ * destination devices.
+ *
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return stream of k-shortest paths
+ */
+ public Stream<Path> getKShortestPaths(DeviceId src, DeviceId dst) {
+ return getKShortestPaths(src, dst, linkWeight());
+ }
+
+ /**
+ * Lazily computes on-demand the k-shortest paths between source and
+ * destination devices.
+ *
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weigher link weight function
+ * @return stream of k-shortest paths
+ */
+ public Stream<Path> getKShortestPaths(DeviceId src, DeviceId dst,
+ LinkWeigher weigher) {
+ DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+ DefaultTopologyVertex dstV = new DefaultTopologyVertex(dst);
+ Set<TopologyVertex> vertices = graph.getVertexes();
+ if (!vertices.contains(srcV) || !vertices.contains(dstV)) {
+ // src or dst not part of the current graph
+ return Stream.empty();
+ }
+
+ return LAZY_KSHORTEST.lazyPathSearch(graph, srcV, dstV, weigher)
+ .map(this::networkPath);
+ }
+
+ /**
* Returns the set of pre-computed shortest disjoint path pairs between
* source and destination devices.
*
diff --git a/core/common/src/test/java/org/onosproject/common/DefaultTopologyTest.java b/core/common/src/test/java/org/onosproject/common/DefaultTopologyTest.java
index 48403d5..481e7f7 100644
--- a/core/common/src/test/java/org/onosproject/common/DefaultTopologyTest.java
+++ b/core/common/src/test/java/org/onosproject/common/DefaultTopologyTest.java
@@ -40,7 +40,6 @@
import org.onosproject.net.topology.TopologyVertex;
import java.util.Set;
-
import static com.google.common.collect.ImmutableSet.of;
import static org.junit.Assert.*;
import static org.onosproject.net.DeviceId.deviceId;
@@ -121,6 +120,12 @@
paths = dt.getPaths(D1, D3, WEIGHER);
assertEquals("incorrect path count", 1, paths.size());
+
+ paths = dt.getKShortestPaths(D1, D2, 42);
+ assertEquals("incorrect path count", 2, paths.size());
+
+ assertEquals("incorrect path count", 2, dt.getKShortestPaths(D1, D2).limit(42).count());
+
}
@Test