Graph Algorithm Visualizer and Ride Matching System

A Flask-based graph algorithm visualizer and ride matching system implementing custom data structures and shortest path algorithms.

Overview

graph-algorithm-visualizer is a Flask-based web application that demonstrates the practical use of Data Structures and Algorithms in a ride-matching environment. The project models a city as a weighted graph and allows users to visualize graph traversal and shortest path algorithms while finding the nearest available rides.

The application integrates multiple fundamental data structures and graph algorithms through an interactive web interface.

Features

Graph Algorithms

• Dijkstra's Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• A* Search Algorithm
• Breadth First Search (BFS)
• Depth First Search (DFS)

Data Structures

• Custom Graph Implementation
• Custom Min Heap
• Custom Hash Table

Ride Management

• Add new rides
• Remove rides
• Reset ride data
• View hash table statistics
• Find nearest available riders

Visualization

• Interactive city graph
• Algorithm execution steps
• Shortest path visualization
• Distance tracking
• Rider location display

Demo

The application allows users to:

• Visualize graph traversal algorithms
• Compute shortest paths between locations
• Compare multiple pathfinding algorithms
• Manage rider information using a custom hash table
• Find the nearest available riders

Project Structure

graph-algorithm-visualizer/
│
├── app.py
├── requirements.txt
├── README.md
├── .gitignore
│
├── dsa/
│   ├── graph.py
│   ├── min_heap.py
│   ├── hash_table.py
│   ├── dijkstra.py
│   ├── bellman_ford.py
│   ├── floyd_warshall.py
│   ├── astar.py
│   ├── astar_heap.py
│   └── traversals.py
│
├── templates/
│   └── index.html
│
├── static/
│   ├── style.css
│   ├── main.js
│   └── city_map.png
│
└── screenshots/

Technologies Used

• Python
• Flask
• HTML
• CSS
• JavaScript

Algorithms Implemented

Dijkstra's Algorithm

Computes the shortest path between two vertices in a graph with non-negative edge weights.

Bellman-Ford Algorithm

Computes shortest paths and supports graphs containing negative edge weights.

Floyd-Warshall Algorithm

Computes shortest paths between all pairs of vertices.

A* Search Algorithm

Uses a heuristic-based approach to efficiently find optimal paths.

Breadth First Search (BFS)

Traverses the graph level by level.

Depth First Search (DFS)

Traverses the graph by exploring as far as possible along each branch.

Installation

Clone the Repository

git clone https://github.com/Pathak-Devesh/graph-algorithm-visualizer.git
cd graph-algorithm-visualizer

Create Virtual Environment

python -m venv venv

Activate Virtual Environment

Windows:

venv\Scripts\activate

Linux/Mac:

source venv/bin/activate

Install Dependencies

pip install -r requirements.txt

Run the Application

python app.py

Open:

http://127.0.0.1:5000

Screenshots

Home Page

The main interface displaying the city graph, available algorithms, and ride management features.

Dijkstra's Algorithm

Visualization of Dijkstra's shortest path algorithm with step-by-step execution.

Bellman-Ford Algorithm

Demonstrates shortest path computation using the Bellman-Ford algorithm.

Floyd-Warshall Algorithm

Visualization of all-pairs shortest path computation using the Floyd-Warshall algorithm.

A* Search Algorithm

Heuristic-based shortest path search using the A* algorithm.

Learning Outcomes

This project demonstrates:

• Graph Data Structures
• Hash Tables
• Heaps and Priority Queues
• Graph Traversal Algorithms
• Shortest Path Algorithms
• Heuristic Search
• Backend Development with Flask
• REST API Development
• Algorithm Visualization

Future Improvements

• Real-world map integration
• User authentication
• Dynamic traffic simulation
• Ride booking functionality
• Database integration
• Real-time route updates

License

This project is intended for educational and learning purposes. Feel free to explore, modify, and learn from the implementation.