Objectives

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.

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 (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
    				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.)

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


When you are done with the lab exercises, you may start on the rest of the project.


© 2017 Caitrin Eaton.