Ce TP a pour but de vous faire travailler les parcours de graphe. Il commence par une partie "préliminaire" sur l'implémentation et quelques questions classiques, puis enchaine sur un problème d'application à des données réelles.

Commencez par exécuter la cellule suivante :

I. Préliminaires

On considère des graphes simples, non-orientés, et pondérés. Les noeuds sont étiquetés par des chaines de caractères, et les arrêtes par des flottants.

On choisi pour représenter les graphes une représentation en "liste d'adjacence".

graphe = {"Caen": [("Paris", 1.5), ("Rennes", 1.)],
         "Paris": [("Caen", 1.5), ("Rennes", 1.5), ("Lille", 1.)], 
         "Rennes": [("Caen", 1.), ("Paris", 1.5)], 
         "Lille": [("Paris", 1.)]}

II. Un graphe secret ?

Un graphe secret (simple, non pondéré, non orienté) (astucieusement nommé graphe_secret) s'est caché dans votre TP. Votre objectif ? Décoder les messages cachés à l'intérieur à l'aide de parcours de graphe.

def parcours_profondeur(G, d, deja_vu):
    """"""
    operation_secrete(d)
    for voisin in #à compléter:
        if voisin not in deja_vu:
            deja_vu[voisin] = True
            # à compléter
            return

deja_vu = {"": True}
# à compléter

from collections import deque

def parcours_largeur(G, d):
    file = deque()
    file.appendleft #à compléter
    deja_vu = {d: True}
    while #à compléter
        operation_secrete(x)
        x = file #à compléter
        for voisin in G[x]:
            if voisin not in deja_vu:
                file.appendleft(voisin)
                #Evite d'ajouter les mêmes sommets à la pile plusieurs fois
                #à compléter
                
#à compléter

III. Un graphe réel

On va maintenant s'intéresser à un vrai graphe de la vie réelle. Mais d'abord, un peu de SQL !

Vous avez à disposition dans ce TP une base de donnée de tronçons de chemin de fer de Normandie. Les attributs de la table Lignes sont les suivants :

• depart la ville de départ
• arrivee la ville d'arrivée
• longueur la longueur du tronçon (en mètres)

A noter, pour les longueur des tronçons, qu'on ne compte que les rails et les gares qui sont effectivement en Normandie. Par exemple, la ville de Paris apparait avec des distances peu réalistes : c'est parce que on compte les rails jusqu'au changement de région, et plus après.

Pour accéder aux données en python, on va utiliser le module sqlite3.

Vous n'avez pas besoin de vous préoccuper de la syntaxe précise !

import sqlite3
con = sqlite3.connect("TrainNormandie.db")
cur = con.cursor()

res = cur.execute("Votre requète SQL ici")

donnees = res.fetchall()

Vous disposez maintenant d'une liste donnees, contenant des triplets (ville de départ, ville d'arrivée, longueur).

On vous demande de répondre à toutes les questions qui suivent en écrivant une fonction permettant d'y répondre sur n'importe quel graphe.

On s'interesse maintenant au trajet avec le moins d'arrêts intermédiaires possibles. Tous les tronçons de la base de donnée sont des trajets directs, sans arrêts.

Quelle parcours serait adapté à résoudre ce problème ?

Code de conversion (il utilise les modules pandas et geopandas, et ne fonctionne pas dans le navigateur) :

import pandas as pd
import geopandas as gpd

#lis le ficher de géométrie dbf avec geopandas
gdf = gpd.read_file("nom_du_fichier.dbf")
#créé une nouvelle colonne longueur, qui prend la longueur de chaque ligne
gdf["LONGUEUR"] = gdf["geometry"].map(lambda x: x.length)
#supprime les colonnes inutiles
gdf = gdf[["DEPART", "ARRIVEE", "LONGUEUR"]]

#créé la base de donnée
from sqlalchemy import create_engine
engine = create_engine('sqlite:///TrainNormandie.db', echo=False)
#sauvegarde la table dans la base de donnée
gdf.to_sql(name='Lignes', con=engine)

À noter que, de base, la colonne geometry contient les coordonnées géographiques d'une ligne.

Entrez le code donné en cours pour accéder à la solution :