app.py

"""
Ride Finder - Flask API for graph algorithm visualization.
Provides endpoints for shortest path algorithms (Dijkstra, Bellman-Ford,
Floyd-Warshall, A*), graph traversals (BFS, DFS), and ride management.
"""

from flask import Flask, render_template, jsonify, request
from dsa.graph import Graph
from dsa.min_heap import MinHeap
from dsa.hash_table import HashTable
from dsa.dijkstra import dijkstra_with_steps
from dsa.traversals import bfs_with_steps, dfs_with_steps
from dsa.bellman_ford import bellman_ford_with_steps
from dsa.floyd_warshall import floyd_warshall_with_steps
from dsa.astar import astar_with_steps

app = Flask(__name__)

# Global graph and ride storage
city = Graph()
rides = HashTable(size=23)


def build_city():
    global city
    city = Graph()
    locations = [
    (0, 110, 49, "Central Station"),
    (1, 250, 90, "Airport"),
    (2, 370, 120, "Mall"),
    (3, 400, 50, "Beach"),
    (7, 530, 95, "Tech Park"),
    (6, 620, 110, "Bus Terminal"),
    (4, 130, 110, "Hospital"),
    (5, 245, 150, "University"),
    (8, 240, 185, "Police Station"),
    (9, 215, 240, "Fire Station"),
    (10, 125, 220, "Bank"),
    (11, 315, 295, "Community Center"),
    (12, 280, 326, "Sports Complex"),
    (13, 356, 198, "Stadium"),
    (14, 555, 165, "Hotel"),
    (15, 195, 310, "Park"),
    (16, 350, 264, "Market"),
    (17, 510, 230, "Theater"),
    (18, 480, 280, "Shopping Plaza"),
    (19, 590, 225, "Museum"),
    (20, 650, 210, "Convention Center"),
    (21, 160, 390, "Library"),
    (22, 270, 420, "Gym"),
    (23, 550, 390, "Restaurant"),
    (24, 650, 380, "Cinema"),
    (25, 190, 440, "School"),
    (26, 350, 540, "Cafe"),
    (27, 485, 465, "Temple"),
    (28, 610, 450, "Lake"),
]
    for loc_id, x, y, label in locations:
        city.add_vertex(loc_id, x, y, label)

    roads = [
        (0, 1, 3), (1, 2, 4), (2, 3, 3), (0, 4, 3), (2, 14, 6),
        (1, 5, 2), (3, 7, 3), (7, 14, 1), (4, 5, 3), (19, 20, 2),
        (5, 8, 1), (9, 15, 3), (8, 13, 6), (17, 14, 2), (7, 6, 3),
        (13, 17, 3), (14, 19, 2), (11, 16, 4), (16, 18, 4), (13, 16, 4),
        (17, 19, 3), (15, 21, 3), (16, 22, 2), (8, 9, 4), (11, 12, 4),
        (19, 24, 3), (21, 22, 4), (22, 23, 3), (23, 24, 4),
        (21, 25, 2), (22, 26, 3), (23, 27, 2), (24, 28, 3),
        (25, 26, 4), (26, 27, 3), (27, 28, 3), (6, 20, 5),
        (0, 5, 4), (15, 12, 3), (17, 24, 4), (17, 18, 3), (9, 10, 4),
        (2, 13, 3), (16, 23, 4), (25, 22, 3), (18, 23, 5), (9, 11, 6),
    ]
    for source, dest, weight in roads:
        city.add_edge(source, dest, weight)


def add_default_rides():
    global rides
    rides = HashTable(size=23)
    default_rides = [
        ("R01", {"driver": "Alice", "loc": 1, "car": "Sedan", "rating": 4.8}),
        ("R02", {"driver": "Bob", "loc": 4, "car": "SUV", "rating": 4.5}),
        ("R03", {"driver": "Charlie", "loc": 7, "car": "Hatch", "rating": 4.9}),
        ("R04", {"driver": "Diana", "loc": 9, "car": "Sedan", "rating": 4.2}),
        ("R05", {"driver": "Eve", "loc": 11, "car": "Van", "rating": 4.7}),
        ("R06", {"driver": "Frank", "loc": 14, "car": "Sedan", "rating": 4.6}),
        ("R07", {"driver": "Grace", "loc": 16, "car": "SUV", "rating": 4.3}),
        ("R08", {"driver": "Hank", "loc": 3, "car": "Hatch", "rating": 4.1}),
        ("R09", {"driver": "Ivy", "loc": 18, "car": "Sedan", "rating": 4.4}),
        ("R10", {"driver": "Jack", "loc": 12, "car": "Van", "rating": 4.8}),
    ]
    for ride_id, ride_data in default_rides:
        rides.put(ride_id, ride_data)


# Initialize city graph and default rides
build_city()
add_default_rides()


# ── Static routes ─────────────────────────────────────────────

@app.route("/")
def index():
    return render_template("index.html")


@app.route("/api/graph")
def get_graph():
    return jsonify(city.to_dict())


@app.route("/api/rides")
def get_rides():
    all_rides = rides.get_all()
    result = []
    for ride in all_rides:
        vertex = city.get_vertex(ride["value"]["loc"])
        result.append({
            "id": ride["key"],
            "driver": ride["value"]["driver"],
            "loc": ride["value"]["loc"],
            "loc_label": vertex.label if vertex else "?",
            "loc_x": vertex.x if vertex else 0,
            "loc_y": vertex.y if vertex else 0,
            "car": ride["value"]["car"],
            "rating": ride["value"]["rating"]
        })
    return jsonify(result)


@app.route("/api/hash_table")
def get_hash_table():
    return jsonify({
        "entries": rides.get_entries_display(),
        "stats": rides.get_stats()
    })


# ── Algorithm endpoints ───────────────────────────────────────

@app.route("/api/dijkstra", methods=["POST"])
def run_dijkstra():
    request_data = request.get_json()
    source = request_data.get("source", 0)
    target = request_data.get("target", None)
    algorithm = request_data.get("algorithm", "dijkstra")

    if algorithm == "bellman_ford":
        return jsonify(bellman_ford_with_steps(city, source, target))
    elif algorithm == "floyd_warshall":
        return jsonify(floyd_warshall_with_steps(city, source, target))
    elif algorithm == "astar":
        return jsonify(astar_with_steps(city, source, target))
    else:
        return jsonify(dijkstra_with_steps(city, source, target))


@app.route("/api/bfs", methods=["POST"])
def run_bfs():
    request_data = request.get_json()
    return jsonify(bfs_with_steps(city, request_data.get("start", 0)))


@app.route("/api/dfs", methods=["POST"])
def run_dfs():
    request_data = request.get_json()
    return jsonify(dfs_with_steps(city, request_data.get("start", 0)))


@app.route("/api/find_riders", methods=["POST"])
def find_riders():
    request_data = request.get_json()
    start = request_data.get("start", 0)
    algorithm = request_data.get("algorithm", "dijkstra")

    if algorithm == "bellman_ford":
        algo_result = bellman_ford_with_steps(city, start)
    elif algorithm == "floyd_warshall":
        algo_result = floyd_warshall_with_steps(city, start)
    elif algorithm == "astar":
        algo_result = astar_with_steps(city, start)
    else:
        algo_result = dijkstra_with_steps(city, start)

    # Build distance map from algorithm results
    vertex_distances = {}
    for distance_entry in algo_result["distances"]:
        vertex_distances[distance_entry["vertex"]] = distance_entry["distance"]

    # Use MinHeap to find top 5 nearest riders
    heap = MinHeap()
    all_rides = rides.get_all()

    for ride in all_rides:
        ride_location = ride["value"]["loc"]
        distance = vertex_distances.get(ride_location, 999999999)
        vertex = city.get_vertex(ride_location)
        ride_info = {
            "id": ride["key"],
            "driver": ride["value"]["driver"],
            "loc": ride_location,
            "loc_label": vertex.label if vertex else "?",
            "car": ride["value"]["car"],
            "rating": ride["value"]["rating"],
            "distance": distance
        }
        heap.insert(distance, ride_info)

    top5 = []
    for _ in range(5):
        if heap.is_empty():
            break
        node, _ = heap.extract_min()
        if node is not None:
            top5.append(node.data)

    return jsonify({
        "top5": top5,
        "algorithm": algorithm,
        "steps": algo_result["steps"],
        "distances": algo_result["distances"]
    })


@app.route("/api/shortest_path", methods=["POST"])
def shortest_path():
    request_data = request.get_json()
    start = request_data.get("start", 0)
    end = request_data.get("end", 0)
    algorithm = request_data.get("algorithm", "dijkstra")

    if algorithm == "bellman_ford":
        result = bellman_ford_with_steps(city, start, end)
    elif algorithm == "floyd_warshall":
        result = floyd_warshall_with_steps(city, start, end)
    elif algorithm == "astar":
        result = astar_with_steps(city, start, end)
    else:
        result = dijkstra_with_steps(city, start, end)

    return jsonify({
        "path": result["path"],
        "path_distance": result["path_distance"],
        "algorithm": algorithm,
        "steps": result["steps"],
        "distances": result["distances"]
    })


# ── Ride management endpoints ─────────────────────────────────

@app.route("/api/add_ride", methods=["POST"])
def add_ride():
    request_data = request.get_json()
    rides.put(request_data["ride_id"], {
        "driver": request_data.get("driver", "?"),
        "loc": request_data.get("location", 0),
        "car": request_data.get("car", "Sedan"),
        "rating": request_data.get("rating", 4.0)
    })
    return jsonify({
        "success": True,
        "entries": rides.get_entries_display(),
        "stats": rides.get_stats()
    })


@app.route("/api/remove_ride", methods=["POST"])
def remove_ride():
    request_data = request.get_json()
    removed = rides.remove(request_data["ride_id"])
    return jsonify({
        "success": removed,
        "entries": rides.get_entries_display(),
        "stats": rides.get_stats()
    })


@app.route("/api/reset")
def reset():
    build_city()
    add_default_rides()
    return jsonify({"success": True})


# ── Application entry point ───────────────────────────────────

if __name__ == "__main__":
    print("=" * 50)
    print("  Ride Finder - DSA Project")
    print("=" * 50)
    print(city)
    print(f"Rides: {rides.get_stats()}")
    print("\nOpen http://127.0.0.1:5000")
    app.run(debug=True, port=5000)