TP : Plus court chemin sur un graphe de OpenStreetMap

OpenStreetMap est un projet collaboratif de cartographie en ligne qui vise à constituer une base de données géographiques libre du monde. Nous allons y accéder via Python avec le module osmnx :

In [1]:

try:
    __import__("cpge")
except ImportError:
    ! pip install git+https://github.com/fortierq/itc-code &> /dev/null
try:
    __import__("osmnx")
except ImportError:
    ! pip install osmnx
import osmnx as ox
import urllib
from cpge import PriorityQueue

try: __import__("cpge") except ImportError: ! pip install git+https://github.com/fortierq/itc-code &> /dev/null try: __import__("osmnx") except ImportError: ! pip install osmnx import osmnx as ox import urllib from cpge import PriorityQueue

Vous pouvez voir d'autres exemples d'utilisation de OpenStreeMap ici.

Par exemple, voici le graphe du réseau routier à proximité du lycée Fénelon Sainte-Marie :

In [2]:

url = "https://raw.githubusercontent.com/fortierq/itc1/master/files/5_graph/tp/tp8/fsm.xml"
xml = urllib.request.urlretrieve(url, "fsm.xml")
G = ox.load_graphml("fsm.xml")
ox.plot_graph_folium(G)

url = "https://raw.githubusercontent.com/fortierq/itc1/master/files/5_graph/tp/tp8/fsm.xml" xml = urllib.request.urlretrieve(url, "fsm.xml") G = ox.load_graphml("fsm.xml") ox.plot_graph_folium(G)

Out[2]:

Make this Notebook Trusted to load map: File -> Trust Notebook

On peut récupérer les sommets (intersections) et les arêtes (routes, places...) du graphe :

In [3]:

nodes, edges = ox.graph_to_gdfs(G)

nodes, edges = ox.graph_to_gdfs(G)

In [4]:

nodes # sommets

nodes # sommets

Out[4]:

	y	x	highway	street_count	geometry
osmid
361116	48.883689	2.327561	traffic_signals	3	POINT (2.32756 48.88369)
361117	48.884690	2.329535	NaN	6	POINT (2.32954 48.88469)
361120	48.885781	2.328834	NaN	3	POINT (2.32883 48.88578)
367915	48.887350	2.314122	traffic_signals	5	POINT (2.31412 48.88735)
367917	48.882206	2.320349	traffic_signals	4	POINT (2.32035 48.88221)
...	...	...	...	...	...
9063641369	48.874462	2.321820	NaN	3	POINT (2.32182 48.87446)
9192953454	48.887148	2.313344	NaN	3	POINT (2.31334 48.88715)
9192953456	48.887104	2.312963	NaN	1	POINT (2.31296 48.88710)
9274896492	48.876382	2.325348	NaN	1	POINT (2.32535 48.87638)
9738056575	48.887489	2.304480	NaN	3	POINT (2.30448 48.88749)

736 rows × 5 columns

Chaque sommet possède un identifiant osmid.

In [5]:

edges # arêtes

edges # arêtes

Out[5]:

			osmid	oneway	name	highway	maxspeed	junction	reversed	length	lanes	geometry	service	access	bridge	tunnel	width
u	v	key
361116	5291668659	0	83537403	True	Place de Clichy	primary	30	circular	False	14.775	NaN	LINESTRING (2.32756 48.88369, 2.32736 48.88367)	NaN	NaN	NaN	NaN	NaN
361117	3999929421	0	554961489	True	Boulevard de Clichy	primary	30	NaN	False	26.195	3	LINESTRING (2.32954 48.88469, 2.32924 48.88455)	NaN	NaN	NaN	NaN	NaN
	272678705	0	4039108	True	Rue Forest	residential	30	NaN	False	77.962	NaN	LINESTRING (2.32954 48.88469, 2.32949 48.88476...	NaN	NaN	NaN	NaN	NaN
361120	94243625	0	25061779	True	Rue Cavallotti	residential	30	NaN	False	76.496	NaN	LINESTRING (2.32883 48.88578, 2.32876 48.88583...	NaN	NaN	NaN	NaN	NaN
367915	27234740	0	24027082	False	Rue de Rome	secondary	30	NaN	False	275.325	2	LINESTRING (2.31412 48.88735, 2.31426 48.88730...	NaN	NaN	NaN	NaN	NaN
...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...
9192953454	2722937422	0	378989486	False	Rue Jouffroy d'Abbans	residential	30	NaN	False	33.667	NaN	LINESTRING (2.31334 48.88715, 2.31363 48.88724...	NaN	NaN	NaN	NaN	NaN
	27234414	0	378989486	False	Rue Jouffroy d'Abbans	residential	30	NaN	True	58.011	NaN	LINESTRING (2.31334 48.88715, 2.31307 48.88706...	NaN	NaN	NaN	NaN	NaN
9192953456	9192953454	0	995537801	True	NaN	service	NaN	NaN	False	29.786	NaN	LINESTRING (2.31296 48.88710, 2.31317 48.88717...	NaN	NaN	NaN	NaN	NaN
9274896492	5291826748	0	402688448	True	Parking Saint-Lazare	service	NaN	NaN	False	135.814	1	LINESTRING (2.32535 48.87638, 2.32530 48.87643...	driveway	NaN	NaN	yes	NaN
9738056575	1987578932	0	678797229	True	Place de Wagram	primary	30	circular	False	41.701	NaN	LINESTRING (2.30448 48.88749, 2.30444 48.88743...	NaN	NaN	NaN	NaN	NaN

1413 rows × 15 columns

On voit par exemple que la place de Clichy est de longueur (length) 14.775m, entre les sommets 361116 et 5291668659 :

In [6]:

nodes.query("osmid == 361116") # sommet dont le osmid est 361116

nodes.query("osmid == 361116") # sommet dont le osmid est 361116

Out[6]:

	y	x	highway	street_count	geometry
osmid
361116	48.883689	2.327561	traffic_signals	3	POINT (2.32756 48.88369)

On peut accéder à une arête avec son index, qui va de $0$ jusqu'à $n - 1$, où $n$ est le nombre d'arêtes :

In [7]:

edges.iloc[0]

edges.iloc[0]

Out[7]:

osmid                                                83537403
oneway                                                   True
name                                          Place de Clichy
highway                                               primary
maxspeed                                                   30
junction                                             circular
reversed                                                False
length                                                 14.775
lanes                                                     NaN
geometry    LINESTRING (2.3275607 48.8836894, 2.3273618 48...
service                                                   NaN
access                                                    NaN
bridge                                                    NaN
tunnel                                                    NaN
width                                                     NaN
Name: (361116, 5291668659, 0), dtype: object

On peut alors accéder à sa longueur avec length :

In [8]:

e = edges.iloc[0]
e["length"]

e = edges.iloc[0] e["length"]

Out[8]:

14.775

Exercice

Écrire l'algorithme de Dijkstra en l'adaptant au graphe G ci-dessus.
En déduire la longueur d'un plus court chemin pour aller de Fénelon Sainte-Marie (sommet d'identifiant 27234946 et de coordonnées GPS (48.879371, 2.317216)) à la gare Saint-Lazare (sommet d'identifiant 5291826748).