aboutsummaryrefslogtreecommitdiffstats
path: root/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
diff options
context:
space:
mode:
Diffstat (limited to 'framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java')
-rw-r--r--framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java253
1 files changed, 253 insertions, 0 deletions
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
new file mode 100644
index 00000000..fa3d0ddf
--- /dev/null
+++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
@@ -0,0 +1,253 @@
+/*
+ * Copyright 2014 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 java.util.Map;
+import java.util.List;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.Random;
+
+
+/**
+ * SRLG Graph Search finds a pair of paths with disjoint risk groups; i.e
+ * if one path goes through an edge in risk group 1, the other path will go
+ * through no edges in risk group 1.
+ */
+public class SrlgGraphSearch<V extends Vertex, E extends Edge<V>>
+ extends AbstractGraphPathSearch<V, E> {
+
+ static final int ITERATIONS = 100;
+ static final int POPSIZE = 50;
+
+ boolean useSuurballe = false;
+
+ static final double INF = 100000000.0;
+
+ int numGroups;
+ Map<E, Integer> riskGrouping;
+
+ Graph<V, E> orig;
+ V src, dst;
+ EdgeWeight<V, E> weight;
+
+ /**
+ * Creates an SRLG graph search object with the given number
+ * of groups and given risk mapping.
+ *
+ * @param groups the number of disjoint risk groups
+ * @param grouping map linking edges to integral group assignments
+ */
+ public SrlgGraphSearch(int groups, Map<E, Integer> grouping) {
+ numGroups = groups;
+ riskGrouping = grouping;
+ }
+
+ /**
+ * Creates an SRLG graph search object from a map, inferring
+ * the number of groups and creating an integral mapping.
+ *
+ * @param grouping map linking edges to object group assignments,
+ * with same-group status linked to equality
+ */
+ public SrlgGraphSearch(Map<E, Object> grouping) {
+ if (grouping == null) {
+ useSuurballe = true;
+ return;
+ }
+ numGroups = 0;
+ HashMap<Object, Integer> tmpMap = new HashMap<>();
+ riskGrouping = new HashMap<>();
+ for (E key: grouping.keySet()) {
+ Object value = grouping.get(key);
+ if (!tmpMap.containsKey(value)) {
+ tmpMap.put(value, numGroups);
+ numGroups++;
+ }
+ riskGrouping.put(key, tmpMap.get(value));
+ }
+ }
+
+ @Override
+ public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+ EdgeWeight<V, E> weight, int maxPaths) {
+ if (maxPaths == ALL_PATHS) {
+ maxPaths = POPSIZE;
+ }
+ if (useSuurballe) {
+ return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS);
+ }
+ if (weight == null) {
+ weight = edge -> 1;
+ }
+ checkArguments(graph, src, dst);
+ orig = graph;
+ this.src = src;
+ this.dst = dst;
+ this.weight = weight;
+ List<Subset> best = new GAPopulation<Subset>()
+ .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups]));
+ Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>();
+ for (Subset s: best) {
+ dpps.addAll(s.buildPaths());
+ }
+ Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>()
+ .search(orig, src, dst, weight, 1);
+ return new Result<V, E>() {
+ final DefaultResult search = (DefaultResult) firstDijkstra;
+
+ public V src() {
+ return src;
+ }
+ public V dst() {
+ return dst;
+
+ }
+ public Set<Path<V, E>> paths() {
+ Set<Path<V, E>> pathsD = new HashSet<>();
+ for (DisjointPathPair<V, E> path: dpps) {
+ pathsD.add(path);
+ }
+ return pathsD;
+ }
+ public Map<V, Double> costs() {
+ return search.costs();
+
+ }
+ public Map<V, Set<E>> parents() {
+ return search.parents();
+
+ }
+ };
+ }
+
+ //finds the shortest path in the graph given a subset of edge types to use
+ private Result<V, E> findShortestPathFromSubset(boolean[] subset) {
+ Graph<V, E> graph = orig;
+ EdgeWeight<V, E> modified = new EdgeWeight<V, E>() {
+ final boolean[] subsetF = subset;
+
+ @Override
+ public double weight(E edge) {
+ if (subsetF[riskGrouping.get(edge)]) {
+ return weight.weight(edge);
+ }
+ return INF;
+ }
+ };
+
+ Result<V, E> res = new DijkstraGraphSearch<V, E>().search(graph, src, dst, modified, 1);
+ return res;
+ }
+ /**
+ * A subset is a type of GA organism that represents a subset of allowed shortest
+ * paths (and its complement). Its fitness is determined by the sum of the weights
+ * of the first two shortest paths.
+ */
+ class Subset implements GAOrganism {
+
+ boolean[] subset;
+ boolean[] not;
+ Random r = new Random();
+
+ /**
+ * Creates a Subset from the given subset array.
+ *
+ * @param sub subset array
+ */
+ public Subset(boolean[] sub) {
+ subset = sub.clone();
+ not = new boolean[subset.length];
+ for (int i = 0; i < subset.length; i++) {
+ not[i] = !subset[i];
+ }
+ }
+
+ @Override
+ public double fitness() {
+ Set<Path<V, E>> paths1 = findShortestPathFromSubset(subset).paths();
+ Set<Path<V, E>> paths2 = findShortestPathFromSubset(not).paths();
+ if (paths1.size() == 0 || paths2.size() == 0) {
+ return INF;
+ }
+ return paths1.iterator().next().cost() + paths2.iterator().next().cost();
+ }
+
+ @Override
+ public void mutate() {
+ int turns = r.nextInt((int) Math.sqrt(subset.length));
+ while (turns > 0) {
+ int choose = r.nextInt(subset.length);
+ subset[choose] = !subset[choose];
+ not[choose] = !not[choose];
+ turns--;
+ }
+ }
+
+ @Override
+ public GAOrganism crossWith(GAOrganism org) {
+ if (!(org.getClass().equals(getClass()))) {
+ return this;
+ }
+ Subset other = (Subset) (org);
+ boolean[] sub = new boolean[subset.length];
+ for (int i = 0; i < subset.length; i++) {
+ sub[i] = subset[i];
+ if (r.nextBoolean()) {
+ sub[i] = other.subset[i];
+ }
+ }
+ return new Subset(sub);
+ }
+
+ @Override
+ public GAOrganism random() {
+ boolean[] sub = new boolean[subset.length];
+ for (int i = 0; i < sub.length; i++) {
+ sub[i] = r.nextBoolean();
+ }
+ return new Subset(sub);
+ }
+
+ /**
+ * Builds the set of disjoint path pairs for a given subset
+ * using Dijkstra's algorithm on both the subset and complement
+ * and returning all pairs with one from each set.
+ *
+ * @return all shortest disjoint paths given this subset
+ */
+ public Set<DisjointPathPair> buildPaths() {
+ Set<DisjointPathPair> dpps = new HashSet<>();
+ for (Path<V, E> path1: findShortestPathFromSubset(subset).paths()) {
+ if (path1.cost() >= INF) {
+ continue;
+ }
+ for (Path<V, E> path2: findShortestPathFromSubset(not).paths()) {
+ if (path2.cost() >= INF) {
+ continue;
+ }
+ DisjointPathPair<V, E> dpp = new DisjointPathPair<>(path1, path2);
+ dpps.add(dpp);
+ }
+ }
+ return dpps;
+ }
+ }
+}