Computer Science 385

Design and Analysis of Algorithms

Spring 2017, Siena College

We will be studying many graph algorithms this semester, some of which you will be implementing in Java. For many of these tasks, you will be working with real-world data sets derived from highway systems.

A big advantage of working with this kind of data is that it has a
connection to reality, and that we can visualize the data and the
results of our manipulations of that data with the Google Maps API.
This data is collected by members of the Travel Mapping (TM) Project
(`http://tm.teresco.org/`). The
Map-based Educational Tools for Algorithm Learning (METAL) Project
(`http://courses.teresco.org/metal/`)
uses data from the TM project and converts it into a format that is
more convenient for us to load into a graph structure and use. Much
more about the project is available at the link above, but everything
you need to know for this week should be in this document.

You will be assigned a partner to work with on this lab. Only one submission per group is needed. The lab is graded out of 100 points.

Getting Set Up

You will need to create a BlueJ project (or set up to work in another IDE, if you prefer) for your programming work on this lab. When you complete the preliminary steps, you will be given a copy of the starter code for the main coding task.

The Graph Data

METAL provides hundreds of graph files that can be used to explore data structures and algorithms. They range in size from just a few to hundreds of thousands of vertices and edges. We can use the small graphs for tracing algorithms (or debugging code) by hand, medium-sized graphs for testing during implementation, and large graphs to help analyze the efficiency of algorithms and our implementations of them.

All graphs are linked from
`http://tm.teresco.org/graphs/`.

The graph data comes in two formats, simple and collapsed, which are
described in detail at
`http://courses.teresco.org/metal/graph-formats.shtml`.
We will use the collapsed format graphs, but will likely talk about
the differences later in the semester.

For this first set of questions, please refer to the `NY-all.tmg`
graph.

Reading the Graph into a Java Program

We need a graph data structure that can be used to store this graph data. In class we have seen that graphs can be stored in either an adjacency matrix or an adjacency list structure, and the graph's edges can either be directed or undirected.

In addition to the topological information we already considered in class, here we will need to store more information with the vertices (label and coordinates) and edges (road names, list of intermediate points).

When you get to this point, you can request your copy of the starter
code. Once you have it, study the code that reads in the graph data
files (the `HighwayGraph` constructor), and the `toString`
method that prints it out.

Run the program's `main` method, passing in the `DC-all.tmg`
graph as its command-line parameter. Compare the output of the
program with the TMG file and be sure you understand how the contents
of the data structure correspond to the contents of the file.

Expanding the Program's Functionality

Your programming tasks involve expanding the functionality of the
`HighwayData` class. **No not modify the code that constructs
the graph to accomplish these tasks.**

Vertex Search

The first task is to perform a search of the graph vertices to find the "extreme" vertices: those are at the northernmost, southernmost, easternmost, and westernmost locations. For each, report the vertex label and its latitude/longitude pair. Also, find the vertices that have the shortest and longest labels. For these, you need only report the label. You may handle ties in any reasonable manner.

Before you start coding, you can see a visualization of this process
using a version of METAL's HDX that has been enhanced to perform
interactive algorithm visualizations, available at
`http://courses.teresco.org/metal/av/`.
Load a small to medium size graph (`DC-all.tmg` is a good choice)
into this version of HDX. Then select "Search Vertices" from the
"Algorithm Selection" and choose "Pretty Slow" for the simulation
speed. Press "Start" and watch as the algorithm searches for the
extreme points and shortest and longest labels.

Edge Search

Your second task is to perform a search of the graph edges to find the
edges with the shortest and longest length. You will likely want to
model your loop structure to traverse the edges in the graph after the
one in the `toString` method.

Implement this edge search in the `main` method of the
`HighwayGraph` class right after your vertex search code.

Submitting

Your lab submission is by demonstration of each item, and then by submitting

the hard copy of this packet you received in lab with a printout of your source code attached. If you do not finish during your lab meeting, you should also attach screen shots of any required output that was not demonstrated during lab.