path: root/dashboard_website/router.py

import datetime

import numpy as np
import requests
from sklearn.cluster import KMeans

from datastructs import *
import db

host = "http://acetyl.net:5000"  # queries acetyl.net:5000, the OSRM engine

endtime = datetime.datetime(2024, 11, 16, hour=18, minute=45)  # 11/18/2023 6:35pm

# external facing functions


# gets single leg route between bike and clue
# should be HD and GeoJSON
def getRouteFullJSON(bike, clue):
    bike = bike.toJSON()
    clue = clue.toJSON()
    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?steps=true&overview=full&geometries=geojson"
    r = requests.get(url)
    return r.json()


def getRouteHDPolyline(bike, clue):
    bike = bike.toJSON()
    clue = clue.toJSON()
    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?overview=full&geometries=geojson"
    r = requests.get(url)

    p = r.json()["routes"][0]["geometry"]["coordinates"]
    return p


def getRouteFastPolyline(bike, clue):
    bike = bike.toJSON()
    clue = clue.toJSON()
    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?geometries=geojson"
    r = requests.get(url)
    p = r.json()["routes"][0]["geometry"]["coordinates"]
    return p


# determines clusters based on current bikes and clues
def getClusters(bikes, clues, endpoint, minimal=True):
    status = 0
    clusters = [[] for bike in bikes]
    route_geos = [[] for bike in bikes]
    times = {}
    active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"]
    active_bikes = [bike for bike in bikes if bike.status != "DISABLED"]
    if len(active_bikes) == 0:
        return status, clusters, route_geos, times
    active_clues = [ clue for clue in clues if (clue.status != "VISITED" and clue.status != "DISABLED") ]
    # select only active bikes
    # select only unvisited clues
    status_c, clusters_t, route_geos_t, times_t = cluster_and_optimize(
        active_clues, bikes, endpoint, minimal
    )
    if status_c != 0: # routing canceled
        return -1, [], [], []
    for i in range(len(bikes)):
        route_geos[i] = route_geos_t[i]
        clusters[i] = clusters_t[i]
        times[i] = times_t[i]

    # return list of clue clusters corresponding to bikes
    return status, clusters, route_geos, times


# utility functions (internal)
def cluster_and_optimize(
    clues: [Clue], bikes: [Bike], end: Point, minimal : bool, time_diff=0.75
):
    """
    Takes a dataframe of gps coordinates, a list of centroids, and an end point and returns a dataframe with a cluster
    :param clues: a list of clues
    :param bikes: a list of centroids
    :param end: the end point of the trip
    :param time_diff: the maximum time difference between the longest trip and the average trip
    :param max_time: the maximum time of the trip
    :param n: the number of routes to create
    :return: a list of lists of clues (ordered by position on route), and a list of json route geojsons
    """
    status = 0
    # OVERRIDE MAX TIME
    max_max_time = endtime - datetime.datetime.now() 
    max_max_time = max_max_time.seconds / 3600
   
    # Create a new column with normalized gps coordinates and centroids
    active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"]
    active_bikes = [bike for bike in bikes if bike.status != "DISABLED"]

    normalized_points, norm_centroids = __normalize_points(clues, active_bikes)
    # Cluster the coordinates
    kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids)
    kmeans.fit(normalized_points)

    # assign pre-determined clues to bikes
    already_assigned_clues = []
    routes = [[] for i in bikes]
    # if we are not doing a hard reset, keep the current target clues
    if minimal:
        for i, bike in enumerate(bikes):
            if (bike.status != "DISABLED") and (bike.target_clue != None):
                #routes[i].append(bike.target_clue)
                print("Already assigned clue at: ", bike.target_clue)
                already_assigned_clues.append(bike.target_clue)
    for clue in clues:
        if clue.assigned_team != 0 and ((clue.assigned_team-1) in active_indices) and (clue not in already_assigned_clues):
            routes[clue.assigned_team - 1].append(clue)
            already_assigned_clues.append(clue)

    # Split the remaining clues into clusters based on the cluster labels
    for i, label in enumerate(kmeans.labels_):
        if clues[i].assigned_team == 0 and (clues[i] not in already_assigned_clues):
            routes[active_indices[label]].append(clues[i])

    routes, times = __minimize_route_time_diff(routes, bikes, end, minimal, time_diff)
    if routes == -1:
        return -1, [], [], []

    # Remove waypoints from the longest route until the trip time is less than the max time
    #for i in range(len(routes)):
    #    resp = __remove_longest_waypoints(routes[i], bikes[i], end, max(max_max_time, bikes[i].timeTilDeadline()/3600), minimal)
    #    if resp == -1:
    #        return -1, [], [], []
    #    routes[i] = resp
    clue_pool = []
    routes_done = [False for bike in bikes if bike.status != "DISABLED"]
    routes = __balance_waypoints(routes, bikes, end, times, clue_pool, routes_done, max_max_time, minimal)
    if routes == -1:
        return -1, [], [], []
    
    # Get the json of the routes
    route_waypoints = []
    geometries = []
    times = []
    for i, route in enumerate(routes):
        if db.should_cancel_routing(): return -1, [], [], []
        route_json = __get_json(
            __clues_to_string(route),
            __clues_to_string([bikes[i].target_clue if (minimal and (bikes[i].target_clue != None))  else bikes[i]]),
            __clues_to_string([end])[:-1],
        )
        geometries.append(route_json["trips"][0]["geometry"]["coordinates"])
        route_waypoints.append(route_json["waypoints"])
        eta = time.time() + route_json["trips"][0]["duration"] + 90 * len(route)
        eta_str = datetime.datetime.fromtimestamp(eta).strftime("%I:%M:%S%p")
        times.append(eta_str)

    # Use the waypoint_index to reorder each route
    
    for i, route in enumerate(routes):
        route2 = ["" for x in route]
        start_index = 0 if (minimal and (bikes[i].target_clue != None)) else 1 # if starting route with first clue, first index of trip must be included
        for j, k in enumerate(route_waypoints[i][1:-1]):
            route2[k["waypoint_index"] - 1] = route[j]
        if (minimal and (bikes[i].target_clue != None)):
            route2.insert(0, bikes[i].target_clue)
        routes[i] = route2

    return status, routes, geometries, times


def __clues_to_string(points: [Clue]):
    """
    Takes a list of points and returns a string of the list of points
    :param points: a list of points
    :return: a string of the list of points
    """
    string = ""
    for i in points:
        string += str(i.longitude) + "," + str(i.latitude) + ";"

    return string


def __get_json(coordinate_string, start, end):
    """
    Takes a string of coordinates and returns the json of the route
    :param coordinate_string: a string of coordinates
    :param start: the start point of the trip
    :param end: the end point of the trip
    :return: the json of the route
    """
    coordinates = requests.get(
        "http://acetyl.net:5000/trip/v1/bike/"
        + start
        + coordinate_string
        + end
        + "?roundtrip=false&source=first&destination=last&geometries=geojson&overview=full&exclude=ferry"
    )
    coordinates = coordinates.json()

    return coordinates


def __get_trip_time(
    coordinate_string, num_waypoints, start, end, time_per_waypoint=90, seconds=False
):
    """
    Takes a string of coordinates and returns the trip time in hours
    :param coordinate_string: a string of coordinates
    :param num_waypoints: the number of waypoints
    :param start: the start point of the trip
    :param end: the end point of the trip
    :param time_per_waypoint: the time per waypoint in seconds
    :return: the trip time in hours
    """
    coordinates = requests.get(
        "http://acetyl.net:5000/trip/v1/bike/"
        + start
        + coordinate_string
        + end
        + "?roundtrip=false&source=first&destination=last&exclude=ferry"
    )
    coordinates = coordinates.json()

    travel_time_seconds = int(coordinates["trips"][0]["duration"])
    waypoint_time_seconds = num_waypoints * time_per_waypoint
    if seconds:
        return travel_time_seconds + waypoint_time_seconds
    total_time_hours = (travel_time_seconds + waypoint_time_seconds) / 3600

    return total_time_hours


def __minimize_route_time_diff(
    routes: [Clue], bikes: [Bike], end: Point, minimal: bool, time_diff
):
    """
    Takes a list of lists of coordinates, a list of start points, an end point, a time difference, and a number of routes
    :param routes: the list of lists of coordinates
    :param starts: the list of start points
    :param end: the end point
    :param time_diff: the time difference
    :param n: the number of routes
    :return: a list of lists of coordinates
    """

    if db.should_cancel_routing(): return -1

    active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"]
    starts = [ bike.target_clue if (minimal and (bike.target_clue != None)) else bike for bike in bikes ] # all bikes regardless of enabled
    
    times = [ ]

    for i, route in enumerate(routes):
        if bikes[i].status == "DISABLED": continue
        times.append(
            __get_trip_time(
                __clues_to_string(route),
                len(route),
                __clues_to_string([starts[i]]),
                __clues_to_string([end])[:-1],
            ) * bikes[i].time_modifier
        )
        if db.should_cancel_routing(): return -1

    # Find the average trip time
    average_time = np.mean(times)

    # Sort the trip times
    sorted_indices = np.argsort(times)

    # Find the difference between the longest trip time and the average trip time
    time_difference = times[sorted_indices[-1]] - average_time
    print(times)
    # If the difference is greater than the time difference, move a coordinate from the longest route to the shortest route
    if time_difference > time_diff:
        # Move a coordinate from the longest route to the shortest route
        for _ in range(max(1,int(time_difference/0.25))): # roughly estimate how many points must be moved to equalize
            closest_coordinate = __find_closest_coordinates(
                routes[active_indices[sorted_indices[-1]]], __mean_center(routes[sorted_indices[0]])
            )[0]
            routes[active_indices[sorted_indices[0]]].append(closest_coordinate)
            routes[active_indices[sorted_indices[-1]]].remove(closest_coordinate)

        # Recursively minimize the time difference between the routes
        return __minimize_route_time_diff(routes, bikes, end, minimal, time_diff)

    # If the difference of the longest trip time from average is less than the time difference, return the routes
    return routes, times

def __balance_waypoints(
    routes: [Clue], bikes: [Bike], end: Point, times, clue_pool: [Clue], routes_done: [bool], max_time, minimal
):
    """
    Takes a list of coordinates, a start point, an end point, and a maximum time and returns a list of coordinates
    :param route_coordinates: the list of coordinates
    :param start: the start point
    :param end: the end point
    :param max_time: the maximum time
    :return: a list of coordinates
    """

    if db.should_cancel_routing(): return -1
    active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"]
    starts = [ bike.target_clue if (minimal and (bike.target_clue != None)) else bike for bike in bikes ] # all bikes regardless of enabled
    max_times = [ min(bike.timeTilDeadline()/3600, max_time) for bike in bikes ]
    time_balances = [ (max_times[i] - times[i]) for i in range(len(times))]
    print(time_balances)
    balanced = True
    for i, balance in enumerate(time_balances):
        if balance < 0 and (not routes_done[active_indices[i]]):
            balanced = False
            break
    if balanced:
        return routes
    # shorten too-long routes
    for i, time_balance in enumerate(time_balances):
        print(i, time_balance)
        if time_balance < 0 and (not routes_done[active_indices[i]]): # route too long
            route_mean = __mean_center(routes[active_indices[i]])
            s, farthest_coordinates = __find_farthest_coordinates(routes[active_indices[i]], route_mean, max(1,min(int(-1*time_balance/0.12),int(len(routes[active_indices[i]])*0.5))))
            for farthest_coordinate in farthest_coordinates:
                routes[active_indices[i]].remove(farthest_coordinate)
                clue_pool.append(farthest_coordinate)
            if s == -1:
                routes_done[active_indices[i]] = True
    # lengthen routes with spare room
    for i, time_balance in enumerate(time_balances):
        if time_balance > 0.15: # route too short
            route_mean = __mean_center(routes[active_indices[i]])
            closest_coordinates = __find_closest_coordinates(clue_pool, route_mean, 1)
            for closest_coordinate in closest_coordinates:
                routes[active_indices[i]].append(closest_coordinate)
                clue_pool.remove(closest_coordinate)

    for i, route in enumerate(routes):
        if bikes[i].status == "DISABLED": continue
        if db.should_cancel_routing(): return -1
        times[active_indices[i]] = __get_trip_time(
                                        __clues_to_string(route),
                                        len(route),
                                        __clues_to_string([starts[i]]),
                                        __clues_to_string([end])[:-1],
                                    ) * bikes[i].time_modifier
        
    return __balance_waypoints(routes, bikes, end, times, clue_pool, routes_done, max_time, minimal)



def __remove_longest_waypoints(
    route_coordinates: [Clue], start: Bike, end: Point, max_time, minimal, start_already_set=False
):
    """
    Takes a list of coordinates, a start point, an end point, and a maximum time and returns a list of coordinates
    :param route_coordinates: the list of coordinates
    :param start: the start point
    :param end: the end point
    :param max_time: the maximum time
    :return: a list of coordinates
    """
    if len(route_coordinates) < 1:
        return []

    if db.should_cancel_routing(): return -1
    
    print(max_time)

    if minimal and (start.status != "DISABLED") and (start.target_clue != None): # already assigned a clue
        start = start.target_clue
    # Find the trip time for the route
    route_time = __get_trip_time(
        __clues_to_string(route_coordinates),
        len(route_coordinates),
        __clues_to_string([start]),
        __clues_to_string([end])[:-1],
    )

    # If the trip time is greater than the max time, remove the waypoint with the longest distance from the mean
    if route_time > max_time:
        print(route_time)
        route_mean = __mean_center(route_coordinates)
        _, farthest_coordinates = __find_farthest_coordinates(route_coordinates, route_mean)
        for farthest_coordinate in farthest_coordinates:
            route_coordinates.remove(farthest_coordinate)

        return __remove_longest_waypoints(route_coordinates, start, end, max_time, minimal, start_already_set=True)

    return route_coordinates




def __normalize_points(clues: [Clue], bikes: [Bike]):
    """
    Takes a list of coordinates and a list of centroids and returns a list of normalized coordinates and a list of
    normalized centroids
    :param clues: the list of coordinates
    :param bikes: the list of centroids
    :return: the list of normalized coordinates and the list of normalized centroids
    """

    # Create a list of latitudes and longitudes
    latitudes = [i.latitude for i in clues]
    longitudes = [i.longitude for i in clues]

    # Find the minimum and maximum latitudes and longitudes
    min_lat = min(latitudes)
    max_lat = max(latitudes)
    min_lon = min(longitudes)
    max_lon = max(longitudes)

    # Normalize the coordinates and centroids using min-max normalization
    normalized_coordinates = []
    normalized_centroids = []

    for i in clues:
        normalized_coordinates.append(
            [
                __min_max_normalize(i.latitude, min_lat, max_lat),
                __min_max_normalize(i.longitude, min_lon, max_lon),
            ]
        )
    for i in bikes:
        normalized_centroids.append(
            [
                __min_max_normalize(i.latitude, min_lat, max_lat),
                __min_max_normalize(i.longitude, min_lon, max_lon),
            ]
        )

    return normalized_coordinates, normalized_centroids


def __min_max_normalize(value, min_value, max_value):
    """
    Takes a value, a minimum value, and a maximum value and returns the normalized value
    :param value: the value
    :param min_value: the minimum value
    :param max_value: the maximum value
    :return: the normalized value
    """
    return (value - min_value) / (max_value - min_value)


def __find_closest_coordinates(clues: [Clue], centroid: Point, n:int=1):
    """
    Takes a list of coordinates and a centroid and returns the clue in the list that is closest to the centroid
    :param clues: the list of coordinates
    :param centroid: the centroid
    :return: the clue in the list that is closest to the centroid
    """
    
    # Convert the clues to a list of points
    closest_coordinates = []
    for _ in range(min(n, len(clues))):
        closest_coordinate = clues[0]
        # remove only unrequired clues
        i = 1
        while closest_coordinate in closest_coordinates:
            closest_coordinate = clues[i]
            i += 1 

        closest_coordinate_distance = __distance(closest_coordinate, centroid)

        for clue in clues:
            if __distance(clue, centroid) < closest_coordinate_distance and (clue not in closest_coordinates):
                closest_coordinate = clue
                closest_coordinate_distance = __distance(clue, centroid)
        
        closest_coordinates.append(closest_coordinate)

    return closest_coordinates


def __find_farthest_coordinates(clues: [Clue], centroid: Point, n:int=1):
    """
    Takes a list of coordinates and a centroid and returns the clue in the list that is farthest from the centroid
    :param clues: the list of coordinates
    :param centroid: the centroid
    :return: the clue in the list that is farthest from the centroid
    """
    print(len(clues),n)
    farthest_coordinates = []
    for _ in range(min(len(clues),n)):
        farthest_coordinate = clues[0]
        # remove only unrequired clues
        i = 1
        while farthest_coordinate.required or (farthest_coordinate in farthest_coordinates):
            if i >= len(clues):
                return -1, farthest_coordinates
            farthest_coordinate = clues[i]
            i += 1 

        farthest_coordinate_distance = __distance(farthest_coordinate, centroid)

        for clue in clues:
            if __distance(clue, centroid) > farthest_coordinate_distance and (not clue.required) and (clue not in farthest_coordinates):
                farthest_coordinate = clue
                farthest_coordinate_distance = __distance(clue, centroid)
        
        farthest_coordinates.append(farthest_coordinate)

    return 0, farthest_coordinates


def __mean_center(clues: [Clue]):
    """
    Takes a list of coordinates and returns the mean center of the coordinates
    :param clues: the list of coordinates
    :return: the mean center of the coordinates
    """
    return Point(
        np.mean([coordinate.latitude for coordinate in clues]),
        np.mean([coordinate.longitude for coordinate in clues]),
    )


def __distance(coordinate1: Clue, coordinate2: Point):
    """
    Takes two coordinates and returns the distance between them
    :param coordinate1: the first coordinate
    :param coordinate2: the second coordinate
    :return: the distance between the two coordinates
    """
    return (
        (coordinate1.latitude - coordinate2.latitude) ** 2
        + (coordinate1.longitude - coordinate2.longitude) ** 2
    ) ** 0.5