HW 11: Shortest Path to Google
Overview
This is a programming homework assignment. You will implement Dijkstra algorithm to find the shortest path in a network graph.
Due Date
This homework is due 7 Dec. via ic312-submit.
Grading
The assignment is graded out of 200 points. It is worth the equivalent of two homework assignments.
Submission and Starter Code
Submission must occur via ic312-submit.
You will be provided the following files:
FindGoogle.java: The main program. You will need to edit this program to add Dijstra's algorithmPingGraph.java: The graph class. You will need to edit this programPingEdge.java: The edge class. You will need to edit this programsimple.txt: A small graph of pings, good for initial testingpingdata.txt: A larger graph of pings, good for more thorough testing
Additionally, YOU SHOULD NOT USE THE ic312 PACKAGE. Instead,
you may make FULL use of java.util.
Description
One way that Google and other huge websites deliver content to your browser so quickly is that they have many servers all around the world, and when you type in google.com, your traffic is directed to the "closest" mirror to you.
For this homework, you will implement Dijkstra's algortihm so that you can determine the shortest path from a given starting hostname to one of Google's mirror hosts. You can tell a hostname is a Google mirror if it ends in 1e100.net.
You also need to implement a directed, weighted graph whose vertices are hostnames like rona.academy.usna.edu and whose edge weights represent the latency in a connection between two hosts. The graph will be relatively sparse, so I recommend you use an adjacency list representation.
For this homework, you can (and should) use classes from java.util such as TreeMap or PriorityQueue. You can also write your own or use something from a previous homework if you want, but it is strongly recommend that you learn to use Java's. It's not hard, and the process of "searching the web to figure out how to use a Java class" is an important programming skill for you to have anyway.
What you have to do
The PingGraph class that you have to complete must contain methods addEdge and neighbors. You can add other methods if you want, but these are the only ones you absolutely need to have in there. You will have to create a data structure for your adjacency list. There are some helpful comments in this file to point out what you need to do.
The FindGoogle class already has a main method to get the filename from the command line, read in the graph from that file, then read in starting vertex names from the terminal and do searches. It also has a isGoogle helper method to determine whether a hostname is a Google mirror. What you need to do is complete the search method that takes a starting vertex name and does Dijkstra's algorithm from there, printing out the closest Google mirror from the given starting hostname.
This should be a standard Dijkstra's search, except that as soon as you "visit" any vertex whose hostname is a Google mirror, you should stop right there and print out that hostname and the total time to reach it - that's the closest one. If someone types a hostname that's not in the graph, or there's no path from there to any 1e100.net host, then your method should print out "unreachable".
There is a nice block of helpful tips in the FindGoogle.java starter code. Remember, you can add extra methods or classes wherever you like, but please don't delete or change the argument/return types of existing methods, so that I can test your program when you submit.
Example Output
The command-line argument to FindGoogle is the name of the file that stores the graph, i.e., has hostname-hostname-latency data to describe the edges. I've provided two such examples in the starter code. Here's what simple.txt looks like:
$ java FindGoogle simple.txt Enter starting hostname, or CTRL-D to quit: one.net b.1e100.net 5.1 Enter starting hostname, or CTRL-D to quit: four.gov b.1e100.net 0.9 Enter starting hostname, or CTRL-D to quit: a.1e100.net a.1e100.net 0.0 Enter starting hostname, or CTRL-D to quit: usna.edu unreachable Enter starting hostname, or CTRL-D to quit:
The file pingdata.txt is a bit larger, and contains actual traceroute data from a few hosts at USNA and elsewhere. Here's a sample run on that file:
$ java FindGoodle pingdata.txt Enter starting hostname, or CTRL-D to quit: rona.academy.usna.edu iad23s08-in-f2.1e100.net 24.631002 Enter starting hostname, or CTRL-D to quit: mich302csd10u unreachable Enter starting hostname, or CTRL-D to quit: my.house.net iad23s08-in-f1.1e100.net 28.944 Enter starting hostname, or CTRL-D to quit: koding.com vc-in-f93.1e100.net 14.231 Enter starting hostname, or CTRL-D to quit: