Our project worked with OpenFlights dataset of airports and flight routes. We implemented BFS, Dijkstra’s and projection of the airports on a png of the world map. Our first step was to parse the data and we created structs to store information about the airports such as location information and coordinates. We also had a struct for the routes as they were stored in a separate file. For our graph class we used the one provided for our labs related to graphs. Our next step was to create a class that builds graphs of various sizes efficiently. This class would create graphs from the airports within a country or a set of countries and our final tests were run on graphs containing all airports and routes.
In implementing our algorithms we used the pseudocode shown in class as the foundation for coding the covered algorithms. For the BFS we kept track of the visited nodes using an unordered map and we kept track of the discovery and cross edges by using edge labels. Our code offers two ways to run BFS: one that has a certain starting point and one that traverses the whole map. Investigating why we couldn’t traverse the whole map from a single starting point we found some airports with no incoming flights, we believe this is likely a discrepancy in the dataset or the airlines that provided these flights were not recorded by OpenFlights since they were obscure. Then we implemented Dijkstra’s and found the shortest path between airports. It was interesting to see that the shortest path was not always the most popular route, when comparing it to travel sites, this is likely due to the fact that people will choose reliable airlines over speed. It also may be the case that the shorter route has longer layovers. Lastly we animated the BFS on a map where we discovered despite the number of airports the depth of the traversal was 7. Here is the BFS traversal shown on a map:
Overall, our algorithms provided interesting results and gave us experience with real world data. It exposed us to the difficulties that come with designing and coding our own projects, compared to the MP’s which had less room for design. As a result, we are more aware of practices we should follow when working on our future projects.