AlgorithmTests

MSTTests.java
package student.algorithms.tests;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.awt.Point;

import org.junit.FixMethodOrder;
import org.junit.Test;
import org.junit.runners.MethodSorters;

import cusack.hcg.database.PlayablePuzzle;
import cusack.hcg.games.graph.graph.GraphInstance;
import cusack.hcg.games.weighted.WeightedInstance;
import cusack.hcg.games.weighted.minimumspanningtree.MinimumSpanningTreeInstance;
import cusack.hcg.graph.Edge;
import cusack.hcg.graph.Graph;
import cusack.hcg.graph.algorithm.standard.ContainsCycle;
import cusack.hcg.graph.algorithm.standard.tests.DataSourceAbstractTest;
import cusack.hcg.model.PuzzleInstance;
import cusack.hcg.model.PuzzleInstanceFactory;
import my.algorithms.MinimumSpanningTree;

@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class MSTTests extends DataSourceAbstractTest {
	
	@Test
	public void test01_K09() {
		verifyStuff(1477, 11);
	}

	@Test
	public void test02_K10() {
		verifyStuff(1478, 11);
	}

	@Test
	public void test03_Spiral() {
		verifyStuff(1490, 11);
	}

	@Test
	public void test04_K12() {
		verifyStuff(1479, 17);
	}

	@Test
	public void test05_K15() {
		verifyStuff(1480, 22);
	}

	@Test
	public void test06_Smallish() {
		verifyStuff(1489, 54);
	}
	
	@Test
	public void test07_Wikipedia() {
		verifyStuff(1193, 38);
	}
	
	@Test
	public void test08_3SAT() {
		verifyStuff(1192, 26);
	}

	@Test
	public void test09_K20() {
		verifyStuff(1481, 25);
	}

	@Test
	public void test10_K25() {
		verifyStuff(1482, 26);
	}

	@Test
	public void test11_K30() {
		verifyStuff(1483, 29);
	}

	@Test
	public void test12_K35() {
		verifyStuff(1484, 43);
	}

	@Test
	public void test13_K40() {
		verifyStuff(1485, 42);
	}

	@Test
	public void test14_K45() {
		verifyStuff(1486, 44);
	}

	@Test
	public void test15_K50() {
		verifyStuff(1487, 54);
	}
	@Test
	public void test16_Big_un() {
		verifyStuff(1187, 51);
	}

	@Test
	public void test17_7Dudes() {
		verifyStuff(1488, 1072);
	}

	@Test
	public void test18_LemkeFamilyGraph() {
		verifyStuff(1492, 337);
	}

	@Test
	public void test19_WebOfLies3() {
		verifyStuff(1491, 1510);
	}

	public void verifyStuff(int puzzle_id, int cost) {
		System.out.println("Testsing solution for puzzle " + puzzle_id);

		// Run the algorithm and get the result
		MinimumSpanningTree msti = new MinimumSpanningTree();

		PlayablePuzzle pp = ds.getPuzzle(puzzle_id);
		PuzzleInstance pi = PuzzleInstanceFactory.createPuzzleInstance(pp);
		msti.setProblemData((MinimumSpanningTreeInstance) pi);
		msti.runAlgorithm();
		String results = msti.getResult();

		// Now test the result against the
		try {
			// -------------------------------------------
			// Do they have the correct weight?
			String[] parts = results.split(";");
			int reportedWeight = Integer.parseInt(parts[0]);
			assertEquals("Incorrect weight for MST", cost, reportedWeight);

			// -------------------------------------------
			// Make sure the number of edges is correct.
			String[] edges = parts[1].split(" ");
			assertEquals("Wrong number of edges", pi.getNumberOfVertices() - 1, edges.length);

			// -------------------------------------------
			// Now construct the MST and make sure it is a spanning tree
			// and has correct weight.
			// (Get the puzzle from the database again since their algorithm
			// might have changed it).
			PuzzleInstance puz = PuzzleInstanceFactory.createPuzzleInstance(pp);
			Graph graph = puz.getGraph().getGraph();
			WeightedInstance puzzle = (WeightedInstance) puz;

			// The new graph that will hold the MST.
			Graph mst = new Graph();
			for (int i = 0; i < graph.getNumberOfVertices(); i++) {
				mst.addNewVertex(new Point(0, 0));
			}

			// Extract the edge weights and construct the MST.
			int totalWeight = 0;
			for (int i = 0; i < edges.length; i++) {
				String e = edges[i].substring(1, edges[i].length() - 1);
				String[] verts = e.split(",");
				int v1 = Integer.parseInt(verts[0]);
				int v2 = Integer.parseInt(verts[1]);
				// System.out.println("Adding edge between "+v1+" and "+v2);
				Edge edge = Edge.createEdge(graph.getVertexAtIndex(v1), graph.getVertexAtIndex(v2));
				int weight = puzzle.getWeightForEdge(edge);
				totalWeight += weight;

				mst.addEdge(mst.getVertexAtIndex(v1), mst.getVertexAtIndex(v2));
			}

			// Make sure the edges form a tree.
			GraphInstance gi = new GraphInstance(mst);
			ContainsCycle cc = new ContainsCycle();
			cc.setProblemData(gi);
			cc.runAlgorithm();
			String result = cc.getResult();
			assertEquals("Edges do not form a spanning tree.", "false", result);

			// -------------------------------------------
			// Finally, do the edges they reported actually add up to the right number?
			assertEquals("Edge weights do not add up to correct number", reportedWeight, totalWeight);

		} catch (Exception e) {
			e.printStackTrace();
			fail("Exception occured so the data must be formatted incorrectly. "
					+ "Stack trace was printed to help you debug.");
		}
	}
}