Overview

For this project you will implement the Breadth-First Search, Depth-First Search and Dijkstra's algorithms.

Objectives

• Practice implementation of graphs.
• Implement Breadth-First Search (BFS) Traversal.
• Implement Depth-First Search (DFS) Traversal.
• Implement Dijkstra's algorithm for shortest path.

Grading

• (20%) Use of HashMap to represent the adjacency properties of the graph.
• (5%) Use of HashMap to represent data associated with a node.
• (70%) Tests
  • (30%) Public Tests
  • (40%) Release Tests
• (5%) Style

Clarifications

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

Code Distribution

The project's code distribution is available by checking out the project named Graphs. The code distribution provides you with the following:

• A package named graphs - Package where classes associated with the graph implementation will be provided.
• A package named tests - Includes the public tests (PublicTests.java) and a shell for a class (StudentTests.java) for student tests. Notice that you are not required to write student tests for this project; however, we recommend you do so.
• A package named utilities - Contains the classes which allow us to perform BFS/DFS/Dijkstras
• A package named travelManager - We have written this application for you and we are providing it to show a possible use of your implementation. You can implement this project without ever running this application.

Specifications

This project has two main tasks: Implementing a graph representation and implementing the BFS/DFS/Dijkstra's algorithms. The class(es) associated with the graph representation will be provided in the graph package; the class(es) implementing the algorithms will be provided in the utilities package. Use the public tests to guide you in the process of defining what is the functionality you need for a graph. Notice that the methods associated with the Graph class are expected to support the implementation of the graph algorithms (you are not required to implement a generic Graph class that supports functionality beyond what is present in the public tests). Feel free to add any classes you understand you need, but make sure they are in either of the two packages mentioned above. Notice that you will not lose any credit if you decide not to add any classes beyond Utilities and Graph.

Your Graph class should define the following two instance variables:

• HashMap<String,HashMap<String,Integer>> adjacencyMap; → represents the adjacency properties of the graph. A vertex is identified by using a String object. We will assume the edge costs are integer values.
• HashMap<String, E> dataMap; → represents the data associated with the vertex. A vertex is identified by using a String object.

Notice that the Graph class is a generic class whose type parameter represents the elements of the graph we are defining (e.g., Graph<Student>, Graph<Double>, etc.)

Utilities Class

The Utilities class implements the methods computing BFS, DFS, and Dijkstras.  The actual methods you need to implement are described at javadoc. 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). 

Travel Manager Application

The travel manager application 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.

Requirements

• Process adjacent vertices in alphabetical order.
• Do not implement DFS using a recursive approach; implement DFS using an explicit stack.
• You must use HashMaps to represent vertices in a graph and adjacent vertices.
• You may not use Collections.sort()
• Verify that your project passes the submit server tests (https://submit.cs.umd.edu/). Those are the results we use to compute your grade.
• See StudentTests.html for information regarding the implementation of student tests.
• You must attempt to submit your project immediately after checking out the project (even if you have not implemented any methods). This will allow you to verify that the submission process is working as expected.
• You should submit your project often. This will keep versions of your project in the submit server that are easy to retrieve (you can also get previous versions from your CVS repository). If your computer crashes or you experience any other problem you will have a permanent backup in the submit server.
• You have three tokens for this project in the submit server.
• Style
  • Good variable names.
  • You must avoid code duplication by calling appropriate methods (rather than cutting and pasting code). You may define your own private utility methods to perform often repeated tasks.
  • Style as defined by the Eclipse Format Element option (Source → Format → Format Element) or as specified in Code Conventions for the JavaTM Programming Language (focus on the following sections: Indentation, Declarations, Statements, White Space, and Naming Conventions).
  • Although you should avoid source lines exceeding 80 characters, you will not be penalize if they are present in your code.

Honor Section Requirements

No addtional requirements.

Submission

Submit your implementation using the Eclipse "Submit Project" option (available by right clicking on the project folder).

Academic Integrity

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