CS 231: Lab #9

Title image Fall 2019

Graphs

The primary goal of this lab is to give you experience implementing a graph. The project is to build a simple video game that uses a graph data structure as a fundamental component. You will create your own graph implementation during lab and then build the video game using the graph to describe the layout of the game world.

A second goal of this project is give you experience implementing Dijkstra's algorithm for computing the shortest path from a node to all other nodes in a graph.

There are several alternative designs for representing a graph. A straightforward design is to use an adjacency list at each vertex in the graph. The adjacency list holds all of the connections leaving that vertex. As each connection should be unique, you can use a Map to store the connections.

Hunt the Wumpus

The particular application this week is the game Hunt The Wumpus. The Wumpus is a monster that lives in a maze (represented by a graph, where each vertex is a room). The Hunter can leave each room through a door (by default, there can be doors in the North, South, East, or West directions). Rooms can have anywhere from 1 to 4 doors.

The Wumpus is located in one of the rooms. If the Hunter walks into the room with the Wumpus, it will eat the Hunter and the game ends (Hunter loses). When the Hunter is within two rooms of the Wumpus, the Hunter can smell the Wumpus, but that doesn't tell the Hunter anything about direction. In order to kill the Wumpus the Hunter has one arrow. At any point, the Hunter can shoot the arrow in a single direction. If the Wumpus is along the path of the arrow, and there are no walls (only doors) in between the Hunter and the Wumpus, then the Hunter slays the Wumpus and wins the game.

Tasks

  1. Create a Vertex Class

    Create a Vertex class to represent the nodes in a graph. In the game, each vertex will represent a room and will connect to up to four other rooms (vertices), one in each of the cardinal directions (north, east, south, west).

    The Vertex class needs to maintain a data structure that stores adjacent vertices. It is up to you exactly how to store it. One option is to use a HashMap with the direction as the key and the node as the value. A second option is to use an array of type Vertex. If you use only the cardinal directions for edges, the array can be size 4. This data structure is the primary field in the Vertex.

    In addition, add fields for whether a room (Vertex) should be visible, its cost or distance (from the Wumpus), and whether it has been marked (or visited). The latter two fields will be used during graph traversal and Dijkstra's algorithm. Write get and set functions for each field.

    Design note: To represent a direction create an enumerated type. Create an enumerated type Direction with the values { North, South, East, West }. An enumerated type can be used in place of an Integer, such as for indexing into an array. By default, enum values start at value 0 and increase by 1.

    Define the following Vertex methods:

    • public static Direction opposite(Direction d) returns the compass opposite of a direction (i.e. returns South for the input North).
    • public void connect(Vertex other, Direction dir): modifies the vertex's adjacency list/map so that it connects with the other Vertex. This is a uni-directional link.
    • public Vertex getNeighbor(Direction dir): returns the Vertex in the specified direction or null.
    • public Collection getNeighbors(): returns a Collection, which could be an ArrayList, of all of the object's neighbors.
    • public String toString() returns a String containing (at least) the number of neighbors, the cost, and the marked flag.

    Make the Vertex class implement the Comparable<Vertex> interface using cost as the value to be compared.

    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.

  2. Define a Graph class

    Create a Graph class that maintains a list of vertices (Vertex objects). You are free to use a standard Java data structure here, such as as an ArrayList. You could also use a simple array of Vertex objects.

    Implement the following methods.

    • public int vertexCount(): returns the number of vertices in the graph.
    • public void addEdge(Vertex v1, Direction dir, Vertex v2): adds v1 and v2 to the graph (if necessary) and adds an edge connecting v1 to v2 via direction dir and a second edge connecting v2 to v1 in the opposite direction, creating a bi-directional link.
    • public void shortestPath(Vertex v0): implements a single-source shortest-path algorithm for the Graph, Dijkstra's algorithm. 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 Dijkstra's algorithm is given below. Note that Dijkstra's algorithm works for graphs with non-negative weight edges. In the default design all edges in the graph will 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.
      										

      You can use Java's PriorityQueue implementation in the algorithm to always visit the next lowest cost vertex or use your own Heap (with a slight modification to allow a specific node to be removed).

      An important implementation detail is that in the last step of Dijkstra's algorithm, 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. Therefore, in the last step, remove w and 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.)

  3. Test the Graph class

    Write a main method in the Graph class 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 can be helpful when visualizing a graph to have a label field in the Vertex class that gets a unique identifier.

When you are done, go ahead and get started on the project.