{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0",
   "metadata": {},
   "source": [
    "# Usage | 2. Network growth\n",
    "This notebook explains how growbikenet orders the edges and why this is important.  \n",
    "Parameters covered: `ranking`, `allow_edge_overlaps`, `crs_projected`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "447684fb-19c9-4d8b-b4f9-5f4247f1f43b",
   "metadata": {},
   "source": [
    "We start every Usage notebook with the standard way of importing growbikenet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19ad27d9-710a-43ee-b206-bfad5b8c34cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import growbikenet as gbn"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "549d063b-5cb5-4489-bf94-b42ec795862a",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "We are going to work with Paris. Downloading its street network for further use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a18d560a-e8f8-4e25-8ece-20d1aa718f47",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import osmnx as ox\n",
    "g = ox.graph_from_place(\"Paris\", network_type='drive')\n",
    "ox.io.save_graph_geopackage(g.to_undirected(), \"Paris_streets.gpkg\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd95b2a6-d29d-4533-940b-086c0a10089b",
   "metadata": {},
   "source": [
    "## Ranking of edges"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "034468a1-0c17-4190-9a1f-3954cef04612",
   "metadata": {},
   "source": [
    "Growbikenet not only creates a potential bicycle network, but also a ranking of the edges. The ranking is important, as it provides an ordering, informing a city which edges to implement first to arrive at a functional network early. The ranking metric is controlled by the parameter `ranking` which is by default set to `'betweenness_centrality'`. Other options are `'closeness_centrality'` and `'random'`.\n",
    "\n",
    "We are going to generate all different rankings (saved in the dictionary `edges_ranked_all`) and visualize them interactively in the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a130a69-befc-40cb-bcba-6119b4e1a2dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked_all = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4819a861-ec8a-4809-8018-50bbca3fdba7",
   "metadata": {},
   "source": [
    "### Betweenness centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b74d1b2-8f22-4a89-b7b8-6f8c3de65ae0",
   "metadata": {},
   "source": [
    "Betweenness centrality is a network centrality measure approximating flow. By ordering edges like this, the first built edge is the one with highest expected flow of cyclists. As was shown in the research on which growbikenet is based, this is a much better ordering than random, and in most cases also better than ordering by closeness centrality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9bb09f07-1292-4215-b654-c2f9a4625b64",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked = gbn.growbikenet(\"Paris\",\n",
    "                               ranking=\"betweenness_centrality\",\n",
    "                               street_network_file=\"Paris_streets.gpkg\",)\n",
    "edges_ranked_all[\"betweenness_centrality\"] = edges_ranked"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c49012ef-e34e-4239-96af-70fdaeaac9a0",
   "metadata": {},
   "source": [
    "The content of the output `edges_ranked` shows several columns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1999e0f-e374-4cdb-88ab-bb1f9651896f",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "edges_ranked.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ded8fac-ef19-4bd9-b907-f976d7d51a2b",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "They are:  \n",
    "- **betweenness_centrality**: The metric to rank edges by.\n",
    "- **geometry**: The geometries of the edges connecting source and target seed points, projected in the coordinate references system (crs) given by the parameter `crs_projected`, rounded to meters. The coordinates correspond to the easting and northing in the crs. These geometries are typically a mix between linestrings and multilinestrings. \n",
    "- **source**, **target**: The OSM IDs of source and target seed points. These are nodes that can be looked up on OSM, for example for OSM ID 11037313412: https://www.openstreetmap.org/node/11037313412\n",
    "- **rank**: The rank which orders the edge by betweenness centrality. These are increasing integers, but not necessarily consecutive, due to potentially empty pieces in-between that are removed due to edge overlaps, see end of this notebook.\n",
    "- **length**: Length of the current edge, rounded to whole meters.\n",
    "- **length_cumulative**: Cumulative length of current and all previous edges, rounded to whole meters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2cb3bab-33d8-437a-ac83-7e92e3609ac5",
   "metadata": {},
   "source": [
    "### Closeness centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abca90fa-a00a-47a2-a6bf-fd936853d2b8",
   "metadata": {},
   "source": [
    "Ranking by closeness centrality means growing from the center."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "526474cf-0830-41a6-ba22-c3d0254a1de3",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked = gbn.growbikenet(\"Paris\",\n",
    "                               ranking=\"closeness_centrality\",\n",
    "                               street_network_file=\"Paris_streets.gpkg\",)\n",
    "edges_ranked_all[\"closeness_centrality\"] = edges_ranked"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b3d80e3-03d4-4717-bf9e-31f826441ed2",
   "metadata": {},
   "source": [
    "### Random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cc01250-d749-4b77-b144-4422db3c8b46",
   "metadata": {},
   "source": [
    "Growbikenet can also showcase suboptimal random growth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48599d7d-f7fa-4145-8534-2922fe63ef4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked = gbn.growbikenet(\"Paris\",\n",
    "                               ranking=\"random\",\n",
    "                               street_network_file=\"Paris_streets.gpkg\",)\n",
    "edges_ranked_all[\"random\"] = edges_ranked"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21d0ea2e-26bb-4d0e-b6d7-ce1d8c9fefb5",
   "metadata": {},
   "source": [
    "### Visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bffa9c4-e2e9-4b9e-ac6f-281ee33221d5",
   "metadata": {},
   "source": [
    "Below the three different growths are visualized together ineractively. Use the slider and buttons to see the different growth patterns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b2ae4d9-a97f-41fb-9163-14cadc5aba1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import ipywidgets as widgets\n",
    "import matplotlib.pyplot as plt\n",
    "step = widgets.IntSlider(\n",
    "    value=4, min=0, max=max(edges_ranked[\"rank\"]), step=1, description=\"Growth step:\", layout=widgets.Layout(width='500px')\n",
    ")\n",
    "ranking = widgets.ToggleButtons(\n",
    "    options=['betweenness_centrality', 'closeness_centrality', 'random'],\n",
    "    description='Ranking:',\n",
    ")\n",
    "def update_map(step=step, ranking=ranking):\n",
    "    fig, ax = plt.subplots(figsize=(8, 6))\n",
    "    edges_ranked_all[ranking][edges_ranked_all[ranking][\"rank\"] <= step].plot(\n",
    "        linewidth=3,\n",
    "        color=\"#096a51\",\n",
    "        ax=ax,\n",
    "    )\n",
    "    ax.set_title(f\"Paris bike net growth, growth step {step}\", fontsize=12)\n",
    "    ax.set_ylim(edges_ranked.total_bounds[1], edges_ranked.total_bounds[3])\n",
    "    ax.set_xlim(edges_ranked.total_bounds[0], edges_ranked.total_bounds[2])\n",
    "    plt.axis('off')\n",
    "    plt.show()\n",
    "\n",
    "widgets.interactive(update_map, step=step, ranking=ranking)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00c866b0-4374-4f0d-9c5f-faea4f98037e",
   "metadata": {},
   "source": [
    "## Allowing edge overlaps"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e42369d-8d0b-404c-a1c4-023f3ab02e2a",
   "metadata": {},
   "source": [
    "Considerable computing time is spent on \"Removing edge overlaps\". \n",
    "\n",
    "*What are edge overlaps?* In the abstract, unrouted network, there can be no edge overlaps in the seed network. However, when the edges are routed, there are often many such overlaps. In general, we do not want to have overlaps as they render length calculations wrong, i.e., the `length` and `length_cumulative` columns in the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf1616db-63b9-462d-8f6c-b78a0e5d6f46",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked_all[\"betweenness_centrality\"].head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65179bc4-e911-4857-bd3b-9e0547eaa63e",
   "metadata": {},
   "source": [
    "Because edge overlaps are removed by default, the lengths are correct. In particular, the total length of the grown network is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "83073098-571f-4d8d-a15f-da21c0794094",
   "metadata": {},
   "outputs": [],
   "source": [
    "int(edges_ranked_all[\"betweenness_centrality\"].length_cumulative.iloc[-1]/1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "460cd555-a563-49fe-80fa-2376a4639542",
   "metadata": {},
   "source": [
    "kilometers."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ffd5c99-4ca1-44f3-ab1c-5ada13db9803",
   "metadata": {},
   "source": [
    "Edge overlap removal also removes edges that would end up completely empty, which is the reason why the rank can show gaps. This can be seen by the difference of the following two numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "076d4cf8-c144-4c45-9438-8b6fc746701c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(len(edges_ranked_all[\"betweenness_centrality\"]),\n",
    "      max(edges_ranked_all[\"betweenness_centrality\"][\"rank\"])+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a1c999c-8eb7-41a0-a997-3351d36efd39",
   "metadata": {},
   "source": [
    "However, if we allow edge overlaps, via `allow_edge_overlaps=True`, this will make the calculation faster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "996fbfee-69d0-4798-9d6a-23c17280d780",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_ranked = gbn.growbikenet(\"Paris\",\n",
    "                               ranking=\"betweenness_centrality\",\n",
    "                               allow_edge_overlaps=True,\n",
    "                               street_network_file=\"Paris_streets.gpkg\",)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76c058f9-7244-4300-babc-c41c91594a87",
   "metadata": {},
   "source": [
    "It also leads to no rank gaps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25c7fd57-0bbb-486f-8d8e-44b053cd46e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(len(edges_ranked),\n",
    "      max(edges_ranked[\"rank\"])+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b0b56fe-e621-44c1-973d-1a5c036ce7b1",
   "metadata": {},
   "source": [
    "But it will also wrongly skew the calculated total length of the network to be much longer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "426827fc-4506-4535-9b54-97acd65677cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "int(edges_ranked.length_cumulative.iloc[-1]/1000)"
   ]
  }
 ],
 "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.12.13"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}