Homework 11: Shortest path to Google

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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

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

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: