C OMPUTER S CIENCE 21A (S PRING T ERM , 2017)
D ATA S TRUCTURES
P ROGRAMMING ASSIGNMENT 3
Shortest path in Graph
You’ve just accepted a new internship at Yahoo, in a city not yet supported by Google Maps. You want to find the fastest route to the company from your house, but you don’t even have a map!
All you know is that your internship probably has a Yahoo sign on its building, and that it’s on an intersection. The na ve way to find the shortest path would be to just take a direct route, but you never know if the direct route has the most traffic. Another thing you could do is try every possible path, but the run-time for that would be ridiculous (no pun intended). However, being a data structures and algorithms student, you know that you can find the shortest path from your house to the Yahoo building, even considering the traffic in the city, by using Dijikstra’s Algorithm.
WHAT YOU’RE GOING TO BE GIVEN
We’ve coded a simulator of driving around this city for you. Starting at your home, you’ll be able to go north, south, east, or west, and how many seconds it takes to get to the next intersection with traffic. Each intersection will be a GraphNode object with the following methods:
public int getX()
public boolean hasNorth()
public GraphNode getNorth()
public int northWeight()
public boolean hasSouth()
public GraphNode getSouth()
public int southWeight()
public boolean hasEast()
public GraphNode getEast()
public int eastWeight()
public boolean hasWest()
public GraphNode getWest()
public int westWeight()
public boolean isGoalNode()
public String getId()
Basically, each node can have a north node, south node, west node, and east node. For example, if n is a node, if n.hasNorth() returns true, then it will have another node at n.getNorth(), and a “cost” to get to that node.
Each node will have a unique string ID of 36 characters, in a format similar to this one:
5451397c-0d6e-4d7d-985f-bd627dcd2fcc
The characters will be different, but the dashes will always be in the same place. This is called a Universally unique identifier (UUID). You will use this ID to store your
nodes in a hash map, allowing for easy indexing into the heap and so you can know which nodes need to be added to the heap. You can get this id by calling node.getId().
There are also two public fields on the graph nodes (to make it easier). Their functions are described later, but they are:
public int priority
public GraphNode previousNode
public String previousDirection
To get the GraphNode of your home, you need to have the following code:
GraphWrapper gw = new GraphWrapper()
GraphNode home = gw.getHome()
Do not touch the GraphWrapper.java or GraphNode.java files.
WHAT YOU HAVE TO CODE
Min-Priority Queue – GraphMinPriorityQueue.java
This is a data structure that allows you to add items with certain priorities, and then be able to extract the item with the lowest priority in O(1) time. We are looking for the shortest path to work, so we will give priority to exploring the locations with the shortest distance to the starting point. This is normally created using a heap data structure. You can access and change the priority of a graph node by accessing its public “priority” field. Your data structure should support the following operations:
1. insert(GraphNode g) – this should insert g into the queue with its priority.
2. pullHighestPriorityElement() – this should return and remove from the priority queue the GraphNode with the highest priority in the queue.
3. rebalance(GraphNode g) – this calls the heapify method described below
4. isEmpty() – Returns true if the queue is empty.
To make this easier for you, each node in the graph has a public int “priority” which you can change.
You will also use a HashMap (defined below) internally your heap, mapping the graph nodes to their index in the heap array, so that you can easily index them. It will also allow you to see if a node is in the priority queue. To indicate deletion, you might want to set the value in the HashMap to -1. This will allow you to write the following method in your heap class:
1. heapify(GraphNode g) – once you change the priority of the GraphNode, you should be able to restore the heap-like property of the priority queue at g.