// TRAII_25_X5_test.java SJ import fi.uef.cs.tra.Graph; import fi.uef.cs.tra.Edge; import fi.uef.cs.tra.Vertex; import java.util.*; public class TRAII_25_X5_test { static TRAII_25_X5 myClass = new TRAII_25_X5_skeleton(); // ^^^^ own id here static Random rnd = new Random(); public static void main(String[] args) { // number of vertices and edges int N = 10; if (args.length > 0) N = Integer.parseInt(args[0]); int E = 10; if (args.length > 1) E = Integer.parseInt(args[1]); // random seed int seed = 42; if (args.length > 2) seed = Integer.parseInt(args[2]); rnd.setSeed(seed); // amount of printing int print = 8; if (args.length > 3) print = Integer.parseInt(args[3]); boolean ok = true; boolean oke = testAllPPathsExample(print); if (oke) System.out.println("\nWith example graph, all test gave expected amount of valid paths."); ok &= testAllPPaths(2, 1, 5f, 10f, seed, print); ok &= testAllPPaths(2, 1, 50f, 10f, seed, print); ok &= testAllPPaths(3, 3, 5f, 10f, seed, print); ok &= testAllPPaths(4, 3, 5f, 10f, seed, print); ok &= testAllPPaths(5, 5, 5f, 10f, seed, print); ok &= testAllPPaths(N, E, 5f, 10.0f, seed, print); rnd.setSeed(System.currentTimeMillis()); int nTest = 50; int k; int errors = 0; for (k = 0; k < nTest; k++) { if (!testAllPPaths(rnd.nextInt(k/3+1)+1, rnd.nextInt(k/2+1)+2, rnd.nextFloat()*10+1, rnd.nextFloat()*20+11, (int)(System.currentTimeMillis()), 0)) errors++; if (errors > 10) break; } if (errors > 0) ok = false; System.out.println("\n" + k + " random path tests " + (k - errors) + " did not gave wrong paths."); ok = ok && oke; if (ok) System.out.println("\nAll tests gave valid paths."); else System.out.println("\nSome paths had errors."); System.out.println("Program does NOT test if the result had all the expected paths."); } // main() /** * Test all paths search for precomputed results. * @param print amount of printing * @return true if all paths are valid, false otherwise */ static boolean testAllPPathsExample(int print) { if (print > 0) System.out.println("\nPath test exampler"); // create an example graph with results List tl = new ArrayList<>(); Graph G = makeExampleInput(tl, print); boolean ok = true; for (testResult tt : tl) { if (print > 1) System.out.println("\n Test from vertex " + tt.start + ", maxW " + tt.maxLen + " paths"); List> result = myClass.allMaxPPaths(G, tt.start, tt.maxLen); if (print > 1) System.out.println(" Got " + result.size() + " paths, expected " + tt.paths); if (result.size() != tt.paths) { System.out.println(" Wrong number of paths: " + result.size() + " expected " + tt.paths); ok = false; } ok &= areValidPaths(result, tt.start, tt.maxLen, print); } if (print > 0) System.out.println("Path result " + ok); return ok; } /** * Test all path search * @param vertices number of vertices. * @param edges number of edges * @param maxEdgeW maximum edge weight * @param maxPathW path weight to test * @param seed random number generator seed * @param print amount of printing * @return true if all paths are valid, false otherwise */ static boolean testAllPPaths(int vertices, int edges, float maxEdgeW, float maxPathW, int seed, int print) { if (print > 0) System.out.println("\nPath test, vertices=" + vertices + " edges="+edges + " max weight=" + maxPathW); Graph G = makeInput(vertices, edges, maxEdgeW, seed, print); boolean ok = true; for (Vertex v : G.vertices()) { if (print > 1) System.out.println(" Test from vertex " + v + " maxW " + maxPathW + " paths"); List> tulos = myClass.allMaxPPaths(G, v, maxPathW); ok &= areValidPaths(tulos, v, maxPathW, print); } if (print > 0) System.out.println("Path test " + ok); return ok; } /** * Test if the given path is valid. * Tarkastaa onko annettu path kelvollinen. * @param path path * @param start expected first vertex * @param maxW maximum weight * @param print amount of printing * @return true if path is valid, false otherwise */ static boolean isValidPath(List path, Vertex start, float maxW, int print) { float weight = 0; boolean ok = true; if (print > 4) System.out.println(" Check path: " + path); if (path.size() < 2) { if (print > 2) System.out.println(" Too short path: " + path); return false; } ListIterator li = path.listIterator(); Vertex prev = li.next(); if (prev != start) { if (print > 2) System.out.println(" Wrong start vertex: " + prev + ", expected: " + start); ok = false; } if (path.size() != new HashSet<>(path).size()) { if (print > 2) System.out.println(" some vertex twice in the path: " + path); ok = false; } while (li.hasNext()) { Vertex next = li.next(); Edge e = prev.getEdge(next); if (e == null) { if (print > 2) System.out.println(" Edge: " + prev + "-" + next + " does not exist!"); ok = false; } else weight += e.getWeight(); prev = next; } if (print > 2 && weight > maxW+0.04f) System.out.println(" Too heavy (" + weight + " max=" +maxW+ ") path: " + path); return (ok && weight <= maxW+0.04f); // allow rounding errors } /** * Test if paths are valid. * @param pathList list of paths * @param start expected first vertex * @param maxW maximum weight of path * @param print amount of printing * @return true if all paths are valid, false otherwise */ static boolean areValidPaths(List> pathList, Vertex start, float maxW, int print) { boolean ok = true; if (print > 3) System.out.println(" Checking path list, there are " + pathList.size() + " paths"); if (pathList.size() != new HashSet<>(pathList).size()) { if (print > 2) System.out.println(" Some paths are repeated!"); ok = false; } for (List L : pathList) { ok &= isValidPath(L, start, maxW, print); } if (print > 3) System.out.println(" Path check result: " + ok); return ok; } /** * Generate a random input graph. * @param vertices number of vertices * @param edges number of edges * @param maxEdgeW maximum edge weight * @param seed random number generator seed * @param print amount of printing * @return new graph */ static Graph makeInput(int vertices, int edges, float maxEdgeW, int seed, int print) { Graph G = GraphMaker.createGraph(vertices, edges, seed, maxEdgeW); if (print > 2) { System.out.println(" Graph: \n" + GraphMaker.toString(G, 1)); } return G; } /** * Build an example graph for testing. * The expected path counsts were calculated manually. * @param results list to store expeced results * @return example graph */ static Graph makeExampleInput(List results, int print) { Graph G = new Graph(); Vertex[] V = new Vertex[6]; V[0] = G.addVertex("a"); V[1] = G.addVertex("b"); V[2] = G.addVertex("c"); V[3] = G.addVertex("d"); V[4] = G.addVertex("e"); V[5] = G.addVertex("f"); V[0].addEdge(V[1], 6f); V[0].addEdge(V[2], 3f); V[1].addEdge(V[3], 2f); V[2].addEdge(V[3], 1f); V[2].addEdge(V[4], 8f); V[2].addEdge(V[5], 4f); V[3].addEdge(V[4], 9f); V[3].addEdge(V[5], 7f); V[4].addEdge(V[5], 5f); if (print > 1) { System.out.println(GraphMaker.toString(G, 1)); System.out.println("a---3---c---4---f"); System.out.println("| |\\ /|"); System.out.println("| | 8 7 |"); System.out.println("| | \\ / |"); System.out.println("6 1 X 5"); System.out.println("| | / \\ |"); System.out.println("| | / \\ |"); System.out.println("| |/ \\|"); System.out.println("b---2---d---9---e"); } results.add(new testResult(V[0], 2, 0)); results.add(new testResult(V[0], 3, 1)); results.add(new testResult(V[0], 7, 5)); results.add(new testResult(V[0], 8, 6)); results.add(new testResult(V[2], 15, 16)); results.add(new testResult(V[2], 20, 25)); results.add(new testResult(V[2], 8, 6)); results.add(new testResult(V[3], 8, 6)); results.add(new testResult(V[3], 100, 32)); return G; } /** * helper class to store expected results. * DO NOT USE IN YOUR SOLUTION. */ static class testResult { Vertex start; float maxLen; int paths; public testResult(Vertex start, float maxLen, int paths) { this.start = start; this.maxLen = maxLen; this.paths = paths; } } }