CS 231: Lab #9

Title image Spring 2018

Graphs

The goal of this lab is to give you an opportunity to implement 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.

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.

Tasks

  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 with these four values. You can define this within its own file or within Vertex.java).

    Define a public static method in Vertex with the signaturepublic 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 its key and a Vertex as its value. This is the primary field in the Vertex. In the game, each Vertex will represent a room in the world map. (You don't have to use a Hashmap; you could also make use of the integer nature of the enum type.) If you use your own HashMap, you'll need a Comparator class that compares Directions.

    Create the following methods:

    • void connect(Vertex other, Direction dir): modify the object's adjacency list/map so that it connects with the other Vertex. This is a uni-directional link.
    • Vertex getNeighbor(Direction dir): returns the Vertex in the specified direction or null.
    • Collection getNeighbors(): returns a Collection, which could be an ArrayList, of all of the object's neighbors.

    Add the fields int cost and boolean marked to the Vertex class along with appropriate accessor methods. These fields will be used during graph traversal.

    Implement the Vertex.toString() method to return 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.

  3. 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.

    • int vertexCount(): returns the number of vertices in the graph.
    • 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.
    • 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.)

  4. 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 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.