The goal of this lab period 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.
- Make a new folder for this week's project.
- Vertex - 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. a 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)
Add the fields
boolean markedto the Vertex class along with associated accessors and mutators. These fields will be used during graph traversal.
Vertex.toString()method to print out the number of neighbors, the cost, and the marked flag.
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.
- Graph - create a Graph class that maintains a list of vertices (Vertex objects). Implement an
int vertexCount()method. You are free to use a standard Java data structure here, such as as an ArrayList.
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.
- 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 (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 add w to q Output: the cost of each vertex v in G is the shortest distance from v0 to v.
Note that you can use your priority queue implementation in the algorithm to always visit the next lowest cost vertex. An important implementation detail: in the last step, it is possible that the vertex w is already in the priority queue. In this case, updating the cost of w does not reorder its position in the queue because the queue has no knowledge of the modification. Adding the vertex a second time will lead to duplicate references to w in the queue. So, at the last step, remove w, then add w. This will work whether or not w is already in the queue. (This consideration is only necessary when dealing with weighted graphs, but we might as well be general here.)
- Write a main method that tests the Graph implementation and shortest path algorithm. Create a simple graph with several vertices and run the shortest path algorithm on one of the vertices. It would be helpful to add a label field to the Vertex class that gets printed out to make this easier to visualize.
Once you have completed the lab, go on to the project.