|
|
AlgorithmTests
ShortestPathTests.java
package student.algorithms.tests;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
import cusack.hcg.database.PlayablePuzzle;
import cusack.hcg.graph.algorithm.standard.tests.DataSourceAbstractTest;
import cusack.hcg.model.PuzzleInstance;
import cusack.hcg.model.PuzzleInstanceFactory;
import student.algorithms.ShortestPathLengths;
//import my.algorithms.ShortestPathLengths;
public class ShortestPathTests extends DataSourceAbstractTest {
public ShortestPathTests() {
super();
}
@Test
public void testC4() {
testPebblingNumbers(659, "0 1 1 2");
}
@Test
public void testPeterson() {
testPebblingNumbers(682, "0 2 2 1 1 1 2 2 2 2");
}
@Test
public void testKemel() {
testPebblingNumbers(124, "0 1 1 1 1 2 3 2");
}
@Test
public void testLemkexP2() {
testPebblingNumbers(1349, "0 1 1 1 1 2 3 2 2 1 2 3 2 4 3 2");
}
@Test
public void testMaybeNot() {
testPebblingNumbers(121, "0 2 2 2 1 1 2 2 2 1 2 2 2 2 2 2");
}
@Test
public void test6DudesAndFriend() {
testPebblingNumbers(139,
"0 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2");
}
@Test
public void testLemekMekel() {
testPebblingNumbers(127, "0 1 1 1 1 2 2 3 3 2 3 2 1 2 4 2 2 1 3 4 2 3 2 2 2 1 4 2 2 3 3 2 2 1 2 2 3 4 3"
+ " 2 5 3 3 2 3 4 4 3 4 3 3 2 3 4 5 3 4 3 4 5 5 6 4 4");
}
@Test
public void testCactusTrickyMerge() {
testPebblingNumbers(722, "0 1 1 2 3 3 4 4 4 5 4 5 6 6 6 7 8 6 5 6 7 8 7 8 8 9 9 10 11 11 11 5 5 6 7 8 7 6 6 7"
+ " 7 6 8 8 6 6 17 18 19 17 20 16 17 16 20 17 16 16 15 15 14 16 16 15 14 13 17 15 16"
+ " 17 16 17 18 18 19 20 15 16 14 12 15 13 16 13 17 11 10 12 13 11 9 11 39 40 41 39 38"
+ " 38 38 39 39 39 38 39 39 39 40 40 41 42 42 42 37 37 28 36 38 38 37 38 38 36 35 37 31"
+ " 31 26 27 28 27 28 29 29 30 31 37 36 34 38 23 28 37 35 22 27 35 28 38 20 25 35 21 33"
+ " 28 24 26 22 32 34 33 31 23 24 25 24 28 27 28 29 29 28 30 30 29 33 27 27 26 26 29 30 28 27 27");
}
@Test
public void test3SATThingy_Version2() {
testPebblingNumbers(1171,"0 1 2 3 4 5 5 4 4 3 4 3 5 5 2 18 17 16 18 18 17 17 16 15 14 15 15 16 15 14 13 12 11"
+ " 13 13 12 11 10 9 10 11 12 11 10 12 11 12 13 11 10 12 13 11 12 13 13 13 14 12 13 12 11 15 14 15 14"
+ " 13 14 15 14 16 14 13 15 15 17 17 16 15 13 14 16 16 14 17 9 8 10 9 7 9 8 10 8 9 11 9 10 10 13 12 14"
+ " 11 13 13 12 8 7 9 6 8 6 5 7 14 9 8 10 7 6 7 8 9 10 9 8 10 10 9 15 16 15 14 16 17 17 18 18 16 17 16"
+ " 18 15 19 19 18 20 21 20 18 17 19 20 21 21 19 20 21 10 10 9 11 11 12 12 11 12 12 12 13 13 13 13 11"
+ " 10 12 11 10 9 12 13 11 11 13 13");
}
@Test
public void testWebOfLies3() {
testPebblingNumbers(249,
"0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 2 1 1 1 1 1"
+ " 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 1"
+ " 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
+ " 2 2 2 2 2");
}
// Helper method.
private void testPebblingNumbers(int puzzle_id, String expectedResult) {
System.out.println("------------------------------");
PlayablePuzzle pp = ds.getPuzzle(puzzle_id);
PuzzleInstance pi = PuzzleInstanceFactory.createPuzzleInstance(pp);
System.out.print("Running on ");
String name = pi.getPuzzleInstanceName();
name = name.substring(name.lastIndexOf(".") + 1);
System.out.print(name);
System.out.print(" : ");
System.out.print(pp.getName());
System.out.print(" (ID ");
System.out.print(puzzle_id);
System.out.println(")");
ShortestPathLengths spl = new ShortestPathLengths();
spl.setProblemData(pi);
long start = System.nanoTime();
spl.runAlgorithm();
long end = System.nanoTime();
elapsedTime += (end - start);
assertEquals(expectedResult.trim(), spl.getResult().trim());
System.out.println(" Test passed!");
System.out.println(" time: " + (end - start) / 1000000 + " milliseconds");
}
}
|