CS 409 HW8 : How Should I Get There?

Homework 8: Handed out: 4/5; Due: 4/19.

Note: This assignment involves programming, which will have to be done using J++ in the CSUGLab. Even if you originally use another variant of Java for your program, make sure it runs in the CSUGLab.

As usual, you can discuss this assignment with anyone you like, but you must write it up yourself.

Overview

In this assignment, you are given data about the road network in the USA. What we want from you are programs to do the following:

1. Given two places in the United States, find (and of course print out) the shortest path between them.
2. Calculate the number of connected components in this network.

Data

In this assignment, you'll be working with a simplified version of National Highway Planning Network Version 3.0 , part of The National Transportation Atlas Data (NTAD) maintained by the Bureau of Transportation Statistics. Note that NHPN is primarily a planning network that contains only the major roads in the country (the top 10% of total road mileage).

The data you will need are in data.zip (1.23M). There are two files in data.zip. You can also choose to download the unzipped files directly:

• road.dat (3.39M)
• place.dat (491K)

Both files are in ASCII format.

Each record in road.dat (that is, each line in the file) represents one segment of a road. The format of a record is as follows:

Field Name	Begin Pos.	End Pos.	Description
ANODE	0	4	Node ID of the beginning of the segment
BNODE	5	9	Node ID for the end of the segment
MILES	10	15	Length of the segment measured in miles
SIGN / DES	16	end	Sign and/or description of the segment

Note:

• There are 131254 records in this file.
• A record is a string. You will need to convert the ANODE and BNODE components to integers (they are integers between 1 and 94549, in fact), the MILES component to an object of type float/double, and the SIGN/DES component to a string. (There are methods to perform all these conversions.) After reading a line from the file, you may get each field by using the substring method of the class String according to the Begin Pos. and End Pos. of that field; trim() can remove white space from the front/end.
• The terms "beginning node" and "ending node" are a bit misleading; all the segments are two-way roads. That is, the record really represents both the road from ANODE to BNODE and the road from BNODE to ANODE.

Some of the nodes have a string description (the name of the corresponding place in most cases); this information is provided in the file place.dat:

Field Name	Begin Pos.	End Pos.	Description
NODE_ID	0	4	ID of the node
DES	5	end	Description/name of the node

Note:

• For this assignment, road.dat is enough to construct the graph; place.dat is provided only to improve the user interface. Since with this file, you can find the corresponding node ID given the name of a place, the user can do graph search using names of places instead of using the node ID.
• Although there are 94549 nodes in this network, some of them do not have descriptions. To save space, I didn't include them in this file. That's why you see only 25840 records in this file. But remember that the nodes used in road.dat are numbered 1-94549.
• The description is not always consistent. For example, one of the node representing a place in Ithaca has the description NYITHACA CBD. The state description NY is at the beginning of the string. For places in Ohio, they put OH at the end of the description. You don't need to spend too much time on this. Just assume that when you are asked to find the distance between two places, the place description is a perfect match for a name in place.dat, or is not included in place.dat at all. And don't spend too much time writing complex structures to search for the string. It's acceptable just to read through the whole file doing string match.

Implementation

• Implement Dijkstra's algorithm to find the shortest path for this network

  Since this is the last programming assignment, you get to design the data structure on your own. Mapping a real world problem to the right representation is a very important part of programming. With the information given to you, you should decide on the right data structure for the graph, and you should implement Dijkstra's algorithm to find the shortest path (so that the sum of the "miles" of all the segments on the resulting path is smallest). You need to choose the right data structure for the priority queue. (Just make a decision between using an array or a binary heap.) For a dataset with smaller size, it might not make a big difference, but for this one, if you use the right thing, you get an answer quickly (or, in a reasonable amount of time) while if you choose unwisely, you will have to WAIT (and lose points!).

• Choose the right algorithm to find the number of connected component in this graph

  Just make your choice between BFS and DFS. (Yes, there's actually more than one connected component, since we have Hawaii and Alaska in this network.) One additional piece information I can give you is that the biggest connected component has around 91000 nodes although the graph is relatively sparse. This turns out to matter when it comes to choosing between BFS and DFS. (Try them both out and you should be able to see the difference...)

• Implement them as methods of class Graph. The only requirement is that this class works correctly with test.java . Email your program to pabo@cs.cornell.edu

• For Dijkstra's algorithm, you need to output the resulting path,
  and each segment in the path should take the format of
  #: [from (nodeID)] - [to (nodeID)] [length of the road] [description]
  So your output should look like this:

   From "NYITHACA C-W" to "NYSYRACUSE ENE":
  
   0:  55021 - 55031  0.3 mi        STATE ST
   1:  55031 - 55030  0.1 mi        STATE ST
   2:  55030 - 55033  0.09 mi  S13   MEADOW ST
   3:  55033 - 55028  0.76 mi        GREEN ST
   4:  55028 - 55035  0.44 mi        STATE ST
   5:  55035 - 55007  1.57 mi        RYDEN RD
   6:  55007 - 54977  1.98 mi        RYDEN RD
   7:  54977 - 54975  0.05 mi        RYDEN RD
   8:  54975 - 54952  1.07 mi  S366
   9:  54952 - 54934  1.18 mi  S13   RYDEN RD
   10:  54934 - 54915  4.71 mi  S13   RYDEN RD
   11:  54915 - 54897  0.53 mi  S13
   12:  54897 - 54842  3.56 mi  S13
   13:  54842 - 54774  3.49 mi  S13
   14:  54774 - 54731  1.65 mi  S281
   15:  54731 - 54715  0.48 mi  S281
   16:  54715 - 54706  0.64 mi  S281
   17:  54706 - 54665  1.04 mi  S281
   18:  54665 - 54649  0.46 mi  S281
   19:  54649 - 54613  0.76 mi  S281
   20:  54613 - 54367  7.73 mi  S281
   21:  54367 - 54268  2.27 mi  I81   ORTH-SOUTH EXWY
   22:  54268 - 54206  1.48 mi  I81   ORTH-SOUTH EXWY
   23:  54206 - 53948  6.64 mi  I81   ORTH-SOUTH EXWY
   24:  53948 - 53694  4.95 mi I81   ORTH-SOUTH EXWY
   25:  53694 - 53619  2.06 mi  I81   ORTH-SOUTH EXWY
   26:  53619 - 53554  1.02 mi  I81   ORTH-SOUTH EXWY
   27:  53554 - 53528  0.28 mi  I81   ORTH-SOUTH EXWY
   28:  53528 - 53416  5.04 mi  I481
   29:  53416 - 53283  1.73 mi  I481
   30:  53283 - 53261  0.43 mi  I481
   31:  53261 - 53185  1.0 mi  I481
   32:  53185 - 53075  1.2 mi  I481
  
   Distance: 60.690002 miles.
  

• The programming part shouldn't be too hard, but the relations might seem a bit complicated at first. If you start off on the wrong side, it might be time-consuming...so START EARLY!!

• You may reuse your code from previous assignments, but you might need to make some slight changes. Note that in CLR p530, what it says about Decrease-Key is a bit misleading. The second argument here is different from the second argument in Exercise 7.5-4, be careful!

Write-up

• Introduction
• Experimental procedures - for example, machine configuration
• Analysis - What data structure did you choose to represent the graph and how did you implement the priority queue? Why did you do it the way you did? What is the resulting running time? Did you use BFS or DFS to get the number of connected components? Why?
• Conclusion - a short summary of what you learned from this homework.
• Raw Data - the result.

Grading

Write-up - 30%
Code - 70%

• construction of the graph - 15%
• Dijkastra algorithm - 25% (10% for priority queue)
• connected component - 20%
• other - 10%

* Bo will the point person for this assignment.

More...

• Relax the restriction on the place names, to accept formats like "Ithaca, NY". Find the closest matching nodes and give the user a selection.

• It might be more interesting to search for the best path according to driving time. Unfortunately we do not have speed limits in this data set. The closest thing I found on the web is a Speed Limit By State table . There is also more data on road conditions in National Highway Planning Network Version 3.0 . This would allow you to estimate the driving time more precisely!