Homework Assignment 5

Due: May 10, 2006. No extensions!!!
If you assignment is not complete, then just hand in whatever you have finished.

The goal of this assignment is to create a computational framework for modeling the DC Metro System network. The scope of this assignment is restricted to information models for the metro stations and the tracks connecting stations. The assignment will give you practice at assembling Java programs from fragments of code and already work.

Problem Statement

The following figure is a simplified model of the Washington DC metro system (most of the stations have been omitted):

Figure 1. Schematic of the DC Metro System.

Source Code

To start, download and compile the following files:

File	Description
Edge.java Node.java Vector.java	Vector.java defines points having (x,y) coordinates. A Node is simply a Vector with a name. An Edge links two Nodes.
Graph.java AdjList.java	Graph.java contains code for assembling a graph from node and edge connectivity between nodes. For each node in the graph, AdjList.java computes the list of adjacent nodes. This information is used in the route planning.
BFSearcher.java Queue.java	Compute a breadth-first search of the nodes. Create a queue of nodes spanning from the source node to the destination node.
MetroStation.java MetroSystem.java	MetroStation.java creates metro station objects. MetroSystem.java creates a model of the entire metro system -- individual metro station objects are stored in the symbol table. The rail network is modeled as a graph (i.e., see Graph.java).
SymbolTable.java	Creates a symbol table.
Track.java	A track is simply a pathway of edges in a graph (e.g., the "green" line). This conceptual representation simplifies a passenger's view of the metro system.

Table 1. Java Source Software Prototype for Metro Simulation Files

Hint. Notice that the following files all have main methods: AdjList.java, Edge.java, Graph.java, MetroStation.java, MetroSystem.java, Node.java, SymbolTable.java, and Track.java. Therefore, a good strategy for learning about the code is to compile and run each of the smaller programs separately.

Metro System Architecture

With these files in place, we can design and implement a MetroSystem class for the entire Washington DC Metro System.

Here is a skeleton of the code:

/*
 *  ==========================================================================
 *  MetroSystem.java: Create a model of the DC Metro System.... 
 *
 *  Written By : Mark Austin                                          May 2006
 *  ==========================================================================
 */

import java.lang.Math;
import java.util.*;
import java.io.*;
import java.text.*;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class MetroSystem {
    protected String sName;
    SymbolTable stations;
    Graph          metro;

    // Constructor methods ....

    public MetroSystem() {
       stations = new SymbolTable();
       metro    = new Graph();
    }

    public MetroSystem( String sName ) {
       this.sName = sName;
       stations = new SymbolTable();
       metro    = new Graph();
    }

    // Create Metro Station objects .....

    public void metroStations() {

        System.out.println("Creating metro stations..." );

        // Create metro stations. (x,y) coordinates measured in miles
        //                        from Union Station.

           // .... FILL IN DETAILS HERE .... 
           // Hint. ... Look in MetroStation.java ...

        // Add metro stations to the metro system database/symbol table.

           // .... FILL IN DETAILS HERE .... 
           // Hint. ... Look in SymbolTable.java ...

        // Define stations along the green and red lines ....

           // .... FILL IN DETAILS HERE .... 
           // Hint. ... Look in SymbolTable.java ...

        // Add track assignments to metro station descriptions ....

           // .... FILL IN DETAILS HERE .... 
           // Hint. ... Look in SymbolTable.java ...
    }

    // Define details of the DC Metro System Network

    public void metroNetwork() {

        System.out.println("Creating metro network..." );

        // Create metro station objects .....

           // .... FILL IN DETAILS HERE .... e.g.,
           // Hine. ... Look in Graph.java .....
           // e.g., ms.metro.addEdge( "College Park", "Fort Totten");
    }

    // Print details of the Metro System 

    public void print() {

        System.out.println("DC Metro System");
        System.out.println("===============");

        // .... FILL IN DETAILS HERE .... 

    }

    // Exercise methods in metro system model 

    public static void main( String args[] ) {

        // Build model of metro stations and rail network ...

        MetroSystem ms = new MetroSystem("DC Metro");
        ms.metroStations();
        ms.metroNetwork();

        // Retrieve and print details of individual metro stations ....

        System.out.println("");
        System.out.println("Metro Station Details");
        System.out.println("=====================");

        // .... FILL IN DETAILS HERE .... 

        // Let's travel from "College Park" to "National Airport"....

        System.out.println();
        System.out.println("Source: College Park");
        System.out.println("Destination: National Airport");
        System.out.println("=============================");

        // .... FILL IN DETAILS HERE .... 

        // Travel distance from "College Park" to "National Airport"....

           // .... FILL IN DETAILS HERE .... 

           System.out.println();
           System.out.println("Distance");
           System.out.println("================================");
           System.out.println("College Park to National Airport = ");
    }
}

Points to note:

The constructor:
```
    public MetroSystem( String sName ) {
       this.sName = sName;
       stations = new SymbolTable();
       metro    = new Graph();
    }
```
shows the essential details for how the metro systgem will be modeled. The metro system has a name. All objects in the metro system will be referred to by their name (e.g., the College Park Metro Station will have the name "College Park"). Objects will be stored in a symbol table called "stations". A graph object will model the metro network.

The output from my program run is as follows:

Script started on Mon May 01 12:56:42 2006
prompt >> java MetroSystem
Creating metro stations...
Creating metro network...

Metro Station Details
=====================
MetroStation("Greenbelt")
   Coordinates = ( 3.5, 10.0 )
   Parking = true
   Track   = { Green }

MetroStation("College Park")
   Coordinates = ( 3.5, 8.0 )
   Parking = true
   Track   = { Green }

MetroStation("Fort Totten")
   Coordinates = ( 0.0, 2.0 )
   Parking = true
   Track   = { Red Green }

MetroStation("DuPont Circle")
   Coordinates = ( -3.0, 0.0 )
   Parking = false
   Track   = { Red }

Source: College Park
Destination: National Airport
=============================
College Park
Fort Totten
Judiciary Sq
National Airport

Distance
================================
College Park to National Airport = 
prompt >>
prompt >> exit
Script done on Mon May 01 12:57:03 2006

Things to do....

Fill in the missing blocks of code in MetroSystem.java. I suggest that you begin by adding the metro station objects to the symbol table.
Add details for the orange line. I have added coordinates for these stations in the table below.
Suppose that you want to travel from College Park to National Airport and then onto New Carrolton. What is the sequence of metro stations that will be visited?
Write code to compute the travel distance between two stations. Use this code to compute the travel distance between College Park and National Airport and then onto New Carrolton.

Hints

You will need to supply the coordinate of each metro station. I assume that "Union Station" is a (x,y) coordinate (0,0). The x coordinate increases to the east, the y coordinate increases to the north. I use units of miles. Therefore, the approximate metro station coordinates are:

Metro Station                 (x,y) coordinate
==============================================
Union Station                   (  0.0,  0.0 )
DuPont Circle                   ( -3.0,  0.0 )
Catholic University             (  0.0,  1.0 )
Fort Totten                     (  0.0,  2.0 )
Silver Spring                   ( -0.5,  9.0 )
National Airport                ( -1.5, -2.0 )
College Park                    (  3.5,  8.0 )
Greenbelt                       (  3.5, 10.0 )

Orange Line Stations
--------------------

New Carrollton                  (  5.0,  8.0 )
Stadium-Armory                  (  1.0, -1.0 )
L Enfant Plaza                  ( -1.0, -1.0 )
Smithsonian                     ( -1.5, -0.8 )
Metro Center                    ( -1.5,  0.0 )
Rosalyn                         ( -4.5,  0.0 )
Ballston-GMU                    ( -6.5,  0.0 )
Vienna                          (-12.0,  0.0 )

... etc ....
==============================================

I am sure there is more accurate way of determining the position of the metro stations, but for this assignemnt this level of accuracy will do.

To compute the travel distance, you will first need to retrieve a list of stations from graph. The method path() in BFSeaarch.java does this. Therefore, an appropriate structure for computing the travel distance is:

    // Travel distance from "Silver Spring" to "National Airport"....

    String travelPath[] = bfs1.path( "Silver Spring" );
    double travelDistance = 0.0;
    for ( int i = 1; i < travelPath.length; i = i + 1) {
        MetroStation m = .....
        MetroStation n = .... 
        travelDistance = travelDistance + ....
    }

Answer.
I get 12.3 miles from Silver Spring to National Airport. Then it's another 13 miles to New Carrollton. The total travel distance is about 25 miles.

What to hand in....

Hand in a copy of your source code for MetroSystem.java and a scripts of I/O for typical program usage. Indicate on your program source code, those parts of the code that YOU HAVE WRITTEN.

To create a script, type something like:

    prompt >> script output-file

Now all input/output on the screen will be echoed to the file "output-file". To terminate the script, type:

    prompt >> exit

Now print "output-file" and hand it in.