Brian O'Connor | 7cbbbb7 | 2016-04-09 02:13:23 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Brian O'Connor | 7cbbbb7 | 2016-04-09 02:13:23 -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 | */ |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 16 | package org.onlab.graph; |
| 17 | |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 18 | import com.google.common.collect.Iterables; |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 19 | import com.google.common.collect.Lists; |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 20 | |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 21 | import org.junit.Before; |
| 22 | import org.junit.Test; |
| 23 | |
| 24 | import java.util.Iterator; |
| 25 | import java.util.List; |
| 26 | import java.util.Set; |
| 27 | |
| 28 | import static com.google.common.collect.ImmutableSet.of; |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 29 | import static org.hamcrest.Matchers.is; |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 30 | import static org.junit.Assert.assertEquals; |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 31 | import static org.junit.Assert.assertThat; |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 32 | import static org.junit.Assert.assertTrue; |
| 33 | |
| 34 | /** |
| 35 | * Class for test KshortestPathsSearch. |
| 36 | */ |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 37 | public class KShortestPathsSearchTest extends GraphTest { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 38 | private KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>(); |
| 39 | private GraphPathSearch.Result<TestVertex, TestEdge> result; |
| 40 | |
| 41 | @Before |
| 42 | public void setUp() { |
| 43 | graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
| 44 | } |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 45 | |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 46 | @Test |
| 47 | public void noPath() { |
| 48 | graph = new AdjacencyListsGraph<>(of(A, B, C, D), |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 49 | of(new TestEdge(A, B), |
| 50 | new TestEdge(B, A), |
| 51 | new TestEdge(C, D), |
| 52 | new TestEdge(D, C))); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 53 | KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 54 | GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weigher, 1); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 55 | Set<Path<TestVertex, TestEdge>> resultPathSet = result.paths(); |
| 56 | assertTrue("There should not be any paths.", resultPathSet.isEmpty()); |
| 57 | } |
| 58 | |
| 59 | @Test |
| 60 | public void testSinglePath() { |
| 61 | //Tests that there is only a single path possible between A and B |
| 62 | graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 63 | this.result = kShortestPathsSearch.search(graph, A, B, weigher, 2); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 64 | assertEquals("incorrect paths count", 1, result.paths().size()); |
| 65 | List<TestEdge> correctEdgeList = Lists.newArrayList(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 66 | correctEdgeList.add(new TestEdge(A, B, W1)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 67 | assertTrue("That wrong path was returned.", |
| 68 | edgeListsAreEqual(correctEdgeList, result.paths().iterator().next().edges())); |
| 69 | } |
| 70 | |
| 71 | @Test |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 72 | public void testResultsAreOneHopPathPlusLongerOnes() { |
| 73 | graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
| 74 | this.result = kShortestPathsSearch.search(graph, B, D, hopWeigher, 42); |
| 75 | assertEquals("incorrect paths count", 3, result.paths().size()); |
| 76 | assertThat("the shortest path size is 1 hop", |
| 77 | Iterables.get(result.paths(), 0).edges().size(), |
| 78 | is(1)); |
| 79 | assertThat("the 2nd shortest path size is 3 hop", |
| 80 | Iterables.get(result.paths(), 1).edges().size(), |
| 81 | is(3)); |
| 82 | assertThat("the 3rd shortest path size is 4 hop", |
| 83 | Iterables.get(result.paths(), 2).edges().size(), |
| 84 | is(4)); |
| 85 | } |
| 86 | |
| 87 | @Test |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 88 | public void testTwoPath() { |
| 89 | //Tests that there are only two paths between A and C and that they are returned in the correct order |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 90 | result = kShortestPathsSearch.search(graph, A, C, weigher, 3); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 91 | assertTrue("There are an unexpected number of paths.", result.paths().size() == 2); |
| 92 | Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator(); |
| 93 | List<TestEdge> correctEdgeList = Lists.newArrayList(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 94 | correctEdgeList.add(new TestEdge(A, B, W1)); |
| 95 | correctEdgeList.add(new TestEdge(B, C, W1)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 96 | assertTrue("The first path from A to C was incorrect.", |
| 97 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 98 | correctEdgeList.clear(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 99 | correctEdgeList.add(new TestEdge(A, C, W3)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 100 | assertTrue("The second path from A to C was incorrect.", |
| 101 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 102 | } |
| 103 | |
| 104 | @Test |
| 105 | public void testFourPath() { |
| 106 | //Tests that there are only four paths between A and E and that they are returned in the correct order |
| 107 | //Also tests the special case where some correct solutions are equal |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 108 | result = kShortestPathsSearch.search(graph, A, E, weigher, 5); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 109 | assertTrue("There are an unexpected number of paths.", result.paths().size() == 4); |
| 110 | Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator(); |
| 111 | List<TestEdge> correctEdgeList = Lists.newArrayList(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 112 | correctEdgeList.add(new TestEdge(A, B, W1)); |
| 113 | correctEdgeList.add(new TestEdge(B, C, W1)); |
| 114 | correctEdgeList.add(new TestEdge(C, E, W1)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 115 | assertTrue("The first path from A to E was incorrect.", |
| 116 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 117 | correctEdgeList.clear(); |
| 118 | //There are two paths of equal length that should hold positions two and three |
| 119 | List<TestEdge> alternateCorrectEdgeList = Lists.newArrayList(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 120 | correctEdgeList.add(new TestEdge(A, C, W3)); |
| 121 | correctEdgeList.add(new TestEdge(C, E, W1)); |
| 122 | alternateCorrectEdgeList.add(new TestEdge(A, B, W1)); |
| 123 | alternateCorrectEdgeList.add(new TestEdge(B, D, W2)); |
| 124 | alternateCorrectEdgeList.add(new TestEdge(D, E, W1)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 125 | List<TestEdge> candidateOne = edgeListIterator.next().edges(); |
| 126 | List<TestEdge> candidateTwo = edgeListIterator.next().edges(); |
| 127 | if (candidateOne.size() == 2) { |
| 128 | assertTrue("The second path from A to E was incorrect.", |
| 129 | edgeListsAreEqual(candidateOne, correctEdgeList)); |
| 130 | assertTrue("The third path from A to E was incorrect.", |
| 131 | edgeListsAreEqual(candidateTwo, alternateCorrectEdgeList)); |
| 132 | } else { |
| 133 | assertTrue("The second path from A to E was incorrect.", |
| 134 | edgeListsAreEqual(candidateOne, alternateCorrectEdgeList)); |
| 135 | assertTrue("The third path from A to E was incorrect.", |
| 136 | edgeListsAreEqual(candidateTwo, correctEdgeList)); |
| 137 | } |
| 138 | correctEdgeList.clear(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 139 | correctEdgeList.add(new TestEdge(A, B, W1)); |
| 140 | correctEdgeList.add(new TestEdge(B, E, W4)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 141 | assertTrue("The fourth path rom A to E was incorrect", |
| 142 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 143 | |
| 144 | } |
| 145 | |
| 146 | @Test |
| 147 | public void testPathsFromSink() { |
| 148 | //H is a sink in this topology, insure there are no paths from it to any other location |
| 149 | for (TestVertex vertex : vertexes()) { |
| 150 | assertTrue("There should be no paths from vertex H to any other node.", |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 151 | kShortestPathsSearch.search(graph, H, vertex, weigher, 1).paths().size() == 0); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 152 | } |
| 153 | } |
| 154 | |
| 155 | @Test |
| 156 | public void testLimitPathSetSize() { |
| 157 | //Checks to make sure that no more than K paths are returned |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 158 | result = kShortestPathsSearch.search(graph, A, E, weigher, 3); |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 159 | assertEquals("There are an unexpected number of paths.", 3, result.paths().size()); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 160 | result = kShortestPathsSearch.search(graph, A, G, weigher, 1); |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 161 | assertEquals("There are an unexpected number of paths.", 1, result.paths().size()); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 162 | } |
| 163 | |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 164 | |
| 165 | @Test |
| 166 | public void testVariableLenPathsWithConstantLinkWeight() { |
| 167 | |
| 168 | /* |
| 169 | * Test graph: |
| 170 | * |
| 171 | * +-+-+ +---+ +---+ +-+-+ |
| 172 | * +--+ B +--+ C +-+ D +--+ E | |
| 173 | * | +-+-+ +---+ +---+ +-+-+ |
| 174 | * | | | |
| 175 | * +-+-+ | +---+ +---+ +-+-+ |
| 176 | * | A | +----+ F +-+ G +--+ H | |
| 177 | * +---+ +---+ +---+ +---+ |
| 178 | */ |
| 179 | graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), of( |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 180 | new TestEdge(A, B), |
| 181 | new TestEdge(B, A), |
| 182 | new TestEdge(B, C), |
| 183 | new TestEdge(C, B), |
| 184 | new TestEdge(C, D), |
| 185 | new TestEdge(D, C), |
| 186 | new TestEdge(D, E), |
| 187 | new TestEdge(E, D), |
| 188 | new TestEdge(E, H), |
| 189 | new TestEdge(H, E), |
| 190 | new TestEdge(H, G), |
| 191 | new TestEdge(G, H), |
| 192 | new TestEdge(G, F), |
| 193 | new TestEdge(F, G), |
| 194 | new TestEdge(F, B), |
| 195 | new TestEdge(B, F) |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 196 | )); |
| 197 | |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 198 | //Tests that there are only two paths between A and G and that they are returned in the correct order |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 199 | result = kShortestPathsSearch.search(graph, A, G, weigher, 5); |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 200 | |
| 201 | assertEquals("There are an unexpected number of paths.", 2, result.paths().size()); |
| 202 | |
| 203 | Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator(); |
| 204 | |
| 205 | List<TestEdge> correctEdgeList = Lists.newArrayList(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 206 | correctEdgeList.add(new TestEdge(A, B)); |
| 207 | correctEdgeList.add(new TestEdge(B, F)); |
| 208 | correctEdgeList.add(new TestEdge(F, G)); |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 209 | assertTrue("The first path from A to G was incorrect.", |
| 210 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 211 | |
| 212 | correctEdgeList.clear(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 213 | correctEdgeList.add(new TestEdge(A, B)); |
| 214 | correctEdgeList.add(new TestEdge(B, C)); |
| 215 | correctEdgeList.add(new TestEdge(C, D)); |
| 216 | correctEdgeList.add(new TestEdge(D, E)); |
| 217 | correctEdgeList.add(new TestEdge(E, H)); |
| 218 | correctEdgeList.add(new TestEdge(H, G)); |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 219 | assertTrue("The second path from A to G was incorrect.", |
| 220 | edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| 221 | } |
| 222 | |
| 223 | |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 224 | private boolean edgeListsAreEqual(List<TestEdge> edgeListOne, List<TestEdge> edgeListTwo) { |
| 225 | if (edgeListOne.size() != edgeListTwo.size()) { |
| 226 | return false; |
| 227 | } |
| 228 | TestEdge edgeOne; |
| 229 | TestEdge edgeTwo; |
| 230 | for (int i = 0; i < edgeListOne.size(); i++) { |
| 231 | edgeOne = edgeListOne.get(i); |
| 232 | edgeTwo = edgeListTwo.get(i); |
| 233 | if (!edgeOne.equals(edgeTwo)) { |
| 234 | return false; |
| 235 | } |
| 236 | } |
| 237 | return true; |
| 238 | } |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 239 | } |