![\"CSC](\"https://img.shields.io/badge/launch-CSC%20notebook-blue.svg\"){kind=icon}
\n",
"\n",
"Others can follow the lesson interactively using Binder. Check the rocket icon on the top of this page.\n",
"```\n",
"\n",
"**Lesson objectives**\n",
"\n",
"This tutorial focuses on **spatial networks** and learn how to construct a routable **directed** graph for Networkx and find shortest paths along the given street network based on travel times or distance by car. In addition, we will learn how to calculate travel times from a single source into all nodes in the graph. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Tutorial\n",
"\n",
"In this tutorial we will focus on a network analysis methods that relate to way-finding.\n",
"Finding a shortest path from A to B using a specific street network is a very common spatial analytics\n",
"problem that has many practical applications.\n",
"\n",
"Python provides easy to use tools for conducting spatial network analysis.\n",
"One of the easiest ways to start is to use a library\n",
"called [Networkx](https://networkx.github.io/documentation/stable/)\n",
"which is a Python module that provides a lot tools that can be used to\n",
"analyze networks on various different ways. It also contains algorithms\n",
"such as [Dijkstra’s\n",
"algorithm](https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html#networkx.algorithms.shortest_paths.weighted.single_source_dijkstra)\n",
"or [A\\*](https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.astar.astar_path.html#networkx.algorithms.shortest_paths.astar.astar_path)\n",
"algoritm that are commonly used to find shortest paths along\n",
"transportation network.\n",
"\n",
"Next, we will learn how to do spatial network analysis in practice."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Typical workflow for routing\n",
"\n",
"If you want to conduct network analysis (in any programming language) there are a few basic steps that typically needs to be done before you can start routing. These steps are:\n",
"\n",
" 1. **Retrieve data** (such as street network from OSM or Digiroad + possibly transit data if routing with PT).\n",
" 2. **Modify the network** by adding/calculating edge weights (such as travel times based on speed limit and length of the road segment).\n",
" 3. **Build a routable graph** for the routing tool that you are using (e.g. for NetworkX, igraph or OpenTripPlanner).\n",
" 4. **Conduct network analysis** (such as shortest path analysis) with the routing tool of your choice. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 1. Retrieve data\n",
"\n",
"As a first step, we need to obtain data for routing. [Pyrosm](https://pyrosm.readthedocs.io/en/latest/) library makes it really easy to retrieve routable networks from OpenStreetMap (OSM) with different transport modes (walking, cycling and driving). \n",
"\n",
"- Let's first extract OSM data for Helsinki that are walkable. In `pyrosm`, we can use a function called `osm.get_network()` which retrieves data from OpenStreetMap. It is possible to specify what kind of roads should be retrieved from OSM with `network_type` -parameter (supports `walking`, `cycling`, `driving`). \n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"| \n", " | access | \n", "area | \n", "bicycle | \n", "bridge | \n", "cycleway | \n", "foot | \n", "footway | \n", "highway | \n", "int_ref | \n", "lanes | \n", "... | \n", "surface | \n", "tunnel | \n", "width | \n", "id | \n", "timestamp | \n", "version | \n", "tags | \n", "osm_type | \n", "geometry | \n", "length | \n", "
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "unclassified | \n", "None | \n", "2 | \n", "... | \n", "paved | \n", "None | \n", "None | \n", "4236349 | \n", "1380031970 | \n", "21 | \n", "{\"name:fi\":\"Erottajankatu\",\"name:sv\":\"Skillnad... | \n", "way | \n", "MULTILINESTRING ((24.94327 60.16651, 24.94337 ... | \n", "14.0 | \n", "
| 1 | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "None | \n", "unclassified | \n", "None | \n", "2 | \n", "... | \n", "paved | \n", "None | \n", "None | \n", "4243035 | \n", "1543430213 | \n", "12 | \n", "{\"name:fi\":\"Korkeavuorenkatu\",\"name:sv\":\"H\\u00... | \n", "way | \n", "MULTILINESTRING ((24.94567 60.16767, 24.94567 ... | \n", "51.0 | \n", "
2 rows × 30 columns
\n", "| \n", " | lon | \n", "lat | \n", "tags | \n", "timestamp | \n", "version | \n", "changeset | \n", "id | \n", "geometry | \n", "
|---|---|---|---|---|---|---|---|---|
| 0 | \n", "24.943271 | \n", "60.166514 | \n", "None | \n", "1390926206 | \n", "2 | \n", "0 | \n", "1372477605 | \n", "POINT (24.94327 60.16651) | \n", "
| 1 | \n", "24.943365 | \n", "60.166444 | \n", "{'highway': 'crossing', 'crossing': 'traffic_s... | \n", "1383915357 | \n", "6 | \n", "0 | \n", "292727220 | \n", "POINT (24.94337 60.16644) | \n", "
| 2 | \n", "24.943403 | \n", "60.166408 | \n", "None | \n", "1374595731 | \n", "1 | \n", "0 | \n", "2394117042 | \n", "POINT (24.94340 60.16641) | \n", "
| 3 | \n", "24.945668 | \n", "60.167668 | \n", "{'highway': 'crossing', 'crossing': 'uncontrol... | \n", "1290714658 | \n", "5 | \n", "0 | \n", "296250563 | \n", "POINT (24.94567 60.16767) | \n", "
| 4 | \n", "24.945671 | \n", "60.167630 | \n", "{'traffic_calming': 'divider'} | \n", "1354578076 | \n", "1 | \n", "0 | \n", "2049084195 | \n", "POINT (24.94567 60.16763) | \n", "
| \n", " | geometry | \n", "u | \n", "v | \n", "length | \n", "
|---|---|---|---|---|
| 0 | \n", "LINESTRING (24.94327 60.16651, 24.94337 60.16644) | \n", "1372477605 | \n", "292727220 | \n", "9.370 | \n", "
| 1 | \n", "LINESTRING (24.94337 60.16644, 24.94340 60.16641) | \n", "292727220 | \n", "2394117042 | \n", "4.499 | \n", "
| 2 | \n", "LINESTRING (24.94567 60.16767, 24.94567 60.16763) | \n", "296250563 | \n", "2049084195 | \n", "4.174 | \n", "
| 3 | \n", "LINESTRING (24.94567 60.16763, 24.94569 60.16744) | \n", "2049084195 | \n", "60072359 | \n", "21.692 | \n", "
| 4 | \n", "LINESTRING (24.94569 60.16744, 24.94571 60.16726) | \n", "60072359 | \n", "6100704327 | \n", "19.083 | \n", "
| \n", " | maxspeed | \n", "highway | \n", "
|---|---|---|
| 30 | \n", "30 | \n", "service | \n", "
| 47 | \n", "30 | \n", "service | \n", "
| 48 | \n", "30 | \n", "service | \n", "
| 49 | \n", "30 | \n", "service | \n", "
| 50 | \n", "30 | \n", "service | \n", "
| \n", " | u | \n", "v | \n", "length | \n", "travel_time_seconds | \n", "
|---|---|---|---|---|
| 0 | \n", "1372477605 | \n", "292727220 | \n", "9.370 | \n", "1.12440 | \n", "
| 1 | \n", "292727220 | \n", "2394117042 | \n", "4.499 | \n", "0.53988 | \n", "
| 2 | \n", "296250563 | \n", "2049084195 | \n", "4.174 | \n", "0.50088 | \n", "
| 3 | \n", "2049084195 | \n", "60072359 | \n", "21.692 | \n", "2.60304 | \n", "
| 4 | \n", "60072359 | \n", "6100704327 | \n", "19.083 | \n", "2.28996 | \n", "
| 5 | \n", "6100704327 | \n", "296250223 | \n", "6.027 | \n", "0.72324 | \n", "
| 6 | \n", "264015226 | \n", "25345665 | \n", "9.644 | \n", "1.15728 | \n", "
| 7 | \n", "25345665 | \n", "296248024 | \n", "7.016 | \n", "0.84192 | \n", "
| 8 | \n", "296248024 | \n", "426911766 | \n", "4.137 | \n", "0.49644 | \n", "
| 9 | \n", "426911766 | \n", "60072364 | \n", "21.132 | \n", "2.53584 | \n", "
| \n", " | node_id | \n", "travel_time | \n", "
|---|---|---|
| 0 | \n", "6.599985e+08 | \n", "0.00000 | \n", "
| 1 | \n", "3.236097e+09 | \n", "7.62948 | \n", "
| 2 | \n", "3.236097e+09 | \n", "10.28592 | \n", "
| 3 | \n", "2.960448e+08 | \n", "11.32884 | \n", "
| 4 | \n", "3.236097e+09 | \n", "11.90532 | \n", "
| \n", " | lon | \n", "lat | \n", "tags | \n", "timestamp | \n", "version | \n", "changeset | \n", "id | \n", "geometry | \n", "
|---|---|---|---|---|---|---|---|---|
| 1372477605 | \n", "24.943271 | \n", "60.166514 | \n", "None | \n", "1390926206 | \n", "2 | \n", "0 | \n", "1372477605 | \n", "POINT (24.94327 60.16651) | \n", "
| 292727220 | \n", "24.943365 | \n", "60.166444 | \n", "{'highway': 'crossing', 'crossing': 'traffic_s... | \n", "1383915357 | \n", "6 | \n", "0 | \n", "292727220 | \n", "POINT (24.94337 60.16644) | \n", "
| 2394117042 | \n", "24.943403 | \n", "60.166408 | \n", "None | \n", "1374595731 | \n", "1 | \n", "0 | \n", "2394117042 | \n", "POINT (24.94340 60.16641) | \n", "
| 296250563 | \n", "24.945668 | \n", "60.167668 | \n", "{'highway': 'crossing', 'crossing': 'uncontrol... | \n", "1290714658 | \n", "5 | \n", "0 | \n", "296250563 | \n", "POINT (24.94567 60.16767) | \n", "
| 2049084195 | \n", "24.945671 | \n", "60.167630 | \n", "{'traffic_calming': 'divider'} | \n", "1354578076 | \n", "1 | \n", "0 | \n", "2049084195 | \n", "POINT (24.94567 60.16763) | \n", "
| \n", " | lon | \n", "lat | \n", "tags | \n", "timestamp | \n", "version | \n", "changeset | \n", "id | \n", "geometry | \n", "node_id | \n", "travel_time | \n", "
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | \n", "24.943271 | \n", "60.166514 | \n", "None | \n", "1390926206 | \n", "2 | \n", "0 | \n", "1372477605 | \n", "POINT (24.94327 60.16651) | \n", "1.372478e+09 | \n", "79.60704 | \n", "
| 1 | \n", "24.943365 | \n", "60.166444 | \n", "{'highway': 'crossing', 'crossing': 'traffic_s... | \n", "1383915357 | \n", "6 | \n", "0 | \n", "292727220 | \n", "POINT (24.94337 60.16644) | \n", "2.927272e+08 | \n", "80.73144 | \n", "
| 2 | \n", "24.943403 | \n", "60.166408 | \n", "None | \n", "1374595731 | \n", "1 | \n", "0 | \n", "2394117042 | \n", "POINT (24.94340 60.16641) | \n", "2.394117e+09 | \n", "81.27132 | \n", "
| 3 | \n", "24.945668 | \n", "60.167668 | \n", "{'highway': 'crossing', 'crossing': 'uncontrol... | \n", "1290714658 | \n", "5 | \n", "0 | \n", "296250563 | \n", "POINT (24.94567 60.16767) | \n", "2.962506e+08 | \n", "103.99572 | \n", "
| 4 | \n", "24.945671 | \n", "60.167630 | \n", "{'traffic_calming': 'divider'} | \n", "1354578076 | \n", "1 | \n", "0 | \n", "2049084195 | \n", "POINT (24.94567 60.16763) | \n", "2.049084e+09 | \n", "103.49484 | \n", "