The goal of this lab is to get you started on the programming project. 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.
- 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, compare the Vertex objects using the comparator, connect a Vertex to several others, and print out the Vertex.
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.
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 Java's PriorityQueue 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.)
See this week's project.