notebooks/04-simplify-graph-consolidate-nodes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simplify network topology and consolidate intersections\n",
    "\n",
    "Author: [Geoff Boeing](https://geoffboeing.com/)\n",
    "\n",
    "  - [Overview of OSMnx](http://geoffboeing.com/2016/11/osmnx-python-street-networks/)\n",
    "  - [GitHub repo](https://github.com/gboeing/osmnx)\n",
    "  - [Examples, demos, tutorials](https://github.com/gboeing/osmnx-examples)\n",
    "  - [Documentation](https://osmnx.readthedocs.io/en/stable/)\n",
    "  - [Journal article/citation](http://geoffboeing.com/publications/osmnx-complex-street-networks/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import osmnx as ox\n",
    "\n",
    "%matplotlib inline\n",
    "ox.config(log_console=True)\n",
    "ox.__version__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Complex intersection consolidation\n",
    "\n",
    "Many real-world street networks feature complex intersections and traffic circles, resulting in a cluster of graph nodes where there is really just one true intersection, as we would think of it in transportation or urban design. Similarly, divided roads are often represented by separate centerline edges: the intersection of two divided roads thus creates 4 nodes, representing where each edge intersects a perpendicular edge, but these 4 nodes represent a single intersection in the real world. Traffic circles similarly create a cluster of nodes where each street's edge intersects the roundabout.\n",
    "\n",
    "OSMnx can consolidate nearby intersections and optionally rebuild the graph's topology."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get a street network and plot it with all edge intersections\n",
    "point = 37.858495, -122.267468\n",
    "G = ox.graph_from_point(point, network_type=\"drive\", dist=500)\n",
    "fig, ax = ox.plot_graph(G, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the complex intersections and traffic circles creating clusters of nodes.\n",
    "\n",
    "We'll specify that any nodes with 15 meter buffers of each other in this network are part of the same intersection. Adjust this tolerance based on the street design standards in the community you are examining, and use a projected graph to work in meaningful units like meters. We'll also specify that we do not want dead-ends returned in our list of consolidated intersections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get a GeoSeries of consolidated intersections\n",
    "G_proj = ox.project_graph(G)\n",
    "intersections = ox.consolidate_intersections(\n",
    "    G_proj, rebuild_graph=False, tolerance=15, dead_ends=False\n",
    ")\n",
    "len(intersections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compare to number of nodes in original graph\n",
    "len(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that these cleaned up intersections give us more accurate intersection counts and densities, but do not alter or integrate with the network's topology.\n",
    "\n",
    "To do that, we need to **rebuild the graph**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# consolidate intersections and rebuild graph topology\n",
    "# this reconnects edge geometries to the new consolidated nodes\n",
    "G2 = ox.consolidate_intersections(G_proj, rebuild_graph=True, tolerance=15, dead_ends=False)\n",
    "len(G2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = ox.plot_graph(G2, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how the traffic circles' many nodes are merged into a new single centroid node, with edge geometries extended to connect to it. Similar consolidation occurs at the intersection of the divided roads.\n",
    "\n",
    "Running `consolidate_intersections` with `rebuild_graph=True` may yield somewhat (but not very) different intersection counts/densities compared to `rebuild_graph=False`. The difference lies in that the latter just merges buffered node points that overlap, whereas the former checks the topology of the overlapping node buffers before merging them.\n",
    "\n",
    "This prevents topologically remote but spatially proximate nodes from being merged. For example:\n",
    "\n",
    "  - A street intersection may lie directly below a freeway overpass's intersection with an on-ramp. We would not want to merge these together and connnect their edges: they are distinct junctions in the system of roads.\n",
    "  - In a residential neighborhood, a bollarded street may create a dead-end immediately next to an intersection or traffic circle. We would not want to merge this dead-end with the intersection and connect their edges.\n",
    "\n",
    "These examples illustrate (two-dimensional) geometric proximity, but topological remoteness. Accordingly, in some situations we may expect higher intersection counts when using `rebuild_graph=True` because it is more cautious with merging in these cases. The trade-off is that it has higher time complexity than `rebuild_graph=False`.\n",
    "\n",
    "## 2. Graph simplification\n",
    "\n",
    "Use simplification to clean-up nodes that are not intersections or dead-ends while retaining the complete edge geometry. OSMnx does this automatically by default when constructing a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a network around some (lat, lng) point and plot it\n",
    "location_point = (33.299896, -111.831638)\n",
    "G = ox.graph_from_point(location_point, dist=500, simplify=False)\n",
    "fig, ax = ox.plot_graph(G, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show which nodes we'd remove if we simplify it (yellow)\n",
    "nc = [\"r\" if ox.simplification._is_endpoint(G, node) else \"y\" for node in G.nodes()]\n",
    "fig, ax = ox.plot_graph(G, node_color=nc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# simplify the network\n",
    "G2 = ox.simplify_graph(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot the simplified network and highlight any self-loop edges\n",
    "loops = [edge[0] for edge in nx.selfloop_edges(G2)]\n",
    "nc = [\"r\" if node in loops else \"y\" for node in G2.nodes()]\n",
    "fig, ax = ox.plot_graph(G2, node_color=nc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# turn off strict mode and see what nodes we'd remove\n",
    "nc = [\"r\" if ox.simplification._is_endpoint(G, node, strict=False) else \"y\" for node in G.nodes()]\n",
    "fig, ax = ox.plot_graph(G, node_color=nc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# simplify network with strict mode turned off\n",
    "G3 = ox.simplify_graph(G.copy(), strict=False)\n",
    "fig, ax = ox.plot_graph(G3, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Cleaning up the periphery of the network\n",
    "\n",
    "This is related to simplification. OSMnx by default (with clean_periphery parameter equal to True) buffers the area you request by 0.5km, and then retrieves the street network within this larger, buffered area. Then it simplifies the topology so that nodes represent intersections of streets (rather than including all the interstitial OSM nodes). Then it calculates the (undirected) degree of each node in this larger network. Next it truncates this network by the actual area you requested (either by bounding box, or by polygon). Finally it saves a dictionary of node degree values as a graph attribute.\n",
    "\n",
    "This has two primary benefits. First, it cleans up stray false edges around the periphery. If clean_periphery=False, peripheral non-intersection nodes within the requested area appear to be cul-de-sacs, as the rest of the edge leading to an intersection outside the area is ignored. If clean_periphery=True, the larger graph is first created, allowing simplification of such edges to their true intersections, allowing their entirety to be pruned after truncating down to the actual requested area. Second, it gives accurate node degrees by both a) counting node neighbors even if they fall outside the retained network (so you don't claim a degree-4 node is degree-2 because only 2 of its neighbors lie within the area), and b) not counting all those stray false edges' terminus nodes as cul-de-sacs that otherwise grossly inflate the count of nodes with degree=1, even though these nodes are really just interstitial nodes in the middle of a chopped-off street segment between intersections.\n",
    "\n",
    "See two examples below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get some bbox\n",
    "bbox = ox.utils_geo.bbox_from_point((45.518698, -122.679964), dist=300)\n",
    "north, south, east, west = bbox"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = ox.graph_from_bbox(north, south, east, west, network_type=\"drive\", clean_periphery=False)\n",
    "fig, ax = ox.plot_graph(G, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the node degree distribution for this graph has many false cul-de-sacs\n",
    "k = dict(G.degree())\n",
    "{n: list(k.values()).count(n) for n in range(max(k.values()) + 1)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above, notice all the peripheral stray edge stubs. Below, notice these are cleaned up and that the node degrees are accurate with regards to the wider street network that may extend beyond the limits of the requested area."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = ox.graph_from_bbox(north, south, east, west, network_type=\"drive\")\n",
    "fig, ax = ox.plot_graph(G, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the streets per node distribution for this cleaned up graph is more accurate\n",
    "# dict keys = count of streets emanating from the node (ie, intersections and dead-ends)\n",
    "# dict vals = number of nodes with that count\n",
    "k = nx.get_node_attributes(G, \"street_count\")\n",
    "{n: list(k.values()).count(n) for n in range(max(k.values()) + 1)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A final example. Compare the network below to the ones in the section above. It has the stray peripheral edges cleaned up. Also notice toward the bottom left, two interstitial nodes remain in that east-west street. Why? These are actually intersections, but their (southbound) edges were removed because these edges' next intersections were south of the requested area's boundaries. However, OSMnx correctly kept these nodes in the graph because they are in fact intersections and should be counted in measures of intersection density, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "location_point = (33.299896, -111.831638)\n",
    "G = ox.graph_from_point(location_point, dist=500, simplify=True)\n",
    "fig, ax = ox.plot_graph(G, node_color=\"r\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python (ox)",
   "language": "python",
   "name": "ox"
  },
  "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.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}