Railroad_Map

Used Google Maps and gRPC to help visualize the benefits of the A* graph search

Table of Contents

• Railroad_Map
  • Background
  • This Project
  • Examples
  • Technologies
  • Running Locally

Background

Graph searching problems are generally phrased as follows: given a graph and two nodes in that graph, what is the shortest path between the two nodes. The canonically famous solution to this problem is Dijkstra's algorithm which is an adaptation on a breadth first search to include weighted edges. However, Dijkstra's algorithm is not very fast. A variant known as A* is significantly faster. If you've ever used a GPS to get directions, you can thank A* for the speed.

So why is A* so much faster? That is the question this visualization seeks to make clear. The difference between A* and Dijkstra is that Dijkstra's algorithm simply fans out from the source node until it finds the destination. At each step, Dijkstra's algorithm decides what node to look at first based on it's distance from the source node alone. In contrast, A* makes its decisions about what node to inspect based on both the distance traveled from the source node and a guess about how far that node is from the destination. Imagine you were looking at a map to find the best way from Chicago to Dallas. Would you consider going 100 miles north in the hopes that magically transports you to Dallas? Probably not. As humans, we are smart enough to keep the destination in mind. You know that Dallas is south of Chicago, so generally you would shy away from paths that take you north because it's the opposite direction from where you want to go. So while Dijkstra will generally check paths fanning out in a circular manner, A* will direct itself towards the destination at every step of the way.

The result: A* outperforms Dijkstra because it reaches the destination faster. It checks fewer paths because it keeps the correct direction in mind at all times.

This Project

This project applies these graph searches to a map of railroads spanning the United States. It allows you to select a source city and a destination city, then performs both graph searches. To visualize what paths are checked by each search, it draws the paths on a map using the Google Maps API. Paths drawn in red are those inspected by A*, those in green are those inspected by Dijkstra's algorithm, and the remaining unchecked paths are drawn in blue. This lets us see that A* simply checks fewer paths than Dijkstra, and that while it fans out around the source city at first, it generally becomes more pointed toward the destination as time goes on.

Examples

Here is a visualization of the path from Washington, D.C. to Minneapolis: Chicago to Dallas: Chicago to Atlanta:

Technologies

• Flask: a super lightweight and quick to use web framework for Python.
• Protocol Buffers: a minimalist serialization tool allowing cross-language and cross-process data structured data transfer with very little memory overhead.
• gRPC: a tool for creating Remote Procedure Call (RPC) services with Protocol Buffers. Generates boilerplate service code which allows clients to communicate to servers running in different threads over HTTP/2.
• Edward: a tool for managing projects that require multiple services running on different processes.
• Google Maps API: Google's JavaScript API to work with embedded maps in websites.

Running Locally

There are a couple steps to getting the server running locally:

1. Install the dependencies with pip install -r requirements.txt
2. Get a Google Maps API key from the Google Developer Console and save it into a secret.py file similar to the example given. If you just edit the example file directly, make sure to remove the example file extension so Python can import it correctly.
3. Generate the base gRPC code and Protobuf classes by navigating into the service directory and running the build script.
4. Start up the services (web server and backend gRPC server). This can be done one of two ways. They can be started separately using python3 server.py and python3 service/railroad_server.py. Alternatively, this project is configured to use edward so if you have it installed you can just run edward start web server
5. Fire up your web browser and navigate to localhost:5000
6. Pick a source and destination from the dropdowns and hit submit to see the results