🚇 NYC Subway Search API
A high-performance subway route search application using GTFS (General Transit Feed Specification) data for the New York City Metro system. Built with FastAPI, SQLAlchemy, and Sliding Window / Binary Search algorithms.
🌐 Live Demo
Hosted on Vercel (Python serverless function).
⚡ Key Features
- O(log N) Direct Route Search:
- Fast binary search ("bisect") implementation for station departures over GTFS schedule data.
- BFS Transfer Route Search:
- Multi-leg transfer route finding constrained to maximum 3-step search depth to maintain minimal runtime latency.
- Haversine Nearest Station Calculation:
- Real-time spatial query calculating closest subway stops from user coordinates ($O(N)$ space / time efficiency).
- Custom exception handling ensuring high availability and zero unhandled server crashes (500 errors).
🛠 Tech Stack
| Category | Technologies |
|---|
| Language | Python 3.14 |
| Backend Framework | FastAPI, Uvicorn, Gunicorn |
| Database & ORM | PostgreSQL, SQLite, SQLAlchemy (ORM) |
| Frontend | HTML5, CSS3, JavaScript |
| Testing & Quality | Pytest (Unit & Integration), Pytest-Cov |
| DevOps & CI/CD | Docker, Docker Compose, GitHub Actions |
Dataset
This application processes NYC Subway GTFS data:
- 563,000+ stop-time schedule records
- 20,000+ trip records
- 1,400+ station records
- 30 subway routes
The data is imported into PostgreSQL and accessed through SQLAlchemy ORM with optimized queries.
🚀 Performance Optimization & Complexity
| Algorithm / Feature | Time Complexity | Space Complexity | Optimization Strategy |
|---|
| Direct Route Search | O(log N + M) | O(M) | Binary search (bisect_left) on cached departure times |
| Transfer Search (BFS) | O(V + E) | O(V) | BFS with visited-state pruning and maximum transfer depth |
| Nearest Station | O(N) | O(1) | Haversine distance over cached station coordinates |
🧪 Testing & Continuous Integration (CI)
- (Excluding non-core data migration scripts via
.coveragerc)
- GitHub Actions automatically runs
pytest and coverage checks on every Push and Pull Request.
Stmts Miss Cover
---------------------------
TOTAL 530 66 88%
.
---
📂 Project Structure
├── .github/
│ └── workflows/
│ └── python-app.yml # GitHub Actions CI Workflow
├── data/
│ └── gtfs/
│ ├── routes.txt
│ ├── stops.txt
│ ├── trips.txt
│ └── stop_times.txt
├── models.py # SQLAlchemy DB Models
├── database.py # Database Connection & Session Management
├── main.py # FastAPI entry point: /search_route, /check_stations, calculate_nearest_station
├── search.py # Core algorithms: direct search (binary search), transfer search (depth-bounded BFS), nearest station (Haversine)
├── test_api.py # Pytest Test Cases
├── .coveragerc # Coverage Exclusions Configuration
├── Dockerfile
├── docker-compose.yml
├── .dockerignore
└── requirements.txt
This is the beginning of the README. Read the rest at the original. Read the full README ↗
