taxi_algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import geopandas as gpd\n",
    "import shapely.geometry\n",
    "\n",
    "import matplotlib\n",
    "%matplotlib inline\n",
    "\n",
    "import glob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'2.1'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.__version__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "files = glob.glob(\"data/taxi_clean/*_od_v2.pkl\")\n",
    "files = files[0:1]\n",
    "\n",
    "df3 = pd.concat(pd.read_pickle(f) for f in files)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>tpep_pickup_datetime</th>\n",
       "      <th>tpep_dropoff_datetime</th>\n",
       "      <th>pickup_longitude</th>\n",
       "      <th>pickup_latitude</th>\n",
       "      <th>dropoff_longitude</th>\n",
       "      <th>dropoff_latitude</th>\n",
       "      <th>trip_distance</th>\n",
       "      <th>NODEID_O</th>\n",
       "      <th>NODEID_D</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2016-04-01 00:00:00</td>\n",
       "      <td>2016-04-01 00:01:59</td>\n",
       "      <td>-73.976883</td>\n",
       "      <td>40.758495</td>\n",
       "      <td>-73.977669</td>\n",
       "      <td>40.753902</td>\n",
       "      <td>0.50</td>\n",
       "      <td>22520</td>\n",
       "      <td>22499</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2016-04-01 00:00:01</td>\n",
       "      <td>2016-04-01 00:03:46</td>\n",
       "      <td>-73.988899</td>\n",
       "      <td>40.745426</td>\n",
       "      <td>-73.991821</td>\n",
       "      <td>40.738445</td>\n",
       "      <td>0.60</td>\n",
       "      <td>21375</td>\n",
       "      <td>20746</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2016-04-01 00:00:02</td>\n",
       "      <td>2016-04-01 00:06:56</td>\n",
       "      <td>-73.979752</td>\n",
       "      <td>40.780949</td>\n",
       "      <td>-73.966621</td>\n",
       "      <td>40.802837</td>\n",
       "      <td>1.80</td>\n",
       "      <td>21737</td>\n",
       "      <td>9051086</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>2016-04-01 00:00:02</td>\n",
       "      <td>2016-04-01 00:04:42</td>\n",
       "      <td>-74.004730</td>\n",
       "      <td>40.719166</td>\n",
       "      <td>-74.002861</td>\n",
       "      <td>40.723362</td>\n",
       "      <td>0.62</td>\n",
       "      <td>20217</td>\n",
       "      <td>20377</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>2016-04-01 00:00:03</td>\n",
       "      <td>2016-04-01 00:17:55</td>\n",
       "      <td>-73.984787</td>\n",
       "      <td>40.768509</td>\n",
       "      <td>-73.936722</td>\n",
       "      <td>40.813862</td>\n",
       "      <td>4.80</td>\n",
       "      <td>21488</td>\n",
       "      <td>42515</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   tpep_pickup_datetime tpep_dropoff_datetime  pickup_longitude  \\\n",
       "0   2016-04-01 00:00:00   2016-04-01 00:01:59        -73.976883   \n",
       "7   2016-04-01 00:00:01   2016-04-01 00:03:46        -73.988899   \n",
       "10  2016-04-01 00:00:02   2016-04-01 00:06:56        -73.979752   \n",
       "13  2016-04-01 00:00:02   2016-04-01 00:04:42        -74.004730   \n",
       "15  2016-04-01 00:00:03   2016-04-01 00:17:55        -73.984787   \n",
       "\n",
       "    pickup_latitude  dropoff_longitude  dropoff_latitude  trip_distance  \\\n",
       "0         40.758495         -73.977669         40.753902           0.50   \n",
       "7         40.745426         -73.991821         40.738445           0.60   \n",
       "10        40.780949         -73.966621         40.802837           1.80   \n",
       "13        40.719166         -74.002861         40.723362           0.62   \n",
       "15        40.768509         -73.936722         40.813862           4.80   \n",
       "\n",
       "    NODEID_O  NODEID_D  \n",
       "0      22520     22499  \n",
       "7      21375     20746  \n",
       "10     21737   9051086  \n",
       "13     20217     20377  \n",
       "15     21488     42515  "
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df3.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uniform_str(x):\n",
    "    strd = str(x)\n",
    "    while len(strd) < 7:\n",
    "        strd = '0' + strd\n",
    "    return strd\n",
    "df[\"NODEID_O\"] = df[\"NODEID_O\"].apply(uniform_str)\n",
    "df[\"NODEID_D\"] = df[\"NODEID_D\"].apply(uniform_str)\n",
    "df[\"pickup_datetime\"] = pd.to_datetime(df[\"tpep_pickup_datetime\"])\n",
    "df[\"dropoff_datetime\"] = pd.to_datetime(df[\"tpep_dropoff_datetime\"])\n",
    "del df['tpep_dropoff_datetime']\n",
    "del df['tpep_pickup_datetime']\n",
    "\n",
    "mn_nodes = gpd.read_file(\"data/mn_nodes.shp\")\n",
    "init_graph = nx.read_gpickle(\"data/final_graph_1st_pass_nx_2.1.pkl\")\n",
    "for a, b in init_graph.edges.items():\n",
    "    b['speed'] = 25.\n",
    "    b['weight'] = (b['dist'] / b['speed']) * 3600"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def first_average(g):\n",
    "    travel_time = ((g[\"dropoff_datetime\"] - g[\"pickup_datetime\"]).mean().total_seconds())\n",
    "    res = g.iloc[0]\n",
    "    res[\"tt_avg\"] = travel_time\n",
    "    res[\"n_trips\"] = len(g)\n",
    "    return res\n",
    "\n",
    "df = df.groupby([\"NODEID_O\", \"NODEID_D\"]).apply(first_average)\n",
    "del df[\"NODEID_O\"]\n",
    "del df[\"NODEID_D\"]\n",
    "df.reset_index(inplace=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# first trip filtering - > 2 mins, < 1 hour\n",
    "df = df[(df[\"NODEID_O\"] != df[\"NODEID_D\"]) &\n",
    "        (df[\"tt_avg\"] > 120) &\n",
    "        (df[\"tt_avg\"] < 3600)].reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import toolz\n",
    "\n",
    "\n",
    "S_trip = None\n",
    "T_s = None\n",
    "O_s = None\n",
    "\n",
    "def trip_dist(trip):\n",
    "    try:\n",
    "        p = nx.algorithms.shortest_path(init_graph,\n",
    "                                    trip[\"NODEID_O\"], \n",
    "                                    trip[\"NODEID_D\"])\n",
    "    except Exception as e:\n",
    "        print(e)\n",
    "        print(\"=================\".format(n1, n2))\n",
    "        return np.nan\n",
    "    edges = ((p[i], p[i+1]) for i in range(len(p) - 1))\n",
    "    street_dist = sum(init_graph.get_edge_data(*e)['dist'] for e in edges)\n",
    "    return street_dist\n",
    "\n",
    "@toolz.curry\n",
    "def trip_path(trip, graph=None):\n",
    "    \"\"\"\n",
    "    Compute trip time (in hours)\n",
    "    \"\"\"\n",
    "    global S_trip\n",
    "    global T_s\n",
    "    try:\n",
    "        p = nx.algorithms.shortest_path(graph,\n",
    "                                    trip[\"NODEID_O\"], \n",
    "                                    trip[\"NODEID_D\"])\n",
    "        edges = ((p[i], p[i+1]) for i in range(len(p) - 1))\n",
    "        for e in edges:\n",
    "            S_trip.add(e)\n",
    "            T_s[e].add(trip.name)\n",
    "\n",
    "    except Exception as e:\n",
    "        n1 = str(e).split(\" \")[-1][:-1]\n",
    "        n2 = str(e).split(\" \")[-3]\n",
    "        print(\"error on nodes {}, {}\".format(n1, n2))\n",
    "        return np.nan\n",
    "    return \",\".join(p)\n",
    "\n",
    "bad = None\n",
    "\n",
    "@toolz.curry\n",
    "def trip_time(p,graph=None):\n",
    "    global bad\n",
    "    edges = ((p[i], p[i+1]) for i in range(len(p) - 1))\n",
    "    t = 0.\n",
    "    for e in edges:\n",
    "        try:\n",
    "            w = graph.get_edge_data(*e)['weight']\n",
    "        except Exception as q:\n",
    "            bad = p\n",
    "            raise q\n",
    "        t += w\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# second trip filtering\n",
    "df[\"dist\"] = df.apply(trip_dist, axis=1)\n",
    "df.dropna(subset=[\"dist\"], inplace=True)\n",
    "df[\"speed\"] = df[\"dist\"] / (df[\"tt_avg\"])\n",
    "df[\"speed\"].hist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "df = df[((df[\"speed\"] * 3600.) > 1) & (df[\"speed\"] < (65 / (3600.)))].reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "count    465110.000000\n",
       "mean         14.490035\n",
       "std           5.981888\n",
       "min           1.001195\n",
       "25%          10.359372\n",
       "50%          13.539822\n",
       "75%          17.621062\n",
       "max          64.894304\n",
       "Name: speed, dtype: float64"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(df[\"speed\"] * 3600).describe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rel_err sum is -195526.78005809945\n",
      "new_rel_err sum is -142514.0988678577\n",
      "rel_err sum is -142514.0988678577\n",
      "new_rel_err sum is -88124.66426537318\n",
      "rel_err sum is -88124.66426537318\n",
      "new_rel_err sum is -35872.74192097382\n",
      "rel_err sum is -35872.74192097382\n",
      "new_rel_err sum is -19504.80044316536\n",
      "rel_err sum is -19504.80044316536\n",
      "new_rel_err sum is 10727.225747638988\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m-------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m     Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-45-f159347d8714>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     15\u001b[0m     \u001b[0mT_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdefaultdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mset\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# basically trips_by_street\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m     \u001b[0mO_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdefaultdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfloat64\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# offset_by_street\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 17\u001b[0;31m     \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"path\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mapply\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0maxis\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstr\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\",\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     18\u001b[0m     \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"et\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"path\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mapply\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     19\u001b[0m     \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"rel_err\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"et\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"tt_avg\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mdf\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"tt_avg\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/pandas/core/frame.py\u001b[0m in \u001b[0;36mapply\u001b[0;34m(self, func, axis, broadcast, raw, reduce, args, **kwds)\u001b[0m\n\u001b[1;32m   4875\u001b[0m                         \u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0maxis\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4876\u001b[0m                         \u001b[0mreduce\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mreduce\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 4877\u001b[0;31m                         ignore_failures=ignore_failures)\n\u001b[0m\u001b[1;32m   4878\u001b[0m             \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4879\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_apply_broadcast\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0maxis\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/pandas/core/frame.py\u001b[0m in \u001b[0;36m_apply_standard\u001b[0;34m(self, func, axis, ignore_failures, reduce)\u001b[0m\n\u001b[1;32m   4971\u001b[0m             \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4972\u001b[0m                 \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mseries_gen\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 4973\u001b[0;31m                     \u001b[0mresults\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunc\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   4974\u001b[0m                     \u001b[0mkeys\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mname\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4975\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/toolz/functoolz.py\u001b[0m in \u001b[0;36m__call__\u001b[0;34m(self, *args, **kwargs)\u001b[0m\n\u001b[1;32m    281\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__call__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    282\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 283\u001b[0;31m             \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_partial\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    284\u001b[0m         \u001b[0;32mexcept\u001b[0m \u001b[0mTypeError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0mexc\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    285\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_should_curry\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwargs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-36-ceeb183f5f0d>\u001b[0m in \u001b[0;36mtrip_path\u001b[0;34m(trip, graph)\u001b[0m\n\u001b[1;32m     30\u001b[0m         p = nx.algorithms.shortest_path(graph,\n\u001b[1;32m     31\u001b[0m                                     \u001b[0mtrip\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"NODEID_O\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 32\u001b[0;31m                                     trip[\"NODEID_D\"])\n\u001b[0m\u001b[1;32m     33\u001b[0m         \u001b[0medges\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     34\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0me\u001b[0m \u001b[0;32min\u001b[0m \u001b[0medges\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/networkx/algorithms/shortest_paths/generic.py\u001b[0m in \u001b[0;36mshortest_path\u001b[0;34m(G, source, target, weight)\u001b[0m\n\u001b[1;32m    140\u001b[0m             \u001b[0;31m# Find shortest source-target path.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    141\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mweight\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 142\u001b[0;31m                 \u001b[0mpaths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbidirectional_shortest_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msource\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtarget\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    143\u001b[0m             \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    144\u001b[0m                 \u001b[0mpaths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdijkstra_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msource\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtarget\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mweight\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/networkx/algorithms/shortest_paths/unweighted.py\u001b[0m in \u001b[0;36mbidirectional_shortest_path\u001b[0;34m(G, source, target)\u001b[0m\n\u001b[1;32m    224\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    225\u001b[0m     \u001b[0;31m# call helper to do the real work\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 226\u001b[0;31m     \u001b[0mresults\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_bidirectional_pred_succ\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msource\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtarget\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    227\u001b[0m     \u001b[0mpred\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msucc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mw\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mresults\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    228\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/.miniconda2/envs/new_gpd_3/lib/python3.6/site-packages/networkx/algorithms/shortest_paths/unweighted.py\u001b[0m in \u001b[0;36m_bidirectional_pred_succ\u001b[0;34m(G, source, target)\u001b[0m\n\u001b[1;32m    275\u001b[0m             \u001b[0mforward_fringe\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    276\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mthis_level\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 277\u001b[0;31m                 \u001b[0;32mfor\u001b[0m \u001b[0mw\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mGsucc\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    278\u001b[0m                     \u001b[0;32mif\u001b[0m \u001b[0mw\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpred\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    279\u001b[0m                         \u001b[0mforward_fringe\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mw\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "# iterative steps\n",
    "again = True\n",
    "done = False\n",
    "base_graph = init_graph.copy()\n",
    "\n",
    "\n",
    "\n",
    "while again:\n",
    "    tt = trip_time(graph=base_graph)\n",
    "    path = trip_path(graph=base_graph)\n",
    "    again = False\n",
    "    S_trip = set() # all touched streets\n",
    "    T_s = defaultdict(set) # basically trips_by_street\n",
    "    O_s = defaultdict(np.float64) # offset_by_street\n",
    "    df[\"path\"] = df.apply(path, axis=1).str.split(\",\")\n",
    "    df[\"et\"] = df[\"path\"].apply(tt)\n",
    "    df[\"rel_err\"] = (df[\"et\"] - df[\"tt_avg\"]) / df[\"tt_avg\"]\n",
    "    df[\"rel_err\"].hist() if not done else None\n",
    "    done = True\n",
    "    for street, trips in T_s.items():\n",
    "        trips_df = df.loc[trips]\n",
    "        O_s[street] = ((trips_df[\"et\"] - trips_df[\"tt_avg\"]) * trips_df[\"n_trips\"]).sum()\n",
    "    k = 1.2\n",
    "    print(\"rel_err sum is {}\".format(df[\"rel_err\"].sum()))\n",
    "    while True:\n",
    "        g_c = base_graph.copy()\n",
    "        tt2 = trip_time(graph=g_c)\n",
    "        for street in S_trip:\n",
    "            a, b = street # street connects nodes a and b\n",
    "            e = base_graph.edges[street]\n",
    "            if O_s[street] < 0:\n",
    "                g_c[a][b]['weight'] = e[\"weight\"] * k\n",
    "            else:\n",
    "                g_c[a][b]['weight'] = e[\"weight\"] / k\n",
    "        df[\"et_new\"] = df[\"path\"].apply(tt2)\n",
    "        df[\"new_rel_err\"] = (df[\"et_new\"] - df[\"tt_avg\"]) / df[\"tt_avg\"]\n",
    "        print(\"new_rel_err sum is {}\".format(df[\"new_rel_err\"].sum()))\n",
    "        if np.abs(df[\"new_rel_err\"]).sum() < np.abs(df[\"rel_err\"]).sum():\n",
    "            df[\"et\"] = df[\"et_new\"]\n",
    "            df[\"rel_err\"] = df[\"new_rel_err\"]\n",
    "            again = True\n",
    "            base_graph = g_c\n",
    "            break\n",
    "        else:\n",
    "            print(\"k updated to {}\".format(k))\n",
    "            k = 1 + (k - 1) * .75\n",
    "            if k < 1.0001:\n",
    "                break            \n",
    "                \n",
    "df[\"rel_err\"].hist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nx.write_gpickle(base_graph,\"data/base_graph_1st_pass_nx_{}.pkl\".format(nx.__version__))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "nx.algorithms.all_pairs_dijkstra_path_length(init_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for e, attrs in base_graph:\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "final_graph = base_graph.copy()\n",
    "for e, attrs in final_graph.edges.iteritems():\n",
    "    attrs[\"speed\"] = attrs[\"weight\"] / attrs[\"dist\"]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "final_graph.edges.iteritems().next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = set(final_graph.edges.iterkeys())\n",
    "ES = S\n",
    "NS = S - S_trip\n",
    "N_S = nodes_by_street = {s: set(final_graph.edges(s)) for s in S}\n",
    "n_s_i = n_by_street = sorted({s: len(N_S[s].intersection(S_trip)) for s in NS}.iteritems(), key=lambda x: x[1], reverse=True)\n",
    "\n",
    "for s, n in n_s_i:\n",
    "    if n == 0:\n",
    "        continue\n",
    "    intersecting_speeds = [final_graph.edges[(e1,e2)]['speed'] for e1, e2 in N_S[s].intersection(ES)]\n",
    "    final_e = final_graph.edges[s]\n",
    "    v_s_i = sum(intersecting_speeds) / float(n)\n",
    "    t_s_i = final_e[\"dist\"] / v_s_i\n",
    "    final_e[\"speed\"] = v_s_i\n",
    "    final_e[\"weight\"] = t_s_i\n",
    "    ES.add(s)\n",
    "    NS = NS - set([s])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nx.write_gpickle(final_graph,\"data/final_graph_1st_pass_nx_{}.pkl\".format(nx.__version__))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "old = 9285\n",
    "thing = (u'9000428', u'0021076')\n",
    "base_graph.edges.iteritems().next()[1]['ix'] = 9285"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "base_graph.edges.iteritems().next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S_trip.__iter__().next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "init_graph.edge[u'0066086']['0087506']['speed'] = 25.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "init_graph.edge[u'0066086']['0087506']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    ".0056284915 * 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pd.__version__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import functools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import toolz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tt = toolz.curry(trip_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tt(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.Series(np.log(e[\"speed\"]) for _, e in final_graph.edges.iteritems()).hist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.e**5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}