Goals and Outcomes

By the end of this project, you will…

• have implemented a graph
• have implemented several fundamental graph algorithms
• have a working maps application that can find paths in real data

Overview

You will be using the data structures you have implemented so far along with a graph to drive a maps application in which you can find nearby buildings and shortest paths between locations.

Connection to Lecture

This project covers lecture17-lecture19 (graphs). You will likely find the code from these lectures to be very useful in this project.

Always Forward, Never Backward

This project is the last data structures project in the course! You will need to use many of your previous data structures to get everything working. In particular, we now absolutely expect you to have two working IDeque implementations (ArrayDeque and LinkedDeque), a working ChainingHashTable, and a working MinFourHeap. If your TrieMap doesn’t work, autocomplete won’t work, but that’s okay.

ISets

When porting your IDictionarys forward, you will notice that the interface changed slightly. We’ve added a keySet method which returns an ISet.

An ISet is backed by an IDictionary that ignores the values. We recommend you look at the implementation of ISet as you might find it instructive. This project will make heavy use of the new keySet method (as opposed to the keys() method) which returns an ISet from an IDictionary in \(\mathcal{O}(1)\) time.

Building an All-Purpose Graph

The first part of this project is writing the Graph class which implements the IGraph interface. You should read the interface documentation to see what methods you should implement. The only restrictions on your backing data structure are (1) it must not use any of the data structures in java.util, and (2) all the methods in the IGraph interface should run in \(\mathcal{O}(1)\) time. As a hint, if you choose a good data structure, none of the methods will be more than 6 lines. Our Graph implementation is 66 lines.

Building the BeaverMapsGraph

Now that we have an all-purpose graph, we will extend on it for the specific case of Open Street Map data. Open Street Map (\url{https://www.openstreetmap.org}) is a free croud-sourced map of the world. The format (called osm) that Open Street Map uses is a form of XML, but we think it’s easier and more useful to use JSON; so, we have downloaded and processed the specific pieces of the data for Pasadena into three JSON files: pasadena.buildings, pasadena.waypoints, and pasadena.roads. We have also included a smaller data set for just Caltech. The first thing you will need to do in your BeaverMapsGraph class is write the constructor which should process each of the three files into vertices and edges in your graph. Open Street Map uses long IDs for each entity which will be the vertices in our graph. Edges are defined by the roads file, where each entry in the list represents multiple edges (one between each consecutive pair of vertices in the inner list).

To parse the buildings file, you should write something like this:

JsonElement bs = fromFile(buildingsFileName);
for (JsonElement b : bs.getAsJsonArray()) {
    Location loc = new Location(b.getAsJsonObject());
    System.out.println("One of the locations is " + loc);
}

The other two files will be similar. Make sure the edge weights in the graph are the distances between Locations (you may find the Location.getDistance method to be helpful here).

At this point, if you run the maps application, you should be able to click on a location and see the location name pop up! The ``Find All Buildings’’ feature should also start working.

Finding Nearby Buildings

Your next task is to make the ‘‘Find Places Nearby’’ functionality work. To do this, you should implement a depth-first search in the dfs method, which stops searching outwards if the distance from the start location is larger than the provided threshold. This does not mean the length of the path from the start to the location. The idea is to search all paths out of the start node until we reach a location that is too far and then backtrack.

Finding Shortest Paths Between Locations

Your next task is to make the ``Find Route’’ functionality work. To do this, you should implement Dijkstra’s Algorithm in the dijkstra method, to compute the shortest path between two locations. Do not add buildings to your path except the start and end ones. Make sure to use the adjacent method to find the edge weights (not getDistance). Unlike in lecture, you will need to only add things you’ve actually seen to the priority queue, because we are working on a very large data set.

OpenEnded Questions