Disjoint Path Pairs (Suurballe) utils
Change-Id: Ie5895899818ea9d6eacf66cbb589ddf33fa3f89d
Disjoint Path Pairs (Suurballe) utils
Change-Id: Ie5895899818ea9d6eacf66cbb589ddf33fa3f89d
Disjoint Path Pairs (SRLG with GA) utils
Change-Id: If072df987621add385ae785f10c8d0a9e45ad559
diff --git a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
new file mode 100644
index 0000000..b62d3b2
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
@@ -0,0 +1,128 @@
+/*
+ * Copyright 2015 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.List;
+import java.util.Objects;
+import java.util.Set;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+
+public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Path<V, E> {
+ public Path<V, E> path1, path2;
+ boolean usingPath1 = true;
+
+ /**
+ * Creates a Disjoint Path Pair from two paths.
+ *
+ * @param p1 first path
+ * @param p2 second path
+ */
+ public DisjointPathPair(Path<V, E> p1, Path<V, E> p2) {
+ path1 = p1;
+ path2 = p2;
+ }
+
+ @Override
+ public V src() {
+ return path1.src();
+ }
+
+ @Override
+ public V dst() {
+ return path1.dst();
+ }
+
+ @Override
+ public double cost() {
+ if (!hasBackup()) {
+ return path1.cost();
+ }
+ return path1.cost() + path2.cost();
+ }
+
+ @Override
+ public List<E> edges() {
+ if (usingPath1 || !hasBackup()) {
+ return path1.edges();
+ } else {
+ return path2.edges();
+ }
+ }
+
+ /**
+ * Checks if this path pair contains a backup/secondary path.
+ *
+ * @return boolean representing whether it has backup
+ */
+ public boolean hasBackup() {
+ return path2 != null && path2.edges() != null;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this)
+ .add("src", src())
+ .add("dst", dst())
+ .add("cost", cost())
+ .add("edges", edges())
+ .toString();
+ }
+
+ @Override
+ public int hashCode() {
+ Set<Path<V, E>> paths;
+ if (!hasBackup()) {
+ paths = of(path1);
+ } else {
+ paths = of(path1, path2);
+ }
+ return Objects.hash(paths);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof DisjointPathPair) {
+ final DisjointPathPair other = (DisjointPathPair) obj;
+ return Objects.equals(this.src(), other.src()) &&
+ Objects.equals(this.dst(), other.dst()) &&
+ (Objects.equals(this.path1, other.path1) &&
+ Objects.equals(this.path2, other.path2)) ||
+ (Objects.equals(this.path1, other.path2) &&
+ Objects.equals(this.path2, other.path1));
+ }
+ return false;
+ }
+
+ /**
+ * Returns number of paths inside this path pair object.
+ *
+ * @return number of paths
+ */
+ public int size() {
+ if (hasBackup()) {
+ return 2;
+ }
+ return 1;
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java.orig b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java.orig
new file mode 100644
index 0000000..1cf22b6
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java.orig
@@ -0,0 +1,169 @@
+/*
+ * Copyright 2015 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.List;
+import java.util.Objects;
+import java.util.Set;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+
+public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Path<V, E> {
+ public Path<V, E> path1, path2;
+ boolean usingPath1 = true;
+
+<<<<<<< HEAD
+ /**
+ * Creates a Disjoint Path Pair from two paths.
+ *
+ * @param p1 first path
+ * @param p2 second path
+ */
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public DisjointPathPair(Path<V, E> p1, Path<V, E> p2) {
+ path1 = p1;
+ path2 = p2;
+ }
+<<<<<<< HEAD
+
+ @Override
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public V src() {
+ return path1.src();
+ }
+
+<<<<<<< HEAD
+ @Override
+ public V dst() {
+ return path1.dst();
+ }
+
+ @Override
+=======
+ public V dst() {
+ return path1.dst();
+ }
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public double cost() {
+ if (!hasBackup()) {
+ return path1.cost();
+ }
+ return path1.cost() + path2.cost();
+ }
+<<<<<<< HEAD
+
+ @Override
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public List<E> edges() {
+ if (usingPath1 || !hasBackup()) {
+ return path1.edges();
+ } else {
+ return path2.edges();
+ }
+ }
+<<<<<<< HEAD
+
+ /**
+ * Checks if this path pair contains a backup/secondary path.
+ *
+ * @return boolean representing whether it has backup
+ */
+ public boolean hasBackup() {
+ return path2 != null && path2.edges() != null;
+ }
+
+ /**
+ * Switches this disjoint path pair to using its backup path, instead of
+ * using its primary.
+ */
+ public void useBackup() {
+ usingPath1 = !usingPath1;
+ }
+
+ @Override
+=======
+ public boolean hasBackup() {
+ return path2 != null && path2.edges() != null;
+ }
+ public void useBackup() {
+ usingPath1 = !usingPath1;
+ }
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public String toString() {
+ return toStringHelper(this)
+ .add("src", src())
+ .add("dst", dst())
+ .add("cost", cost())
+ .add("edges", edges())
+ .toString();
+ }
+<<<<<<< HEAD
+
+ @Override
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public int hashCode() {
+ Set<Path<V, E>> paths;
+ if (!hasBackup()) {
+ paths = of(path1);
+ } else {
+ paths = of(path1, path2);
+ }
+ return Objects.hash(paths);
+ }
+<<<<<<< HEAD
+
+ @Override
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof DisjointPathPair) {
+ final DisjointPathPair other = (DisjointPathPair) obj;
+ return Objects.equals(this.src(), other.src()) &&
+ Objects.equals(this.dst(), other.dst()) &&
+ (Objects.equals(this.path1, other.path1) &&
+ Objects.equals(this.path2, other.path2)) ||
+ (Objects.equals(this.path1, other.path2) &&
+ Objects.equals(this.path2, other.path1));
+ }
+ return false;
+ }
+<<<<<<< HEAD
+
+ /**
+ * Returns number of paths inside this path pair object.
+ *
+ * @return number of paths
+ */
+=======
+>>>>>>> Disjoint Path Pairs (Suurballe) utils
+ public int size() {
+ if (hasBackup()) {
+ return 2;
+ }
+ return 1;
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
new file mode 100644
index 0000000..230609f
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
@@ -0,0 +1,38 @@
+package org.onlab.graph;
+
+/**
+ * Interface representing an "organism": a specific solution
+ * to a problem where solutions can be evaluated in terms
+ * of fitness. These organisms can be used to represent any
+ * class of problem that genetic algorithms can be run on.
+ */
+interface GAOrganism {
+ /**
+ * A fitness function that determines how
+ * optimal a given organism is.
+ *
+ * @return fitness of organism
+ */
+ double fitness();
+
+ /**
+ * A method that slightly mutates an organism.
+ */
+ void mutate();
+
+ /**
+ * Creates a new random organism.
+ *
+ * @return random GAOrganism
+ */
+ GAOrganism random();
+
+ /**
+ * Returns a child organism that is the result
+ * of "crossing" this organism with another.
+ *
+ * @param other Other organism to cross with
+ * @return child organism
+ */
+ GAOrganism crossWith(GAOrganism other);
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
new file mode 100644
index 0000000..ae7f182
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
@@ -0,0 +1,75 @@
+package org.onlab.graph;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+
+/**
+ * Represents a population of GAOrganisms. This class can be used
+ * to run a genetic algorithm on the population and return the fittest solutions.
+ */
+class GAPopulation<Organism extends GAOrganism> extends ArrayList<Organism> {
+ Random r = new Random();
+
+ /**
+ * Steps the population through one generation. The 75% least fit
+ * organisms are killed off and replaced with the children of the
+ * 25% (as well as some "random" newcomers).
+ */
+ void step() {
+ Collections.sort(this, (org1, org2) -> {
+ double d = org1.fitness() - org2.fitness();
+ if (d < 0) {
+ return -1;
+ } else if (d == 0) {
+ return 0;
+ }
+ return 1;
+ });
+ int maxSize = size();
+ for (int i = size() - 1; i > maxSize / 4; i--) {
+ remove(i);
+ }
+ for (Organism org: this) {
+ if (r.nextBoolean()) {
+ org.mutate();
+ }
+ }
+ while (size() < maxSize * 4 / 5) {
+ Organism org1 = get(r.nextInt(size()));
+ Organism org2 = get(r.nextInt(size()));
+ add((Organism) org1.crossWith(org2));
+ }
+
+ while (size() < maxSize) {
+ Organism org1 = get(r.nextInt(size()));
+ add((Organism) org1.random());
+ }
+ }
+
+ /**
+ * Runs GA for the specified number of iterations, and returns
+ * a sample of the resulting population of solutions.
+ *
+ * @param generations Number of generations to run GA for
+ * @param populationSize Population size of GA
+ * @param sample Number of solutions to ask for
+ * @param template Template GAOrganism to seed the population with
+ * @return ArrayList containing sample number of organisms
+ */
+ List<Organism> runGA(int generations, int populationSize, int sample, Organism template) {
+ for (int i = 0; i < populationSize; i++) {
+ add((Organism) template.random());
+ }
+
+ for (int i = 0; i < generations; i++) {
+ step();
+ }
+ for (int i = size() - 1; i >= sample; i--) {
+ remove(i);
+ }
+ return new ArrayList<>(this);
+ }
+}
+
diff --git a/utils/misc/src/main/java/org/onlab/graph/SRLGGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SRLGGraphSearch.java
new file mode 100644
index 0000000..21f687a
--- /dev/null
+++ b/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;
+ }
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
new file mode 100644
index 0000000..76591c8
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
@@ -0,0 +1,193 @@
+/*
+ * Copyright 2015 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.ArrayList;
+import java.util.Set;
+import java.util.List;
+import java.util.Map;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.stream.Collectors;
+
+/**
+ * Suurballe shortest-path graph search algorithm capable of finding both
+ * a shortest path, as well as a backup shortest path, between a source and a destination
+ * such that the sum of the path lengths is minimized.
+ */
+public class SuurballeGraphSearch<V extends Vertex, E extends Edge<V>> extends DijkstraGraphSearch<V, E> {
+
+ @Override
+ public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+ EdgeWeight<V, E> weight, int maxPaths) {
+
+ if (weight == null) {
+ weight = edge -> 1;
+ }
+
+ List<DisjointPathPair<V, E>> dpps = new ArrayList<>();
+
+ final EdgeWeight weightf = weight;
+ DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS);
+ DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS);
+
+ //choose an arbitrary shortest path to run Suurballe on
+ Path<V, E> shortPath = null;
+ if (firstDijkstraS.paths().size() == 0) {
+ return firstDijkstraS;
+ }
+ for (Path p: firstDijkstraS.paths()) {
+ shortPath = p;
+ //transforms the graph so tree edges have 0 weight
+ EdgeWeight<V, Edge<V>> modified = edge -> {
+ if (classE().isInstance(edge)) {
+ return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src())
+ - firstDijkstra.cost(edge.dst());
+ }
+ return 0;
+ };
+ EdgeWeight<V, E> modified2 = edge ->
+ weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
+
+ //create a residual graph g' by removing all src vertices and reversing 0 length path edges
+ MutableGraph<V, Edge<V>> gt = mutableCopy(graph);
+
+ Map<Edge<V>, E> revToEdge = new HashMap<>();
+ graph.getEdgesTo(src).forEach(gt::removeEdge);
+ for (E edge: shortPath.edges()) {
+ gt.removeEdge(edge);
+ Edge<V> reverse = new Edge<V>() {
+ final Edge<V> orig = edge;
+ public V src() {
+ return orig.dst();
+ }
+ public V dst() {
+ return orig.src();
+ }
+ public String toString() {
+ return "ReversedEdge " + "src=" + src() + " dst=" + dst();
+ }
+ };
+ revToEdge.put(reverse, edge);
+ gt.addEdge(reverse);
+ }
+
+ //rerun dijkstra on the temporary graph to get a second path
+ Result<V, Edge<V>> secondDijkstra;
+ secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS);
+
+ Path<V, Edge<V>> residualShortPath = null;
+ if (secondDijkstra.paths().size() == 0) {
+ dpps.add(new DisjointPathPair<V, E>(shortPath, null));
+ continue;
+ }
+
+ for (Path p2: secondDijkstra.paths()) {
+ residualShortPath = p2;
+
+ MutableGraph<V, E> roundTrip = mutableCopy(graph);
+
+ List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList());
+
+ tmp.forEach(roundTrip::removeEdge);
+
+ shortPath.edges().forEach(roundTrip::addEdge);
+
+ if (residualShortPath != null) {
+ for (Edge<V> edge: residualShortPath.edges()) {
+ if (classE().isInstance(edge)) {
+ roundTrip.addEdge((E) edge);
+ } else {
+ roundTrip.removeEdge(revToEdge.get(edge));
+ }
+ }
+ }
+ //Actually build the final result
+ DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS);
+ Path<V, E> path1 = lastSearch.paths().iterator().next();
+ path1.edges().forEach(roundTrip::removeEdge);
+
+ Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths();
+ Path<V, E> backup = null;
+ if (bckpaths.size() != 0) {
+ backup = bckpaths.iterator().next();
+ }
+
+ dpps.add(new DisjointPathPair<>(path1, backup));
+ }
+ }
+
+ for (int i = dpps.size() - 1; i > 0; i--) {
+ if (dpps.get(i).size() <= 1) {
+ dpps.remove(i);
+ }
+ }
+
+ return new Result<V, E>() {
+ final DefaultResult search = firstDijkstra;
+
+ public V src() {
+ return src;
+ }
+ public V dst() {
+ return dst;
+ }
+ public Set<Path<V, E>> paths() {
+ Set<Path<V, E>> pathsD = new HashSet<>();
+ int paths = 0;
+ for (DisjointPathPair<V, E> path: dpps) {
+ pathsD.add((Path<V, E>) path);
+ paths++;
+ if (paths == maxPaths) {
+ break;
+ }
+ }
+ return pathsD;
+ }
+ public Map<V, Double> costs() {
+ return search.costs();
+ }
+ public Map<V, Set<E>> parents() {
+ return search.parents();
+ }
+ };
+ }
+
+ private Class<?> clazzV;
+
+ public Class<?> classV() {
+ return clazzV;
+ }
+
+ private Class<?> clazzE;
+
+ public Class<?> classE() {
+ return clazzE;
+ }
+ /**
+ * Creates a mutable copy of an immutable graph.
+ *
+ * @param graph immutable graph
+ * @return mutable copy
+ */
+ public MutableGraph mutableCopy(Graph<V, E> graph) {
+ clazzV = graph.getVertexes().iterator().next().getClass();
+ clazzE = graph.getEdges().iterator().next().getClass();
+ return new MutableAdjacencyListsGraph<V, E>(graph.getVertexes(), graph.getEdges());
+ }
+}
+
diff --git a/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java
new file mode 100644
index 0000000..885fbe5
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java
@@ -0,0 +1,183 @@
+/*
+ * Copyright 2015 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 org.junit.Test;
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.HashMap;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertTrue;
+
+
+
+/**
+ * Test of the Suurballe backup path algorithm.
+ */
+public class SRLGGraphSearchTest extends BreadthFirstSearchTest {
+ @Override
+ protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
+ return new SRLGGraphSearch<TestVertex, TestEdge>(null);
+ }
+
+ public void setWeights() {
+ weight = new EdgeWeight<TestVertex, TestEdge>() {
+ @Override
+ public double weight(TestEdge edge) {
+ return edge.weight();
+ }
+ };
+ }
+ public void setDefaultWeights() {
+ weight = null;
+ }
+ @Override
+ public void defaultGraphTest() {
+
+ }
+
+ @Override
+ public void defaultHopCountWeight() {
+
+ }
+
+ @Test
+ public void onePathPair() {
+ setDefaultWeights();
+ TestEdge aB = new TestEdge(A, B, 1);
+ TestEdge bC = new TestEdge(B, C, 1);
+ TestEdge aD = new TestEdge(A, D, 1);
+ TestEdge dC = new TestEdge(D, C, 1);
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(aB, bC, aD, dC));
+ Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>();
+ riskProfile.put(aB, 0);
+ riskProfile.put(bC, 0);
+ riskProfile.put(aD, 1);
+ riskProfile.put(dC, 1);
+ SRLGGraphSearch<TestVertex, TestEdge> search =
+ new SRLGGraphSearch<TestVertex, TestEdge>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, GraphPathSearch.ALL_PATHS).paths();
+ System.out.println("\n\n\n" + paths + "\n\n\n");
+ assertTrue("one disjoint path pair found", paths.size() == 1);
+ checkIsDisjoint(paths.iterator().next(), riskProfile);
+ }
+ public void checkIsDisjoint(Path<TestVertex, TestEdge> p, Map<TestEdge, Integer> risks) {
+ assertTrue("The path is not a DisjointPathPair", (p instanceof DisjointPathPair));
+ DisjointPathPair<TestVertex, TestEdge> q = (DisjointPathPair) p;
+ Set<Integer> p1Risks = new HashSet<Integer>();
+ Set<Integer> p2Risks = new HashSet<Integer>();
+ for (TestEdge e: q.edges()) {
+ p1Risks.add(risks.get(e));
+ }
+ if (!q.hasBackup()) {
+ return;
+ }
+ Path<TestVertex, TestEdge> pq = q.path2;
+ for (TestEdge e: pq.edges()) {
+ assertTrue("The paths are not disjoint", !p1Risks.contains(risks.get(e)));
+ }
+ }
+ @Test
+ public void complexGraphTest() {
+ setDefaultWeights();
+ TestEdge aB = new TestEdge(A, B, 1);
+ TestEdge bC = new TestEdge(B, C, 1);
+ TestEdge aD = new TestEdge(A, D, 1);
+ TestEdge dC = new TestEdge(D, C, 1);
+ TestEdge cE = new TestEdge(C, E, 1);
+ TestEdge bE = new TestEdge(B, E, 1);
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(aB, bC, aD, dC, cE, bE));
+ Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>();
+ riskProfile.put(aB, 0);
+ riskProfile.put(bC, 0);
+ riskProfile.put(aD, 1);
+ riskProfile.put(dC, 1);
+ riskProfile.put(cE, 2);
+ riskProfile.put(bE, 3);
+ SRLGGraphSearch<TestVertex, TestEdge> search =
+ new SRLGGraphSearch<TestVertex, TestEdge>(4, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths();
+ }
+
+ @Test
+ public void multiplePathGraphTest() {
+ setDefaultWeights();
+ TestEdge aB = new TestEdge(A, B, 1);
+ TestEdge bE = new TestEdge(B, E, 1);
+ TestEdge aD = new TestEdge(A, D, 1);
+ TestEdge dE = new TestEdge(D, E, 1);
+ TestEdge aC = new TestEdge(A, C, 1);
+ TestEdge cE = new TestEdge(C, E, 1);
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(aB, bE, aD, dE, aC, cE));
+ Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>();
+ riskProfile.put(aB, 0);
+ riskProfile.put(bE, 1);
+ riskProfile.put(aD, 2);
+ riskProfile.put(dE, 3);
+ riskProfile.put(aC, 4);
+ riskProfile.put(cE, 5);
+ SRLGGraphSearch<TestVertex, TestEdge> search =
+ new SRLGGraphSearch<TestVertex, TestEdge>(6, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths();
+ assertTrue("> one disjoint path pair found", paths.size() >= 1);
+ checkIsDisjoint(paths.iterator().next(), riskProfile);
+ }
+ @Test
+ public void onePath() {
+ setDefaultWeights();
+ TestEdge aB = new TestEdge(A, B, 1);
+ TestEdge bC = new TestEdge(B, C, 1);
+ TestEdge aD = new TestEdge(A, D, 1);
+ TestEdge dC = new TestEdge(D, C, 1);
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(aB, bC, aD, dC));
+ Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>();
+ riskProfile.put(aB, 0);
+ riskProfile.put(bC, 0);
+ riskProfile.put(aD, 1);
+ riskProfile.put(dC, 0);
+ SRLGGraphSearch<TestVertex, TestEdge> search =
+ new SRLGGraphSearch<TestVertex, TestEdge>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, GraphPathSearch.ALL_PATHS).paths();
+ System.out.println(paths);
+ assertTrue("no disjoint path pairs found", paths.size() == 0);
+ }
+ @Test
+ public void noPath() {
+ setDefaultWeights();
+ TestEdge aB = new TestEdge(A, B, 1);
+ TestEdge bC = new TestEdge(B, C, 1);
+ TestEdge aD = new TestEdge(A, D, 1);
+ TestEdge dC = new TestEdge(D, C, 1);
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(aB, bC, aD, dC));
+ Map<TestEdge, Integer> riskProfile = new HashMap<>();
+ riskProfile.put(aB, 0);
+ riskProfile.put(bC, 0);
+ riskProfile.put(aD, 1);
+ riskProfile.put(dC, 0);
+ SRLGGraphSearch<TestVertex, TestEdge> search =
+ new SRLGGraphSearch<>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths();
+ assertTrue("no disjoint path pairs found", paths.size() == 0);
+ }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
new file mode 100644
index 0000000..0d2d13b
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
@@ -0,0 +1,154 @@
+/*
+ * 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 org.junit.Test;
+import java.util.Set;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertEquals;
+//import static org.junit.Assert.assertTrue;
+
+
+
+/**
+ * Test of the Suurballe backup path algorithm.
+ */
+public class SuurballeGraphSearchTest extends BreadthFirstSearchTest {
+
+ @Override
+ protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
+ return new SuurballeGraphSearch<>();
+ }
+
+ public void setWeights() {
+ weight = new EdgeWeight<TestVertex, TestEdge>() {
+ @Override
+ public double weight(TestEdge edge) {
+ return edge.weight();
+ }
+ };
+ }
+ public void setDefaultWeights() {
+ weight = null;
+ }
+ @Override
+ public void defaultGraphTest() {
+
+ }
+
+ @Override
+ public void defaultHopCountWeight() {
+
+ }
+
+ @Test
+ public void basicGraphTest() {
+ setDefaultWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(A, D, 1),
+ new TestEdge(D, C, 1)));
+ executeSearch(graphSearch(), graph, A, C, weight, 1, 4.0);
+ }
+
+ @Test
+ public void multiplePathOnePairGraphTest() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(A, D, 1),
+ new TestEdge(D, C, 1),
+ new TestEdge(B, E, 2),
+ new TestEdge(C, E, 1)));
+ executeSearch(graphSearch(), graph, A, E, weight, 1, 6.0);
+ }
+
+ @Test
+ public void multiplePathsMultiplePairs() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, E, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(C, E, 1),
+ new TestEdge(A, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(A, E, 2)));
+ GraphPathSearch.Result<TestVertex, TestEdge> result =
+ graphSearch().search(graph, A, E, weight, GraphPathSearch.ALL_PATHS);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ System.out.println("\n\n" + paths + "\n\n\ndone\n");
+ assertEquals("incorrect paths count", 3, paths.size());
+ DisjointPathPair<TestVertex, TestEdge> dpp = (DisjointPathPair<TestVertex, TestEdge>) paths.iterator().next();
+ assertEquals("incorrect disjoint paths per path", 2, dpp.size());
+ }
+
+ @Test
+ public void differingPrimaryAndBackupPathLengths() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(A, D, 1),
+ new TestEdge(D, C, 1),
+ new TestEdge(B, E, 1),
+ new TestEdge(C, E, 1)));
+ executeSearch(graphSearch(), graph, A, E, weight, 1, 5.0);
+ }
+
+ @Test
+ public void onePath() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(A, C, 4),
+ new TestEdge(C, D, 1)));
+ GraphPathSearch.Result<TestVertex, TestEdge> result =
+ graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ assertEquals("incorrect paths count", 1, paths.size());
+ DisjointPathPair<TestVertex, TestEdge> dpp = (DisjointPathPair<TestVertex, TestEdge>) paths.iterator().next();
+ assertEquals("incorrect disjoint paths count", 1, dpp.size());
+ }
+
+ @Test
+ public void noPath() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(A, C, 4)));
+ GraphPathSearch.Result<TestVertex, TestEdge> result =
+ graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ assertEquals("incorrect paths count", paths.size(), 0);
+ }
+
+ @Test
+ public void disconnected() {
+ setWeights();
+ Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of());
+ GraphPathSearch.Result<TestVertex, TestEdge> result =
+ graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ assertEquals("incorrect paths count", 0, paths.size());
+ }
+}