zorazrr/cs225-final-project

CS225 data structures (sp22) final project on graph algorithms

CS225 Final Project: The Complete California Experience

Presentation Video • Data • Repo Structure • Running Instructions • Team

Presentation Video

Data

We are using the California Road Network and Points of Interest data and focusing on the following two files:

• California Road Network's Nodes (Node ID, Longitude, Latitude)
• California Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

Repo Structure

Deliverables

• All major files that contain our functions and classes are in the root directory. The structure of those files is outlined in Project Structure.

• Datasets are stored as txt files in /data.

• Tests are in /tests.

• Project report, development log, contract, etc. are in /documents.

Project Structure

Running Instructions

Make sure you are running the program in Docker. If not, follow This Guide to get started.

Executable

To use our Complete California Experience program, run make then ./main in the root directory. Follow the instructions of our program and you are good to go!

We call all the functions in main.cpp for you (through a fleshed-out utils.cpp that will print clear instructions on what your user input should be). The required inputs for each of the functionality are as follows:

1. GPS (Dijkstra's):
   • Input: starting node number and ending node number (both should be integer between 0 and 21047)
   • Output: the shortest path (nodes it passes through) and the distance of the shortest path (in km)
   • Image Output: californiaShortestPath.png that outlines the shortest path on the California map constructed from our nodes
2. Sporadic Tour (Welsh-Powell Colorability):
   • Input: an integer within the given bounds (currently it's 1-3)
   • Output: the node numbers, based on our colorability algorithm, that correspond to your given input and represent places you should visit
3. Nearest Attraction (KD Tree Nearest Neighbors):
   • Input: longitude (-124.389343 ~ -114.294258) and latitude (32.541302 ~ 42.017231)
   • Output: a latitude - longitude pair that indicates a California attraction that is closest to your current location
4. Lazy/Cluster Travel (BFS):
   • Input: starting node number (integer between 0 and 21047)
   • Output: a traversal path within your current cluster

In addition to the above overarching functions that are called in main.cpp, we also have clear input and output definitions in the comments for each small functions, so you can always refer to those.

Tests

To run the test cases, run make test then ./test in the root directory.

We constructed several small to medium sized datasets in /data directory, which are used as test cases to evaluate if the output of our algorithms are as expected. We also tested for edge cases such as when the graph is not fully connected. Our tests focus on testing the functionality of graph construction, Djikstra's algorithm, Welsh-Powell algorithm, and KD Tree construction.

Team

We are TreeLovers who love California:

• Ellie Chang (elliepc2)
• Grace Zhang (gracewz2)
• Zora Zhang (ruoranz2)