Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | 5ab426f | 2016-04-09 01:19:45 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Laboratory |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | package org.onlab.graph; |
| 18 | |
| 19 | import org.junit.Test; |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 20 | |
| 21 | import java.util.HashMap; |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 22 | import java.util.HashSet; |
| 23 | import java.util.Map; |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 24 | import java.util.Set; |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 25 | |
| 26 | import static com.google.common.collect.ImmutableSet.of; |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 27 | import static org.junit.Assert.assertEquals; |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 28 | import static org.junit.Assert.assertTrue; |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 29 | import static org.onlab.graph.GraphPathSearch.ALL_PATHS; |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 30 | |
| 31 | /** |
| 32 | * Test of the Suurballe backup path algorithm. |
| 33 | */ |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 34 | public class SrlgGraphSearchTest extends BreadthFirstSearchTest { |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 35 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 36 | @Override |
| 37 | protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() { |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 38 | return new SrlgGraphSearch<>(null); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 39 | } |
| 40 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 41 | public void setDefaultWeights() { |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 42 | weigher = null; |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 43 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 44 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 45 | @Override |
| 46 | public void defaultGraphTest() { |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 47 | } |
| 48 | |
| 49 | @Override |
| 50 | public void defaultHopCountWeight() { |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 51 | } |
| 52 | |
| 53 | @Test |
| 54 | public void onePathPair() { |
| 55 | setDefaultWeights(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 56 | TestEdge aB = new TestEdge(A, B); |
| 57 | TestEdge bC = new TestEdge(B, C); |
| 58 | TestEdge aD = new TestEdge(A, D); |
| 59 | TestEdge dC = new TestEdge(D, C); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 60 | Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), |
| 61 | of(aB, bC, aD, dC)); |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 62 | Map<TestEdge, Integer> riskProfile = new HashMap<>(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 63 | riskProfile.put(aB, 0); |
| 64 | riskProfile.put(bC, 0); |
| 65 | riskProfile.put(aD, 1); |
| 66 | riskProfile.put(dC, 1); |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 67 | SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 68 | Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 69 | System.out.println("\n\n\n" + paths + "\n\n\n"); |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 70 | assertEquals("one disjoint path pair found", 1, paths.size()); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 71 | checkIsDisjoint(paths.iterator().next(), riskProfile); |
| 72 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 73 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 74 | public void checkIsDisjoint(Path<TestVertex, TestEdge> p, Map<TestEdge, Integer> risks) { |
| 75 | assertTrue("The path is not a DisjointPathPair", (p instanceof DisjointPathPair)); |
| 76 | DisjointPathPair<TestVertex, TestEdge> q = (DisjointPathPair) p; |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 77 | Set<Integer> p1Risks = new HashSet<>(); |
| 78 | for (TestEdge e : q.edges()) { |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 79 | p1Risks.add(risks.get(e)); |
| 80 | } |
| 81 | if (!q.hasBackup()) { |
| 82 | return; |
| 83 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 84 | Path<TestVertex, TestEdge> pq = q.secondary(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 85 | for (TestEdge e: pq.edges()) { |
| 86 | assertTrue("The paths are not disjoint", !p1Risks.contains(risks.get(e))); |
| 87 | } |
| 88 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 89 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 90 | @Test |
| 91 | public void complexGraphTest() { |
| 92 | setDefaultWeights(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 93 | TestEdge aB = new TestEdge(A, B); |
| 94 | TestEdge bC = new TestEdge(B, C); |
| 95 | TestEdge aD = new TestEdge(A, D); |
| 96 | TestEdge dC = new TestEdge(D, C); |
| 97 | TestEdge cE = new TestEdge(C, E); |
| 98 | TestEdge bE = new TestEdge(B, E); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 99 | Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E), |
| 100 | of(aB, bC, aD, dC, cE, bE)); |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 101 | Map<TestEdge, Integer> riskProfile = new HashMap<>(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 102 | riskProfile.put(aB, 0); |
| 103 | riskProfile.put(bC, 0); |
| 104 | riskProfile.put(aD, 1); |
| 105 | riskProfile.put(dC, 1); |
| 106 | riskProfile.put(cE, 2); |
| 107 | riskProfile.put(bE, 3); |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 108 | SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(4, riskProfile); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 109 | search.search(graph, A, E, weigher, ALL_PATHS).paths(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 110 | } |
| 111 | |
| 112 | @Test |
| 113 | public void multiplePathGraphTest() { |
| 114 | setDefaultWeights(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 115 | TestEdge aB = new TestEdge(A, B); |
| 116 | TestEdge bE = new TestEdge(B, E); |
| 117 | TestEdge aD = new TestEdge(A, D); |
| 118 | TestEdge dE = new TestEdge(D, E); |
| 119 | TestEdge aC = new TestEdge(A, C); |
| 120 | TestEdge cE = new TestEdge(C, E); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 121 | Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E), |
| 122 | of(aB, bE, aD, dE, aC, cE)); |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 123 | Map<TestEdge, Integer> riskProfile = new HashMap<>(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 124 | riskProfile.put(aB, 0); |
| 125 | riskProfile.put(bE, 1); |
| 126 | riskProfile.put(aD, 2); |
| 127 | riskProfile.put(dE, 3); |
| 128 | riskProfile.put(aC, 4); |
| 129 | riskProfile.put(cE, 5); |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 130 | SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(6, riskProfile); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 131 | Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 132 | assertTrue("> one disjoint path pair found", paths.size() >= 1); |
| 133 | checkIsDisjoint(paths.iterator().next(), riskProfile); |
| 134 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 135 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 136 | @Test |
| 137 | public void onePath() { |
| 138 | setDefaultWeights(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 139 | TestEdge aB = new TestEdge(A, B); |
| 140 | TestEdge bC = new TestEdge(B, C); |
| 141 | TestEdge aD = new TestEdge(A, D); |
| 142 | TestEdge dC = new TestEdge(D, C); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 143 | Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), |
| 144 | of(aB, bC, aD, dC)); |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 145 | Map<TestEdge, Integer> riskProfile = new HashMap<>(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 146 | riskProfile.put(aB, 0); |
| 147 | riskProfile.put(bC, 0); |
| 148 | riskProfile.put(aD, 1); |
| 149 | riskProfile.put(dC, 0); |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 150 | SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 151 | Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 152 | System.out.println(paths); |
| 153 | assertTrue("no disjoint path pairs found", paths.size() == 0); |
| 154 | } |
Thomas Vachuska | 48e64e4 | 2015-09-22 15:32:55 -0700 | [diff] [blame] | 155 | |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 156 | @Test |
| 157 | public void noPath() { |
| 158 | setDefaultWeights(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 159 | TestEdge aB = new TestEdge(A, B); |
| 160 | TestEdge bC = new TestEdge(B, C); |
| 161 | TestEdge aD = new TestEdge(A, D); |
| 162 | TestEdge dC = new TestEdge(D, C); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 163 | Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E), |
| 164 | of(aB, bC, aD, dC)); |
| 165 | Map<TestEdge, Integer> riskProfile = new HashMap<>(); |
| 166 | riskProfile.put(aB, 0); |
| 167 | riskProfile.put(bC, 0); |
| 168 | riskProfile.put(aD, 1); |
| 169 | riskProfile.put(dC, 0); |
Jonathan Hart | d9df7bd | 2015-11-10 17:10:25 -0800 | [diff] [blame] | 170 | SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 171 | Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths(); |
Nikhil Cheerla | f7c2e1a | 2015-07-09 12:06:37 -0700 | [diff] [blame] | 172 | assertTrue("no disjoint path pairs found", paths.size() == 0); |
| 173 | } |
| 174 | } |