Homework 10: Shortest path to Google
- Due before class on Wednesday, December 9
- Submit using the submit program
as
312 hw 10.
This homework counts as 2 homework grades.
1 Overview
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 I recommend learning how 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.
2 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.
3 Starter code
You can get all these files at once by downloading the file
hw11.tar.gz
and running tar xzvf hw11.tar.gz
4 Examples
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:
one.net two.com 1.5 one.net a.1e100.net 11.2 two.com three.org 1.5 one.net three.org 2.2 three.org b.1e100.net 3.3 three.org four.gov 2.0 four.gov b.1e100.net 0.9
Here's an example run of the program on this graph:
$ 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: