Cleaned up the SRLG and disjoint path code and naming.
Change-Id: I02b6fe5ee1e3f5eadc4e88800386a23349ee5e58
diff --git a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
index b62d3b2..206a34c 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
@@ -19,52 +19,67 @@
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;
-
+/**
+ * Pair of disjoint paths.
+ *
+ * @param <V> type of vertex
+ * @param <E> type of edge
+ */
public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Path<V, E> {
- public Path<V, E> path1, path2;
- boolean usingPath1 = true;
+
+ private Path<V, E> primary, secondary;
+ boolean primaryActive = true;
/**
- * Creates a Disjoint Path Pair from two paths.
+ * Creates a disjoint path pair from two paths.
*
- * @param p1 first path
- * @param p2 second path
+ * @param primary primary path
+ * @param secondary secondary path
*/
- public DisjointPathPair(Path<V, E> p1, Path<V, E> p2) {
- path1 = p1;
- path2 = p2;
+ public DisjointPathPair(Path<V, E> primary, Path<V, E> secondary) {
+ this.primary = primary;
+ this.secondary = secondary;
}
@Override
public V src() {
- return path1.src();
+ return primary.src();
}
@Override
public V dst() {
- return path1.dst();
+ return primary.dst();
+ }
+
+ /**
+ * Returns the primary path.
+ *
+ * @return primary path
+ */
+ public Path<V, E> primary() {
+ return primary;
+ }
+
+ /**
+ * Returns the secondary path.
+ *
+ * @return primary path
+ */
+ public Path<V, E> secondary() {
+ return secondary;
}
@Override
public double cost() {
- if (!hasBackup()) {
- return path1.cost();
- }
- return path1.cost() + path2.cost();
+ return hasBackup() ? primary.cost() + secondary.cost() : primary.cost();
}
@Override
public List<E> edges() {
- if (usingPath1 || !hasBackup()) {
- return path1.edges();
- } else {
- return path2.edges();
- }
+ return primaryActive || !hasBackup() ? primary.edges() : secondary.edges();
}
/**
@@ -73,7 +88,7 @@
* @return boolean representing whether it has backup
*/
public boolean hasBackup() {
- return path2 != null && path2.edges() != null;
+ return secondary != null && secondary.edges() != null;
}
@Override
@@ -88,13 +103,8 @@
@Override
public int hashCode() {
- Set<Path<V, E>> paths;
- if (!hasBackup()) {
- paths = of(path1);
- } else {
- paths = of(path1, path2);
- }
- return Objects.hash(paths);
+ return hasBackup() ? Objects.hash(primary) + Objects.hash(secondary) :
+ Objects.hash(primary);
}
@Override
@@ -106,10 +116,10 @@
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));
+ (Objects.equals(this.primary, other.primary) &&
+ Objects.equals(this.secondary, other.secondary)) ||
+ (Objects.equals(this.primary, other.secondary) &&
+ Objects.equals(this.secondary, other.primary));
}
return false;
}
@@ -120,9 +130,6 @@
* @return number of paths
*/
public int size() {
- if (hasBackup()) {
- return 2;
- }
- return 1;
+ return hasBackup() ? 2 : 1;
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java
index 885fbe5..8bfd270 100644
--- a/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java
@@ -17,44 +17,37 @@
package org.onlab.graph;
import org.junit.Test;
-import java.util.Set;
+
+import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
-import java.util.HashMap;
+import java.util.Set;
import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
-
-
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
/**
* Test of the Suurballe backup path algorithm.
*/
public class SRLGGraphSearchTest extends BreadthFirstSearchTest {
+
@Override
protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
- return new SRLGGraphSearch<TestVertex, TestEdge>(null);
+ return new SRLGGraphSearch<>(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
@@ -66,34 +59,34 @@
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>();
+ Map<TestEdge, Integer> riskProfile = new HashMap<>();
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();
+ SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
System.out.println("\n\n\n" + paths + "\n\n\n");
- assertTrue("one disjoint path pair found", paths.size() == 1);
+ assertEquals("one disjoint path pair found", 1, paths.size());
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()) {
+ Set<Integer> p1Risks = new HashSet<>();
+ for (TestEdge e : q.edges()) {
p1Risks.add(risks.get(e));
}
if (!q.hasBackup()) {
return;
}
- Path<TestVertex, TestEdge> pq = q.path2;
+ Path<TestVertex, TestEdge> pq = q.secondary();
for (TestEdge e: pq.edges()) {
assertTrue("The paths are not disjoint", !p1Risks.contains(risks.get(e)));
}
}
+
@Test
public void complexGraphTest() {
setDefaultWeights();
@@ -105,16 +98,15 @@
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>();
+ Map<TestEdge, Integer> riskProfile = new HashMap<>();
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();
+ SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(4, riskProfile);
+ search.search(graph, A, E, weight, ALL_PATHS).paths();
}
@Test
@@ -128,19 +120,19 @@
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>();
+ Map<TestEdge, Integer> riskProfile = new HashMap<>();
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();
+ SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(6, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
assertTrue("> one disjoint path pair found", paths.size() >= 1);
checkIsDisjoint(paths.iterator().next(), riskProfile);
}
+
@Test
public void onePath() {
setDefaultWeights();
@@ -150,17 +142,17 @@
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>();
+ 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<TestVertex, TestEdge>(2, riskProfile);
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, GraphPathSearch.ALL_PATHS).paths();
+ SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
System.out.println(paths);
assertTrue("no disjoint path pairs found", paths.size() == 0);
}
+
@Test
public void noPath() {
setDefaultWeights();
@@ -175,9 +167,8 @@
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();
+ SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile);
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
assertTrue("no disjoint path pairs found", paths.size() == 0);
}
}