Due: Friday, May 5, 2017, 11:59 pm

## Graphs

The goal of this lab is to give you an opportunity to implement a graph. This week you will be implementing a video game that uses a graph data structure as a fundamental component. We will create our own graph implementation during lab, and then build upon it for use in the video game.

There are several alternatives for organizing data to represent a graph. We will implement an adjacency list. Each vertex in the graph maintains a collection of adjacent vertices–we will use a Map for this collection.

1. Make a new folder for this week's project.
2. Vertex Class: create a Vertex class. Each vertex in our graph will be able to connect to up to four other vertices, one in each of the cardinal directions (north, east, south, west). Create a Direction enum (you can define this within its own file or within Vertex.java).

Define a public static method in Vertex with signature `public Direction opposite(Direction d)` that returns the compass opposite of a direction (i.e. South for North...).

The Vertex class needs to maintain a Map (e.g. HashMap) of edges. Each entry in the edge map has a Direction as key and a Vertex as value. This is the primary field in the Vertex.

Create the following methods (these are all one-liners that manipulate the edge map):

• `void connect(Vertex other, Direction dir)`
• `Vertex getNeighbor(Direction dir)`
• `Collection getNeighbors()`

Add the fields `int cost` and `boolean marked` to the Vertex class along with associated getters and setters. These fields will be used during graph traversal.

Implement the `Vertex.toString()` method to print out the number of neighbors, the cost, and the marked flag.

Make the Vertex class implement the Comparable<Vertex> interface.

Create a main method that tests the Direction enum and Vertex class so far. This should, at a minimum, try the opposite method on each Direction, create at least two Vertex objects and assign different costs, connect a Vertex to several others, and print out the Vertex.

3. Graph class: create a Graph class that maintains a list of vertices (Vertex objects). Implement a `int vertexCount()` method. You are free to use a standard Java data structure here, such as as an ArrayList.

Implement a `void addEdge(Vertex v1, Direction dir, Vertex v2)` method that adds v1 and v2 to the graph (if necessary) and adds edges connecting v1 to v2 via direction dir and connecting v2 to v1 via the opposite direction.

4. In the Graph class, add a method `void shortestPath(Vertex v0)` that implements a single-source shortest-path algorithm for the Graph. This method finds the cost of the shortest path between v0 and every other connected vertex in the graph, counting every edge as having unit cost. An outline of the algorithm–known as Dijkstra's algorithm–is below. Note that Dijkstra's algorithm works for graphs with non-negative weight edges, but in this case all edges have the same weight.

```	Given: a graph G and starting vertex v0 in G

Initialize all vertices in G to be unmarked and have infinite cost

Create a priority queue, q, that orders vertices by lowest cost

Set the cost of v0 to 0 and add it to q

while q is not empty:
let v be the vertex in q with lowest cost
remove v from q
mark v as visited
for each vertex w that neighbors v:
if w is not marked and v.cost + 1 < w.cost:
w.cost = v.cost + 1