1 files changed, 135 insertions, 5 deletions

diff --git a/framework/src/onos/core/common/src/main/java/org/onosproject/common/DefaultTopology.java b/framework/src/onos/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
index bdf7d732..3c5c540d 100644
--- a/framework/src/onos/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
+++ b/framework/src/onos/core/common/src/main/java/org/onosproject/common/DefaultTopology.java
@@ -23,14 +23,19 @@ import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSetMultimap;
 import com.google.common.collect.ImmutableSetMultimap.Builder;
 import org.onlab.graph.DijkstraGraphSearch;
+import org.onlab.graph.DisjointPathPair;
 import org.onlab.graph.GraphPathSearch;
 import org.onlab.graph.GraphPathSearch.Result;
+import org.onlab.graph.SRLGGraphSearch;
+import org.onlab.graph.SuurballeGraphSearch;
 import org.onlab.graph.TarjanGraphSearch;
 import org.onlab.graph.TarjanGraphSearch.SCCResult;
 import org.onosproject.net.AbstractModel;
 import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.DefaultDisjointPath;
 import org.onosproject.net.DefaultPath;
 import org.onosproject.net.DeviceId;
+import org.onosproject.net.DisjointPath;
 import org.onosproject.net.Link;
 import org.onosproject.net.Path;
 import org.onosproject.net.provider.ProviderId;
@@ -45,10 +50,11 @@ import org.onosproject.net.topology.TopologyEdge;
 import org.onosproject.net.topology.TopologyGraph;
 import org.onosproject.net.topology.TopologyVertex;
 
-import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.stream.Collectors;
 
 import static com.google.common.base.MoreObjects.toStringHelper;
 import static com.google.common.base.Preconditions.checkArgument;
@@ -67,6 +73,9 @@ public class DefaultTopology extends AbstractModel implements Topology {
 
     private static final DijkstraGraphSearch<TopologyVertex, TopologyEdge> DIJKSTRA = new DijkstraGraphSearch<>();
     private static final TarjanGraphSearch<TopologyVertex, TopologyEdge> TARJAN = new TarjanGraphSearch<>();
+    private static final SuurballeGraphSearch<TopologyVertex, TopologyEdge> SUURBALLE =
+            new SuurballeGraphSearch<>();
+
 
     private final long time;
     private final long creationTime;
@@ -315,15 +324,135 @@ public class DefaultTopology extends AbstractModel implements Topology {
         return builder.build();
     }
 
+    /**
+     * /**
+     * Returns the set of pre-computed shortest disjoint path pairs between source and
+     * destination devices.
+     *
+     * @param src source device
+     * @param dst destination device
+     * @return set of shortest disjoint path pairs
+     */
+    public Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst) {
+        return getDisjointPaths(src, dst, (LinkWeight) null);
+    }
+
+    /**
+     * Computes on-demand the set of shortest disjoint path pairs between source and
+     * destination devices.
+     *
+     * @param src    source device
+     * @param dst    destination device
+     * @param weight link weight function
+     * @return set of disjoint shortest path pairs
+     */
+    public Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst, LinkWeight weight) {
+        final DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+        final 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();
+        }
+
+        GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
+                SUURBALLE.search(graph, srcV, dstV, weight, ALL_PATHS);
+        ImmutableSet.Builder<DisjointPath> builder = ImmutableSet.builder();
+        for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+            builder.add(networkDisjointPath((org.onlab.graph.DisjointPathPair<TopologyVertex, TopologyEdge>) path));
+        }
+        return builder.build();
+    }
+
+    /**
+     * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+     * destination devices.
+     *
+     * @param src         source device
+     * @param dst         destination device
+     * @param weight      edge weight object
+     * @param riskProfile map representing risk groups for each edge
+     * @return set of shortest disjoint paths
+     */
+    private Set<DisjointPath> disjointPaths(DeviceId src, DeviceId dst, LinkWeight weight,
+                                                Map<TopologyEdge, Object> riskProfile) {
+        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();
+        }
+
+        SRLGGraphSearch<TopologyVertex, TopologyEdge> srlg = new SRLGGraphSearch<>(riskProfile);
+        GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
+                srlg.search(graph, srcV, dstV, weight, ALL_PATHS);
+        ImmutableSet.Builder<DisjointPath> builder = ImmutableSet.builder();
+        for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
+            builder.add(networkDisjointPath((org.onlab.graph.DisjointPathPair<TopologyVertex, TopologyEdge>) path));
+        }
+        return builder.build();
+    }
+
+    /**
+     * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+     * destination devices.
+     *
+     * @param src         source device
+     * @param dst         destination device
+     * @param weight      edge weight object
+     * @param riskProfile map representing risk groups for each link
+     * @return set of shortest disjoint paths
+     */
+    public Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst, LinkWeight weight,
+                                              Map<Link, Object> riskProfile) {
+        Map<TopologyEdge, Object> riskProfile2 = new HashMap<>();
+        for (Link l : riskProfile.keySet()) {
+            riskProfile2.put(new TopologyEdge() {
+                Link cur = l;
+
+                public Link link() {
+                    return cur;
+                }
+
+                public TopologyVertex src() {
+                    return () -> src;
+                }
+
+                public TopologyVertex dst() {
+                    return () -> dst;
+                }
+            }, riskProfile.get(l));
+        }
+        return disjointPaths(src, dst, weight, riskProfile2);
+    }
+
+    /**
+     * Computes on-demand the set of shortest disjoint risk groups path pairs between source and
+     * destination devices.
+     *
+     * @param src         source device
+     * @param dst         destination device
+     * @param riskProfile map representing risk groups for each link
+     * @return set of shortest disjoint paths
+     */
+    public Set<DisjointPath> getDisjointPaths(DeviceId src, DeviceId dst, Map<Link, Object> riskProfile) {
+        return getDisjointPaths(src, dst, null, riskProfile);
+    }
+
     // Converts graph path to a network path with the same cost.
     private Path networkPath(org.onlab.graph.Path<TopologyVertex, TopologyEdge> path) {
-        List<Link> links = new ArrayList<>();
-        for (TopologyEdge edge : path.edges()) {
-            links.add(edge.link());
-        }
+        List<Link> links = path.edges().stream().map(TopologyEdge::link).collect(Collectors.toList());
         return new DefaultPath(CORE_PROVIDER_ID, links, path.cost());
     }
 
+    private DisjointPath networkDisjointPath(DisjointPathPair<TopologyVertex, TopologyEdge> path) {
+        return new DefaultDisjointPath(CORE_PROVIDER_ID,
+                                       (DefaultPath) networkPath(path.primary()),
+                                       (DefaultPath) networkPath(path.secondary()));
+    }
+
     // Searches for SCC clusters in the network topology graph using Tarjan
     // algorithm.
     private SCCResult<TopologyVertex, TopologyEdge> searchForClusters() {
@@ -334,6 +463,7 @@ public class DefaultTopology extends AbstractModel implements Topology {
     private ImmutableMap<ClusterId, TopologyCluster> buildTopologyClusters() {
         ImmutableMap.Builder<ClusterId, TopologyCluster> clusterBuilder = ImmutableMap.builder();
         SCCResult<TopologyVertex, TopologyEdge> results = clusterResults.get();
+
         // Extract both vertexes and edges from the results; the lists form
         // pairs along the same index.
         List<Set<TopologyVertex>> clusterVertexes = results.clusterVertexes();