Optimal_Routes.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tCSzbcSYrchv"
      },
      "source": [
        "# FINDING OPTIMAL ROUTES"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8GqkqMNmrqBs",
        "outputId": "a3f0952d-4a88-4314-9c7b-81fe5cfcc417"
      },
      "outputs": [],
      "source": [
        "# disabled for debug purposes\n",
        "# !pip install osmnx\n",
        "# !pip install networkx"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "yathFw28rU6W"
      },
      "outputs": [],
      "source": [
        "import osmnx as ox\n",
        "import networkx as nx\n",
        "# ox.config(log_console=True, use_cache=True)\n",
        "# # define the start and end locations in latlng\n",
        "# start_latlng = (37.78497,-122.43327)\n",
        "# end_latlng = (37.78071,-122.41445)\n",
        "# # location where you want to find your route\n",
        "# place     = 'San Francisco, California, United States'\n",
        "# # find shortest route based on the mode of travel\n",
        "# mode      = 'walk'        # 'drive', 'bike', 'walk'\n",
        "# # find shortest path based on distance or time\n",
        "# optimizer = 'time'        # 'length','time'\n",
        "# # create graph from OSM within the boundaries of some \n",
        "# # geocodable place(s)\n",
        "# graph = ox.graph_from_place(place, network_type = mode)\n",
        "# # find the nearest node to the start location\n",
        "# orig_node = ox.get_nearest_node(graph, start_latlng)\n",
        "# # find the nearest node to the end location\n",
        "# dest_node = ox.get_nearest_node(graph, end_latlng)\n",
        "# #  find the shortest path\n",
        "# shortest_route = nx.shortest_path(graph,\n",
        "#                                   orig_node,\n",
        "#                                   dest_node,\n",
        "#                                   weight=optimizer)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZK3NBMEHtPjN"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "import csv\n",
        "import datetime as dt\n",
        "import matplotlib.pyplot as plt"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 354
        },
        "id": "LZMYxlrntRB2",
        "outputId": "5166e5bf-27fd-461c-822f-7ebac9021edf"
      },
      "outputs": [],
      "source": [
        "df = pd.read_csv('https://raw.githubusercontent.com/hauntedcupoftea/nikolaj/main/datasets/crimedata2016.csv')\n",
        "df.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 354
        },
        "id": "NRQjq06suXMy",
        "outputId": "6591ee94-e0db-4eb7-904f-646968b334b4"
      },
      "outputs": [
        {
          "ename": "NameError",
          "evalue": "name 'df' is not defined",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "Cell \u001b[0;32mIn [5], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m timelist \u001b[39m=\u001b[39m []\n\u001b[0;32m----> 2\u001b[0m \u001b[39mfor\u001b[39;00m i \u001b[39min\u001b[39;00m \u001b[39mrange\u001b[39m(\u001b[39mlen\u001b[39m(df)):\n\u001b[1;32m      3\u001b[0m     datetime_object \u001b[39m=\u001b[39m dt\u001b[39m.\u001b[39mdatetime\u001b[39m.\u001b[39mstrptime(df[\u001b[39m'\u001b[39m\u001b[39mDate\u001b[39m\u001b[39m'\u001b[39m][i][\u001b[39m-\u001b[39m\u001b[39m11\u001b[39m:], \u001b[39m'\u001b[39m\u001b[39m%\u001b[39m\u001b[39mI:\u001b[39m\u001b[39m%\u001b[39m\u001b[39mM:\u001b[39m\u001b[39m%\u001b[39m\u001b[39mS \u001b[39m\u001b[39m%\u001b[39m\u001b[39mp\u001b[39m\u001b[39m'\u001b[39m)\n\u001b[1;32m      4\u001b[0m     timelist\u001b[39m.\u001b[39mappend(datetime_object)\n",
            "\u001b[0;31mNameError\u001b[0m: name 'df' is not defined"
          ]
        }
      ],
      "source": [
        "timelist = []\n",
        "for i in range(len(df)):\n",
        "    datetime_object = dt.datetime.strptime(df['Date'][i][-11:], '%I:%M:%S %p')\n",
        "    timelist.append(datetime_object)\n",
        "df['Time'] = timelist\n",
        "df.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 206
        },
        "id": "bUvMsZ37uaqT",
        "outputId": "0715a4e6-c0f0-4d38-bb88-306e525b8d4a"
      },
      "outputs": [],
      "source": [
        "cleandf = df.drop(['Date', 'X Coordinate', 'Y Coordinate', 'Beat', 'Year', 'FBI Code'], axis=1)\n",
        "cleandf.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Tz5Q9sdGueK4",
        "outputId": "d964ee38-dfd7-48f3-c75b-6f33967fcaca"
      },
      "outputs": [],
      "source": [
        "# using sklearn's label encoder for more complex encoders where severity isn't needed\n",
        "from sklearn import preprocessing as pp\n",
        "lp = pp.LabelEncoder()\n",
        "op = pp.OrdinalEncoder()\n",
        "# creating a manual encoder for descriptions\n",
        "basicCrime = list(set(cleandf['Primary Type']))\n",
        "basicCrime"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6KVAdqu9ugn4",
        "outputId": "177a329b-0b63-4b58-e959-449abd275752"
      },
      "outputs": [],
      "source": [
        "# manual encoding of crimes based on severity\n",
        "# in order to generate a heatmap of which areas are the most dangerous\n",
        "primList = {'NON - CRIMINAL': 0, 'NON-CRIMINAL (SUBJECT SPECIFIED)': 0, 'NON-CRIMINAL': 0,\n",
        "            'INTIMIDATION': 1, 'OBSCENITY': 1, 'OTHER OFFENSE': 1, 'PUBLIC INDECENCY': 1,\n",
        "            'LIQUOR LAW VIOLATION': 2, 'PUBLIC PEACE VIOLATION': 2, 'CONCEALED CARRY LICENSE VIOLATION': 2,\n",
        "            'PROSTITUTION': 3, 'GAMBLING': 3, 'INTERFERENCE WITH PUBLIC OFFICER': 3, 'STALKING': 3,\n",
        "            'ARSON': 6, 'BURGLARY': 5, 'BATTERY': 2, 'ROBBERY': 5, 'SEX OFFENSE': 5, 'ASSAULT': 3,\n",
        "            'THEFT': 4, 'DECEPTIVE PRACTICE': 5, 'CRIMINAL TRESPASS': 4, 'CRIMINAL DAMAGE': 4, 'WEAPONS VIOLATION' : 5,\n",
        "            'MOTOR VEHICLE THEFT': 5, 'OFFENSE INVOLVING CHILDREN': 5, 'KIDNAPPING': 5, 'NARCOTICS': 5,\n",
        "            'OTHER NARCOTIC VIOLATION' : 4,'HUMAN TRAFFICKING' : 6,'CRIM SEXUAL ASSAULT' : 6, 'HOMICIDE' : 6}\n",
        "len(primList)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 354
        },
        "id": "HV5DzfSOukg3",
        "outputId": "c7e18835-8ef3-4259-af54-078880d2c743"
      },
      "outputs": [],
      "source": [
        "# running the encode, along with the other encoders and adding them all to the dataframe\n",
        "encodePrim = [primList[i] for i in cleandf['Primary Type']]\n",
        "cleandf['desc'] = lp.fit_transform(cleandf['Description'])\n",
        "cleandf['locdesc'] = lp.fit_transform(cleandf['Location Description'])\n",
        "cleandf['type'] = encodePrim\n",
        "cleandf.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rIaTTeVwunjr",
        "outputId": "5c178f07-f69b-4b1c-8152-54b313f40b9e"
      },
      "outputs": [],
      "source": [
        "from collections import Counter\n",
        "count = Counter(cleandf['Location'])\n",
        "print(count)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 417
        },
        "id": "rRqI-xLpusan",
        "outputId": "de53cf28-a507-4dad-8566-bc0f9b222b09"
      },
      "outputs": [],
      "source": [
        "# colormap = {0 : '#0d0887', 1 : '#5d02a4', 2 : '#9b169e', 3 : '#c94579', \n",
        "#             4 : '#ed7953', 5 : '#fcb331', 6 : '#f0f821'}\n",
        "# plt.scatter(cleandf['Longitude'], cleandf['Latitude'], marker='.', \n",
        "#             c=[colormap[i] for i in cleandf['type']])\n",
        "# plt.show()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hLg788oVuxih",
        "outputId": "f8dc9d79-b589-4e93-d085-8f490c5edaf1"
      },
      "outputs": [],
      "source": [
        "# making a time filter\n",
        "def timeFilter(start: str, end: str) -> pd.DataFrame:\n",
        "    start = dt.datetime.strptime(start, '%H:%M:%S')\n",
        "    end = dt.datetime.strptime(end, '%H:%M:%S')\n",
        "    if (start < end):\n",
        "        return cleandf.loc[(df['Time'] >= start) & (df['Time'] < end)]\n",
        "    else:\n",
        "        return cleandf.loc[(df['Time'] >= start) | (df['Time'] < end)]\n",
        "\n",
        "# examplse of if\n",
        "ifs = timeFilter('17:00:00', '09:00:00')\n",
        "# example of else\n",
        "els = timeFilter('09:00:00','17:00:00')\n",
        "# check to see if we cover everything\n",
        "print(len(ifs) + len(els) == len(cleandf))\n",
        "els.shape"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 354
        },
        "id": "pMaC2OPsuzqM",
        "outputId": "b0b7f72a-e952-4243-a91a-558f39c7234b"
      },
      "outputs": [],
      "source": [
        "cleandf.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dBcbkN40u9Sz"
      },
      "outputs": [],
      "source": [
        "from sklearn.cluster import *\n",
        "def one():\n",
        "    nCluster = int(input())\n",
        "#    color = list(np.random.choice(range(256), size=nCluster))\n",
        "    model = KMeans(n_clusters=nCluster)\n",
        "    results = model.fit_predict(cleandf.loc(axis=1)['Latitude':'Longitude'])\n",
        "#    plt.scatter(cleandf['Longitude'], cleandf['Latitude'], marker='.', \n",
        "#                c=[color[i] for i in results])\n",
        "    return results"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "N6NVXrXku_ZR",
        "outputId": "76be1af9-db56-40c8-ba26-c7320925c0c4"
      },
      "outputs": [],
      "source": [
        "results = one()\n",
        "color = list(np.random.choice(range(256), size=len(set(results))))\n",
        "cleandf['cluster'] = results"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "huRBlbDTvboG"
      },
      "outputs": [],
      "source": [
        "from scipy.spatial import Delaunay\n",
        "def alpha_shape(points, alpha, only_outer=True):\n",
        "    assert points.shape[0] > 3, \"Need at least four points\"\n",
        "    def add_edge(edges, i, j):\n",
        "        if (i, j) in edges or (j, i) in edges:\n",
        "            assert (j, i) in edges, \"Can't go twice over same directed edge right?\"\n",
        "            if only_outer:\n",
        "                edges.remove((j, i))\n",
        "            return\n",
        "        edges.add((i, j))\n",
        "    tri = Delaunay(points)\n",
        "    edges = set()\n",
        "    for ia, ib, ic in tri.vertices:\n",
        "        pa = points[ia]\n",
        "        pb = points[ib]\n",
        "        pc = points[ic]\n",
        "        a = np.sqrt((pa[0] - pb[0]) ** 2 + (pa[1] - pb[1]) ** 2)\n",
        "        b = np.sqrt((pb[0] - pc[0]) ** 2 + (pb[1] - pc[1]) ** 2)\n",
        "        c = np.sqrt((pc[0] - pa[0]) ** 2 + (pc[1] - pa[1]) ** 2)\n",
        "        s = (a + b + c) / 2.0\n",
        "        area = np.sqrt(s * (s - a) * (s - b) * (s - c))\n",
        "        circum_r = a * b * c / (4.0 * area)\n",
        "        if circum_r < alpha:\n",
        "            add_edge(edges, ia, ib)\n",
        "            add_edge(edges, ib, ic)\n",
        "            add_edge(edges, ic, ia)\n",
        "    return edges"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 417
        },
        "id": "KxySvZAivhN_",
        "outputId": "91f8d3e6-af7b-49b2-c5c7-274faf6d3cec"
      },
      "outputs": [],
      "source": [
        "import warnings\n",
        "warnings.filterwarnings(\"ignore\")\n",
        "# Plotting the output\n",
        "fig, ax = plt.subplots(figsize=(30, 8))\n",
        "for i in range(len(set(results))):\n",
        "    fildf = cleandf[cleandf['cluster'] == i]\n",
        "    nmod = KMeans(int(np.power(len(fildf), 0.25)))\n",
        "    nmod.fit([[i, j] for i, j in zip(fildf['Longitude'], fildf['Latitude'])])\n",
        "    centers = nmod.cluster_centers_\n",
        "    points = np.array([[i, j] for i, j in zip(fildf['Longitude'], fildf['Latitude'])])\n",
        "    try:\n",
        "        edges = alpha_shape(centers, alpha=4, only_outer=True)\n",
        "    except:\n",
        "        continue\n",
        "    plt.subplot(1, 3, 1)\n",
        "    plt.plot(points[:, 0], points[:, 1], '.')\n",
        "    # USE EDGES AND CENTERS TO PLOT NORMAL ROUTES, REMOVE POINTS AND ALL REFERENCES IN FINAL CODE\n",
        "    for i, j in edges:\n",
        "        plt.plot(centers[[i, j], 0], centers[[i, j], 1])\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t6xoMktwvtic",
        "outputId": "1f7bdb15-6f3c-49c7-f733-4325e8ef0c02"
      },
      "outputs": [],
      "source": [
        "print(edges)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UhRUdH_SvzNG",
        "outputId": "05c6a014-2241-462b-c292-be65dbf6993e"
      },
      "outputs": [],
      "source": [
        "print(centers)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Afi3yfpmxEdZ",
        "outputId": "3efe40a8-637a-4c66-d563-6002b2ad49cc"
      },
      "outputs": [],
      "source": [
        "centers[1]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "w_ajoAVt0IW7",
        "outputId": "3d75e14b-2449-4168-9311-e09d382f64cd"
      },
      "outputs": [],
      "source": [
        "centers[0]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Qk25ZgT6wMaL"
      },
      "outputs": [],
      "source": [
        "# ox.config(log_console=True, use_cache=True)\n",
        "# # define the start and end locations in latlng\n",
        "# # start_latlng = (37.78497,-122.43327)\n",
        "# # end_latlng = (37.78071,-122.41445)\n",
        "\n",
        "# start_latlang = centers[0]\n",
        "# end_latlng = centers[2]\n",
        "# # location where you want to find your route\n",
        "# place     = 'Chicago, Illinois, United States'\n",
        "# # find shortest route based on the mode of travel\n",
        "# mode      = 'drive'        # 'drive', 'bike', 'walk'\n",
        "# # find shortest path based on distance or time\n",
        "# optimizer = 'time'        # 'length','time'\n",
        "# # create graph from OSM within the boundaries of some \n",
        "# # geocodable place(s)\n",
        "# graph = ox.graph_from_place(place, network_type = mode)\n",
        "# # find the nearest node to the start location\n",
        "# orig_node = ox.get_nearest_node(graph, start_latlng)\n",
        "# # find the nearest node to the end location\n",
        "# dest_node = ox.get_nearest_node(graph, end_latlng)\n",
        "# #  find the shortest path\n",
        "# shortest_route = nx.shortest_path(graph,\n",
        "#                                   orig_node,\n",
        "#                                   dest_node,\n",
        "#                                   weight=optimizer)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qh68jb52z4PR"
      },
      "outputs": [],
      "source": [
        "\n",
        "# shortest_route_map = ox.plot_route_folium(graph, shortest_route)\n",
        "# shortest_route_map"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 855
        },
        "id": "-oCSG0uLbAvq",
        "outputId": "fec492fd-f794-4a0c-8500-e4ddbdb72946"
      },
      "outputs": [],
      "source": [
        "def find_route(st,end):\n",
        "  ox.config(log_console=True, use_cache=True)\n",
        "  # define the start and end locations in latlng\n",
        "  # start_latlng = (37.78497,-122.43327)\n",
        "  # end_latlng = (37.78071,-122.41445)\n",
        "\n",
        "  start_latlang = st\n",
        "  end_latlng = end\n",
        "  # location where you want to find your route\n",
        "  place     = 'Chicago, Illinois, United States'\n",
        "  # find shortest route based on the mode of travel\n",
        "  mode      = 'drive'        # 'drive', 'bike', 'walk'\n",
        "  # find shortest path based on distance or time\n",
        "  optimizer = 'time'        # 'length','time'\n",
        "  # create graph from OSM within the boundaries of some \n",
        "  # geocodable place(s)\n",
        "  graph = ox.graph_from_place(place, network_type = mode)\n",
        "  # find the nearest node to the start location\n",
        "  orig_node = ox.get_nearest_node(graph, start_latlang)\n",
        "  # find the nearest node to the end location\n",
        "  dest_node = ox.get_nearest_node(graph, end_latlng)\n",
        "  #  find the shortest path\n",
        "  shortest_route = nx.shortest_path(graph,\n",
        "                                    orig_node,\n",
        "                                    dest_node,\n",
        "                                    weight=optimizer)\n",
        " \n",
        "  shortest_route_map = ox.plot_route_folium(graph, shortest_route)\n",
        "  return shortest_route_map\n",
        "find_route(centers[0],centers[1])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jirtxafziN7s"
      },
      "outputs": [],
      "source": [
        "# import gmplot  \n",
        "# latitudeList = [ 28.691234, 28.818390, 29.089301 ]  \n",
        "# longitudeList = [ 77.193802, 77.023890, 76.865211 ]  \n",
        "# myGmap = gmplot.GoogleMapPlotter(28.612894, 77.229446, 11)  \n",
        "# myGmap.scatter( latitudeList, longitudeList, '#FF0000', size = 40, marker = False )  \n",
        "# # drawing a polygon using the polygon() method  \n",
        "# # of the GoogleMapPlotter class with the help of coordinates  \n",
        "# myGmap.polygon( latitudeList, longitudeList, color = 'cornflowerblue' )  \n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "authorship_tag": "ABX9TyNybwmqDQ6NSvdpYJOB2ArZ",
      "include_colab_link": true,
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.9.15 ('tf')",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.9.15"
    },
    "vscode": {
      "interpreter": {
        "hash": "6314624a9b716fa5073b1b74923d7a0fe6a712a100f298bdf1d68454cdfed291"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}