{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Routing, speed imputation, and travel times\n",
    "\n",
    "Including parallelized shortest-path solving via built-in multiprocessing in OSMnx.\n",
    "\n",
    "Author: [Geoff Boeing](https://geoffboeing.com/)\n",
    "\n",
    "  - [Documentation](https://osmnx.readthedocs.io/)\n",
    "  - [Journal article and citation info](https://doi.org/10.1111/gean.70009)\n",
    "  - [Code repository](https://github.com/gboeing/osmnx)\n",
    "  - [Examples gallery](https://github.com/gboeing/osmnx-examples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!uv pip install --system --quiet osmnx[all]\n",
    "import multiprocessing as mp\n",
    "\n",
    "import numpy as np\n",
    "import osmnx as ox\n",
    "\n",
    "np.random.seed(0)\n",
    "ox.__version__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "place = \"Piedmont, California, USA\"\n",
    "G = ox.graph.graph_from_place(place, network_type=\"drive\")\n",
    "Gp = ox.projection.project_graph(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Fast nearest node/edge search with OSMnx\n",
    "\n",
    "The nearest_nodes and nearest_edges functions take arrays of x and y (or lng/lat) coordinates and return the nearest node/edge to each."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# randomly sample n points spatially-constrained to the network's geometry\n",
    "points = ox.utils_geo.sample_points(ox.convert.to_undirected(Gp), n=100)\n",
    "X = points.x.values\n",
    "Y = points.y.values\n",
    "X0 = X.mean()\n",
    "Y0 = Y.mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find each nearest node to several points, and optionally return distance\n",
    "nodes, dists = ox.distance.nearest_nodes(Gp, X, Y, return_dist=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# or, find the nearest node to a single point\n",
    "node = ox.distance.nearest_nodes(Gp, X0, Y0)\n",
    "node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find each nearest edge to several points, and optionally return distance\n",
    "edges, dists = ox.distance.nearest_edges(Gp, X, Y, return_dist=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the nearest edge to a single point\n",
    "edge = ox.distance.nearest_edges(Gp, X0, Y0)\n",
    "edge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Basic routing by distance\n",
    "\n",
    "Pick two nodes. Then find the shortest path between origin and destination, using weight='length' to find the shortest path by minimizing distance traveled (otherwise it treats each edge as weight=1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the shortest path (by distance) between these nodes then plot it\n",
    "orig = next(iter(G))\n",
    "dest = list(G)[120]\n",
    "route = ox.routing.shortest_path(G, orig, dest, weight=\"length\")\n",
    "fig, ax = ox.plot.plot_graph_route(G, route, route_color=\"y\", route_linewidth=6, node_size=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or get *k* shortest paths, weighted by some attribute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "routes = ox.routing.k_shortest_paths(G, orig, dest, k=30, weight=\"length\")\n",
    "fig, ax = ox.plot.plot_graph_routes(\n",
    "    G,\n",
    "    list(routes),\n",
    "    route_colors=\"y\",\n",
    "    route_linewidth=4,\n",
    "    node_size=0,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Imputing travel speeds and times\n",
    "\n",
    "The `add_edge_speeds` function add edge speeds (km per hour) to graph as new `speed_kph` edge attributes. Imputes free-flow travel speeds for all edges based on mean `maxspeed` value of edges, per highway type. This mean-imputation can obviously be imprecise, and the caller can override it by passing in `hwy_speeds` and/or `fallback` arguments that correspond to local speed limit standards. See docstring for details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# impute speed on all edges missing data\n",
    "G = ox.routing.add_edge_speeds(G)\n",
    "\n",
    "# calculate travel time (seconds) for all edges\n",
    "G = ox.routing.add_edge_travel_times(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# see mean speed/time values by road type\n",
    "edges = ox.convert.graph_to_gdfs(G, nodes=False)\n",
    "edges[\"highway\"] = edges[\"highway\"].astype(str)\n",
    "edges.groupby(\"highway\")[[\"length\", \"speed_kph\", \"travel_time\"]].mean().round(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# same thing again, but this time pass in a few default speed values (km/hour)\n",
    "# to fill in edges with missing `maxspeed` from OSM\n",
    "hwy_speeds = {\"residential\": 35, \"secondary\": 50, \"tertiary\": 60}\n",
    "G = ox.routing.add_edge_speeds(G, hwy_speeds=hwy_speeds)\n",
    "G = ox.routing.add_edge_travel_times(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate two routes by minimizing travel distance vs travel time\n",
    "orig = list(G)[1]\n",
    "dest = list(G)[120]\n",
    "route1 = ox.routing.shortest_path(G, orig, dest, weight=\"length\")\n",
    "route2 = ox.routing.shortest_path(G, orig, dest, weight=\"travel_time\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot the routes\n",
    "fig, ax = ox.plot.plot_graph_routes(\n",
    "    G,\n",
    "    routes=[route1, route2],\n",
    "    route_colors=[\"r\", \"y\"],\n",
    "    route_linewidth=6,\n",
    "    node_size=0,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compare the two routes\n",
    "route1_length = int(sum(ox.routing.route_to_gdf(G, route1, weight=\"length\")[\"length\"]))\n",
    "route2_length = int(sum(ox.routing.route_to_gdf(G, route2, weight=\"travel_time\")[\"length\"]))\n",
    "route1_time = int(sum(ox.routing.route_to_gdf(G, route1, weight=\"length\")[\"travel_time\"]))\n",
    "route2_time = int(sum(ox.routing.route_to_gdf(G, route2, weight=\"travel_time\")[\"travel_time\"]))\n",
    "print(\"Route 1 is\", route1_length, \"meters and takes\", route1_time, \"seconds.\")\n",
    "print(\"Route 2 is\", route2_length, \"meters and takes\", route2_time, \"seconds.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The yellow route minimizes travel time, and is thus longer but faster than the red route.\n",
    "\n",
    "For more examples of travel time, see the [isochrones example](13-isolines-isochrones.ipynb).\n",
    "\n",
    "For more examples of routing, including using elevation as an impedance, see the [elevations example](12-node-elevations-edge-grades.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Multiprocessing\n",
    "\n",
    "Calculating lots of shortest paths can be slow, but OSMnx has built-in shortest path solver parallelization and multiprocessing. With the `shortest_path` function, you can pass in a single origin-destination pair to solve the one shortest path, or you can pass in lists of origins and destinations to solve each shortest path between the pairs.\n",
    "\n",
    "If you're solving shortest paths for multiple origins/destinations, the `cpus` argument determines how many CPU cores to utilize for parallelized solving. Multiprocessing adds some overhead, but it's faster if you're solving a lot of paths. It also has higher RAM requirements (as it must copy data into each sub-process), so be careful with your RAM when setting the `cpus` argument.\n",
    "\n",
    "If you are multiprocessing, always remember to protect your entry point. From the [Python docs](https://docs.python.org/3/library/multiprocessing.html#multiprocessing-programming):\n",
    "\n",
    "> Make sure that the main module can be safely imported by a new Python interpreter without causing unintended side effects (such as starting a new process)... one should protect the “entry point” of the program by using `if __name__ == '__main__':`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate 100,000 shortest-path routes using random origin-destination pairs\n",
    "n = 100_000\n",
    "origs = np.random.choice(G.nodes, size=n, replace=True)\n",
    "dests = np.random.choice(G.nodes, size=n, replace=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# wrap your script in an `if` block to protect the entry point\n",
    "if __name__ == \"__main__\":\n",
    "    # it takes 2.3 seconds to solve all the routes using all the cores on my computer\n",
    "    # I have a 24-thread AMD 5900x: performance will depend on your specific CPU\n",
    "    # uncomment below to actually run the code with multiprocessing\n",
    "    # routes = ox.routing.shortest_path(G, origs, dests, weight=\"travel_time\", cpus=None)\n",
    "    print(mp.cpu_count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "# it takes 29 seconds to solve all the routes using just 1 core on my computer\n",
    "routes = ox.routing.shortest_path(G, origs, dests, weight=\"travel_time\", cpus=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# how many total results did we get\n",
    "print(len(routes))\n",
    "\n",
    "# and how many were solvable paths\n",
    "# some will be unsolvable due to directed graph perimeter effects\n",
    "routes_valid = [r for r in routes if r is not None]\n",
    "print(len(routes_valid))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Miscellaneous routing notes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The routing correctly handles one-way streets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = ox.graph.graph_from_address(\n",
    "    \"N. Sicily Pl., Chandler, Arizona\",\n",
    "    dist=800,\n",
    "    network_type=\"drive\",\n",
    "    truncate_by_edge=True,\n",
    ")\n",
    "origin = (33.307792, -111.894940)\n",
    "destination = (33.312994, -111.894998)\n",
    "origin_node = ox.distance.nearest_nodes(G2, origin[1], origin[0])\n",
    "destination_node = ox.distance.nearest_nodes(G2, destination[1], destination[0])\n",
    "route = ox.routing.shortest_path(G2, origin_node, destination_node)\n",
    "fig, ax = ox.plot.plot_graph_route(G2, route, route_color=\"c\", node_size=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, when there are parallel edges between nodes in the route, OSMnx picks the shortest edge to plot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "location_point = (33.299896, -111.831638)\n",
    "G2 = ox.graph.graph_from_point(location_point, dist=400, truncate_by_edge=True)\n",
    "origin = (33.301821, -111.829871)\n",
    "destination = (33.301402, -111.833108)\n",
    "origin_node = ox.distance.nearest_nodes(G2, origin[1], origin[0])\n",
    "destination_node = ox.distance.nearest_nodes(G2, destination[1], destination[0])\n",
    "route = ox.routing.shortest_path(G2, origin_node, destination_node)\n",
    "fig, ax = ox.plot.plot_graph_route(G2, route, route_color=\"c\", node_size=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}