Objective

The objectives of this project are:

• Practice implementation of graphs

• Implement Breadth-First Search (BFS) Traversal

• Implement Depth-First Search (DFS) Traversal

• Implement Dijkstra's algorithm for shortest path

• Practice using the Java Collections Framework.

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/spring2007/cmsc132/Projects/p4/clarifications.html

Overview

For this project you will complete the following tasks:

• Implement the classes Vertex, Edge, and Graph that allows us to represent a graph (directed and undirected). 
• Implement DFS and BFS.
• Implement  Dijkstra's algorithm so we can compute shortest paths.

Your project will be graded as follows:

• Tests (90 %)

  • Public JUnit tests  (44 %)

  • Release JUnit tests  (46 %)

• StudentTests (10 %)           

For this project:

• There are three tokens for release testing.
• The project's code distribution is available by checking out the project named p6.
• The code distribution provides you with the following:
  • A folder named src - In this folder you will find the packages, graph, utilities,and tests.
  • A package named graph - In this package you will implement the Vertex, Edge, and Graph classes.  We have left a shell for each of these classes.  We have defined for each one of them the instance variables associated with the class.  You don't need to add any other variables in order to complete the implementation.
  • A package named utilities - We have left a shell for the Utilities class you are expected to implement. In this class you will find the methods that perform BFS, DFS and Dijkstras on a graph.
  • A package named tests - You will find the JUnit public tests we provided in this package. 

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:

• private LinkedList<Edge<E>> edges; // Represents the neighbors (successors) of the vertex.

• private E data;  // Represents the vertex's data

• private String name; // Name of the vertex

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:

• private Vertex<E> startVertex, endVertex;

• private int cost:    // edge's cost

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:

• TreeMap<String, Vertex<E>> vertexMap;  // Keeps track of vertices in the graph.  A vertex is identified via its name.

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

• You must use the appropriate generic version of TreeMaps, Stack, LinkedList, ArrayList or any other collection.  For example, if you need an ArrayList of Vertex object, the ArrayList should be declared as ArrayList<Vertex> list rather than ArrayList list.  
• You must follow Java conventions for identifiers.  For example, class/interface names must start with capitals
• You must use a priority queue for the implementation of Dijkstra's algorithm.
• Do not implement DFS using a recursive approach; implement DFS using an explicit stack.
• You must use meaningful variable names.
• You must indent your code using three or four spaces or by using the Eclipse "Correct Indentation" option.
• You must use the same style for blocks of curly brackets ({ }) throughout your code. 

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

Web Accessibility