Chapitre 18 : Les graphes.

Introduction :

Les graphes sont des structures de données qui modélisent des relations entre des objets.

Un graphe est composé de nœuds (ou sommets) et de liens (ou arêtes) qui connectent ces nœuds. Ils sont utilisés pour représenter des réseaux, comme des chemins dans un GPS, des connexions sur les réseaux sociaux ou des dépendances dans un système.

1. Définition:

Un graphe est une structure de données qui comporte des objets appelés "sommets".

Il y a deux types de graphes :

les graphes non-orientés. Les sommets sont reliés entre eux par des arêtes n'ayant pas de sens.
les graphes orientés. Les sommets sont reliés entre eux par des arcs ayant un sens.

Les arcs ou les arêtes forment des relations entre les sommets.

Un graphe est une structure de données relationnelles.

Les sommets peuvent aussi être appelés des noeuds.

2. Définitions:

Dans un graphe non-orienté :

deux sommets sont adjacents si une arête les relie.
deux arêtes sont adjacentes si elles ont un sommet en commun.
Soit A et B deux sommets, on note A-B ou (A,B) une arête qui le relie.
une chaîne reliant deux sommets est la succession d'arêtes adjacentes reliant ces deux points.
un graphe est dit connexe si pour n'importe quelle paire de sommets, il existe une chaîne qui les relie.
un graphe est dit complet si chaque sommet est adjacent à tous les autres.
le degré d'un sommet correspond au nombre d'arêtes dont il est une extrémité.
un cycle est une chaîne ayant pour extrémités un unique sommet.

3. Exercice:

A faire dans le cahier.

On considère le graphe ci-dessous :

Citer deux sommets adjacents.
Citer deux sommets non adjacents.
Citer deux arêtes adjacentes.
Quel est le degré de Emma?
Citer un cycle initalisé en Laura.
Ce graphe est-il complet?
Citer 2 chaînes distinctes reliant Bob et Julia.

4. Degrés et adjacence dans un graphe orienté

Un graphe orienté est un ensemble de sommets reliés entre eux par des arcs ayant un sens (une direction).

Dans un tel graphe :

Le degré sortant d’un sommet est le nombre d’arcs qui partent de ce sommet.
Le degré entrant d’un sommet est le nombre d’arcs qui arrivent vers ce sommet.

Exemple :

Dans cet exemple :

A a un degré sortant de 2 et un degré entrant de 0.
J a un degré entrant de 1 et un degré sortant de 2.

Deux sommets sont adjacents s’il existe un arc qui relie l’un à l’autre.

Dans un graphe orienté, on distingue :

Adjacence sortante : un sommet A est adjacent à B s’il existe un arc A → B.
Adjacence entrante : un sommet B est adjacent à A s’il existe un arc A → B.

Si rien n'est précisé, on considérera que l'adjacence est sortante.

5. Exercice:

A faire dans le cahier.

On considérera ici que les adjacences sont sortantes.

Dans le graphe ci-dessous :

Citer les sommets adjacents à Emma.
Quel est le degré entrant de Emma?
Quel est le degré sortant de Emma?
Citer un cycle initalisé en Fiona.
Justifier qu'aucun cycle n'est initialisé en David.

6. Stockage du type G = [V, E]:

Il existe plusieurs façons de stocker un graphe non-orienté dans Python, l'une d'elle est la création d'une liste de deux éléments :

Le premier élément est une liste contenant les strings associés aux sommets.
Le deuxième élément est une liste de tuples contenant deux valeurs. Chaque valeur est un string associé à un sommet. Le tuple représente une arête.

7. Exercice : Opérations sur un graphe non orienté

On considère le graphe ci-dessous :

On a implémenté ce graphe à l'aide du code suivant :

graphe = [
    ["Alice", "Bob", "Charlie", "David", "Emma", "Fiona", "George", "Hannah", "Ian", "Julia", "Kevin", "Laura", "Mike", "Nancy", "Olivia", "Paul"],
    [
        ("Alice", "Bob"), 
        ("Bob", "Charlie"), 
        ("Charlie", "David"), 
        ("David", "Emma"), 
        ("Emma", "Fiona"), 
        ("Fiona", "George"), 
        ("George", "Hannah"), 
        ("Hannah", "Ian"), 
        ("Ian", "Julia"), 
        ("Julia", "Kevin"), 
        ("Kevin", "Laura"), 
        ("Laura", "Mike"), 
        ("Mike", "Nancy"), 
        ("Nancy", "Olivia"), 
        ("Olivia", "Paul"),
        ("Alice", "Fiona"), 
        ("Emma", "Ian"), 
        ("David", "Kevin"), 
        ("Hannah", "Nancy")
    ]
]

Complétez les fonctions ci-dessous conformément à leurs documentations.

graphe_exemple = [ ["Alice", "Bob", "Charlie", "David", "Emma", "Fiona", "George", "Hannah", "Ian", "Julia", "Kevin", "Laura", "Mike", "Nancy", "Olivia", "Paul"], [ ("Alice", "Bob"), ("Bob", "Charlie"), ("Charlie", "David"), ("David", "Emma"), ("Emma", "Fiona"), ("Fiona", "George"), ("George", "Hannah"), ("Hannah", "Ian"), ("Ian", "Julia"), ("Julia", "Kevin"), ("Kevin", "Laura"), ("Laura", "Mike"), ("Mike", "Nancy"), ("Nancy", "Olivia"), ("Olivia", "Paul"), ("Alice", "Fiona"), ("Emma", "Ian"), ("David", "Kevin"), ("Hannah", "Nancy") ] ] def nombre_de_sommets(graphe: list) -> int: """ Retourne le nombre de sommets du graphe. """ ... def nombre_d_aretes(graphe: list) -> int: """ Retourne le nombre d'arêtes du graphe. """ ... def degre_sommet(graphe: list, sommet: str) -> int: """ Retourne le degré (nombre d'arêtes incidentes) du sommet donné. """ ... def adjacent_sommets(graphe: list, sommet1: str, sommet2: str) -> bool: """ Retourne True si sommet1 et sommet2 sont reliés par une arête, False sinon. """ ... def ajout_arete(graphe: list, arete: tuple) -> None: """ Ajoute l'arête donnée au graphe (si elle n'y est pas déjà). Le graphe est modifié sur place. """ ... def suppression_arete(graphe: list, arete: tuple) -> None: """ Supprime l'arête donnée du graphe (si elle est présente). Le graphe est modifié sur place. Les arêtes peuvent être lues dans les deux sens. """ ... def ajout_sommet(graphe: list, sommet: str) -> None: """ Ajoute un sommet au graphe (s'il n'y est pas déjà). Le graphe est modifié sur place. """ ... def suppression_sommet(graphe: list, sommet: str) -> None: """ Supprime le sommet du graphe ainsi que toutes les arêtes qui l'utilisent. Le graphe est modifié sur place. """ ... # Exemple d'utilisation possible : # print(nombre_de_sommets(graphe_exemple))

Tests :

Affichage :

Console:

>>>

8. Matrice d'adjacence:

Il existe plusieurs façons de stocker un graphe non-orienté dans Python, l'une d'elle est la création d'une matrice d'adjacence.

S'il y a \(n\) sommets, on associe à chaque sommet un unique nombre entier de \([0;n-1]\).

On créait alors la matrice de taille \(n \times n\) contenant les valeurs \(a_{i,j}\) avec \(i\) et \(j\) deux nombres entiers appartenant à \([0;n-1]\).

\(a_{i,j}\) correspond au nombre d'arêtes reliant les sommets associés à \(i\) et \(j\).

9. Exercice:

On considère le graphe ci-dessous :

On a implémenté ce graphe à l'aide du dictionnaire et de la matrice ci-dessous :

dico = {'Alice': 0, 'Bob': 1, 'Charlie': 2, 'David': 3, 'Emma': 4, 'Fiona': 5, 'George': 6, 'Hannah': 7, 'Ian': 8, 'Julia': 9, 'Kevin': 10, 'Laura': 11, 'Mike': 12, 'Nancy': 13, 'Olivia': 14, 'Paul': 15}
matrice = [
    [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
]

Écrire les fonctions suivantes utilisant/modifiant le dictionnaire et/ou la matrice:
1. nombre_de_sommets(dico: dict, matrice: list) -> int
2. nombre_d_aretes(dico: dict, matrice: list) -> int
3. degre_sommet(dico: dict, matrice: list, sommet: str) -> int
4. adjacent_sommets(dico: dict, matrice: list, sommet1: str, sommet2: str) -> bool
5. ajout_arete(dico: dict, matrice: list, arete: tuple) -> None , où arete est un tuple de string.
6. suppression_arete(dico: dict, matrice: list, arete: tuple) -> None , où arete est un tuple de string. Si plusieurs arêtes relient les deux mêmes sommets, une seule arête sera supprimée.
7. ajout_sommet(dico: dict, matrice: list, sommet: str) -> None
8. suppression_sommet(dico: dict, matrice: list, sommet: str) -> None. On veillera à supprimer toutes les arêtes comportant ce sommet.

10. Classes:

Les graphes non orientés ne sont pas naturellement présents dans Python, mais nous pouvons créer une classe qui leur correspond.

11. Exercice:

Nous allons compléter le fichier structures.py du chapitre Modularité en créant la classe GrapheNonOriente dont voici les contraintes :

l'initialisation se fait sans paramètre (autre que self bien sûr)
Les attributs sont :
1. l'attribut privé __sommets de type list qui correspond à la liste des sommets
2. l'attribut privé __aretes de type list qui correspond à la liste de tuples représentant les arêtes.
3. l'attribut privé __dico_sommets de type dict qui correspond au dictionnaire des correspondances des sommets avec un nombre entier
4. l'attribut privé __matrice_adjacence de type list qui correspond à la matrice d'adjacence.
Les méthodes sont :
1. la méthode publique liste_sommets(self) -> list qui retourne une liste contenant les sommets
2. la méthode publique liste_aretes(self) -> list qui retourne une liste de tuples des arêtes.
3. la méthode publique nb_sommets(self) -> int
4. la méthode publique nb_aretes(self) -> int
5. la méthode publique degre_sommet(self,sommet: str) -> int
6. la méthode publique sommets_adjacents(self,sommet) -> list qui retourne une liste (vide ou non) des sommets adjacents au sommet passé en argument.
7. la méthode privée __constru_dico(self) -> None qui reconstruit le dictionnaire à partir des sommets de l'attribut __sommets.
8. la méthode privée __constru_matrice(self) -> None qui reconstruit la matrice à l'aide du dictionnaire et des arêtes.
9. la méthode publique dictionnaire(self) -> dict qui retourne le dictionnaire des sommets.
10. la méthode publique matrice(self) -> list qui retourne la liste de listes correspondant à la matrice d'adjacence.
11. la méthode publique ajout_arete(self,sommet1: str,sommet2: str) -> None
12. la méthode publique suppr_arete(self,sommet1: str,sommet2: str) -> None. Si plusieurs arêtes relient les deux mêmes sommets, une seule arête sera supprimée.
13. la méthode publique ajout_sommet(self,sommet: str) -> None
14. la méthode publique suppr_sommet(self,sommet: str) -> None. On veillera à supprimer toutes les arêtes comportant ce sommet.

12. Exercice:

Dans un autre fichier, importer le fichier structures.py puis écrire les lignes de commandes permettant d'implémenter le graphe graphe suivant en tant qu'objet GrapheNonOriente.

On peut être malin et utiliser le code présent ci-dessous:

s = ["Alice", "Bob", "Charlie", "David", "Emma", "Fiona", "George", "Hannah", "Ian", "Julia", "Kevin", "Laura", "Mike", "Nancy", "Olivia", "Paul"]
a=[ ("Alice", "Bob"), 
    ("Bob", "Charlie"), 
    ("Charlie", "David"), 
    ("David", "Emma"), 
    ("Emma", "Fiona"), 
    ("Fiona", "George"), 
    ("George", "Hannah"), 
    ("Hannah", "Ian"), 
    ("Ian", "Julia"), 
    ("Julia", "Kevin"), 
    ("Kevin", "Laura"), 
    ("Laura", "Mike"), 
    ("Mike", "Nancy"), 
    ("Nancy", "Olivia"), 
    ("Olivia", "Paul"),
    ("Alice", "Fiona"), 
    ("Emma", "Ian"), 
    ("David", "Kevin"), 
    ("Hannah", "Nancy") ]

Tester la structure en :
1. tapant dans la console graphe.liste_sommets();
2. tapant dans la console graphe.liste_aretes();
3. tapant dans la console graphe.dictionnaire();
4. tapant dans la console graphe.matrice();
5. cherchant avec combien de personnes "David" est lié;
6. affichant les sommets adjacents de "Kevin".

13. Exercice:

Écrire une fonction voisin_du_voisin(graphe, sommet: str) -> list qui retourne la liste des sommets qui sont exactement à une distance de deux du sommet précisé.

Par exemple, voisin_du_voisin(graphe,"Julia") renverra ["Emma","Hannah","David","Laura"] (pas forcément dans cet ordre) avec le graphe de l'exercice précédent.

14. Exercice:

Dans le même fichier structures.py, créer la classe GrapheOriente en reprenant toutes les contraintes de l'exercice précédent mais en l'adaptant à un graphe orienté.

Dans le cas d'un graphe orienté avec deux noeuds A et B avec une seul arête orienté de A vers B, on dira que A a pour sommet adjacent B et que B n'a pas de sommet adjacent.

15. Graphes pondérés:

Un graphe orienté ou non orienté peut être pondéré.

Cette pondération peut représenter des valeurs réelles telles que:

une distance entre deux points
un temps mis pour un trajet
le nombre de fois où deux personnes ont échangé sur un réseau social
...

16. Exercice:

Dans structures.py, créer la classe GrapheNonOrientePondere et GrapheOrientePondere qui reprend les contraintes de la partie 9 en ajoutant ou en modifiant:

l'attribut aretes est maintenant une liste de tuples de trois éléments, deux strings correspondants aux sommets puis un float correspondant à la pondération.
la méthode publique ajout_arete(self,sommet1,sommet2,valeur) est donc adapté
la méthode publique suppr_arete(self,sommet1,sommet2,valeur) est donc adapté
la méthode publique distance(self,sommet1,sommet2) retourne la pondération de l'arête correspondante (cas où il y en a plusieurs?).
la méthode publique modif_pondere_arete(self,sommet1,sommet2,valeur,nouvelle_valeur)qui permet de modifier la pondération d'une arête.

17. Exercice:

Dans un fichier , importer le fichier structures.py puis copier/coller les lignes de commandes suivantes permettant d'implémenter le graphe suivant en tant qu'objet GrapheNonOrientePondere.

import os
os.chdir("U:\\terminaleNSI")
import structures    

# Création du graphe
graphe1 = structures.GrapheNonOrientePondere()

# Définition des sommets
sommets = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "S", "Q", "R", "P"]

# Ajout des sommets au graphe
for sommet in sommets:
    graphe1.ajout_sommet(sommet)

# Ajout des arêtes avec les poids
graphe1.ajout_arete("A", "B", 3)
graphe1.ajout_arete("B", "C", 7)
graphe1.ajout_arete("C", "D", 6)
graphe1.ajout_arete("D", "E", 2)
graphe1.ajout_arete("E", "F", 8)
graphe1.ajout_arete("F", "G", 4)
graphe1.ajout_arete("G", "H", 5)
graphe1.ajout_arete("H", "I", 9)
graphe1.ajout_arete("I", "J", 1)
graphe1.ajout_arete("J", "K", 7)
graphe1.ajout_arete("K", "L", 3)
graphe1.ajout_arete("L", "M", 5)
graphe1.ajout_arete("M", "N", 6)
graphe1.ajout_arete("N", "O", 4)
graphe1.ajout_arete("O", "S", 8)
graphe1.ajout_arete("Q", "S", 8)
graphe1.ajout_arete("C", "E", 8)
graphe1.ajout_arete("A", "F", 10)
graphe1.ajout_arete("E", "I", 6)
graphe1.ajout_arete("D", "K", 2)
graphe1.ajout_arete("H", "N", 9)
graphe1.ajout_arete("M", "Q", 2)
graphe1.ajout_arete("J", "R", 3)
graphe1.ajout_arete("K", "R", 4)
graphe1.ajout_arete("L", "R", 2)
graphe1.ajout_arete("R", "M", 2)
graphe1.ajout_arete("R", "N", 4)
graphe1.ajout_arete("B", "E", 3)
graphe1.ajout_arete("H", "P", 4)
graphe1.ajout_arete("P", "N", 2)

Écrire une fonction longueur_chaine(graphe,liste) dont les caractéristiques sont les suivantes:

graphe est un objet de type GrapheNonOrientePondere
liste correspond à une liste de string correspondant aux sommets.
elle renvoie un tuple formé d'un booléen puis d'un integer :
- elle renvoie (False,0) si un sommet de la liste n'existe pas.
- elle renvoie (False,1) si la chaine correspondante à la liste n'existe pas.
- elle renvoie (True,x) avec x correspondant à la longueur de la chaine sinon.

18. Exercice:

Dans un fichier, importer le fichier structures.py puis copier/coller les commandes suivantes permettant d'implémenter le graphe suivant en tant qu'objet GrapheOrientePondere.

import os
os.chdir("U:\\terminaleNSI")
import structures    

# Initialiser le graphe orienté pondéré
graphe1 = structures.GrapheOrientePondere()

# Définition des sommets
sommets = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "S", "Q", "R", "P"]

# Ajout des sommets au graphe
for sommet in sommets:
    graphe1.ajout_sommet(sommet)

# Ajout des arêtes avec leurs poids
graphe1.ajout_arete("A", "B", 3)
graphe1.ajout_arete("B", "C", 7)
graphe1.ajout_arete("C", "D", 6)
graphe1.ajout_arete("D", "E", 2)
graphe1.ajout_arete("E", "F", 8)
graphe1.ajout_arete("F", "G", 4)
graphe1.ajout_arete("G", "H", 5)
graphe1.ajout_arete("H", "I", 9)
graphe1.ajout_arete("I", "J", 1)
graphe1.ajout_arete("J", "K", 7)
graphe1.ajout_arete("K", "L", 3)
graphe1.ajout_arete("L", "M", 5)
graphe1.ajout_arete("M", "N", 6)
graphe1.ajout_arete("N", "O", 4)
graphe1.ajout_arete("O", "S", 8)
graphe1.ajout_arete("Q", "S", 8)
graphe1.ajout_arete("E", "C", 8)
graphe1.ajout_arete("A", "F", 10)
graphe1.ajout_arete("E", "I", 6)
graphe1.ajout_arete("I", "E", 6)  # Lien dans les deux sens avec le même poids
graphe1.ajout_arete("D", "K", 2)
graphe1.ajout_arete("H", "N", 9)
graphe1.ajout_arete("M", "Q", 2)
graphe1.ajout_arete("J", "R", 3)
graphe1.ajout_arete("K", "R", 4)
graphe1.ajout_arete("L", "R", 2)
graphe1.ajout_arete("R", "M", 2)
graphe1.ajout_arete("R", "N", 4)
graphe1.ajout_arete("B", "E", 3)
graphe1.ajout_arete("H", "P", 4)
graphe1.ajout_arete("P", "N", 2)
graphe1.ajout_arete("E", "D", 3)

Écrire les fonctions suivantes :

successeurs(graphe,sommet) qui prend en argument un objet de type GrapheOrientePondere et un string correspondant à un sommet et qui renvoie la liste des sommets successeurs.
predecesseurs(graphe,sommet) qui prend en argument un objet de type GrapheOrientePondere et un string correspondant à un sommet et qui renvoie la liste des sommets prédecesseurs.
longueur_chaine(graphe,liste) qui possède les mêmes conditions que dans l'exercice 15 sauf que le graphe est ici orienté.
Tester ces fonctions!

19. Exercice:

Copier/coller dans un fichier france.py,les lignes suivantes permettant d'implémenter une carte routière des grands axes de France en tant que graphe non orienté et pondéré.

La pondération représente le temps en minutes d'un trajet.

import os
os.chdir("U:\\terminaleNSI")
import structures

routes=structures.GrapheNonOrientePondere()

sommets=["Menton","Nice","Le Luc","Toulon","Marseille","Aubagne","Aix-en-Provence","Salon-de-Provence",
"Arles","Avignon","Nîmes","Orange","Montpellier","Béziers","Narbonne","Perpignan","Carcassonne","Toulouse",
"Montauban","Tarbes","Pau","Biarritz","Bordeaux","Brive-la-Gaillarde","Limoges","Angoulême","Saintes","La Rochelle",
"Niort","Poitiers","La Roche-sur-Yon","Nantes","Saint-Nazaire","Vannes","Lorient","Quimper","Brest","Morlaix",
"Saint-Brieuc","Rennes","Angers","Caen","Le Havre","Le Mans","Tours","Rouen","Amiens","Paris","Lille","Calais",
"Dunkerque","Valenciennes","Saint-Quentin","Reims","Metz","Nancy","Strasbourg","Mulhouse","Besançon","Dijon","Troyes",
"Beaune","Auxerre","Orléans","Lyon","Saint-Étienne","Clermont-Ferrand","Bourges","Annecy","Grenoble","Valence","Gap",
"Montélimar","Montluçon","Grasse","Cannes","Givors","Clermont-l'Hérault","Limalonges","Cholet","La Roche-Bernard",
"Savenay","Pontchâteau","Redon","Châteaulin","Carhaix-Plouguer","Loudéac","Pontivy","Parthenay","Saumur","Laval",
"Chartres","Alençon","Dreux","Evreux","Avranches","Mayenne","Saint-Malo","Fougères","Saint-Arnoult-en-Yvelines",
"Châteauroux","Vierzon","Blois","Chémery","Le Dognon","Boulogne-sur-Mer","Berck","Abbeville","Neufchâtel-en-Bray",
"Beauvais","Arras","Lens","Hénin-Beaumont","Douai","Compiègne","Sens","Maubeuge","La Capelle","Charleville-Mézières",
"Laon","Soissons","Châlons-en-Champagne","Saint-Dizier","Chaumont","Vitry-le-François","Sommesous","Colmar","Vesoul",
"Belfort & Montbéliard","Épinal","Dole","Pouilly-en-Auxois","Montargis","La Charité-sur-Loire","Nevers","Moulins",
"Chalon-sur-Saône","Mâcon","Paray-le-Monial","Montmélian","Chambéry","Aix-les-Bains","Albertville","Bourgoin-Jallieu",
"Bourg-en-Bresse","Pont-d'Ain","Agen","Langon","Mont-de-Marsan","Carros","Saint-Martin-du-Var","Villars-sur-Var","Puget-Théniers",
"Saint-Julien-du-Verdon","Saint-André-les-Alpes","Digne-les-Bains","Barrême","Castellane","Châteauredon","Manosque","Brignoles","Les Mées"]

for sommet in sommets:
    routes.ajout_sommet(sommet)

routes.ajout_arete("Cannes","Nice",27)
routes.ajout_arete("Nice","Menton",34)
routes.ajout_arete("Grasse","Cannes",32)
routes.ajout_arete("Le Luc","Cannes",55)
routes.ajout_arete("Toulon","Le Luc",62)
routes.ajout_arete("Brignoles","Le Luc",37)
routes.ajout_arete("Aix-en-Provence","Brignoles",35)
routes.ajout_arete("Aubagne","Toulon",35)
routes.ajout_arete("Marseille","Aubagne",23)
routes.ajout_arete("Marseille","Aix-en-Provence",28)
routes.ajout_arete("Aix-en-Provence","Aubagne",28)
routes.ajout_arete("Salon-de-Provence","Aix-en-Provence",25)
routes.ajout_arete("Arles","Salon-de-Provence",30)
routes.ajout_arete("Avignon","Salon-de-Provence",45)
routes.ajout_arete("Nîmes","Arles",27)
routes.ajout_arete("Nîmes","Orange",41)
routes.ajout_arete("Avignon","Orange",30)
routes.ajout_arete("Montpellier","Nîmes",47)
routes.ajout_arete("Montélimar","Orange",40)
routes.ajout_arete("Montélimar","Valence",43)
routes.ajout_arete("Les Mées","Gap",52)
routes.ajout_arete("Manosque","Les Mées",22)
routes.ajout_arete("Aix-en-Provence","Manosque",52)
routes.ajout_arete("Grenoble","Gap",113)
routes.ajout_arete("Béziers","Montpellier",61)
routes.ajout_arete("Givors","Valence",61)
routes.ajout_arete("Givors","Lyon",28)
routes.ajout_arete("Saint-Étienne","Givors",38)
routes.ajout_arete("Clermont-Ferrand","Saint-Étienne",103)
routes.ajout_arete("Béziers","Clermont-l'Hérault",51)
routes.ajout_arete("Clermont-l'Hérault","Montpellier",41)
routes.ajout_arete("Clermont-Ferrand","Clermont-l'Hérault",209)
routes.ajout_arete("Narbonne","Béziers",30)
routes.ajout_arete("Carcassonne","Narbonne",43)
routes.ajout_arete("Perpignan","Narbonne",45)
routes.ajout_arete("Toulouse","Carcassonne",68)
routes.ajout_arete("Tarbes","Toulouse",107)
routes.ajout_arete("Pau","Tarbes",36)
routes.ajout_arete("Biarritz","Pau",86)
routes.ajout_arete("Biarritz","Bordeaux",133)
routes.ajout_arete("Bordeaux","Brive-la-Gaillarde",137)
routes.ajout_arete("Brive-la-Gaillarde","Clermont-Ferrand",126)
routes.ajout_arete("Limoges","Brive-la-Gaillarde",64)
routes.ajout_arete("Montluçon","Clermont-Ferrand",79)
routes.ajout_arete("Angoulême","Limoges",86)
routes.ajout_arete("Saintes","Angoulême",70)
routes.ajout_arete("Saintes","Bordeaux",83)
routes.ajout_arete("Angoulême","Limalonges",46)
routes.ajout_arete("Limalonges","Poitiers",46)
routes.ajout_arete("La Rochelle","Saintes",55)
routes.ajout_arete("La Rochelle","Niort",52)
routes.ajout_arete("Saintes","Niort",56)
routes.ajout_arete("Niort","Poitiers",62)
routes.ajout_arete("Niort","Limalonges",64)
routes.ajout_arete("Montauban","Toulouse",44)
routes.ajout_arete("Montauban","Brive-la-Gaillarde",98)
routes.ajout_arete("Poitiers","Tours",78)
routes.ajout_arete("La Roche-sur-Yon","Niort",69)
routes.ajout_arete("Nantes","La Roche-sur-Yon",57)
routes.ajout_arete("La Roche-sur-Yon","Cholet",54)
routes.ajout_arete("Cholet","Parthenay",55)
routes.ajout_arete("Parthenay","Poitiers",60)
routes.ajout_arete("Nantes","Angers",66)
routes.ajout_arete("Cholet","Angers",46)
routes.ajout_arete("Angers","Saumur",38)
routes.ajout_arete("Saumur","Tours",45)
routes.ajout_arete("Parthenay","Saumur",95)
routes.ajout_arete("Saint-Nazaire","Nantes",57)
routes.ajout_arete("La Roche-Bernard","Saint-Nazaire",46)
routes.ajout_arete("Savenay","Nantes",37)
routes.ajout_arete("Saint-Nazaire","Savenay",25)
routes.ajout_arete("Pontchâteau","Savenay",13)
routes.ajout_arete("La Roche-Bernard","Pontchâteau",17)
routes.ajout_arete("Vannes","La Roche-Bernard",38)
routes.ajout_arete("Vannes","Redon",57)
routes.ajout_arete("Redon","Rennes",57)
routes.ajout_arete("La Roche-Bernard","Redon",34)
routes.ajout_arete("Lorient","Vannes",47)
routes.ajout_arete("Quimper","Lorient",50)
routes.ajout_arete("Quimper","Châteaulin",22)
routes.ajout_arete("Brest","Châteaulin",38)
routes.ajout_arete("Châteaulin","Carhaix-Plouguer",33)
routes.ajout_arete("Carhaix-Plouguer","Lorient",67)
routes.ajout_arete("Brest","Morlaix",47)
routes.ajout_arete("Morlaix","Saint-Brieuc",70)
routes.ajout_arete("Saint-Brieuc","Loudéac",43)
routes.ajout_arete("Saint-Brieuc","Rennes",77)
routes.ajout_arete("Carhaix-Plouguer","Loudéac",66)
routes.ajout_arete("Pontivy","Loudéac",22)
routes.ajout_arete("Pontivy","Vannes",46)
routes.ajout_arete("Lorient","Pontivy",47)
routes.ajout_arete("Rennes","Angers",103)
routes.ajout_arete("Rennes","Laval",66)
routes.ajout_arete("Laval","Le Mans",56)
routes.ajout_arete("Angers","Le Mans",66)
routes.ajout_arete("Le Mans","Tours",72)
routes.ajout_arete("Saint-Brieuc","Saint-Malo",64)
routes.ajout_arete("Saint-Malo","Avranches",49)
routes.ajout_arete("Rennes","Avranches",62)
routes.ajout_arete("Laval","Mayenne",26)
routes.ajout_arete("Mayenne","Alençon",63)
routes.ajout_arete("Alençon","Le Mans",42)
routes.ajout_arete("Avranches","Caen",68)
routes.ajout_arete("Saint-Malo","Rennes",51)
routes.ajout_arete("Rennes","Fougères",42)
routes.ajout_arete("Fougères","Mayenne",60)
routes.ajout_arete("Avranches","Fougères",26)
routes.ajout_arete("Caen","Alençon",77)
routes.ajout_arete("Caen","Le Havre",64)
routes.ajout_arete("Le Havre","Rouen",60)
routes.ajout_arete("Caen","Rouen",85)
routes.ajout_arete("Rouen","Evreux",45)
routes.ajout_arete("Evreux","Dreux",36)
routes.ajout_arete("Dreux","Chartres",42)
routes.ajout_arete("Caen","Evreux",99)
routes.ajout_arete("Alençon","Dreux",97)
routes.ajout_arete("Le Mans","Chartres",80)
routes.ajout_arete("Saint-Arnoult-en-Yvelines","Paris",60)
routes.ajout_arete("Chartres","Saint-Arnoult-en-Yvelines",34)
routes.ajout_arete("Orléans","Saint-Arnoult-en-Yvelines",66)
routes.ajout_arete("Dreux","Paris",74)
routes.ajout_arete("Evreux","Paris",88)
routes.ajout_arete("Vierzon","Bourges",23)
routes.ajout_arete("Châteauroux","Bourges",60)
routes.ajout_arete("Châteauroux","Vierzon",40)
routes.ajout_arete("Orléans","Vierzon",58)
routes.ajout_arete("Blois","Chémery",38)
routes.ajout_arete("Tours","Chémery",57)
routes.ajout_arete("Chémery","Châteauroux",67)
routes.ajout_arete("Chémery","Vierzon",37)
routes.ajout_arete("Tours","Blois",42)
routes.ajout_arete("Blois","Orléans",42)
routes.ajout_arete("Poitiers","Le Dognon",106)
routes.ajout_arete("Limoges","Le Dognon",33)
routes.ajout_arete("Le Dognon","Montluçon",75)
routes.ajout_arete("Le Dognon","Châteauroux",55)
routes.ajout_arete("Bourges","Montluçon",66)
routes.ajout_arete("Rouen","Neufchâtel-en-Bray",60)
routes.ajout_arete("Neufchâtel-en-Bray","Amiens",45)
routes.ajout_arete("Neufchâtel-en-Bray","Abbeville",63)
routes.ajout_arete("Le Havre","Neufchâtel-en-Bray",90)
routes.ajout_arete("Beauvais","Paris",73)
routes.ajout_arete("Beauvais","Amiens",44)
routes.ajout_arete("Abbeville","Amiens",35)
routes.ajout_arete("Berck","Abbeville",22)
routes.ajout_arete("Boulogne-sur-Mer","Berck",25)
routes.ajout_arete("Boulogne-sur-Mer","Calais",26)
routes.ajout_arete("Calais","Dunkerque",35)
routes.ajout_arete("Dunkerque","Lille",56)
routes.ajout_arete("Lille","Valenciennes",42)
routes.ajout_arete("Saint-Quentin","Valenciennes",58)
routes.ajout_arete("Amiens","Saint-Quentin",61)
routes.ajout_arete("Hénin-Beaumont","Douai",10)
routes.ajout_arete("Lens","Hénin-Beaumont",14)
routes.ajout_arete("Arras","Hénin-Beaumont",25)
routes.ajout_arete("Hénin-Beaumont","Lille",27)
routes.ajout_arete("Douai","Valenciennes",34)
routes.ajout_arete("Amiens","Arras",74)
routes.ajout_arete("Berck","Arras",75)
routes.ajout_arete("Arras","Lens",14)
routes.ajout_arete("Boulogne-sur-Mer","Lens",80)
routes.ajout_arete("Beauvais","Compiègne",49)
routes.ajout_arete("Compiègne","Saint-Quentin",60)
routes.ajout_arete("Paris","Compiègne",72)
routes.ajout_arete("Compiègne","Soissons",41)
routes.ajout_arete("Soissons","Reims",56)
routes.ajout_arete("Paris","Soissons",91)
routes.ajout_arete("Soissons","Laon",31)
routes.ajout_arete("Paris","Sens",92)
routes.ajout_arete("Valenciennes","Maubeuge",32)
routes.ajout_arete("La Capelle","Maubeuge",43)
routes.ajout_arete("La Capelle","Charleville-Mézières",64)
routes.ajout_arete("Saint-Quentin","La Capelle",57)
routes.ajout_arete("Laon","La Capelle",58)
routes.ajout_arete("Reims","Charleville-Mézières",61)
routes.ajout_arete("Laon","Reims",43)
routes.ajout_arete("Saint-Quentin","Laon",37)
routes.ajout_arete("Reims","Châlons-en-Champagne",35)
routes.ajout_arete("Châlons-en-Champagne","Vitry-le-François",27)
routes.ajout_arete("Vitry-le-François","Saint-Dizier",27)
routes.ajout_arete("Sommesous","Vitry-le-François",30)
routes.ajout_arete("Paris","Sommesous",132)
routes.ajout_arete("Sommesous","Châlons-en-Champagne",28)
routes.ajout_arete("Troyes","Sommesous",46)
routes.ajout_arete("Châlons-en-Champagne","Metz",101)
routes.ajout_arete("Saint-Dizier","Chaumont",63)
routes.ajout_arete("Saint-Dizier","Nancy",80)
routes.ajout_arete("Sens","Troyes",50)
routes.ajout_arete("Metz","Nancy",53)
routes.ajout_arete("Colmar","Strasbourg",72)
routes.ajout_arete("Mulhouse","Colmar",47)
routes.ajout_arete("Nancy","Colmar",140)
routes.ajout_arete("Nancy","Épinal",53)
routes.ajout_arete("Épinal","Mulhouse",103)
routes.ajout_arete("Vesoul","Épinal",70)
routes.ajout_arete("Besançon","Vesoul",50)
routes.ajout_arete("Vesoul","Belfort & Montbéliard",54)
routes.ajout_arete("Belfort & Montbéliard","Mulhouse",36)
routes.ajout_arete("Besançon","Belfort & Montbéliard",69)
routes.ajout_arete("Chaumont","Vesoul",107)
routes.ajout_arete("Dole","Besançon",47)
routes.ajout_arete("Dijon","Dole",39)
routes.ajout_arete("Beaune","Dijon",36)
routes.ajout_arete("Beaune","Dole",44)
routes.ajout_arete("Dijon","Chaumont",75)
routes.ajout_arete("Auxerre","Pouilly-en-Auxois",116)
routes.ajout_arete("Pouilly-en-Auxois","Dijon",55)
routes.ajout_arete("Pouilly-en-Auxois","Beaune",29)
routes.ajout_arete("Troyes","Chaumont",72)
routes.ajout_arete("Sens","Auxerre",54)
routes.ajout_arete("Montargis","Sens",51)
routes.ajout_arete("Orléans","Montargis",59)
routes.ajout_arete("Montargis","La Charité-sur-Loire",68)
routes.ajout_arete("Bourges","La Charité-sur-Loire",62)
routes.ajout_arete("La Charité-sur-Loire","Nevers",22)
routes.ajout_arete("Nevers","Moulins",55)
routes.ajout_arete("Montluçon","Moulins",55)
routes.ajout_arete("Moulins","Lyon",143)
routes.ajout_arete("Moulins","Paray-le-Monial",43)
routes.ajout_arete("Paray-le-Monial","Mâcon",57)
routes.ajout_arete("Paray-le-Monial","Chalon-sur-Saône",53)
routes.ajout_arete("Mâcon","Chalon-sur-Saône",40)
routes.ajout_arete("Chalon-sur-Saône","Beaune",29)
routes.ajout_arete("Mâcon","Lyon",50)
routes.ajout_arete("Mâcon","Bourg-en-Bresse",30)
routes.ajout_arete("Bourg-en-Bresse","Besançon",112)
routes.ajout_arete("Bourg-en-Bresse","Dole",74)
routes.ajout_arete("Bourg-en-Bresse","Pont-d'Ain",23)
routes.ajout_arete("Lyon","Pont-d'Ain",49)
routes.ajout_arete("Pont-d'Ain","Annecy",84)
routes.ajout_arete("Annecy","Albertville",56)
routes.ajout_arete("Montmélian","Albertville",24)
routes.ajout_arete("Chambéry","Montmélian",20)
routes.ajout_arete("Chambéry","Aix-les-Bains",21)
routes.ajout_arete("Aix-les-Bains","Annecy",28)
routes.ajout_arete("Grenoble","Montmélian",34)
routes.ajout_arete("Bourgoin-Jallieu","Chambéry",41)
routes.ajout_arete("Bourgoin-Jallieu","Grenoble",43)
routes.ajout_arete("Lyon","Bourgoin-Jallieu",40)
routes.ajout_arete("Valence","Grenoble",65)
routes.ajout_arete("Agen","Toulouse",75)
routes.ajout_arete("Langon","Agen",57)
routes.ajout_arete("Bordeaux","Langon",54)
routes.ajout_arete("Mont-de-Marsan","Langon",55)
routes.ajout_arete("Mont-de-Marsan","Pau",74)
routes.ajout_arete("Biarritz","Mont-de-Marsan",97)
routes.ajout_arete("Manosque","Brignoles",60)
routes.ajout_arete("Les Mées","Digne-les-Bains",26)
routes.ajout_arete("Châteauredon","Digne-les-Bains",12)
routes.ajout_arete("Châteauredon","Barrême",19)
routes.ajout_arete("Barrême","Saint-André-les-Alpes",13)
routes.ajout_arete("Castellane","Saint-Julien-du-Verdon",16)
routes.ajout_arete("Saint-André-les-Alpes","Saint-Julien-du-Verdon",7)
routes.ajout_arete("Saint-Julien-du-Verdon","Puget-Théniers",36)
routes.ajout_arete("Puget-Théniers","Villars-sur-Var",17)
routes.ajout_arete("Villars-sur-Var","Saint-Martin-du-Var",18)
routes.ajout_arete("Saint-Martin-du-Var","Carros",6)
routes.ajout_arete("Nice","Carros",9)
routes.ajout_arete("Castellane","Grasse",61)

20. Exercice:

Dans un nouveau fichier, importer france.

Dans toute la suite de l'exercice, graphe correspondra au graphe france.routes.

Écrire une fonction villes_adjacentes(graphe,ville_depart: str) qui renvoie une liste de toutes les villes où il existe une route directe entre ces villes et ville_depart.
Écrire la fonction villes_proches_directes(graphe, ville_depart, distance) qui renvoie une liste de toutes les villes qui sont à un temps inférieur ou égal de ville_depart et pour lesquelles une route y mène directement sans passer par une autre.
Écrire la fonction route_existante(graphe, ville1: str, ville2: str) -> bool où ville1 et ville2 sont des villes et qui renvoie si une route directe existe entre ces deux villes.
À l'aide de la fonction longueur_chaine vu précédemment, calculer le temps du trajet Nice ; Cannes ; Le Luc ; Brignoles ; Aix-en-Provence ; Marseille.
Écrire la fonction temps_mis(graphe, chaine: list) -> str qui prend en paramètre un graphe et une liste chaine de strings correpondants à des villes.

Elle retournera un string exprimant le temps mis en heures et en minutes ou un string indiquant que le chemin n'existe pas comme ci-dessous.

Exemple:
```
>>> temps_mis(graphe, ["Nice","Cannes","Le Luc"])
"1h22min"
>>> temps_mis(graphe, ["Nice","Paris","Brest"])
"La chaine Nice - Paris - Brest n'existe pas."
            
```
Commencer à imaginer la fonction villes_proches(graphe, ville_depart, distance) qui renvoie une liste de toutes les villes qui sont à un temps inférieur ou égal de ville_depart. Penser au cas où la valeur de distance commence à être grande 🥶, très grande 🤯. On fera cette question dans le chapitre suivant.