Project #6 (Graphs)

CMSC 132

Due Date: Friday Nov 18, 6:00 pm

Object-Oriented Programming II

Type of Homework: Closed

Fall 2005


Objective

The objectives of this project are:

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

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 afterthought 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:

We have implement the method compareTo for you.  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:

We have implement the method loadSimpleGraph for you.

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

Utilities class

This Utilities class implements the static 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 in order 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.

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

Requirements

Honor Section Requirements

In addition to the above requirements, you must satisfy the following requirements:

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