tom | e348941 | 2014-08-29 02:30:38 -0700 | [diff] [blame^] | 1 | package org.onlab.graph; |
| 2 | |
| 3 | import org.junit.Test; |
| 4 | |
| 5 | import java.util.Set; |
| 6 | |
| 7 | import static org.junit.Assert.assertEquals; |
| 8 | |
| 9 | /** |
| 10 | * Test of the BFS algorithm. |
| 11 | */ |
| 12 | public abstract class BreadthFirstSearchTest extends AbstractGraphSearchTest { |
| 13 | |
| 14 | @Override |
| 15 | protected GraphPathSearch<TestVertex, TestEdge> graphSearch() { |
| 16 | return null; // new BreadthFirstSearch(); |
| 17 | } |
| 18 | |
| 19 | @Test |
| 20 | public void basics() { |
| 21 | runBasics(3, 8.0, 7); |
| 22 | } |
| 23 | |
| 24 | @Test |
| 25 | public void defaultWeight() { |
| 26 | weight = null; |
| 27 | runBasics(3, 3.0, 7); |
| 28 | } |
| 29 | |
| 30 | protected void runBasics(int expectedLength, double expectedCost, int expectedPaths) { |
| 31 | g = new AdjacencyListsGraph<>(vertices(), edges()); |
| 32 | |
| 33 | GraphPathSearch<TestVertex, TestEdge> search = graphSearch(); |
| 34 | Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths(); |
| 35 | assertEquals("incorrect paths count", 1, paths.size()); |
| 36 | |
| 37 | Path p = paths.iterator().next(); |
| 38 | assertEquals("incorrect src", A, p.src()); |
| 39 | assertEquals("incorrect dst", H, p.dst()); |
| 40 | assertEquals("incorrect path length", expectedLength, p.edges().size()); |
| 41 | assertEquals("incorrect path cost", expectedCost, p.cost(), 0.1); |
| 42 | |
| 43 | paths = search.search(g, A, null, weight).paths(); |
| 44 | printPaths(paths); |
| 45 | assertEquals("incorrect paths count", expectedPaths, paths.size()); |
| 46 | } |
| 47 | |
| 48 | } |