Our project loads airport data and route data to create a graph and compute Dijkstra’s, DFS, and Kosaraju's. To obtain the graph of relavent data, we reformatted the data from the OpenFlights CSV’s to have only the airport’s identifiers, longitude, latitude, and names (for the purpose of a readable output). Then, a graph was created using the formatted data. With this as our input of a graph of all airports, the user input of a starting airport, and the user input of a destination airport, we used Dijkstra’s algorithm to find the shortest route from the starting airport to the destination Airport. Dijkstra’s algorithm will output the path as a vector of strings, with the strings being the three letter airport code from the starting to destination airport. DFS was used to parse through each node of the graph. With an input of a a graph of airports we used Kosaraju’s algorithm to output and int of the number of strongly connected components in the given graph. To confirm that each algorithm was working as intended, we made sufficient smaller test cases that considers each edge case for each algorithm. We also ran tests using the full data sets of airports and routes to confirm that our algorithm is working as expected. Instructions to run each test is given in the README.md.
Our leading question to the project was creating a search algorithm to the shortest paths between any two airports. We also wanted to implement a strongly connected components algorithm to identify the airports with the most traffic. As stated in our proposal, we used Dijkstra’s algorithm to compute the shortest path from and to any airport. We also implemented Kosaraju’s algorithm to identify the strongly connected components in a given graph of airports to figure out the number of airports with the most traffic. Unfortunately as stated in our proposal, we planned to implement a GUI if time allowed, but we did not have enough time for this. Ultimately our project was successful. Our group effectively completed each component that was proposed and did not encounter any conflicts. If we were to nitpick what we would do differently as a team, we believe we could have communicated more often.
In the implementation of DFS, we initially had two functions under no class, one performing DFS until it ran into an unvisited node, and another helper function to catch when it didn’t, which we found was necessary with a graph that may be disconnected. When running our tests, we got an error that our variables were out of scope. We changed it to be its own class, which solved this problem. In the DFS test, we import the values for the nodes from the graph, in order to resize and iterate through the graph correctly. However, after writing our test case to ensure that we iterate through all nodes of the graph, we noticed that the size of the graph we were making was zero. As we found out, this was not an issue with our code, but with where we ran the test from. Because of our filepathing, we found out that tests had to be ran from the “cpp-project-template-main” directory rather than the directory where the tests were (algorithms/parsing). While implementing Dijkstra’s Algorithm, we noticed that we needed to utilize heap instead of a priority queue. When first implementing Dijkstra’s using a priority queue, we noticed that the output is incorrect as queue did not consider the distance. After switching to heap we fixed this issue.