ONOS-745 Refactoring topology to compute only broadcast tree and not pre-compute paths.
ONOS-744 Refactoring graph search to allow requesting max number of paths.
Change-Id: I28467246b92df32ebb3155c45774ecc051fdd3dd
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
index cf35f66..91204fc 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
@@ -36,19 +36,19 @@
public void noSuchSourceArgument() {
graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
of(new TestEdge(B, C, 1))),
- A, H, weight);
+ A, H, weight, 1);
}
@Test(expected = NullPointerException.class)
public void nullGraphArgument() {
- graphSearch().search(null, A, H, weight);
+ graphSearch().search(null, A, H, weight, 1);
}
@Test(expected = NullPointerException.class)
public void nullSourceArgument() {
graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
of(new TestEdge(B, C, 1))),
- null, H, weight);
+ null, H, weight, 1);
}
@Test
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
index 4e9f5e6..9380054 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -21,6 +21,7 @@
import java.util.Set;
import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
/**
* Test of the Bellman-Ford algorithm.
@@ -56,7 +57,7 @@
graph = new AdjacencyListsGraph<>(vertexes, edges);
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight, ALL_PATHS).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -65,10 +66,10 @@
assertEquals("incorrect path length", 5, p.edges().size());
assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
- paths = search.search(graph, A, G, weight).paths();
+ paths = search.search(graph, A, G, weight, ALL_PATHS).paths();
assertEquals("incorrect paths count", 0, paths.size());
- paths = search.search(graph, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
printPaths(paths);
assertEquals("incorrect paths count", 6, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
index 96a77e6..76c0cc2 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -20,6 +20,7 @@
import java.util.Set;
import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
/**
* Test of the BFS and similar path search algorithms.
@@ -47,7 +48,8 @@
graph = new AdjacencyListsGraph<>(vertexes(), edges());
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths =
+ search.search(graph, A, H, weight, ALL_PATHS).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -56,7 +58,7 @@
assertEquals("incorrect path length", pathLength, p.edges().size());
assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
- paths = search.search(graph, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
}
@@ -68,7 +70,7 @@
EdgeWeight<TestVertex, TestEdge> weight,
int pathCount, double pathCost) {
GraphPathSearch.Result<TestVertex, TestEdge> result =
- search.search(graph, src, dst, weight);
+ search.search(graph, src, dst, weight, ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
@@ -78,4 +80,21 @@
}
}
+ // Executes the single-path search and validates its results.
+ protected void executeSinglePathSearch(GraphPathSearch<TestVertex, TestEdge> search,
+ Graph<TestVertex, TestEdge> graph,
+ TestVertex src, TestVertex dst,
+ EdgeWeight<TestVertex, TestEdge> weight,
+ int pathCount, double pathCost) {
+ GraphPathSearch.Result<TestVertex, TestEdge> result =
+ search.search(graph, src, dst, weight, 1);
+ Set<Path<TestVertex, TestEdge>> paths = result.paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", Math.min(pathCount, 1), paths.size());
+ if (pathCount > 0) {
+ Path<TestVertex, TestEdge> path = paths.iterator().next();
+ assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+ }
+ }
+
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
index d225377..5348bf6 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -22,6 +22,7 @@
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.onlab.graph.DepthFirstSearch.EdgeType;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
/**
* Test of the DFS algorithm.
@@ -52,7 +53,7 @@
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(graph, A, H, weight);
+ search.search(graph, A, H, weight, 1);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect path count", 1, paths.size());
@@ -77,7 +78,7 @@
// Perform narrow path search to a specific destination.
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(graph, A, null, weight);
+ search.search(graph, A, null, weight, ALL_PATHS);
assertEquals("incorrect paths count", 7, result.paths().size());
int[] types = new int[]{0, 0, 0, 0};
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index e11ccb2..d906e65 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -55,16 +55,16 @@
new TestEdge(C, D, 1),
new TestEdge(D, C, 1)));
GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
- paths = gs.search(graph, A, D, weight).paths();
+ paths = gs.search(graph, A, D, weight, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 0, paths.size());
- paths = gs.search(graph, A, null, weight).paths();
+ paths = gs.search(graph, A, null, weight, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
@@ -78,6 +78,7 @@
new TestEdge(B, D, 1),
new TestEdge(C, D, 1)));
executeSearch(graphSearch(), graph, A, D, weight, 2, 2.0);
+ executeSinglePathSearch(graphSearch(), graph, A, D, weight, 1, 2.0);
}
@Test
@@ -93,6 +94,7 @@
new TestEdge(F, G, 1),
new TestEdge(A, G, 4)));
executeSearch(graphSearch(), graph, A, G, weight, 5, 4.0);
+ executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
}
@Test
@@ -106,6 +108,7 @@
new TestEdge(F, G, 1), new TestEdge(F, H, 1),
new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
executeSearch(graphSearch(), graph, A, E, weight, 3, 3.0);
+ executeSinglePathSearch(graphSearch(), graph, A, E, weight, 1, 3.0);
}
@Test
@@ -123,6 +126,7 @@
new TestEdge(G, A, -5),
new TestEdge(A, G, 4)));
executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
+ executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
}
@Test