- Documentation
- Installation
- How to Build (with execution examples)
- Testing
- Project Structure
- Features
-
- Link to Project Proposal can be found Here
-
- Link to Development Documentation can be found Here
-
- Link to Team Contracts can be found Here
-
- Link to Results can be found Here
To setup this project, clone the repository locally using the command
git clone https://github.com/cleeclee123/CS225-Final-Project.gitthen cd into the newly made directory to be able to utilize the commands in the How to Build section.
The following description has been modified from CS225 MP documentation.
Preparing the Codebase: This project uses CMake. This allows for us to use libraries such as Catch2 that can be installed in our system rather than providing them specifcally in each project. This means that we need to use CMake to build our own custom makefiles. To do this we need to run the following in the base directory of the project. Which in this project is the CS225-Final-Project directory (or whatever you have have named it).
mkdir build
cd buildThis first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system. Now you need to actually run CMake as follows.
cmake ..This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build. You will need to run make every time you change source code and want to compile it again.
To build the file, use the command:
make mainThere are 4 main commands that can be run after building the main executable from the main command:
./main default
./main parser [airport file] [airline file] [routes file]
./main dijkstra0 [src airport IATA] [dest airport IATA]
./main iddfs0 [src airport IATA] [dest airport IATA] [number of layovers]
./main extra0 [src airport IATA] [dest airport IATA] [airline] [airplane]
./main dfs0 [starting airport IATA]
./main dijkstra1 [airport file] [airline file] [routes file] [src airport IATA] [dest airport IATA]
./main iddfs1 [airport file] [airline file] [routes file] [src airport IATA] [dest airport IATA] [number of layovers]
./main extra1 [airport file] [airline file] [routes file] [src airport IATA] [dest airport IATA] [airline] [airplane]
./main dfs1 [airport file] [airline file] [routes file] [starting airport]
./main dontrunthisThe command ./main will default to a prompt, similar to what you see above, listing all of the available commands.
The command ./main default is suggested to be run first. This gives a demo of what we have built. Specifically, this tests the shortest route avaliable from Willard Airport to London Heathrow Airport on a Boeing 747 operated by American Airlines.
The commands followed by "0" runs the respective algorithm/feature on a the entire Open Flights datasets: airports.dat, airline.dat, routes.dat.
The commands followed by "1" runs the respective algorithm/feature on the datasets passed in as argv[0] to argv[2].
Executing the last command is at your own risk, you have been warned.
Checking for memory leaks:
valgrind --leak-check=full ./mainThe code provides a wide variety of tests for the various functions within the program. To run them and see the resulting account of success and failure use the command:
make testto build them, and then run the test executible using:
./testThe tests that will be run are located within the tests folder of the project. We have included visualizations of the graphs in the tests folder. /
This command will specifically run the data cleaning/parser test cases.
./test [part=1]This command will specifically run the graph construction test cases.
./test [part=2]This command will specifically run the search algorithm test cases.
./test [part=3]This command will specifically run DFS test cases.
./test [part=4]- The codebase can be found in
/projectsHere- In our codebase, tests and datasets can be found in
/tests - The main function is found in the entry directory,
/entry /srccontains all of our code for the parser, objects, and algorithms- The
/libhas been copied over from mp_schedule
- In our codebase, tests and datasets can be found in
- Our Development Log can be founds in
/dev-logsHere - Our Project Documentation can be founds in
/documentsHere
-
- Airport parser
- Helper function used with line parameter and delimiter parameter
- Skips if split data is above the amount of data for the Airport constructor
- Removes \N from input and changes it to blank entry
- Converts some Y/N values into booleans
- Airline parser
- Same as Airport but for Airline objects
- Routes parser
- Same as Airport but for Edge objects
- Airport parser
-
- Airport class
- Holds information about Airports such as the IATA and longitude/latitude coordinates
- Airline class
- Hold information about Airlines, this class helps us answer the "addiitonal constraints" portion of our leading question (along with the edge class that has the corresponding airline iata)
- Edge class
- Holds information about flights/avaliable routes from a src to dest airport
- Graph class
- Abstracts away the adjacency list implementation and other methods to help construct the graph and test the construction
- The graph also contains the dfs traversal and a data member that holds the resulting traversal. You must call
cpp graph.clearTraversal();after each traversal - The graph class also has two methods that counts the number of connected components and determine if two airports are in the same connected component. This was initally used as a check before searching; however, we now use it to help us to build test cases
- Airport class
-
- Dijkstra's Shortest-Path Algorithm
- Finds a path between a "from" and "to" airport
- Path found will be the shortest in terms of distance
- If two airports are unconnected, empty return
- Iterative Deepening Depth First Search Algorithm
- Finds a path between a "from" and "to" airport
- May not be shortest path b/c does not account for edge weight
- Works as a combination of DFS and BFS
- Runs DFS at incrementing depths
- Restricted by a max depth, which represents the number of flights the path can take
- If two airports are unconnected or path outside of max depth, empty return
- DFS
- Searches graph to find path between
- Does not account for edge weights
- First searches down, and then across, hence depth-first search
- Dijkstra's Shortest-Path Algorithm