Add K-shortest path API to PathService.
Change-Id: I96732666f31a7a2b2df9a16f63e77bc0a367da83
diff --git a/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java b/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
index 2c43fc7..35b9fce 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/AbstractPathService.java
@@ -39,6 +39,7 @@
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.stream.Stream;
import static com.google.common.base.Preconditions.checkNotNull;
import static org.onosproject.net.topology.AdapterLinkWeigher.adapt;
@@ -105,6 +106,40 @@
}
@Override
+ public Stream<Path> getKShortestPaths(ElementId src, ElementId dst,
+ LinkWeigher weigher) {
+ checkNotNull(src, ELEMENT_ID_NULL);
+ checkNotNull(dst, ELEMENT_ID_NULL);
+
+ LinkWeigher internalWeigher = weigher != null ? weigher : DEFAULT_WEIGHER;
+
+ // Get the source and destination edge locations
+ EdgeLink srcEdge = getEdgeLink(src, true);
+ EdgeLink dstEdge = getEdgeLink(dst, false);
+
+ // If either edge is null, bail with no paths.
+ if (srcEdge == null || dstEdge == null) {
+ return Stream.empty();
+ }
+
+ DeviceId srcDevice = srcEdge != NOT_HOST ? srcEdge.dst().deviceId() : (DeviceId) src;
+ DeviceId dstDevice = dstEdge != NOT_HOST ? dstEdge.src().deviceId() : (DeviceId) dst;
+
+ // If the source and destination are on the same edge device, there
+ // is just one path, so build it and return it.
+ if (srcDevice.equals(dstDevice)) {
+ return Stream.of(edgeToEdgePath(srcEdge, dstEdge, null, internalWeigher));
+ }
+
+ // Otherwise get all paths between the source and destination edge
+ // devices.
+ Topology topology = topologyService.currentTopology();
+
+ return topologyService.getKShortestPaths(topology, srcDevice, dstDevice, internalWeigher)
+ .map(path -> edgeToEdgePath(srcEdge, dstEdge, path, internalWeigher));
+ }
+
+ @Override
public Set<DisjointPath> getDisjointPaths(ElementId src, ElementId dst, LinkWeight weight) {
return getDisjointPaths(src, dst, adapt(weight));
}
diff --git a/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java b/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java
new file mode 100644
index 0000000..efcba8c
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/topology/HopCountLinkWeigher.java
@@ -0,0 +1,73 @@
+/*
+ * 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.onosproject.net.topology;
+
+import static org.onosproject.net.Link.State.ACTIVE;
+import static org.onosproject.net.Link.Type.INDIRECT;
+
+import org.onlab.graph.ScalarWeight;
+import org.onlab.graph.Weight;
+
+/**
+ * Link weight for measuring link cost as hop count with indirect links
+ * being as expensive as traversing the entire graph to assume the worst.
+ */
+public class HopCountLinkWeigher implements LinkWeigher {
+
+ public static final LinkWeigher DEFAULT_HOP_COUNT_WEIGHER = new HopCountLinkWeigher();
+
+ private static final ScalarWeight ZERO = new ScalarWeight(0.0);
+ private static final ScalarWeight ONE = new ScalarWeight(1.0);
+ private static final ScalarWeight DEFAULT_INDIRECT = new ScalarWeight(Short.MAX_VALUE);
+
+ private final ScalarWeight indirectLinkCost;
+
+ /**
+ * Creates a new hop-count weight.
+ */
+ public HopCountLinkWeigher() {
+ this.indirectLinkCost = DEFAULT_INDIRECT;
+ }
+
+ /**
+ * Creates a new hop-count weight with the specified cost of indirect links.
+ *
+ * @param indirectLinkCost indirect link cost
+ */
+ public HopCountLinkWeigher(double indirectLinkCost) {
+ this.indirectLinkCost = new ScalarWeight(indirectLinkCost);
+ }
+
+ @Override
+ public Weight weight(TopologyEdge edge) {
+ if (edge.link().state() == ACTIVE) {
+ return edge.link().type() == INDIRECT ? indirectLinkCost : ONE;
+ } else {
+ return getNonViableWeight();
+ }
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return ZERO;
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return ScalarWeight.NON_VIABLE_WEIGHT;
+ }
+
+}
diff --git a/core/api/src/main/java/org/onosproject/net/topology/PathService.java b/core/api/src/main/java/org/onosproject/net/topology/PathService.java
index adfca3d..1530649 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/PathService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/PathService.java
@@ -20,8 +20,11 @@
import org.onosproject.net.Link;
import org.onosproject.net.Path;
+import static org.onosproject.net.topology.HopCountLinkWeigher.DEFAULT_HOP_COUNT_WEIGHER;
+
import java.util.Map;
import java.util.Set;
+import java.util.stream.Stream;
/**
* Service for obtaining pre-computed paths or for requesting computation of
@@ -68,6 +71,33 @@
Set<Path> getPaths(ElementId src, ElementId dst, LinkWeigher weigher);
/**
+ * Returns the k-shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(ElementId src, ElementId dst) {
+ return getKShortestPaths(src, dst, DEFAULT_HOP_COUNT_WEIGHER);
+ }
+
+ /**
+ * Returns the k-shortest paths between source and
+ * destination devices.
+ *
+ * @param src source device
+ * @param dst destination device
+ * @param weigher edge-weight entity
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(ElementId src, ElementId dst,
+ LinkWeigher weigher) {
+ return getPaths(src, dst, weigher).stream();
+ }
+
+
+ /**
* Returns the set of all disjoint shortest path pairs between the
* specified source and destination elements. The path is computed using
* the default edge-weight function, which by default is hop-count.
diff --git a/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java b/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
index 76ae91e..70a38f9 100644
--- a/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
+++ b/core/api/src/main/java/org/onosproject/net/topology/TopologyService.java
@@ -23,6 +23,8 @@
import org.onosproject.net.Link;
import org.onosproject.net.Path;
+import static org.onosproject.net.topology.HopCountLinkWeigher.DEFAULT_HOP_COUNT_WEIGHER;
+
import java.util.Map;
import java.util.Set;
import java.util.stream.Stream;
@@ -158,8 +160,19 @@
* Returns 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 topology topology descriptor
+ * @param src source device
+ * @param dst destination device
+ * @return stream of k-shortest paths
+ */
+ default Stream<Path> getKShortestPaths(Topology topology,
+ DeviceId src, DeviceId dst) {
+ return getKShortestPaths(topology, src, dst, DEFAULT_HOP_COUNT_WEIGHER);
+ }
+
+ /**
+ * Returns the k-shortest paths between source and
+ * destination devices.
*
* @param topology topology descriptor
* @param src source device