FIT2004 S2/2018: Assignment 4
Total marks: 5
DEADLINE: Friday, 12-Oct-2018 23:55:00 AEST
LATE PENALTY: 25 % per day
CLASS: You may be interviewed by the tutor who may ask you a series of questions to assess your understanding of this exercise, and gauge how you implemented it. You will also be given feedback on your assignment. Failing to attend will result in you being awarded zero mark for the assignment (unless you have an approved special consideration). It is required that you implement this exercise strictly using Python programming language. Practical work is marked on the time and space complex- ity of your program and also on your understanding of the program. A perfect program with zero understanding implies you will get zero marks! “Forgetting” is not an acceptable explanation for lack of understanding. Markers are not obliged to mark programs that do not run or that crash.
SUBMISSION REQUIREMENT: You will need to submit a zipped file con- taining your Python program (named get lucky.py) as well as a PDF file briefly describing your solution and its space and time complexity. The PDF file must give an outline of your solution (e.g., a high level idea of how did you solve it) and the worst-case space and time complexity of your solution. Penalties will be applied if you fail to submit the PDF file. The zipped file is to be submitted on Moodle before the deadline.
Important: The assignments will be checked for plagiarism using an advanced pla- giarism detector and the students will be interviewed by tutors to demonstrate the understanding of their code. Last year, many students were detected by the plagia- rism detector and almost all got zero mark for the assignment and, as a result, many failed the unit. “Helping” others is NOT okay. Please do not share your solutions with others. If someone asks you for help, ask them to visit us during consultation hours for help.
Minimum Detour Path
Ring ring. You take the call. It is Alice on the other side.
Alice: “I want to have a chat with you. Can I come to your place if you are home?”
An alarm bell starts ringing in your head “Did she get to know about my scrabble 2.0 project for Cindy?”. You worriedly reply: “hmmmm…okay, yeah sure, I am home”.
You spend next 15 minutes thinking about different responses to calm her down. Finally, Alice arrives. To your surprise, she is in a really good mood and is holding a box of sweets and hands it over to you saying “Here are some sweets for a sweet friend. Your algorithm helped me to optimize my ebay listings and maximize the profit. I am so grateful to you.”
You are happy to hear that your hardwork helped her, and even happier to find out that she does not know about your scrabble 2.0 project. “Thanks. I must admit that it took me
⃝c Muhammad Aamir Cheema, Monash University
a while to understand the dynamic programming and solve the problems. And I still think I need to practice more to master the dynamic programming. Anyway, never mind Alice”. Alice smiles and says, “Practice makes perfect! :)’.
You nod, “Yes, you are right! Anyhoo, I hope your ebay business is not taking too much of your time and you are having fun.”
Alice exhales, “The competition is cut throat but I am having fun. I enjoy coming up with new business strategies to compete with other businesses. For example, I am selling some heavy products for which the postage cost is quite high. To attract more customers, I have introduced a promotion that promises free same-day delivery to one lucky customer everyday. To keep the same-day delivery promise and to save the postage cost, I deliver the order myself, take a selfie while delivering the product and post it on our Facebook page to promote my business. This has significantly increased the number of orders I receive.”
You: “That’s interesting. But it must be quite hectic to deliver the order yourself.”.
Alice: “Exactly! That’s why I need your help in choosing the “lucky” customer. Everyday, I receive many orders from local customers (customers living in Melbourne) and my plan is to choose a customer such that delivering to him/her minimizes the distance I need to drive. For example, if I am going from home to work, I want to find the shortest route from home to work that passes through the delivery address of at least one customer. That will be the “lucky” customer ;)”
You get sarcastic: “That’s so transparent Alice :P”
Alice ignores your sarcasm and continues: ”Well, I have downloaded Melbourne road network from OpenStreetMap. I have also written a script that obtains all recent orders from ebay and maps the delivery addresses for each order on the map. However, I do not know much about graph algorithms and am not sure how to find the shortest route.”
You: “What a coincidence! We recently learned shortest path algorithms. I was planning to solve some graph problems to improve my understanding. I will be happy to help. Give me the details”.
Alice is so happy to hear this and explains the detailed requirements which are formally de- scribed below.
Input
The input files edges.txt and customers.txt are provided in the zipped file tester.zip which can be downloaded from Moodle. Below are the first few lines from edges.txt.
Vertices of the road network have sequential IDs starting from 0. The first line in edges.txt indicates the maximum ID of any vertex in the graph. For example, in the sample graph given in edges.txt, the maximum ID for any vertex is 1000. Every other line in edges.txt corresponds to an edge in the road network: first two columns are the IDs of vertices and the third column is the length of the edge connecting the two vertices. E.g., the second line indicates that there is an edge between the vertices with IDs 0 and 1 and the edge length is 950 meters. All roads in the network are bidirectional, i.e., the graph is not directional.
1000 0 1 950 0 2 3590 1 3 3340 2 5 1370
2
The file customers.txt contains the locations (delivery addresses) of customers. We assume that each customer is located on one of the vertices in the graph. We also assume that a vertex cannot have more than one customers. Below are the first 3 lines from customers.txt denoting that we have a customer on each of the vertices with IDs 5, 54 and 145.
Task 1: Computing shortest path
The first task is to compute the shortest path and shortest distance between any two given vertices s and t. The time complexity of your algorithm must be O(E log V ) and the space complexity must be O(V + E) where V and E are the total number of vertices and edges in the graph, respectively.
You have been provided with a template get_lucky.py which reads the input (IDs of source and target vertices) and provides a function print_solution(path,distance,task_id) to help you printing the output in the required format. The function takes three parame- ters, where path is a list containing vertices in the order in which they appear in the path, distance is the length of the path and task_id is the task for which you want to print the solution (which should take the value 1 for task 1 and 2 for task 2). For example, assume that the shortest path between the source vertex 222 and the target vertex 183 is 220 –> 202 –> 186 –> 183 with total distance 1580. To print this in the required format, you must create a list path=[220,202,186,183] and call print_solution(path,1580,1). The function will print the following:
You MUST use print_solution function to print your output. Task 2: The minimum detour path
The minimum detour path is the shortest route from s to t that passes through at least one customer. Your algorithm must print the minimum detour path and its total length (called minimum detour distance). The following is a naive approach to find the minimum detour path and minimum detour distance.
5 54 145
Shortest path: 220 --> 202 --> 186 --> 183 Shortest distance: 1580
# naive algorithm minDetourDist = infinity luckyCustomer = -1 for each customer c
detourDist = dist(s,c) + dist(c,t) #use Disjkstra’s algorithm
if detourDist < minDetourDist:
luckyCustomer = c
minDetourDist = detourDist
minDetourPath = path from s to luckyCustomer + path from luckyCustomer to t print minDetourDist and shortestDetourPath
3
In the above algorithm the shortest distance/path between two vertices is computed using Dijkstra’s algorithm. The for loop in the above algorithm requires calling Dijkstra’s algorithm 2C times where C is the total number of customers. Therefore, the time complexity of the above algorithm is O(C · E log V ). Your solution must compute the minimum detour path and minimum detour distance in O(E log V ) time complexity and O(V + E) space complexity in the worst-case.
Similar to Task 1, you must use print_solution(path,distance,task_id) function to print your output for the task 2 in the required format. For example, if the source vertex is 222 and the target vertex is 183, the minimum detour path is 220 –> 202 –> 186 –> 183 –> 200 –> 183 with distance 3240 meters. Here, the customer is located on the vertex 200. To print this in the required format, you must create a list path=[220,202,186,183,200,183] and call print_solution(path,3240,2) (note that the value of task_id is 2). The function will print the following:
Note that the output displays (C) with the vertex 200 denoting that this vertex contains a customer.
It is possible that there are more than one minimum detour paths. In this case, you can print any path of your choice. Your answer will be considered correct if the detour path is the minimal, i.e., there does not exist any other path between s to t that has a smaller distance and contains at least one customer.
Sample Output
This section provides sample output for different pairs of source and target vertices. You have also been provided with a naive solution in naive-solution.py which uses a text file FW.txt that contains pre-computed all-pairs shortest distances (computed by Floyd-Warshall algorithm) to solve the two tasks. You can run naive-solution.py to check sample output for different pairs of source and target vertices. Below are some examples.
Minimum detour path: 220 --> 202 --> 186 --> 183 --> 200(C) --> 183 Minimum detour distance: 3240
Enter source vertex: 220 Enter target vertex: 183
Shortest path: 220 --> 202 --> 186 --> 183 Shortest distance: 1580
Minimum detour path: 220 --> 202 --> 186 --> 183 --> 200(C) --> 183 Minimum detour distance: 3240
As stated earlier, in the minimum detour path, the vertex which has a customer located on it is denoted as (C), i.e., the vertex 200 has a customer located on it. Note that you do not have to worry about printing it as the function print_solution does this itself for every vertex which has a customer located on it.
Below is another example where the shortest distance is 320 meters and the minimum detour distance is 71520 meters (and the lucky customer is 315).
4
Enter source vertex: 580 Enter target vertex: 585
Shortest path: 580 --> 585 Shortest distance: 320
Minimum detour path: 580 --> 556 --> 536 --> 512 --> 497 --> 488 --> 481 --> 479 --> 491 --> 535 --> 591 --> 270 --> 239 --> 238 --> 240 --> 241 --> 245 --> 250 --> 255 --> 277 --> 284 --> 297 --> 303 --> 315(C) --> 303 --> 297 --> 284 --> 277 --> 255 --> 250 --> 245 --> 241 --> 240 --> 238 --> 239 --> 270 --> 591 --> 535 --> 491 --> 479 --> 481 --> 488 --> 497 --> 512 --> 536 --> 556 --> 580 --> 585
Minimum detour distance: 71520
It is also possible that the shortest path may be the same as the minimum detour path. See the example below.
Enter source vertex: 947 Enter target vertex: 1000
Shortest path: 947 --> 948 --> 949 --> 951(C) --> 977 --> 995 --> 1000 Shortest distance: 8500
Minimum detour path: 947 --> 948 --> 949 --> 951(C) --> 977 --> 995 --> 1000 Minimum detour distance: 8500
In some cases, a minimum detour path may contain more than one customers. In such case, Alice will manually look at the route and decide the “lucky” customer herself. Your task is only to return the minimum detour path containing at least one customer. In the example below, the minimum detour path contains two customers (767 and 747).
Enter source vertex: 849 Enter target vertex: 790
Shortest path: 849 --> 848 --> 846 --> 836 --> 831 --> 803 --> 731 --> 714 --> 720 --> 724 --> 727 --> 736 --> 790 Shortest distance: 16880
Minimum detour path: 849 --> 848 --> 846 --> 836 --> 831 --> 837 --> 838 --> 842 --> 852 --> 862 --> 868 --> 886 --> 904 --> 824 --> 815 --> 797 --> 767(C) --> 763 --> 747(C) --> 734 --> 723 --> 722 --> 721 --> 718 -->
717 --> 716 --> 715 --> 714 --> 720 --> 724 --> 727 --> 736 --> 790 Minimum detour distance: 18510
Note that it is also possible that a customer is located on a source or a target vertex. In the example below, the customer is located on the source vertex.
5
Enter source vertex: 315 Enter target vertex: 255
Shortest path: 315(C) --> 303 --> 297 --> 284 --> 277 --> 255 Shortest distance: 2230
Minimum detour path: 315(C) --> 303 --> 297 --> 284 --> 277 --> 255 Minimum detour distance: 2230
The user may enter the same ID for both source and the target vertices, i.e., Alice may want to start from her home, deliver an item and then return to her home. Below are some examples.
Enter source vertex: 300 Enter target vertex: 300
Shortest path: 300 Shortest distance: 0
Minimum detour path: 300 --> 277 --> 284 --> 297 --> 303 --> 315(C) --> 303 --> 297 --> 284 --> 277 --> 300 Minimum detour distance: 4320
In the example below, the target vertex is the same as the source vertex and a customer is located on the source vertex. Therefore, the shortest distance and minimum detour distance both are 0.
Enter source vertex: 315 Enter target vertex: 315
Shortest path: 315(C) Shortest distance: 0
Minimum detour path: 315(C) Minimum detour distance: 0
Things to note
You will lose all marks for a given task if your algorithm does not produce correct results for the task for all sample testcases shown above. Also, heavy penalties are applied if your complexity is worse than the required complexity and you may lose all marks if the complexity is similar to that of the naive algorithm. Your algorithm will also be checked on a different road network and customers file using a variety of test cases. Task 2 is the critical part of the assignment and is worth majority of the marks for this assignment. Therefore, do not assume that you will get around 50% marks by completing only the task 1.
You have also been provided with a tester which you can use to ensure that your output matches the sample output. If you have issues using testers, contact your tutors or attend a consultation.
6