{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# OSMnx + igraph for faster performance\n",
    "\n",
    "Author: [Geoff Boeing](https://geoffboeing.com/)\n",
    "\n",
    "NetworkX is ubiquitous, easy to use, and sufficiently fast for most use cases. But it can be slow for analyzing very large graphs because it is pure Python, trading off speed for ease of use. Fortunately, converting OSMnx-created NetworkX graphs to other graph libraries' types is relatively quick and simple and makes analysis much faster for those use cases where it's needed. For example, you might consider converting your NetworkX graph to igraph, graph-tool, or cugraph for analysis. This example demonstrates igraph.\n",
    "\n",
    "First install [igraph](https://igraph.org/python/) or run Jupyter from the [Docker container](https://hub.docker.com/r/gboeing/osmnx) (which already has it installed along with OSMnx and NetworkX).\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 operator\n",
    "\n",
    "import igraph as ig\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import osmnx as ox\n",
    "\n",
    "%matplotlib inline\n",
    "print(ox.__version__)\n",
    "print(ig.__version__)\n",
    "\n",
    "weight = \"length\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Construct graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create networkx graph\n",
    "G_nx = ox.graph_from_place(\"Piedmont, CA, USA\", network_type=\"drive\")\n",
    "osmids = list(G_nx.nodes)\n",
    "G_nx = nx.relabel.convert_node_labels_to_integers(G_nx)\n",
    "\n",
    "# give each node its original osmid as attribute since we relabeled them\n",
    "osmid_values = {k: v for k, v in zip(G_nx.nodes, osmids)}\n",
    "nx.set_node_attributes(G_nx, osmid_values, \"osmid\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "# convert networkx graph to igraph\n",
    "G_ig = ig.Graph(directed=True)\n",
    "G_ig.add_vertices(G_nx.nodes)\n",
    "G_ig.add_edges(G_nx.edges())\n",
    "G_ig.vs[\"osmid\"] = osmids\n",
    "G_ig.es[weight] = list(nx.get_edge_attributes(G_nx, weight).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert len(G_nx.nodes()) == G_ig.vcount()\n",
    "assert len(G_nx.edges()) == G_ig.ecount()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "source = list(G_nx.nodes())[0]\n",
    "target = list(G_nx.nodes())[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "path1 = G_ig.get_shortest_paths(v=source, to=target, weights=weight)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "path2 = nx.shortest_path(G_nx, source, target, weight=weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert path1 == path2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "path_length1 = G_ig.shortest_paths(source=source, target=target, weights=weight)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "path_length2 = nx.shortest_path_length(G_nx, source, target, weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert path_length1 == path_length2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centrality analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "closeness1 = G_ig.closeness(vertices=None, mode=\"ALL\", cutoff=None, weights=weight, normalized=True)\n",
    "max_closeness1 = np.argmax(closeness1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "closeness2 = nx.closeness_centrality(G_nx, distance=weight, wf_improved=True)\n",
    "max_closeness2 = max(closeness2.items(), key=operator.itemgetter(1))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# confirm same node has max closeness in both graphs\n",
    "assert G_nx.nodes[max_closeness2][\"osmid\"] == G_ig.vs[max_closeness1][\"osmid\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}