GEO-DSA: Path Finding & Algorithm Visualizer (Google Maps Style)

Welcome to GEO-DSA, a comprehensive university-level Data Structures and Algorithms (DSA) project. This project implements and visualizes almost every fundamental data structure, pathfinding algorithm, sorting routine, prefix autocomplete trie, spatial partitioning system, and recursive backtracking solver from scratch in TypeScript.

The user interface replicates Google Maps (featuring animated highway transit flows, traffic multipliers, water/building terrain costs, and side-by-side twin map comparisons).

---

🚀 Installation & Running Guide

Ensure you have Node.js installed (v18 or higher recommended).

1. Initialize and Run the Backend API

The server stores maps and route histories inside a persistent SQLite database (database.db).

cd server
npm install
npm run dev

The server will start on http://localhost:5000.

2. Initialize and Run the Frontend Client

The client dashboard renders the interactive pathfinding canvas visualizer.

cd client
npm install
npm run dev

Open http://localhost:5173 in your browser.

---

📂 Project Directory Structure

DSA/
├── client/
│   ├── src/
│   │   ├── datastructures/      <-- Manual Data Structures (Custom TS implementations)
│   │   │   ├── LinkedList.ts    <-- Doubly Linked List for Undo/Redo & histories
│   │   │   ├── Stack.ts         <-- Stack structure for DFS and Backtracking
│   │   │   ├── Queue.ts         <-- Queue structure for BFS & Animation frames
│   │   │   ├── MinHeap.ts       <-- Binary Min-Heap Priority Queue for Dijkstra/A*
│   │   │   ├── Graph.ts         <-- Custom weighted directed Graph class
│   │   │   ├── BST.ts           <-- BST for saved route indexing
│   │   │   ├── Trie.ts          <-- Prefix Trie for destination autocomplete suggestions
│   │   │   └── SpatialPartition.ts <-- Quadtree for canvas proximity queries
│   │   ├── algorithms/          <-- Manual Algorithms
│   │   │   ├── pathfinding.ts   <-- BFS, DFS, Dijkstra, A*, Greedy BFS, Bidirectional, Bellman-Ford, Floyd-Warshall
│   │   │   ├── maze.ts          <-- Recursive Backtrack, stack DFS, Prim's & Kruskal's maze
│   │   │   └── graph.ts         <-- Cycle Detection, Connected Components, Prim/Kruskal MST
│   │   ├── store/
│   │   │   └── useStore.ts      <-- Zustand application state management store
│   │   ├── components/          <-- React UI Component Layouts
│   │   │   ├── CanvasMap.tsx    <-- Interactive HTML5 Canvas map renderer
│   │   │   ├── Sidebar.tsx      <-- Controls menu
│   │   │   ├── StatsPanel.tsx   <-- Diagnositics
│   │   │   ├── ComparePanel.tsx <-- Head-to-head dual canvas side-by-side mode
│   │   └── App.tsx              <-- Navigation layout
│   ├── tailwind.config.js
│   └── postcss.config.js
├── server/
│   ├── src/
│   │   ├── index.ts             <-- Express API setup & endpoints
│   │   └── database.ts          <-- SQLite initialization & connection pool
│   └── tsconfig.json
└── README.md

---

🛠️ Data Structures Implemented (From Scratch)

To comply with rigorous university academic standards, no external libraries are used for data operations. Every class is coded manually in vanilla TypeScript:

1. Doubly Linked List (LinkedList.ts): Contains pointers to prev and next nodes, providing $O(1)$ insertions and deletions. Used to track route histories and paint-brush operations.
2. Stack (Stack.ts): A classic LIFO container supporting push, pop, and peek operations. Powers DFS traversals, backtracking recursions, and undo-redo tracking.
3. Queue (Queue.ts): A FIFO queue optimized with an offset index to achieve amortized $O(1)$ dequeues (avoiding expensive JavaScript array shifts). Powers BFS and animation frame buffers.
4. Binary Min-Heap (MinHeap.ts): A complete binary tree array mapping elements to index relations Left = 2i + 1, Right = 2i + 2. Maintains optimal distance priorities, resolving extractMin in $O(\log V)$. Powers Dijkstra and A*.
5. Graph (Graph.ts): A flexible structure supporting vertices, directed/undirected weighted edges, and dynamic generation of Adjacency List maps and Adjacency Matrix grids.
6. Binary Search Tree (BST.ts): Implements standard binary partitioning. Supports duplicate numerical keys by stacking matching elements in array buckets at matching nodes. Used to sort/store route logs.
7. Trie (Trie.ts): A character-level prefix tree providing $O(L)$ query lookups (where $L$ is query string length). Backs the Google Maps search autocomplete feature.
8. Quadtree (SpatialPartition.ts): Performs 2D coordinate-based grid splitting (Divide and Conquer). Drastically speeds up click and hover detection on coordinate systems.

---

📈 Algorithmic Complexity Reference Table

Algorithm	Type	Time Complexity (Best/Worst)	Space Complexity	Guaranteed Shortest Path?
A* Search	Pathfinding	$O((E + V) \log V)$	$O(V)$	Yes (with admissible heuristic)
Dijkstra	Pathfinding	$O((E + V) \log V)$	$O(V)$	Yes (on non-negative weights)
BFS	Pathfinding	$O(E + V)$	$O(V)$	Yes (on unweighted edges)
DFS	Pathfinding	$O(E + V)$	$O(V)$	No
Bellman-Ford	Pathfinding	$O(V \cdot E)$	$O(V)$	Yes (supports negative weights)
Floyd-Warshall	Pathfinding	$O(V^3)$	$O(V^2)$	Yes (All-Pairs on downsampled subgrid)
Quick Sort	Sorting	$O(N \log N)$ / $O(N^2)$	$O(\log N)$	Stable pivot partition
Merge Sort	Sorting	$O(N \log N)$	$O(N)$	Guaranteed stable sort
Heap Sort	Sorting	$O(N \log N)$	$O(1)$	In-place sorting
Binary Search	Searching	$O(\log N)$	$O(1)$	Requires sorted array inputs

---

🗺️ Google Maps Theme Details

• Highway Speedups: Highways are drawn in gold/orange and speed up vehicle transit (weight cost drops to 0.5).
• Transit Modes:
  • Driving (Optimal highway travel, traffic penalties apply).
  • Walking (Ignores highway benefits, standard speed, ignores traffic).
  • Biking (Highways blocked, streets normal speed).
  • Emergency Rescue (Ignores traffic congestion penalties, pushes speed limits).
• Traffic Multipliers: Heavy congestion regions apply up to 3.0x multipliers on travel duration weights.