The instructions are in the pdf. The due date is this coming Wednesday at 4:00
4 5 3 1 2 8 1 3 7 4 3 2 4 2 3 2 3 5 1 2 2 4 3 2 CS 3353 Fall 2022 Programming Homework 2 – The least annoying path Due Date: 10/28/2020 (Fri) 11:59 pm. Tony & Priscilla is a retired couple who like to travel (by driving) a lot. However, when the plan their trip to travel from 1 city to another, their priority is a bit different from others. Since they have retired, they have all the time in the world, so finding the shortest path from one city to another is not their priority. However, they hate traffic and bad road conditions and other kind of annoyances. So they would like to find a path that they don’t need to endure too strong an annoyance. Another thing that is different is that Tony and Priscilla don’t mind traveling long distances where there are some annoyances along the way, but they definitely want to avoid traveling on ANY road that has high annoyance, even if it means they can reach they destination faster or has to endure such high annoyance for just a short period of time. (Once you get to a certain age, you will understand …. ) To help them do it, they have mapped out roads between each pair of cities and give them a (floating point number) score (> 0), where the larger the number, the more annoying the road is. So when they plan a trip to a city where they have to go through other cities, they will always take the path such that the most annoying road in the path is the most bearable. (Note the sum of all “annoying- ness” of the edges along the path does not mean anything in this problem). This can be converted to the following graph problem: given a weight graph G=(V,E). Define the annoying-ness of a path from vertex s to vertex t to be the maximum weight of an edge among all the edges along the path. The task above becomes that giving s and t, find the path that has the least annoying-ness. Notice that if there are multiple paths that have the same least annoying-ness, you just need to return one path. Example For the following graph: S A B C D S T E F G H 1 10 8 8 1 3 6 6 7 6 6 The least annoying path from S to T is the path S->E->F->G->H->T, with the cost 7 (along the path, the edge with the maximum weight has cost 7). For path S->A->T has cost 10, and the path S->B->C->D->T, the cost is 8. Algorithm For this problem: given two vertices s and t in an weighted undirected graph G, find the least annoying path (i.e. the path such that the weight of the maximum edge along the path is minimized.) Find the MST of G, and then find the path from s to t ONLY using the edges on that MST. In this homework, you are to implement a solution to this problem using this algorithm. You have the choice of how to implement the MST, and how to find the path from s to t on the MST. Program specification You are to implement following class called MyGraph. It represents an undirected graph with weights on each edge. You must implement the following methods: Methods: • Constructors: o MyGraph(int n): Create a graph with n vertices. The vertices are labelled 1..n o MyGraph(const MyGraph& g): Construct a new graph that is a copy of g • Methods o bool AddEdge(int a, int b, float w): Add an edge between vertex a and b, with weight w. If the edge already exists or a vertex is not on the graph, do nothing and return false. Otherwise (addition is successful) return true. o void Output(ostream& os): Output the graph to the ostream& specified. Your output should have the following format: ▪ The first line print the number of vertices. ▪ Each subsequent line prints an edge. It should print three numbers: the two vertices associated with the edge (print the vertex with the smaller number first), and the weight of the edge. You should have one space character between the numbers, and no space at the end. You can order the edges whatever way you want. o pair<>
, float> HW2Prog(int s, int t): This is the main function that you have to implement for this homework. ▪ The function will find a least annoying path from s to t. The return will be a pair. The first item of the pair (vector) denotes the path from s to t. The first item of the vector should be s and the last one should be t, and the vector is the order of the vertices on the path from s to t. The second item (float) denote the actual annoyance (i.e. the weight of the edge that has maximum weight on the path). . You will be given a driver program, hw2main.C. The program will read in a file containing a graph, together with the pairs of vertices where the least annoying path is wanted. It will then run the main program and output the result. The input file format is as follows. • The first line contains three integers, which represent the number of vertices (n) of the graph, the number of edges (e), and the number (c) of least annoying path to be found. • The next e lines contain the edges of the graph. Each line has three numbers, the first two number represents the two vertices, where the third represent weight of the edge. • The next c lines contain the pair of vertices where the least annoying path is needed. Each line has two numbers, s and t respectively. You can assume the input file is correctly formatted. If not, you are not responsible. Task You should implement all the methods in the class. Note the following: • You are allowed to create extra methods for the graph class. • You are allowed to create extra classes to be used. • You are free to choose any implementation of the graph you prefer (adjacency matrix, adjacency list etc.) • You can also choose which algorithm you use (Kruskal, Prim, etc.) What to hand in You have to hand in two files (zipped into a .zip file) (-20 if you hand in more than two files): • One file contains all your source code (including your implementation of MyGraph class, but without the code for hw2main.C). You should call your file MyGraph.h • One file containing a description on how you implement your algorithms for HW2Prog method. Include your choice of how your graph is being represented and what algorithm you use. Grading For this homework, full mark is 100. You get 95 points for successful implementation of the algorithm. Partial credit will be given. For all programs that is successful, I will run more tests and measure the running time of the program. Those who run fastest will get extra score as follows: Rank Bonus 1 60 2 45 3 35 4-6 25 7-10 20 11-15 15 16-25 10 26-35 5 o If there are ties the bonus will be averaged. For example, if there are two people tied for second, each of them will get (45+35)/2 = 30 bonus points. Notice that we measure ties not by exact time, but that the difference in running time is small enough. o There will be multiple test cases with various size graphs and solutions. Each program will be run multiple times and the average of the time will be used. Different test cases will be comparing independently (so we do not add the run time of 5 cases together). Notice that some test case may contains up to 1000s of vertices and 100000s of edges. Bonus 2 You get 15 extra points if you can prove that the algorithm is correct. You should include an extra pdf file (named proof.pdf) that describe your proof. (Hint: contradiction is probably the easiest way to do it). Example Suppose the input file looks like this 4 5 3 1 2 8 1 3 7 4 3 2 4 2 3 2 3 5 1 2 2 4 3 2 The main program will first create a graph of 4 vertices, with the following 5 edges: Then you should find the least annoying path of the following: • From 1->2 : path 1->3->2, weight 7 (notice that 1->3->4->2 is also a solution, your program can output either of those). • From 2->4 : path 2->4, weight 3 • From 3->2 : path 3->4->2, weight 3 For your HW2Prog(int s, int t) function in this case • HW2Prog(1, 2) will return the vector [1 3 2] and the number 7 1 2 4 3 8 7 5 3 2 • HW2Prog(2, 4) will return the vector [2 4], and the number 3 • HW2Prog(3, 2) will return the vector [3 4 2], and the number 3