Assignment 3: The Hobbit Reunion (32 marks)
Due: Thursday, March 27, 2014 (11:59pm)Learning Objectives
The purpose of this assignment is to learn about network-layer routing algorithms. Along the way, you will also explore some of the tradeoffs between different design decisions in routing, and get a sense of how network topology affects the run-time of routing algorithms.
Background
In the blockbuster Hobbit movie, 13 dwarf friends reunite for a special meeting at the home of Bilbo Baggins, a Hobbit who lives in a Hobbit hole in Bag Hill. The meeting is arranged by wizard Gandalf, who has a detailed map of the Middle-Earth universe, and knows exactly where each of the dwarves lives. However, he needs your help in figuring out a good route for each dwarf to take to get to Bilbo's house.
Problem Description
Your task is to write a program in C or C++ that can calculate good routing paths for the Hobbit reunion meeting. As input, your program will read a network topology file (representing the map), and starting location information about each of the dwarves. As output, your program will display information about the travel route recommended for each dwarf, and some simple summary statistics to quantify how good these routes are. You will do this for several different routing algorithms and network topology files.
As an initial example, consider the following very simple map of Canada:
C E 300 120 8 2
C R 400 300 3 4
C S 600 360 4 4
C V 800 600 5 1
R W 500 360 6 3
S E 400 180 5 1
S R 250 150 3 6
S W 800 600 1 1
T M 200 240 12 2
W T 800 500 10 1
Each line in the topology file defines a direct path between two places. For example, the first line specifies a path from node C (Calgary) to node E (Edmonton), with a distance of 300 kilometers, a travel time of 180 minutes, 8 magical gold coins collected along the path, and 2 evil trolls encountered while doing so. Because the coins are magical, they re-appear and are available for each unique traveler that traverses the link. All links in this topology are bidirectional, so the relative ordering of the two endpoint nodes does not matter. There will be at most one direct link between any pair of nodes in the graph. You may also assume that the network topology is connected in the graph theory sense (i.e., no isolated nodes).
Technical Requirements
The first task for your program is to read in the topology file and construct a suitable internal representation of the network topology, using an appropriate data structure. You may assume that all node names are single upper-case alphabetic characters (i.e., a maximum of 26 nodes), all distances D are positive integers (0 < D < 1000), all travel times T are positive integers (0 < T < 1000), all gold coin counts C are positive integers (0 < C < 100), and the number of evil trolls E is a positive integer (0 < E < 10).
For testing and debugging purposes, here is a version of the Canada map topology file along with a sample list of where each dwarf lives in the Canada example. The full map is available in the same format, along with Gandalf's suitably alphabetized complete address book.
The specific routing algorithms that your program should model are:
- Shortest Hop Path (SHP): This algorithm finds the shortest path from source to destination, where the length of a path refers to the number of hops (i.e., links) traversed. Note that this algorithm ignores the physical distance, travel time, gold coins, and trolls for each link.
- Shortest Distance Path (SDP): This algorithm finds the shortest path from source to destination, where the length of a path refers to the cumulative total distance traveled. Note that this algorithm ignores the number of hops, travel time, as well as gold and trolls.
- Shortest Time Path (STP): This algorithm finds the shortest path from source to destination, where the length of a path refers to the cumulative travel time for traversing the chosen links in the path. Note that this algorithm ignores the number of hops, as well as the distance (although distance and time are often correlated). Gold and trolls are also irrelevant.
- Fewest Trolls Path (FTP): This algorithm finds the path from source to destination that minimizes the number of trolls encountered. Note that this algorithm ignores the number of hops, as well as time, distance, and gold (although gold and trolls are often correlated).
For all algorithms, whenever ties occur, they can be broken arbitrarily (e.g., alphabetically, by shoe size, random coin flip, your choice).
Your program should report a routing summary that shows the best (hop by hop) route for each dwarf to take to get to the reunion, as well as a quantitative summary of the number of hops (links) traversed, the distance traveled, the time consumed, the gold collected, and the number of trolls encountered on this route. The starting location for each dwarf is different, and the destination of each trip is always Bilbo's home. Only the one-way path to the destination needs to be considered.
Use a table format for reporting these results, with one table for each of the four routing algorithms (in the order given). For each table, there should be one dwarf per row (suitably alphabetized), with the required information reported in order from left to right. You should report one such routing summary table for each routing algorithm. Here is an example of the possible output and format for SHP routing on the small Canadian example, and an example of what FTP routing might look like on the Middle Earth dataset if Bilbo lived at node X (which he doesn't). With proper design, your program should be easily configurable to select between each routing algorithm. You do not need to do all of them in a single run.
When you are finished, submit your properly documented program (20 marks total, with 12 marks for the overall design, and 2 marks for each of the 4 routing algorithms supported), along with your tables of routing results (2 marks for each routing table, for a total of 8 marks), and a brief (maximum one page) written summary (4 marks) of your observations about the relative performance of the different routing algorithms on the given network topology.
Bonus: Up to 4 bonus marks are available for implementing one more routing algorithm called Maximum Gold Path (MGP). This algorithm finds the path from source to destination that maximizes the number of gold coins that are collected and brought to Bilbo's house, without traversing any link more than once. You can visit a given node more than once (including Bilbo's house), provided you use different links to get in and out each time before arriving at your final destination. This algorithm ignores the number of hops, as well as time, distance, and number of trolls. Show the resulting routing table in a format like the others. (Warning: MGP is a bit of a head-scratcher for just 4 marks, but it could be a lot of fun as well! The first person to figure out which dwarf collects the most gold, and how much gold he collects, gets a free pizza!)
Tips
- Focus first on making sure that your program can read in and model the network topology properly.
- Next, focus on getting ONE routing algorithm working. SHP is probably the easiest one, if you use (for example) Dijkstra's classic shortest path algorithm, with a link cost of 1 for each hop traversed. Spend sufficient time testing your Dijkstra's algorithm to make sure that it is working properly.
- You can model some of the other routing algorithms simply by tweaking the definition of "link cost" for Dijkstra's algorithm.
- Test your algorithm(s) on the small Canadian example before tackling the much larger Middle-Earth topology. You should be able to verify the small results by hand. If you can't get things working on the big topology, then at least show your results on the small topology to get partial marks.
- Some of the algorithms are harder to do than others. Try to do the easy ones first, so that you at least have partial results to submit.
- MGP is definitely a challenge, so leave it for the very end.