diff options
Diffstat (limited to 'framework/src/onos/utils/misc/src/test/java/org/onlab/graph')
18 files changed, 0 insertions, 1758 deletions
diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java deleted file mode 100644 index 6e8635dd..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java +++ /dev/null @@ -1,37 +0,0 @@ -/* - * 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 com.google.common.testing.EqualsTester; -import org.junit.Test; - -/** - * Test of the base edge implementation. - */ -public class AbstractEdgeTest { - - @Test - public void equality() { - TestVertex v1 = new TestVertex("1"); - TestVertex v2 = new TestVertex("2"); - new EqualsTester() - .addEqualityGroup(new TestEdge(v1, v2, 1), - new TestEdge(v1, v2, 1)) - .addEqualityGroup(new TestEdge(v2, v1, 1)) - .testEquals(); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java deleted file mode 100644 index b42cacf6..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java +++ /dev/null @@ -1,61 +0,0 @@ -/* - * Copyright 2014-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 static com.google.common.collect.ImmutableSet.of; -import static org.junit.Assert.assertEquals; - -/** - * Base for all graph search tests. - */ -public abstract class AbstractGraphPathSearchTest extends GraphTest { - - /** - * Creates a test-specific graph search to exercise. - * - * @return graph search - */ - protected abstract AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch(); - - @Test(expected = IllegalArgumentException.class) - public void noSuchSourceArgument() { - graphSearch().search(new AdjacencyListsGraph<>(of(B, C), - of(new TestEdge(B, C, 1))), - A, H, weight, 1); - } - - @Test(expected = NullPointerException.class) - public void nullGraphArgument() { - 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, 1); - } - - @Test - public void samenessThreshold() { - AbstractGraphPathSearch<TestVertex, TestEdge> search = graphSearch(); - search.setSamenessThreshold(0.3); - assertEquals("incorrect threshold", 0.3, search.samenessThreshold(), 0.01); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java deleted file mode 100644 index 1f22b5c4..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java +++ /dev/null @@ -1,72 +0,0 @@ -/* - * 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 com.google.common.collect.ImmutableSet; -import com.google.common.testing.EqualsTester; -import org.junit.Test; - -import java.util.Set; - -import static org.junit.Assert.assertEquals; - -/** - * Tests of the graph implementation. - */ -public class AdjacencyListsGraphTest { - - private static final TestVertex A = new TestVertex("A"); - private static final TestVertex B = new TestVertex("B"); - private static final TestVertex C = new TestVertex("C"); - private static final TestVertex D = new TestVertex("D"); - private static final TestVertex E = new TestVertex("E"); - private static final TestVertex F = new TestVertex("F"); - private static final TestVertex G = new TestVertex("G"); - - private final Set<TestEdge> edges = - ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(B, C, 1), - new TestEdge(C, D, 1), new TestEdge(D, A, 1), - new TestEdge(B, D, 1)); - - @Test - public void equality() { - Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F); - Set<TestVertex> vertexes2 = ImmutableSet.of(A, B, C, D, E, F, G); - - AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges); - AdjacencyListsGraph<TestVertex, TestEdge> same = new AdjacencyListsGraph<>(vertexes, edges); - AdjacencyListsGraph<TestVertex, TestEdge> different = new AdjacencyListsGraph<>(vertexes2, edges); - - new EqualsTester() - .addEqualityGroup(graph, same) - .addEqualityGroup(different) - .testEquals(); - } - - @Test - public void basics() { - Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F); - AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges); - assertEquals("incorrect vertex count", 6, graph.getVertexes().size()); - assertEquals("incorrect edge count", 5, graph.getEdges().size()); - - assertEquals("incorrect egress edge count", 1, graph.getEdgesFrom(A).size()); - assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(A).size()); - assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(C).size()); - assertEquals("incorrect egress edge count", 2, graph.getEdgesFrom(B).size()); - assertEquals("incorrect ingress edge count", 2, graph.getEdgesTo(D).size()); - } -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java deleted file mode 100644 index ff363bfb..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java +++ /dev/null @@ -1,77 +0,0 @@ -/* - * Copyright 2014-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.HashSet; -import java.util.Set; - -import static org.junit.Assert.assertEquals; -import static org.onlab.graph.GraphPathSearch.ALL_PATHS; - -/** - * Test of the Bellman-Ford algorithm. - */ -public class BellmanFordGraphSearchTest extends BreadthFirstSearchTest { - - @Override - protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() { - return new BellmanFordGraphSearch<>(); - } - - @Test - @Override - public void defaultGraphTest() { - executeDefaultTest(7, 5, 5.0); - } - - @Test - public void defaultHopCountWeight() { - weight = null; - executeDefaultTest(10, 3, 3.0); - } - - @Test - public void searchGraphWithNegativeCycles() { - Set<TestVertex> vertexes = new HashSet<>(vertexes()); - vertexes.add(Z); - - Set<TestEdge> edges = new HashSet<>(edges()); - edges.add(new TestEdge(G, Z, 1.0)); - edges.add(new TestEdge(Z, G, -2.0)); - - graph = new AdjacencyListsGraph<>(vertexes, edges); - - GraphPathSearch<TestVertex, TestEdge> search = graphSearch(); - 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(); - assertEquals("incorrect src", A, p.src()); - assertEquals("incorrect dst", H, p.dst()); - 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, ALL_PATHS).paths(); - assertEquals("incorrect paths count", 0, paths.size()); - - paths = search.search(graph, A, null, weight, ALL_PATHS).paths(); - printPaths(paths); - assertEquals("incorrect paths count", 6, paths.size()); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java deleted file mode 100644 index 0b574aff..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java +++ /dev/null @@ -1,100 +0,0 @@ -/* - * Copyright 2014-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 static org.junit.Assert.assertEquals; -import static org.onlab.graph.GraphPathSearch.ALL_PATHS; - -/** - * Test of the BFS and similar path search algorithms. - */ -public class BreadthFirstSearchTest extends AbstractGraphPathSearchTest { - - @Override - protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() { - return new BreadthFirstSearch<>(); - } - - @Test - public void defaultGraphTest() { - executeDefaultTest(7, 3, 8.0); - } - - @Test - public void defaultHopCountWeight() { - weight = null; - executeDefaultTest(7, 3, 3.0); - } - - // Executes the default test - protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) { - graph = new AdjacencyListsGraph<>(vertexes(), edges()); - - GraphPathSearch<TestVertex, TestEdge> search = graphSearch(); - 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(); - assertEquals("incorrect src", A, p.src()); - assertEquals("incorrect dst", H, p.dst()); - assertEquals("incorrect path length", pathLength, p.edges().size()); - assertEquals("incorrect path cost", pathCost, p.cost(), 0.1); - - paths = search.search(graph, A, null, weight, ALL_PATHS).paths(); - printPaths(paths); - assertEquals("incorrect paths count", pathCount, paths.size()); - } - - // Executes the search and validates its results. - protected void executeSearch(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, ALL_PATHS); - Set<Path<TestVertex, TestEdge>> paths = result.paths(); - printPaths(paths); - assertEquals("incorrect paths count", pathCount, paths.size()); - if (pathCount > 0) { - Path<TestVertex, TestEdge> path = paths.iterator().next(); - assertEquals("incorrect path cost", pathCost, path.cost(), 0.1); - } - } - - // 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/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java deleted file mode 100644 index 8eb09df6..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java +++ /dev/null @@ -1,110 +0,0 @@ -/* - * 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 com.google.common.testing.EqualsTester; -import org.junit.Test; - -import static com.google.common.collect.ImmutableList.of; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertNull; - -/** - * Test of the default mutable path. - */ -public class DefaultMutablePathTest extends DefaultPathTest { - - @Test - public void equality() { - DefaultPath<TestVertex, TestEdge> p1 = - new DefaultPath<>(of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1)), 2.0); - DefaultPath<TestVertex, TestEdge> p2 = - new DefaultPath<>(of(new TestEdge(A, B, 1), - new TestEdge(B, D, 1)), 2.0); - new EqualsTester().addEqualityGroup(new DefaultMutablePath<>(p1), - new DefaultMutablePath<>(p1)) - .addEqualityGroup(new DefaultMutablePath<>(p2)) - .testEquals(); - } - - @Test - public void empty() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - assertNull("src should be null", p.src()); - assertNull("dst should be null", p.dst()); - assertEquals("incorrect edge count", 0, p.edges().size()); - assertEquals("incorrect path cost", 0.0, p.cost(), 0.1); - } - - @Test - public void pathCost() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - p.setCost(4); - assertEquals("incorrect path cost", 4.0, p.cost(), 0.1); - } - - private void validatePath(Path<TestVertex, TestEdge> p, - TestVertex src, TestVertex dst, int length) { - validatePath(p, src, dst, length, 0.0); - } - - @Test - public void insertEdge() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - p.insertEdge(new TestEdge(B, C, 1)); - p.insertEdge(new TestEdge(A, B, 1)); - validatePath(p, A, C, 2); - } - - @Test - public void appendEdge() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - p.appendEdge(new TestEdge(A, B, 1)); - p.appendEdge(new TestEdge(B, C, 1)); - validatePath(p, A, C, 2); - } - - @Test - public void removeEdge() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - p.appendEdge(new TestEdge(A, B, 1)); - p.appendEdge(new TestEdge(B, C, 1)); - p.appendEdge(new TestEdge(C, C, 2)); - p.appendEdge(new TestEdge(C, D, 1)); - validatePath(p, A, D, 4); - - p.removeEdge(new TestEdge(A, B, 1)); - validatePath(p, B, D, 3); - - p.removeEdge(new TestEdge(C, C, 2)); - validatePath(p, B, D, 2); - - p.removeEdge(new TestEdge(C, D, 1)); - validatePath(p, B, C, 1); - } - - @Test - public void toImmutable() { - MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>(); - p.appendEdge(new TestEdge(A, B, 1)); - p.appendEdge(new TestEdge(B, C, 1)); - validatePath(p, A, C, 2); - - assertEquals("immutables should equal", p.toImmutable(), p.toImmutable()); - validatePath(p.toImmutable(), A, C, 2); - } -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java deleted file mode 100644 index 92befbfe..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java +++ /dev/null @@ -1,57 +0,0 @@ -/* - * 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 com.google.common.testing.EqualsTester; -import org.junit.Test; - -import java.util.List; - -import static com.google.common.collect.ImmutableList.of; -import static org.junit.Assert.assertEquals; - -/** - * Test of the default path. - */ -public class DefaultPathTest extends GraphTest { - - @Test - public void equality() { - List<TestEdge> edges = of(new TestEdge(A, B, 1), new TestEdge(B, C, 1)); - new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, 2.0), - new DefaultPath<>(edges, 2.0)) - .addEqualityGroup(new DefaultPath<>(edges, 3.0)) - .testEquals(); - } - - @Test - public void basics() { - Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1)), 2.0); - validatePath(p, A, C, 2, 2.0); - } - - // Validates the path against expected attributes - protected void validatePath(Path<TestVertex, TestEdge> p, - TestVertex src, TestVertex dst, - int length, double cost) { - assertEquals("incorrect path length", length, p.edges().size()); - assertEquals("incorrect source", src, p.src()); - assertEquals("incorrect destination", dst, p.dst()); - assertEquals("incorrect path cost", cost, p.cost(), 0.1); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java deleted file mode 100644 index 3977ebf1..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java +++ /dev/null @@ -1,97 +0,0 @@ -/* - * Copyright 2014-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 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. - */ -public class DepthFirstSearchTest extends AbstractGraphPathSearchTest { - - @Override - protected DepthFirstSearch<TestVertex, TestEdge> graphSearch() { - return new DepthFirstSearch<>(); - } - - @Test - public void defaultGraphTest() { - executeDefaultTest(3, 6, 5.0, 12.0); - executeBroadSearch(); - } - - @Test - public void defaultHopCountWeight() { - weight = null; - executeDefaultTest(3, 6, 3.0, 6.0); - executeBroadSearch(); - } - - protected void executeDefaultTest(int minLength, int maxLength, - double minCost, double maxCost) { - graph = new AdjacencyListsGraph<>(vertexes(), edges()); - DepthFirstSearch<TestVertex, TestEdge> search = graphSearch(); - - DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result = - search.search(graph, A, H, weight, 1); - Set<Path<TestVertex, TestEdge>> paths = result.paths(); - assertEquals("incorrect path count", 1, paths.size()); - - Path path = paths.iterator().next(); - System.out.println(path); - assertEquals("incorrect src", A, path.src()); - assertEquals("incorrect dst", H, path.dst()); - - int l = path.edges().size(); - assertTrue("incorrect path length " + l, - minLength <= l && l <= maxLength); - assertTrue("incorrect path cost " + path.cost(), - minCost <= path.cost() && path.cost() <= maxCost); - - System.out.println(result.edges()); - printPaths(paths); - } - - public void executeBroadSearch() { - graph = new AdjacencyListsGraph<>(vertexes(), edges()); - DepthFirstSearch<TestVertex, TestEdge> search = graphSearch(); - - // Perform narrow path search to a specific destination. - DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result = - search.search(graph, A, null, weight, ALL_PATHS); - assertEquals("incorrect paths count", 7, result.paths().size()); - - int[] types = new int[]{0, 0, 0, 0}; - for (EdgeType t : result.edges().values()) { - types[t.ordinal()] += 1; - } - assertEquals("incorrect tree-edge count", 7, - types[EdgeType.TREE_EDGE.ordinal()]); - assertEquals("incorrect back-edge count", 1, - types[EdgeType.BACK_EDGE.ordinal()]); - assertEquals("incorrect cross-edge & forward-edge count", 4, - types[EdgeType.FORWARD_EDGE.ordinal()] + - types[EdgeType.CROSS_EDGE.ordinal()]); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java deleted file mode 100644 index 17f08225..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java +++ /dev/null @@ -1,165 +0,0 @@ -/* - * Copyright 2014-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.text.DecimalFormat; -import java.util.HashSet; -import java.util.Set; - -import static com.google.common.collect.ImmutableSet.of; -import static org.junit.Assert.assertEquals; - -/** - * Test of the Dijkstra algorithm. - */ -public class DijkstraGraphSearchTest extends BreadthFirstSearchTest { - - @Override - protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() { - return new DijkstraGraphSearch<>(); - } - - @Test - @Override - public void defaultGraphTest() { - executeDefaultTest(7, 5, 5.0); - } - - @Test - @Override - public void defaultHopCountWeight() { - weight = null; - executeDefaultTest(10, 3, 3.0); - } - - @Test - public void noPath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - 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, 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, 1).paths(); - printPaths(paths); - assertEquals("incorrect paths count", 0, paths.size()); - - 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); - } - - @Test - public void simpleMultiplePath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D), - of(new TestEdge(A, B, 1), - new TestEdge(A, C, 1), - 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 - public void denseMultiplePath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G), - of(new TestEdge(A, B, 1), - new TestEdge(A, C, 1), - new TestEdge(B, D, 1), - new TestEdge(C, D, 1), - new TestEdge(D, E, 1), - new TestEdge(D, F, 1), - new TestEdge(E, G, 1), - 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 - public void dualEdgeMultiplePath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), - of(new TestEdge(A, B, 1), new TestEdge(A, C, 3), - new TestEdge(B, D, 2), new TestEdge(B, C, 1), - new TestEdge(B, E, 4), new TestEdge(C, E, 1), - new TestEdge(D, H, 5), new TestEdge(D, E, 1), - new TestEdge(E, F, 1), new TestEdge(F, D, 1), - 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 - public void negativeWeights() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G), - of(new TestEdge(A, B, 1), - new TestEdge(A, C, -1), - new TestEdge(B, D, 1), - new TestEdge(D, A, -2), - new TestEdge(C, D, 1), - new TestEdge(D, E, 1), - new TestEdge(D, F, 1), - new TestEdge(E, G, 1), - new TestEdge(F, G, 1), - 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 - public void disconnectedPerf() { - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - disconnected(); - } - - - @Test - public void disconnected() { - Set<TestVertex> vertexes = new HashSet<>(); - for (int i = 0; i < 200; i++) { - vertexes.add(new TestVertex("v" + i)); - } - - graph = new AdjacencyListsGraph<>(vertexes, of()); - - long start = System.nanoTime(); - for (TestVertex src : vertexes) { - executeSearch(graphSearch(), graph, src, null, null, 0, 0); - } - long end = System.nanoTime(); - DecimalFormat fmt = new DecimalFormat("#,###"); - System.out.println("Compute cost is " + fmt.format(end - start) + " nanos"); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java deleted file mode 100644 index ca6c56c4..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java +++ /dev/null @@ -1,43 +0,0 @@ -package org.onlab.graph; - -import static org.junit.Assert.*; - -import org.junit.Test; - -import com.google.common.collect.ImmutableList; -import com.google.common.testing.EqualsTester; - -/** - * Test of DisjointPathPair. - */ -public class DisjointPathPairTest { - - private static final TestVertex A = new TestVertex("A"); - private static final TestVertex B = new TestVertex("B"); - private static final TestVertex C = new TestVertex("C"); - private static final TestVertex D = new TestVertex("D"); - - private static final TestEdge AB = new TestEdge(A, B, 1.0); - private static final TestEdge BC = new TestEdge(B, C, 1.0); - private static final TestEdge AD = new TestEdge(A, D, 1.0); - private static final TestEdge DC = new TestEdge(D, C, 1.0); - - private static final Path<TestVertex, TestEdge> ABC - = new DefaultPath<>(ImmutableList.of(AB, BC), 1.0); - private static final Path<TestVertex, TestEdge> ADC - = new DefaultPath<>(ImmutableList.of(AD, DC), 1.0); - - @Test - public void testSwappingPrimarySecondaryDoesntImpactHashCode() { - assertEquals(new DisjointPathPair<>(ABC, ADC).hashCode(), - new DisjointPathPair<>(ADC, ABC).hashCode()); - } - - @Test - public void testSwappingPrimarySecondaryDoesntImpactEquality() { - new EqualsTester() - .addEqualityGroup(new DisjointPathPair<>(ABC, ADC), - new DisjointPathPair<>(ADC, ABC)); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/GraphTest.java deleted file mode 100644 index d29282fc..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/GraphTest.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * 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.Set; - -import static com.google.common.collect.ImmutableSet.of; - -/** - * Base class for various graph-related tests. - */ -public class GraphTest { - - static final TestVertex A = new TestVertex("A"); - static final TestVertex B = new TestVertex("B"); - static final TestVertex C = new TestVertex("C"); - static final TestVertex D = new TestVertex("D"); - static final TestVertex E = new TestVertex("E"); - static final TestVertex F = new TestVertex("F"); - static final TestVertex G = new TestVertex("G"); - static final TestVertex H = new TestVertex("H"); - static final TestVertex Z = new TestVertex("Z"); - - protected Graph<TestVertex, TestEdge> graph; - - protected EdgeWeight<TestVertex, TestEdge> weight = - new EdgeWeight<TestVertex, TestEdge>() { - @Override - public double weight(TestEdge edge) { - return edge.weight(); - } - }; - - protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) { - for (Path p : paths) { - System.out.println(p); - } - } - - protected Set<TestVertex> vertexes() { - return of(A, B, C, D, E, F, G, H); - } - - protected Set<TestEdge> edges() { - return of(new TestEdge(A, B, 1), new TestEdge(A, C, 3), - new TestEdge(B, D, 2), new TestEdge(B, C, 1), - new TestEdge(B, E, 4), new TestEdge(C, E, 1), - new TestEdge(D, H, 5), new TestEdge(D, E, 1), - new TestEdge(E, F, 1), new TestEdge(F, D, 1), - new TestEdge(F, G, 1), new TestEdge(F, H, 1)); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/HeapTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/HeapTest.java deleted file mode 100644 index f34185e2..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/HeapTest.java +++ /dev/null @@ -1,97 +0,0 @@ -/* - * 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 com.google.common.collect.Ordering; -import com.google.common.testing.EqualsTester; -import org.junit.Test; - -import java.util.ArrayList; -import java.util.Comparator; - -import static com.google.common.collect.ImmutableList.of; -import static org.junit.Assert.*; - -/** - * Heap data structure tests. - */ -public class HeapTest { - - private ArrayList<Integer> data = - new ArrayList<>(of(6, 4, 5, 9, 8, 3, 2, 1, 7, 0)); - - private static final Comparator<Integer> MIN = Ordering.natural().reverse(); - private static final Comparator<Integer> MAX = Ordering.natural(); - - @Test - public void equality() { - new EqualsTester() - .addEqualityGroup(new Heap<>(data, MIN), - new Heap<>(data, MIN)) - .addEqualityGroup(new Heap<>(data, MAX)) - .testEquals(); - } - - @Test - public void empty() { - Heap<Integer> h = new Heap<>(new ArrayList<Integer>(), MIN); - assertTrue("should be empty", h.isEmpty()); - assertEquals("incorrect size", 0, h.size()); - assertNull("no item expected", h.extreme()); - assertNull("no item expected", h.extractExtreme()); - } - - @Test - public void insert() { - Heap<Integer> h = new Heap<>(data, MIN); - assertEquals("incorrect size", 10, h.size()); - h.insert(3); - assertEquals("incorrect size", 11, h.size()); - } - - @Test - public void minQueue() { - Heap<Integer> h = new Heap<>(data, MIN); - assertFalse("should not be empty", h.isEmpty()); - assertEquals("incorrect size", 10, h.size()); - assertEquals("incorrect extreme", (Integer) 0, h.extreme()); - - for (int i = 0, n = h.size(); i < n; i++) { - assertEquals("incorrect element", (Integer) i, h.extractExtreme()); - } - assertTrue("should be empty", h.isEmpty()); - } - - @Test - public void maxQueue() { - Heap<Integer> h = new Heap<>(data, MAX); - assertFalse("should not be empty", h.isEmpty()); - assertEquals("incorrect size", 10, h.size()); - assertEquals("incorrect extreme", (Integer) 9, h.extreme()); - - for (int i = h.size(); i > 0; i--) { - assertEquals("incorrect element", (Integer) (i - 1), h.extractExtreme()); - } - assertTrue("should be empty", h.isEmpty()); - } - - @Test - public void iterator() { - Heap<Integer> h = new Heap<>(data, MIN); - assertTrue("should have next element", h.iterator().hasNext()); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/KshortestPathSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/KshortestPathSearchTest.java deleted file mode 100644 index 3e8900b8..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/KshortestPathSearchTest.java +++ /dev/null @@ -1,197 +0,0 @@ -/* - * 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 static com.google.common.collect.ImmutableSet.of; -import static org.junit.Assert.*; - -import java.io.ByteArrayOutputStream; -//import java.io.PrintStream; -import java.util.ArrayList; -import java.util.Iterator; -import java.util.List; - -import org.junit.After; -import org.junit.AfterClass; -import org.junit.Before; -import org.junit.BeforeClass; -import org.junit.Test; - -public class KshortestPathSearchTest extends BreadthFirstSearchTest { - - private final ByteArrayOutputStream outContent = new ByteArrayOutputStream(); - - @Test - public void noPath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - new TestEdge(C, D, 1), - new TestEdge(D, C, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, D, weight, 1); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 0, result.size()); - } - - @Test - public void test2Path() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - new TestEdge(B, D, 1), - new TestEdge(D, B, 1), - new TestEdge(A, C, 1), - new TestEdge(C, A, 1), - new TestEdge(C, D, 1), - new TestEdge(D, C, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, D, weight, 2); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 2, result.size()); - // assertEquals("printing the paths", outContent.toString()); - } - - @Test - public void test3Path() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - new TestEdge(A, D, 1), - new TestEdge(D, A, 1), - new TestEdge(B, D, 1), - new TestEdge(D, B, 1), - new TestEdge(A, C, 1), - new TestEdge(C, A, 1), - new TestEdge(C, D, 1), - new TestEdge(D, C, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, D, weight, 3); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 3, result.size()); - // assertEquals("printing the paths", outContent.toString()); - } - - @Test - public void test4Path() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - new TestEdge(A, C, 1), - new TestEdge(C, A, 1), - new TestEdge(B, D, 1), - new TestEdge(D, B, 1), - new TestEdge(C, E, 1), - new TestEdge(E, C, 1), - new TestEdge(D, F, 1), - new TestEdge(F, D, 1), - new TestEdge(F, E, 1), - new TestEdge(E, F, 1), - new TestEdge(C, D, 1), - new TestEdge(D, C, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, F, weight, 4); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 4, result.size()); - // assertEquals("printing the paths", outContent.toString()); - } - - @Test - public void test6Path() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F), - of(new TestEdge(A, B, 1), - new TestEdge(B, A, 1), - new TestEdge(A, C, 1), - new TestEdge(C, A, 1), - new TestEdge(B, D, 1), - new TestEdge(D, B, 1), - new TestEdge(B, C, 1), - new TestEdge(C, B, 1), - new TestEdge(D, E, 1), - new TestEdge(E, D, 1), - new TestEdge(C, E, 1), - new TestEdge(E, C, 1), - new TestEdge(D, F, 1), - new TestEdge(F, D, 1), - new TestEdge(E, F, 1), - new TestEdge(F, E, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, F, weight, 6); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 6, result.size()); - // assertEquals("printing the paths", outContent.toString()); - } - - @Test - public void dualEdgePath() { - graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), - of(new TestEdge(A, B, 1), new TestEdge(A, C, 3), - new TestEdge(B, D, 2), new TestEdge(B, C, 1), - new TestEdge(B, E, 4), new TestEdge(C, E, 1), - new TestEdge(D, H, 5), new TestEdge(D, E, 1), - new TestEdge(E, F, 1), new TestEdge(F, D, 1), - new TestEdge(F, G, 1), new TestEdge(F, H, 1), - new TestEdge(A, E, 3), new TestEdge(B, D, 1))); - KshortestPathSearch<TestVertex, TestEdge> gs = new KshortestPathSearch<TestVertex, TestEdge>(graph); - List<List<TestEdge>> result = gs.search(A, G, weight, 6); - List<Path> paths = new ArrayList<>(); - Iterator<List<TestEdge>> itr = result.iterator(); - while (itr.hasNext()) { - System.out.println(itr.next().toString()); - } - assertEquals("incorrect paths count", 6, result.size()); - // assertEquals("printing the paths", outContent.toString()); - } - - @BeforeClass - public static void setUpBeforeClass() throws Exception { - } - - @AfterClass - public static void tearDownAfterClass() throws Exception { - } - - @Before - public void setUp() throws Exception { - // System.setOut(new PrintStream(outContent)); - } - - @After - public void tearDown() throws Exception { - // System.setOut(null); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java deleted file mode 100644 index 26d50364..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java +++ /dev/null @@ -1,174 +0,0 @@ -/* - * 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.HashMap; -import java.util.HashSet; -import java.util.Map; -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<>(null); - } - - 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<>(); - riskProfile.put(aB, 0); - riskProfile.put(bC, 0); - riskProfile.put(aD, 1); - riskProfile.put(dC, 1); - 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"); - 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<>(); - for (TestEdge e : q.edges()) { - p1Risks.add(risks.get(e)); - } - if (!q.hasBackup()) { - return; - } - 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(); - 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<>(); - 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<>(4, riskProfile); - search.search(graph, A, E, weight, 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<>(); - 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<>(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(); - 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<>(); - 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, C, weight, 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, ALL_PATHS).paths(); - assertTrue("no disjoint path pairs found", paths.size() == 0); - } -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java deleted file mode 100644 index 0d2d13b0..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java +++ /dev/null @@ -1,154 +0,0 @@ -/* - * 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()); - } -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java deleted file mode 100644 index 40f90513..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java +++ /dev/null @@ -1,125 +0,0 @@ -/* - * 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 static com.google.common.collect.ImmutableSet.of; -import static org.junit.Assert.assertEquals; -import static org.onlab.graph.TarjanGraphSearch.SccResult; - -/** - * Tarjan graph search tests. - */ -public class TarjanGraphSearchTest extends GraphTest { - - private void validate(SccResult<TestVertex, TestEdge> result, int cc) { - System.out.println("Cluster count: " + result.clusterVertexes().size()); - System.out.println("Clusters: " + result.clusterVertexes()); - assertEquals("incorrect cluster count", cc, result.clusterCount()); - } - - private void validate(SccResult<TestVertex, TestEdge> result, - int i, int vc, int ec) { - assertEquals("incorrect cluster count", vc, result.clusterVertexes().get(i).size()); - assertEquals("incorrect edge count", ec, result.clusterEdges().get(i).size()); - } - - @Test - public void basic() { - graph = new AdjacencyListsGraph<>(vertexes(), edges()); - TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>(); - SccResult<TestVertex, TestEdge> result = gs.search(graph, null); - validate(result, 6); - } - - @Test - public void singleCluster() { - graph = new AdjacencyListsGraph<>(vertexes(), - of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1), - new TestEdge(C, D, 1), - new TestEdge(D, E, 1), - new TestEdge(E, F, 1), - new TestEdge(F, G, 1), - new TestEdge(G, H, 1), - new TestEdge(H, A, 1))); - - TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>(); - SccResult<TestVertex, TestEdge> result = gs.search(graph, null); - validate(result, 1); - validate(result, 0, 8, 8); - } - - @Test - public void twoUnconnectedCluster() { - graph = new AdjacencyListsGraph<>(vertexes(), - of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1), - new TestEdge(C, D, 1), - new TestEdge(D, A, 1), - new TestEdge(E, F, 1), - new TestEdge(F, G, 1), - new TestEdge(G, H, 1), - new TestEdge(H, E, 1))); - TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>(); - SccResult<TestVertex, TestEdge> result = gs.search(graph, null); - validate(result, 2); - validate(result, 0, 4, 4); - validate(result, 1, 4, 4); - } - - @Test - public void twoWeaklyConnectedClusters() { - graph = new AdjacencyListsGraph<>(vertexes(), - of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1), - new TestEdge(C, D, 1), - new TestEdge(D, A, 1), - new TestEdge(E, F, 1), - new TestEdge(F, G, 1), - new TestEdge(G, H, 1), - new TestEdge(H, E, 1), - new TestEdge(B, E, 1))); - TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>(); - SccResult<TestVertex, TestEdge> result = gs.search(graph, null); - validate(result, 2); - validate(result, 0, 4, 4); - validate(result, 1, 4, 4); - } - - @Test - public void twoClustersConnectedWithIgnoredEdges() { - graph = new AdjacencyListsGraph<>(vertexes(), - of(new TestEdge(A, B, 1), - new TestEdge(B, C, 1), - new TestEdge(C, D, 1), - new TestEdge(D, A, 1), - new TestEdge(E, F, 1), - new TestEdge(F, G, 1), - new TestEdge(G, H, 1), - new TestEdge(H, E, 1), - new TestEdge(B, E, -1), - new TestEdge(E, B, -1))); - - TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>(); - SccResult<TestVertex, TestEdge> result = gs.search(graph, weight); - validate(result, 2); - validate(result, 0, 4, 4); - validate(result, 1, 4, 4); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestEdge.java deleted file mode 100644 index 951f655b..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestEdge.java +++ /dev/null @@ -1,73 +0,0 @@ -/* - * 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.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; - -/** - * Test edge. - */ -public class TestEdge extends AbstractEdge<TestVertex> { - - private final double weight; - - /** - * Creates a new edge between the specified source and destination vertexes. - * - * @param src source vertex - * @param dst destination vertex - * @param weight edge weight - */ - public TestEdge(TestVertex src, TestVertex dst, double weight) { - super(src, dst); - this.weight = weight; - } - - /** - * Returns the edge weight. - * - * @return edge weight - */ - public double weight() { - return weight; - } - - @Override - public int hashCode() { - return 31 * super.hashCode() + Objects.hash(weight); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof TestEdge) { - final TestEdge other = (TestEdge) obj; - return super.equals(obj) && Objects.equals(this.weight, other.weight); - } - return false; - } - - @Override - public String toString() { - return toStringHelper(this).add("src", src()).add("dst", dst()). - add("weight", weight).toString(); - } - -} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestVertex.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestVertex.java deleted file mode 100644 index b0b92a4a..00000000 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/TestVertex.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * 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.Objects; - -/** - * Test vertex. - */ -public class TestVertex implements Vertex { - - private final String name; - - public TestVertex(String name) { - this.name = name; - } - - @Override - public int hashCode() { - return name.hashCode(); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof TestVertex) { - final TestVertex other = (TestVertex) obj; - return Objects.equals(this.name, other.name); - } - return false; - } - - @Override - public String toString() { - return name; - } - -} |