package ferzle.algorithms;
import java.util.ArrayList;
import java.util.HashSet;
import cusack.hcg.comm.DataSource;
import cusack.hcg.database.PlayablePuzzle;
import cusack.hcg.database.User;
import cusack.hcg.games.weighted.WeightedInstance;
import cusack.hcg.graph.Edge;
import cusack.hcg.graph.Vertex;
import cusack.hcg.model.PuzzleInstance;
import cusack.hcg.model.PuzzleInstanceFactory;
public class ValidTSPSolutionChecker {
DataSource ds;
public static void main(String[] args) {
ValidTSPSolutionChecker checker = new ValidTSPSolutionChecker();
// Change the details on the following two lines to match the graph/output you want to test.
int puzzleID = 1322;
String sol = "92:1 9 11 12 2 8 3 10 7 4 6 14 0 13 5";
checker.checkSolution(puzzleID, sol);
}
/*
* Checks the valididy of a TSP solution.
* Replace puzzleID with the correct puzzleID that you ran your algorithm on,
* and sol with the output of your algorithm and run it.
*/
public ValidTSPSolutionChecker() {
if (ds == null) {
ds = DataSource.createDS(false);
User u = null;
while (u == null) {
String user = "guest";
String pass = "guest";
u = ds.logInUser(user, pass);
}
}
}
public void checkSolution(int puzzleID, String solution) {
PlayablePuzzle p = ds.getPuzzle(puzzleID);
if (p == null) {
System.out.println("Puzzle not found.");
} else {
PuzzleInstance pi = PuzzleInstanceFactory.createPuzzleInstance(p);
if (pi instanceof WeightedInstance) {
WeightedInstance wi = (WeightedInstance) pi;
int n = wi.getNumberOfVertices();
int solWeight = 0;
int []sol = new int[n];
try {
String parts[] = solution.split(":");
solWeight = Integer.parseInt(parts[0]);
// -------------------------------------------------------------
// First check that the solution is a permutation of
// [0...(n-1)]
String verts[] = parts[1].split(" ");
if (verts.length != n) {
System.out.println("**** The list does not contain precisely " + n + " vertices.");
return;
}
HashSet<Integer> vertSet = new HashSet<Integer>();
int ind=0;
for (String s : verts) {
int num = Integer.parseInt(s);
sol[ind]=num;
ind++;
vertSet.add(num);
}
for (int i = 0; i < n; i++) {
if (!vertSet.contains(Integer.valueOf(i))) {
System.out.println("**** " + i + " is missing from the list");
return;
}
}
// -------------------------------------------------------------
// Now verify that the cost they specify is actually the
// cost.
ArrayList<Vertex> vertices = wi.getVertices();
int actualWeight = 0;
for(int i=0;i<n-1;i++) {
int w = wi.getWeightForEdge(Edge.createEdge(vertices.get(sol[i]),vertices.get(sol[i+1])));
actualWeight+=w;
}
int w = wi.getWeightForEdge(Edge.createEdge(vertices.get(sol[n-1]),vertices.get(sol[0])));
actualWeight+=w;
if(actualWeight==solWeight) {
System.out.println("The solution weight is correct!");
System.out.println("NOTE: This algorithm does NOT verify that the solution is optimal.\n"
+ "It only verfies that it is a valid Hamiltonian cycle and\n"
+ "that the weight reported is the weight of the cycle.");
} else {
System.out.println("**** The solution weight of "+solWeight+" is incorrect. It should be "+actualWeight);
}
} catch (NumberFormatException e) {
System.out.println("**** Solution is not in the correct format.");
}
} else {
System.out.println("**** Not a Wieghted Graph!");
}
}
}
}