12.1- TP - Graphes

Ce TP a pour but de vous faire travailler les implémentations de structure de données, et les parcours de graphe.

Commencez par exécuter la cellule suivante :

Python

code masqué : pas besoin de le lire pour suivre, exécutez-le simplement

I. Graphes non pondérés

Les dictionnaires en python

Dans le cours sur les graphes, on manipule souvent des dictionnaires. Ce sont une structure qui permet d'associer des "clés" (souvent des chaines de caractère) à des "valeurs".

On les créé avec des accolades :

d = {
    "clé": "valeur",
    "une autre clé": ["les", "valeurs", "peuvent", "être", "n'importe", "quel", "type"], 
    "jamais deux sans trois": 3
}

Les dictionnaires permettent d'accéder facilement à la valeur correspondant à une clé :

d["clé"] #renvoie "valeur"

Mais aussi de modifier la valeur associée à une clé, ou d'insérer un nouveau couple (clé, valeur) :

d["clé"] = "nouvelle valeur"
d["nouvelle clé"] = [1, 2, 3]

Dans cet exemple, lorsque la clé existe, la valeur est remplacée, et lorsqu'elle n'existe pas, elle est créée.

Enfin, on peut faire une boucle for sur les dictionnaires de la manière suivante :

for cle in d:
    #faire quelque chose avec les éléments

cle prend ici successivement la valeurs de toutes les clés du dictionnaire, dans un ordre arbitraire.

I.1. Préliminaires sur les graphes

On considère des graphes non-orientés. Les noeuds sont étiquetés par des chaines de caractères.

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

Question 1

Quel type python correspondrait à une telle représentation ici ?

Et non, car on étiquette les noeuds par des chaines de caractères. Ca aurait été la cas si on avait eu des noeuds entiers consécutifs.

Non plus !

C'est ça ! Le dictionnaire associe à chaque noeud la liste de ses voisins.

Ca fait beaucoup de dictionnaires là non ?

Question 2

Déclarer une variable graphe_1 contenant le graphe suivant, qui représente les liaisons ferroviaires entre les villes.

Python

Loading editor...

graphe_1 = {"Caen": ["Paris", "Rennes"],
         "Paris": ["Caen", "Rennes","Lille"], 
         "Rennes": ["Caen", "Paris"], 
         "Lille": ["Paris"]}

Afficher un graphe

On vous fournit une fonction pour afficher un graphe : afficher_graphe(graphe). Le graphe est dessiné sous la cellule, une fois son exécution terminée.

On peut aussi colorer en rouge certains sommets ou arêtes : afficher_graphe(graphe, sommets_rouges=["Caen"], aretes_rouges=[("Caen", "Paris")]).

Question 3

Affichez le graphe ci-dessus. Est-ce le même ?

Python

Loading editor...

Question 4

Ce graphe est-il connexe ?

Python

Loading editor...

Question 5

On vous donne cette fois un nouveau graphe, représentant le réseau ferrovière nord-américain. Affichez-le. Est-il connexe ?

Python

Loading editor...

graphe_2 = {"New York": ["Washington", "Montreal"], 
           "Anchorage": ["Fairbanks"], 
           "Washington": ["New York", "Chicago"], 
           "Chicago": ["Los Angeles", "Washington", "Montreal", "Seattle"], 
           "Los Angeles": ["Chicago", "Seattle"], 
           "Fairbanks": ["Anchorage"], 
           "Seattle": ["Los Angeles", "Chicago", "Vancouver"], 
           "Vancouver": ["Seattle", "Montreal"], 
           "Montreal": ["Vancouver", "New York", "Chicago"]}

Python

Loading editor...

I.2. Détecter si un graphe est connexe

On aimerais désormais écrire une fonction pour déterminer si un graphe est connexe, ou non.

Pour cela, on va partir d'un sommet, puis suivre les arrêtes tant que c'est possible. Si on arrive à atteindre tous les sommets depuis notre sommet initial, c'est que le graphe est connexe.

Q6

Compléter la fonction suivante, en remplacant les ... par du code faisant ce que le commentaire indique. Que fait cette fonction ?

Cette fonction parcours le graphe en suivant les arrêtes, en notant tous les sommets qu'elle parcours.

Python

Loading editor...

def parcours(g, s, deja_vu):
    """g est un graphe, s est un sommet, deja_vu est un dictionnaire de sommets vers des booléens"""
    
    # si le sommet s est à vrai dans deja_vu, renvoyer sans rien faire
    
    ...
    
    # sinon, ajouter le sommet s à deja_vu avec la valeur `True`
    
    ...
    
    # parcourir tous les voisins de s
    
    ...
    
        # pour chaque voisin v, appelez parcours(g, v, deja_vu)
        
        ...

Q7

On veut désormais tester si le graphe est connexe en utilisant la fonction parcours. Pour cela, on va l'appeler avec s un sommet quelconque et deja_vu le dictionnaire vide, puis simplement compter le nombre d'éléments dans deja_vu : si il y en a le même nombre que dans le graphe, c'est que celui-ci est connexe.

Vous pouvez prendre un objet quelconque d'un dictionnaire avec next(iter(g)).

Ecrivez une fonction est_connexe(g) revoyant True si le graphe est connexe, False sinon.

Python

Loading editor...

Visualiser le parcours

Le dictionnaire deja_vu retient ses clés dans l'ordre où elles ont été ajoutées : list(deja_vu) donne donc l'ordre dans lequel votre fonction parcours a visité les sommets.

La fonction animer_parcours(graphe, ordre) affiche le graphe, et allume les sommets un par un dans l'ordre donné. Essayez-la une fois votre fonction parcours terminée :

Python

Loading editor...

deja_vu = {}
parcours(graphe_2, "Chicago", deja_vu)
animer_parcours(graphe_2, list(deja_vu))

Q8

Testez votre fonction sur les deux exemples précédents.

Python

Loading editor...

II. Un graphe réel

On va maintenant s'intérésser à un vrai graphe de la vie réelle.

Vous avez à disposition dans ce TP une base de donnée de tronçons de chemin de fer de Normandie.

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 !

Q9

Executez le code suivant (sans tenter de le comprendre), et affichez la variable donnees. Que contient-elle ?

Python

Loading editor...

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

res = cur.execute("SELECT depart, arrivee FROM Lignes")

donnees = res.fetchall()

Python

Loading editor...

Question 10

Écrivez une fonction pour convertir cette liste en un graphe au format de la première partie. Attention à bien placer les arrêtes dans les deux sens !

Vous pouvez ensuite afficher le graphe.

Python

Loading editor...

Question 11

Le réseau ferré normand est-il connexe ?

Python

Loading editor...

Question 12

Quel est le degrés moyen des sommets du graphe ? Et le degrés maximum ?

Python

Loading editor...

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

Code d'accès