| /* |
| * Copyright 2017-present 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.hamcrest.Matchers.containsInAnyOrder; |
| import static org.junit.Assert.*; |
| |
| import java.util.ArrayList; |
| import java.util.List; |
| import java.util.stream.Collectors; |
| import java.util.stream.Stream; |
| |
| import org.junit.Before; |
| import org.junit.Test; |
| |
| import com.google.common.collect.ImmutableList; |
| |
| public class LazyKShortestPathsSearchTest extends GraphTest { |
| |
| LazyKShortestPathsSearch<TestVertex, TestEdge> sut; |
| |
| @Before |
| public void setUp() { |
| sut = new LazyKShortestPathsSearch<>(); |
| } |
| |
| @Test |
| public void noPath() { |
| graph = new AdjacencyListsGraph<>(of(A, B, C, D), |
| of(new TestEdge(A, B), |
| new TestEdge(B, A), |
| new TestEdge(C, D), |
| new TestEdge(D, C))); |
| Stream<Path<TestVertex, TestEdge>> result = sut.lazyPathSearch(graph, A, D, weigher); |
| assertEquals("There should not be any paths.", 0, result.count()); |
| } |
| |
| @Test |
| public void fourPath() { |
| graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
| Stream<Path<TestVertex, TestEdge>> result = sut.lazyPathSearch(graph, A, E, weigher); |
| List<Path<TestVertex, TestEdge>> rList = result.limit(42).collect(Collectors.toList()); |
| |
| assertEquals("There are an unexpected number of paths.", 4, rList.size()); |
| |
| // The shortest path |
| List<TestEdge> expectedEdges = new ArrayList<>(); |
| expectedEdges.add(new TestEdge(A, B, W1)); |
| expectedEdges.add(new TestEdge(B, C, W1)); |
| expectedEdges.add(new TestEdge(C, E, W1)); |
| |
| assertEquals("The first path from A to E was incorrect.", |
| expectedEdges, rList.get(0).edges()); |
| assertEquals(W3, rList.get(0).cost()); |
| |
| |
| // There are two paths of equal cost as next shortest path |
| expectedEdges.clear(); |
| expectedEdges.add(new TestEdge(A, C, W3)); |
| expectedEdges.add(new TestEdge(C, E, W1)); |
| |
| List<TestEdge> alternateEdges = new ArrayList<>(); |
| alternateEdges.add(new TestEdge(A, B, W1)); |
| alternateEdges.add(new TestEdge(B, D, W2)); |
| alternateEdges.add(new TestEdge(D, E, W1)); |
| |
| assertThat(ImmutableList.of(rList.get(1).edges(), rList.get(2).edges()), |
| containsInAnyOrder(expectedEdges, alternateEdges)); |
| assertEquals(W4, rList.get(1).cost()); |
| assertEquals(W4, rList.get(2).cost()); |
| |
| |
| // last shortest path |
| expectedEdges.clear(); |
| expectedEdges.add(new TestEdge(A, B, W1)); |
| expectedEdges.add(new TestEdge(B, E, W4)); |
| |
| assertEquals("The fourth path rom A to E was incorrect", |
| expectedEdges, rList.get(3).edges()); |
| assertEquals(W5, rList.get(3).cost()); |
| } |
| |
| } |