Graphs

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
- (50%) Public Tests
- (20%) 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. You need to define a class named Graph. Feel free to add any other classes you understand you need.
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.

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. Feel free to add any classes you understand you need, but make sure they are in the graph package. Notice that you will not lose any credit if you decide not to add any classes beyond 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.)

The actual methods you need to implement are described at javadoc. You will find in the graphs 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 graph 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).

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.

Good Faith Attempt

The good faith attempt is represented by the public test testBFSGoodFaithAttempt.