| package org.onlab.graph; |
| |
| import com.google.common.collect.Lists; |
| import org.junit.Before; |
| import org.junit.Test; |
| |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Set; |
| |
| import static com.google.common.collect.ImmutableSet.of; |
| import static org.junit.Assert.assertEquals; |
| import static org.junit.Assert.assertTrue; |
| |
| /** |
| * Class for test KshortestPathsSearch. |
| */ |
| public class KShortestPathsSearchTest<V extends Vertex, E extends Edge<V>> extends GraphTest { |
| private KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>(); |
| private GraphPathSearch.Result<TestVertex, TestEdge> result; |
| |
| @Before |
| public void setUp() { |
| graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
| } |
| @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))); |
| KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>(); |
| GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weight, 1); |
| Set<Path<TestVertex, TestEdge>> resultPathSet = result.paths(); |
| assertTrue("There should not be any paths.", resultPathSet.isEmpty()); |
| } |
| |
| @Test |
| public void testSinglePath() { |
| //Tests that there is only a single path possible between A and B |
| graph = new AdjacencyListsGraph<>(vertexes(), edges()); |
| this.result = kShortestPathsSearch.search(graph, A, B, weight, 2); |
| Iterator<Path<TestVertex, TestEdge>> itr = result.paths().iterator(); |
| assertEquals("incorrect paths count", 1, result.paths().size()); |
| List<TestEdge> correctEdgeList = Lists.newArrayList(); |
| correctEdgeList.add(new TestEdge(A, B, 1)); |
| assertTrue("That wrong path was returned.", |
| edgeListsAreEqual(correctEdgeList, result.paths().iterator().next().edges())); |
| } |
| |
| @Test |
| public void testTwoPath() { |
| //Tests that there are only two paths between A and C and that they are returned in the correct order |
| result = kShortestPathsSearch.search(graph, A, C, weight, 3); |
| assertTrue("There are an unexpected number of paths.", result.paths().size() == 2); |
| Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator(); |
| List<TestEdge> correctEdgeList = Lists.newArrayList(); |
| correctEdgeList.add(new TestEdge(A, B, 1)); |
| correctEdgeList.add(new TestEdge(B, C, 1)); |
| assertTrue("The first path from A to C was incorrect.", |
| edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| correctEdgeList.clear(); |
| correctEdgeList.add(new TestEdge(A, C, 3)); |
| assertTrue("The second path from A to C was incorrect.", |
| edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| } |
| |
| @Test |
| public void testFourPath() { |
| //Tests that there are only four paths between A and E and that they are returned in the correct order |
| //Also tests the special case where some correct solutions are equal |
| result = kShortestPathsSearch.search(graph, A, E, weight, 5); |
| assertTrue("There are an unexpected number of paths.", result.paths().size() == 4); |
| Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator(); |
| List<TestEdge> correctEdgeList = Lists.newArrayList(); |
| correctEdgeList.add(new TestEdge(A, B, 1)); |
| correctEdgeList.add(new TestEdge(B, C, 1)); |
| correctEdgeList.add(new TestEdge(C, E, 1)); |
| assertTrue("The first path from A to E was incorrect.", |
| edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| correctEdgeList.clear(); |
| //There are two paths of equal length that should hold positions two and three |
| List<TestEdge> alternateCorrectEdgeList = Lists.newArrayList(); |
| correctEdgeList.add(new TestEdge(A, C, 3)); |
| correctEdgeList.add(new TestEdge(C, E, 1)); |
| alternateCorrectEdgeList.add(new TestEdge(A, B, 1)); |
| alternateCorrectEdgeList.add(new TestEdge(B, D, 2)); |
| alternateCorrectEdgeList.add(new TestEdge(D, E, 1)); |
| List<TestEdge> candidateOne = edgeListIterator.next().edges(); |
| List<TestEdge> candidateTwo = edgeListIterator.next().edges(); |
| if (candidateOne.size() == 2) { |
| assertTrue("The second path from A to E was incorrect.", |
| edgeListsAreEqual(candidateOne, correctEdgeList)); |
| assertTrue("The third path from A to E was incorrect.", |
| edgeListsAreEqual(candidateTwo, alternateCorrectEdgeList)); |
| } else { |
| assertTrue("The second path from A to E was incorrect.", |
| edgeListsAreEqual(candidateOne, alternateCorrectEdgeList)); |
| assertTrue("The third path from A to E was incorrect.", |
| edgeListsAreEqual(candidateTwo, correctEdgeList)); |
| } |
| correctEdgeList.clear(); |
| correctEdgeList.add(new TestEdge(A, B, 1)); |
| correctEdgeList.add(new TestEdge(B, E, 4)); |
| assertTrue("The fourth path rom A to E was incorrect", |
| edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList)); |
| |
| } |
| |
| @Test |
| public void testPathsFromSink() { |
| //H is a sink in this topology, insure there are no paths from it to any other location |
| for (TestVertex vertex : vertexes()) { |
| assertTrue("There should be no paths from vertex H to any other node.", |
| kShortestPathsSearch.search(graph, H, vertex, weight, 1).paths().size() == 0); |
| } |
| } |
| |
| @Test |
| public void testLimitPathSetSize() { |
| //Checks to make sure that no more than K paths are returned |
| result = kShortestPathsSearch.search(graph, A, E, weight, 3); |
| assertTrue("There are an unexpected number of paths.", result.paths().size() == 3); |
| result = kShortestPathsSearch.search(graph, A, G, weight, 1); |
| assertTrue("There are an unexpected number of paths.", result.paths().size() == 1); |
| } |
| |
| private boolean edgeListsAreEqual(List<TestEdge> edgeListOne, List<TestEdge> edgeListTwo) { |
| if (edgeListOne.size() != edgeListTwo.size()) { |
| return false; |
| } |
| TestEdge edgeOne; |
| TestEdge edgeTwo; |
| for (int i = 0; i < edgeListOne.size(); i++) { |
| edgeOne = edgeListOne.get(i); |
| edgeTwo = edgeListTwo.get(i); |
| if (!edgeOne.equals(edgeTwo)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| } |