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%) Secret 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.
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.
See Student Tests for information regarding the implementation of student tests for this project.
See Style Guidelines for information regarding style.
Keep in mind that we use submit server results to compute part of the grade associated with a project, therefore you must verify that your project works in the submit server. Also notice you will receive points for release tests even if you don't release test your project (e.g., you ran out of tokens).

Good Faith Attempt

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