Project #4 (Graphs)

CMSC 132

Due Date: Thursday Oct 18, 6:00 pm

Object-Oriented Programming II

Type of Homework: Closed

Fall 2007


Objective

The objectives of this project are:

This project is considered a closed project.  Make sure you read the open/closed policy before continuing working on this project.

Project Clarifications

Any clarifications or corrections associated with this project will be available at:

http://www.cs.umd.edu/class/fall2007/cmsc132/projects/p4/clarifications.html

Overview

For this project you will complete the following tasks:

Your project will be graded as follows:

For this project:

Specifications

Important Restrictions

The TAs have been instructed not to help you debug your code unless you have written a test case that demonstrates that your project is malfunctioning.  You should be writing and using your test cases WHILE you are implementing the project, not as an after thought at the very end.  Testing and software development go hand-in-hand.

Classes You Need to Implement

To represent a graph you need to implement three classes:

Vertex class

The Vertex class represents a vertex in the graph.  The instance variables associated with this class are:

A description of the class methods can be found at project javadoc.

Edge class

The Edge class represents an edge in the graph.  The instance variables associated with this class are:

A description of the class methods can be found at project javadoc.

Graph class

The Graph class can represent both a directed or undirected graph.  The instance variable associated with this class is:

A description of the class methods can be found at project javadoc.

Utilities class

This Utilities class implements the methods computing BFS, DFS, and Dijkstras.  You will find in the utilities package an interface named CallBack.  A class implementing this interface represents a class that will process a vertex.  An example of such a class is PrintCallBack (which you will find in the utilities package).  This class is used to generate the string that represents the path we follow when performing a breadth-first search or a depth-first search.  Each time we reach a vertex, the implementation of DFS and BFS are expected to call the processVertex method to apply whatever processing needs to be done to the vertex.  We have implemented PrintCallBack for you (don't modify it).  Notice that in this project we will initialize the data component of a vertex to null for simplicity.

Feel free to modify the Vertex and Edge class in order to implement Dijkstra's algorithm.

A description of the class methods can be found at project javadoc.

Requirements

Travel Manager Application

The TravelManagerDemo.avi video shows an application (TravelManager.java) that relies on the classes you will implement for this project.  The travel manager computes driving directions based on traffic information downloaded from the specified URL.  You can find the application and an applet in the code distribution.

Submission

Submit your project using the submit project option associated with Eclipse. 

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects.  We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program