{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "469e4bb7",
   "metadata": {},
   "source": [
    "# Road networks: a starting point\n",
    "\n",
    "This notebook contains the Python code to load the driving network of **Pisa, Italy**, inspect its edges, and choose weights for route calculations. It can be easily adapted to other cities and locations around the world. \n",
    "\n",
    "For dealing with graphs we use **NetworkX** for graphs and we rely on **Matplotlib** for drawing the simple map. Make sure that the package `networkx matplotlib osmnx jupyterlab` are installed in your Python environment before opening the notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ca3a9fa",
   "metadata": {},
   "source": [
    "## 1. Import the libraries\n",
    "\n",
    "`Path` and `math` belong to the Python standard library. The conventional alias `nx` makes NetworkX calls easy to recognize (it is a similar idea to using `np` for numpy or `plt` for `matplotlib.pyplot`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0d01871",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "import math\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "print(\"NetworkX version:\", nx.__version__)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3da5de58",
   "metadata": {},
   "source": [
    "## 2. Load the Pisa network\n",
    "\n",
    "The GraphML file stores a **directed multigraph**: nodes represent intersections or road endpoints, edges represent road segments, and parallel edges may connect the same ordered pair of nodes. Edge directions encode permitted driving directions in this dataset. An edge is identified by `(u, v, key)`. Note that this is slightly more general with respect to graphs that we discussed during the lectures, but in practice we expect the network to be a graph, or to be easily converted into one. \n",
    "\n",
    "In this OSMnx-exported file, numeric attributes are stored as strings, so we explicitly convert the coordinates, lengths (metres), and existing travel-time estimates (seconds). Other OpenStreetMap attributes remain in their raw serialized form. These can be used to define weights for the edges.\n",
    "\n",
    "If the cache is absent, we query the same 2.5 km bounding box as the course notebooks and estimate travel times before saving. OpenStreetMap changes over time, so fresh downloads may differ from previous caches. Retain the saved file for reproducibility. See the [OSMnx documentation](https://osmnx.readthedocs.io/en/stable/user-reference.html) for the download and caching functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5189450",
   "metadata": {},
   "outputs": [],
   "source": [
    "data_path = Path(\"data/pisa_drive.graphml\")\n",
    "if not data_path.is_file():\n",
    "    import osmnx as ox  # Needed only when the local dataset is missing.\n",
    "\n",
    "    print(\"Downloading the Pisa driving network from OpenStreetMap...\")\n",
    "    downloaded = ox.graph.graph_from_point(\n",
    "        (43.714485, 10.405618),  # central Pisa: latitude, longitude\n",
    "        dist=2500,             # bounding-box distance in metres\n",
    "        network_type=\"drive\", simplify=True, retain_all=False,\n",
    "    )\n",
    "    # Match the speed assumptions used in the course dataset.\n",
    "    highway_speeds = {\n",
    "        \"motorway\": 110, \"motorway_link\": 70,\n",
    "        \"trunk\": 90, \"trunk_link\": 60,\n",
    "        \"primary\": 60, \"primary_link\": 45,\n",
    "        \"secondary\": 50, \"secondary_link\": 40,\n",
    "        \"tertiary\": 40, \"tertiary_link\": 35,\n",
    "        \"residential\": 30, \"living_street\": 20,\n",
    "        \"service\": 20, \"unclassified\": 30,\n",
    "    }\n",
    "    downloaded = ox.routing.add_edge_speeds(\n",
    "        downloaded, hwy_speeds=highway_speeds, fallback=30,\n",
    "    )\n",
    "    downloaded = ox.routing.add_edge_travel_times(downloaded)\n",
    "    data_path.parent.mkdir(parents=True, exist_ok=True)\n",
    "    ox.io.save_graphml(downloaded, filepath=data_path)\n",
    "    print(f\"Saved network to {data_path}\")\n",
    "else:\n",
    "    print(f\"Loading cached network from {data_path}\")\n",
    "\n",
    "G = nx.read_graphml(data_path, node_type=int, force_multigraph=True)\n",
    "assert G.is_directed() and G.is_multigraph()\n",
    "\n",
    "for node, attributes in G.nodes(data=True):\n",
    "    attributes[\"x\"] = float(attributes[\"x\"])  # longitude\n",
    "    attributes[\"y\"] = float(attributes[\"y\"])  # latitude\n",
    "\n",
    "for u, v, key, attributes in G.edges(keys=True, data=True):\n",
    "    for name in (\"length\", \"travel_time\"):\n",
    "        attributes[name] = float(attributes[name])\n",
    "        assert math.isfinite(attributes[name]) and attributes[name] > 0\n",
    "\n",
    "print(type(G).__name__)\n",
    "print(f\"{G.number_of_nodes():,} nodes; {G.number_of_edges():,} directed edges\")\n",
    "u, v, key = next(iter(G.edges(keys=True)))\n",
    "print(\"Example edge:\", (u, v, key))\n",
    "print({name: G[u][v][key].get(name) for name in\n",
    "       (\"name\", \"highway\", \"length\", \"travel_time\")})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "83e112cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# A quick geographical sketch using node coordinates.\n",
    "# Segments are drawn straight between endpoints; curved road geometry is omitted.\n",
    "positions = {node: (a[\"x\"], a[\"y\"]) for node, a in G.nodes(data=True)}\n",
    "fig, ax = plt.subplots(figsize=(8, 8))\n",
    "nx.draw_networkx_edges(G, positions, ax=ax, arrows=False,\n",
    "                       width=0.4, edge_color=\"gray\")\n",
    "ax.set(title=\"Pisa driving network\", xlabel=\"Longitude (degrees)\",\n",
    "       ylabel=\"Latitude (degrees)\")\n",
    "latitude = sum(a[\"y\"] for _, a in G.nodes(data=True)) / G.number_of_nodes()\n",
    "ax.set_aspect(1 / math.cos(math.radians(latitude)))\n",
    "ax.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "425cead0",
   "metadata": {},
   "source": [
    "## 3. Set edge weights\n",
    "\n",
    "For shortest paths, a weight is an **additive cost**: a smaller sum is preferable. NetworkX does not require a special attribute named `weight`; we select the attribute when calling an algorithm.\n",
    "\n",
    "Here are three choices:\n",
    "\n",
    "- `hops`: assign 1 to every edge, so the cost counts road segments.\n",
    "- `length`: use the existing segment length in metres.\n",
    "- `model_time_s`: compute a travel time in seconds from length and an assigned speed, using $t=\\ell/(v/3.6)$ when $v$ is in km/h.\n",
    "\n",
    "The uniform speed below is an assumption. The existing `travel_time` attribute is a separate cached estimate, not a measured journey time. A uniform speed gives the same optimal routes as distance; varying the speeds can change them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00df70a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set a constant attribute on all edges.\n",
    "nx.set_edge_attributes(G, 1.0, \"hops\")\n",
    "\n",
    "# Set attributes edge by edge. Edit this assumption for a different model.\n",
    "assumed_speed_kph = 30.0\n",
    "assert assumed_speed_kph > 0\n",
    "for u, v, key, attributes in G.edges(keys=True, data=True):\n",
    "    attributes[\"model_speed_kph\"] = assumed_speed_kph\n",
    "    attributes[\"model_time_s\"] = attributes[\"length\"] / (assumed_speed_kph / 3.6)\n",
    "\n",
    "print(G[u][v][key])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc1f4f30",
   "metadata": {},
   "source": [
    "We can also change one specific directed edge. We use a copy so that rerunning this example leaves the baseline graph unchanged. The reverse direction and other parallel edges keep their own weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fe4fd5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_slow = G.copy()\n",
    "u, v, key = next(iter(G_slow.edges(keys=True)))\n",
    "edge = G_slow[u][v][key]\n",
    "edge[\"model_speed_kph\"] = 10.0\n",
    "edge[\"model_time_s\"] = edge[\"length\"] / (edge[\"model_speed_kph\"] / 3.6)\n",
    "print(f\"Edge {(u, v, key)}: \"\n",
    "      f\"{G[u][v][key]['model_time_s']:.1f} s before, \"\n",
    "      f\"{edge['model_time_s']:.1f} s after\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3d43221",
   "metadata": {},
   "source": [
    "## 4. Use the weights in shortest-path calculations\n",
    "\n",
    "We choose two distinct nodes from the largest strongly connected component, so a directed route exists between them. This selection does not remove any edges from `G`.\n",
    "\n",
    "For a multigraph, NetworkX uses the **minimum cost among parallel edges** for each step. A returned path lists nodes; it does not specify the chosen edge keys. `weight=None` counts edges, just like our explicit `hops` weights. If a named attribute is missing, NetworkX normally treats its weight as 1; we check all weights to avoid silently mixing units."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc1184b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "weight_names = (\"hops\", \"length\", \"model_time_s\", \"travel_time\")\n",
    "for _, _, _, attributes in G.edges(keys=True, data=True):\n",
    "    assert all(name in attributes and math.isfinite(attributes[name])\n",
    "               and attributes[name] > 0 for name in weight_names)\n",
    "\n",
    "component = max(nx.strongly_connected_components(G), key=len)\n",
    "source = min(component, key=lambda node: (G.nodes[node][\"x\"], node))\n",
    "target = max(component, key=lambda node: (G.nodes[node][\"x\"], node))\n",
    "assert source != target\n",
    "print(\"Source:\", source, \"Target:\", target)\n",
    "\n",
    "routes = {}\n",
    "for weight, unit in [(\"hops\", \"segments\"), (\"length\", \"m\"),\n",
    "                     (\"model_time_s\", \"s\"), (\"travel_time\", \"s\")]:\n",
    "    path = nx.shortest_path(G, source, target, weight=weight)\n",
    "    cost = nx.shortest_path_length(G, source, target, weight=weight)\n",
    "    routes[weight] = path\n",
    "    print(f\"{weight:16s}: {cost:9.2f} {unit}, {len(path) - 1} segments\")\n",
    "\n",
    "assert nx.shortest_path_length(G, source, target, weight=None) == \\\n",
    "       nx.shortest_path_length(G, source, target, weight=\"hops\")\n",
    "assert math.isclose(\n",
    "    nx.shortest_path_length(G, source, target, weight=\"model_time_s\"),\n",
    "    nx.shortest_path_length(G, source, target, weight=\"length\") / (assumed_speed_kph / 3.6),\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46700b27",
   "metadata": {},
   "source": [
    "### Continue by yourself\n",
    "\n",
    "1. Try to compute centrality measures for node and/or edges, using one or more that we have met in the course.\n",
    "2. Use the centrality measure to assess the impact of removing (or closing) a road. \n",
    "3. Produce a detailed report for your results.\n",
    "\n",
    "The exact assignment is left relatively vague in order for you to have some flexibility. A few examples of interesting questions could be:\n",
    "\n",
    " * What if we make a portion of Pisa pedestrian-only? Would that impact travel times?\n",
    " * Is closing a specific road going to impact strongly on the traffic?\n",
    " * Can you suggest improvements for the general road networks of Pisa?\n",
    " * What is the impact for these measure in choosing different weights? What do you think is most representative?\n",
    "\n",
    "**Data attribution:** street data © [OpenStreetMap contributors](https://www.openstreetmap.org/copyright), available under the Open Database License (ODbL). This notebook uses the course's cached Pisa driving-network extract."
   ]
  }
 ],
 "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.14.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
