🗺️ Quickest Path Algorithm

Project n°3 of Year 2024-2025 at ALGOSUP

📋 Project Overview

This project provides a high-performance software solution to calculate the quickest path between two landmarks in the United States. The solution is exposed as a REST API, capable of handling requests efficiently and returning responses in JSON or XML formats. The challenge we reached was to not exceed 1 second for the response time after calculation and API handling.

👨‍💻 Team 7

Name	Role	Profile
Abderrazaq Makran	Program Manager	LinkedIn GitHub
Elone Dellile	Project Manager	LinkedIn GitHub
Guillaume Deramchi	Technical Lead	LinkedIn GitHub
Pierre Gorin	Quality Assurance	LinkedIn GitHub
Benoît De Keyn	Software Engineer	LinkedIn GitHub
Axel David	Software Engineer	LinkedIn GitHub

📝 Project Documents

🚀 Features

Core application: Calculates the shortest or approximate quickest path between two landmarks.
REST API: Provides a web service for sending requests and receiving responses.
Multi-Format Support: Returns responses in JSON or XML.
Performance Optimization: Designed to handle large datasets efficiently.
Debugging Information: Provides additional information for debugging purposes.
Comparator Mode: Compares the precision of A* and Dijkstra's algorithms.
Command Line Interface: Supports various commands for configuration and control.
Front End: Provides a user-friendly interface to test the API.
Cross-Platform: Works on Windows, macOS, and Linux.
Data Integrity Checker: A tool to ensure the integrity of your dataset.
Personalization: Allows customization of the heuristic weight and number of landmarks: You can tune the heuristic weight from 0 (behaves as Dijkstra's algorithm) to as far as you want (so relying only on the estimation of distance to goal). In the second situation, the algorithm will be faster but may give a poor path due to obstacles not taken into account. 1.02 is a good value to keep a path below 1% of the optimal path.

📈 Algorithm Explanation

Imagine you are in a city and want to find the quickest route to a destination. You have a map, but instead of just looking at the map, you also have some "landmarks" that help you estimate distances more accurately. Here's how our algorithm works:

Landmarks: Think of landmarks as well-known points in the city, like famous buildings or intersections. These landmarks help you estimate how far you are from your destination. For example, if you know the distance from your current location to a landmark and from the landmark to your destination, you can make a good guess about the total distance.
A Algorithm*: This is like having a smart GPS that not only looks at the direct distance but also considers the estimated distance to the destination. It combines:
- g(n): The actual cost from the start point to the current point.
- h(n): The estimated cost from the current point to the destination, using landmarks.
Dijkstra's Algorithm: This is like a traditional GPS that only looks at the actual distances without any estimation. It finds the shortest path by exploring all possible routes.
Comparator Mode: This mode compares the paths found by A* and Dijkstra's algorithms. It helps us understand how close the path found with A* algorithm is to the optimal path found by Dijkstra's one, within a far faster time.
Why A* ?: A* algorithm with landmarks table (aka A* ALT) is faster because it uses estimates to prioritize which paths to explore, reducing the number of unnecessary calculations by pruning paths that are unlikely to be the shortest. It is a good balance between speed and accuracy.

📦 Dataset

The dataset used for this project is the USA road network, which contains a list of ~28 000 000 weighted edges between ~24 000 000 nodes. The dataset is stored in a CSV file you can find here: USA-roads.csv.

📂 Project Structure

Global Structure

2024-2025-project-3-quickest-path-team-7/
├── code/
│   ├── front/
│   ├── integrity_checker/
│   ├── path_finder/
├── Document/
│   ├── Functional/
│   ├── Technical/
│   ├── QA/
│   └── Management/
├── README.md
└── LICENSE

Code Structure

code/
├── front/
│   ├── index.html
│   ├── style.css
│   └── main.js
├── integrity_checker/
│   ├── checker.cpp
│   └── checker.hpp
├── path_finder/
│   ├── files/
│   │   ├── USA-roads.csv
│   │   ... (built backups)
│   │   ... (output files)
│   ├── headers/
│   │   ├── algorithms.hpp
│   │   ├── api.hpp
│   │   ├── graph.hpp
│   │   ... (other headers)
│   └── main.cpp
├── macLinuxProjectBuilder.sh
└── windowsProjectBuilder.bat

⚙️ Setup and Installation

1. Install LFS

To deal with large files in Git, you need to install Git LFS (Large File Storage) before cloning the repository.

However, if you use GitHub Desktop, go to step 4 directly.

For Windows:

winget install --id=GitHub.GitLFS

For macOS:

brew install git-lfs

For Linux:

sudo apt-get install git-lfs

2. Enable LFS for Git

In any terminal, run the following command:

git lfs install

3. Clone the repository

git clone https://github.com/algosup/2024-2025-project-3-quickest-path-team-7.git
cd 2024-2025-project-3-quickest-path-team-7

4. Run the project

The 2 scripts provided here to build and run the project on Windows and macOS/Linux will automatically :

Install the compiler if needed
Compile the C++ code for path_finder
Run the server
Open the front end in your default browser

For Windows:

Run the provided batch script to build and run the project:

cd code
windowsProjectBuilder.bat

For macOS/Linux:

Run the provided shell script to build and run the project:

cd code
sh macLinuxProjectBuilder.sh

If required, give the execution rights to the script before running it:

chmod 777 macLinuxProjectBuilder.sh

🌐 Front End

A front end is provided to conveniently test the API. It is launched automatically by the project builders or can be run manually by opening code/front/index.html.

📚 API Documentation

Endpoints

1. `GET /path`

Calculates the quickest path between two landmarks.

Request Parameters:

start (integer): ID of the start landmark.
end (integer): ID of the destination landmark.
format (optional, string): Response format (json or xml).

Example Requests:

GET /path?start=100&end=200
GET /path?start=100&end=200&format=xml

Example Responses:

JSON:

{
    "path_length": "12079",
    "path": ["100", "150", "200"]
}

XML:

<response>
    <path_length>12079</path_length>
    <path>
        <node>100</node>
        <node>150</node>
        <node>200</node>
    </path>
</response>

2. `GET /comp_path`

Compares the quickest path calculated by A* and Dijkstra's algorithms. Oversize percentage is the percentage of the path length that the A* algorithm can exceed compared to Dijkstra's algorithm which is the optimal path.

Request Parameters:

start (integer): ID of the start landmark.
end (integer): ID of the destination landmark.
format (optional, string): Response format (json or xml).

Example Request:

GET /comp_path?start=100&end=200
GET /comp_path?start=100&end=200&format=xml

Example Response in JSON:

{
    "dataset": "USA-roads.csv",
    "start": "100",
    "end": "200",
    "oversize_percentage": "10.0",
    "dijkstra_path_length": "110",
    "astar_path_length": "120",
    "time_unit": "milliseconds",
    "astar_calculation_time": "50",
    "dijkstra_calculation_time": "100",
    "astar_nodes_quantity": "3",
    "dijkstra_nodes_quantity": "3",
    "heuristic_weight": "1.0",
    "landmarks_quantity": "10",
    "compared_path": [
        {
            "astar": {"id": "100", "weight": "0"},
            "dijkstra": {"id": "100", "weight": "0"}
        },
        {
            "astar": {"id": "150", "weight": "60"},
            "dijkstra": {"id": "150", "weight": "55"}
        },
        {
            "astar": {"id": "200", "weight": "120"},
            "dijkstra": {"id": "200", "weight": "110"}
        }
    ]
}

3. `GET /debug_path`

Calculates the quickest path between two landmarks with additional debugging information.

Request Parameters:

start (integer): ID of the start landmark.
end (integer): ID of the destination landmark.
format (optional, string): Response format (json or xml).

Example Request:

GET /debug_path?start=100&end=200
GET /debug_path?start=100&end=200&format=xml

Example Response in JSON:

{
    "dataset": "USA-roads.csv",
    "start": "100",
    "end": "200",
    "path_length": "120",
    "time_unit": "milliseconds",
    "calculation_time": "50",
    "heuristic_weight": "1.0",
    "landmarks_quantity": "10",
    "landmarks": ["1", "2", "3"],
    "nodes_quantity": "3",
    "path": [
        {"id": "100", "weight": "0"},
        {"id": "150", "weight": "60"},
        {"id": "200", "weight": "120"}
    ]
}

🖥️ Server Documentation

Commands

The server supports various commands that can be executed from the command line:

[integer]: Ask for a node Y to calculate the path between X and Y.
[string]: Read if it's a keyword for a preloaded path (such as fast, med, longest,...) and run it.
"comparator": Activate the comparator mode to evaluate the difference between A* and Dijkstra precision.
"exit comparator": Deactivate the comparator mode.
"weight": Change the heuristic weight.
"qty lm": Change the number of landmarks.
"build lm": Rebuild the landmarks.
"build graph": Rebuild the graph.
"display lm": Display the landmarks.
"pwd": Display the current working directory.
"new dataset": Change the dataset name.
"files location": Change the location of input/output files.
"display files": Display the current files paths.
"new port": Change the port number.
"display api": Display/hide the API responses and requests specifically.
"stop": Exit the program.

Example Commands

To change the heuristic weight: The weight must be a positive number, it allows to balance the weight of the heuristic function in the A* algorithm as explained above.
```
weight
Enter the weight: 1.5
```
To change the number of landmarks: Landmarks distances are precomputed then read to estimate distances meeded for A* heuristics.
```
qty lm
Enter the number of landmarks: 10
```
To change the port number of the API: The port number must be a positive integer, it allows to change the port access to API server.
```
new port
Enter the new port number: 8080
```

📄 License

This project is licensed under the MIT License. See the LICENSE file for details.

Name		Name	Last commit message	Last commit date
Latest commit History 282 Commits
.github		.github
Document		Document
code		code
googletest @ 7d76a23		googletest @ 7d76a23
.DS_Store		.DS_Store
.gitattributes		.gitattributes
.gitignore		.gitignore
.gitmodules		.gitmodules
CMakeLists.txt		CMakeLists.txt
LICENSE		LICENSE
README.md		README.md

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

🗺️ Quickest Path Algorithm

Table of Contents

📋 Project Overview

👨‍💻 Team 7

📝 Project Documents

🚀 Features

📈 Algorithm Explanation

📦 Dataset

📂 Project Structure

Global Structure

Code Structure

⚙️ Setup and Installation

1. Install LFS

For Windows:

For macOS:

For Linux:

2. Enable LFS for Git

3. Clone the repository

4. Run the project

For Windows:

For macOS/Linux:

🌐 Front End

📚 API Documentation

Endpoints

1. `GET /path`

2. `GET /comp_path`

3. `GET /debug_path`

🖥️ Server Documentation

Commands

Example Commands

📄 License

About

Releases

Packages

Contributors 6

Languages

License

algosup/2024-2025-project-3-quickest-path-team-7

Folders and files

Latest commit

History

Repository files navigation

🗺️ Quickest Path Algorithm

Table of Contents

📋 Project Overview

👨‍💻 Team 7

📝 Project Documents

🚀 Features

📈 Algorithm Explanation

📦 Dataset

📂 Project Structure

Global Structure

Code Structure

⚙️ Setup and Installation

1. Install LFS

For Windows:

For macOS:

For Linux:

2. Enable LFS for Git

3. Clone the repository

4. Run the project

For Windows:

For macOS/Linux:

🌐 Front End

📚 API Documentation

Endpoints

1. GET /path

2. GET /comp_path

3. GET /debug_path

🖥️ Server Documentation

Commands

Example Commands

📄 License

About

Topics

Resources

License

Stars

Watchers

Forks

Releases

Packages 0

Contributors 6

Languages

1. `GET /path`

2. `GET /comp_path`

3. `GET /debug_path`

Packages