Graphes, exercice réseau ferroviaire

D'après Informatique tronc commun - ITC - PSI, MP, PC p232-233

Auteur(s) : Janny Steeven, Cherrière Théodore, Redaud Jeanne, Shu-Quartier-dit-Maire Wenqi, édition Ellipses

Présentation⚓︎

Dans cet exercice, on s’inspirera de l’évolution du réseau ferroviaire dans onze villes de France (Paris, Lille, Strasbourg, Lyon, Tours, Rennes, Bordeaux, Marseille, Nice, Toulouse et Brest) afin de prendre en main la manipulation de graphes.

Remarque: Sur le graphisme ci-dessous, Nantes est notée \(x_7\) comme Bordeaux. Pour simplifier, Nantes ne pas utilisée dans notre implémentation du graphe, c'est pour cela que le graphe contient 11 villes et non pas 12.

Plus précisément, on s’intéresse a la création et manipulation de plans P définis comme un ensemble de n villes numérotées de 1 a n, et d’un ensemble de m lignes ferroviaires les reliant entre elles. On supposera que tous les trains circulent a double-sens.

Implémentation d'une matrice d'adjacence et d'un tableau `plan`⚓︎

Ce réseau peut être étudié en implémentant deux variables :

la matrice d'adjacence (une des deux représentations classiques d'un graphe)

Python
adjacence_P1 =  [[0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
                [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
                [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

et un tableau plan tel que :

le plan P sous forme d’une liste de listes plan contenant (n+ 1) sous-tableaux tels que :

plan[O] contient [n,m], un tableau a deux elements avec n le nombre de villes, et m le nombre dc routes;
pour chaque ville \(x_i\), plan[i] contient un tableau a n elements, dont 1e premier plan [i][0] correspond au nombre de villes voisines, et les n — 1 éléments suivants (non nécessairement remplis) contiennent les indices des villes adjacentes (dans un ordre arbitraire et sans redondance).

Pour 1e plan P1 , on aurait donc n = 11, m = 7, on peut dénnir la variable plan_P1 telle que

plan_P1 [O] = [11, 7] ,
plan_P1[1]= [5, 2, 3, 4, 5, 6, None, None, None, None, None] puisque la ville 1 a 5 voisins sur les 11.
plan_P1[2] = [1, 1, None, None, None, None, None, None, None, None, None] carla ville 2 n'est réliée qu'à la ville 1

Ainsi :

Python
plan_P1 = [[11, 7],
            [5, 2, 3, 4, 5, 6] + 5 * [None],    # Ville 1
            [1, 1] + 9 * [None],                # Ville 2
            [1, 1] + 9 * [None],                # Ville 3
            [2, 1, 8] + 8 * [None],             # Ville 4
            [2, 1, 7] + 8 * [None],             # Ville 5
            [1, 1] + 9 *[None] ,                # Ville 6
            [1, 5] + 9 * [None],                # Ville 7
            [1, 4] + 9 * [None],                # Ville 8
            [0] + 10 * [None],                  # Ville 9
            [0] + 10 * [None],                  # Ville 10
            [0] + 10 * [None]]                  # Ville 11

Questions⚓︎

Q1 Complète la fonction plan_from_matrice qui prend un argmument la matrice d'adjacence et retourne le plan décrit ci-dessus.

Python
def plan_from_matrice(adjacence):
    n = len(adjacence)
    plan = [] # initialisation de la liste vide

    # Ajout de la première ligne [n, m] m initialisé à 0, elle sera modifiée par la suite
    m = 0
    plan.append([n, m])

    # Création des lignes suivantes
    for i in range(n):
        voisins = []
        for j in range(n):
            if adjacence[i][j] == 1:
                voisins.append(j + 1)  # on passe à l'index qui commence à 1 au lieu de 0
                m += 1        
        ligne = [len(voisins)] + .....

        ligne += [None] * (.....)  # compléter avec des None pour avoir n éléments
        plan.append(ligne)

    # modificaition de la première ligne
    plan[...][...] = m // ... # les routes sont comptées deux fois
    return plan

Q2 Réciproquement la fonction matrice_from_plan retourne la matrice d'adjacence à partir du plan.

Complète la fonction suivante

Python
def matrice_from_plan(plan : list) -> [[int]]:
    nb_villes = len(plan) - 1 # car plan[0] ne correspond pas à une ville

    matrice = [[0] * nb_villes for _ in range(nb_villes)] # inititialisation d'une matrice vide

    # Parcours de plan et indicarion des adjacences dans la matrice

    for indice_ville in range(1, len(plan)): 
        for voisin in plan[.....][1:]:
            if voisin != None:
                matrice[.....][....] = 1
    return matrice

Remarque: les deux lignes for voisin in plan[.....][1:]: et if voisin != None: peuvent être remplacées par une seule en utilisant le premier élément de la liste qui donne le nombre de voisin(s). Donc par for voisin in plan[.....][1:(1+plan[indice_ville][0])]:

compositions de fonctions réciproques⚓︎

Les deux fonctions plan_from_matrice et matrice_from_plan étant réciproques, leur composée donne la fonction identité.

Nous pouvons le constater en évaluant plan_from_matrice(matrice_from_plan(plan_P1)) == plan_P1

Q3 Ecrire une fonction est_adjacent(plan: list, i: int, j: int) qui renvoie True si les villes i et jsont adjacentes, Falsesinon.

Q4 Complète la fonction parcours(plan, i)qui donne la liste des villes accessibles depuis la ville ì. Quel est le type de parcours utilisé ici : largeur ou profondeur ?

Python
from collections import deque

def parcours(plan, depart):
    atteintes = [...] # ajout de la ville de depart
    file = deque()
    file.append(depart)

    while file:
        ville = file.popleft()  # retrait du début (FIFO)
        for voisin in plan[...][1:(1+plan[ville][0])]: # Attention le premier élément de plan est le nombre de voisin, il sert à calculer la tranche
            if voisin not in ....: # si la ville n'a pas déja été atteinte
                atteintes.append(...)
                file.append(....)
    return atteintes

Q5 A partir de la fonction précédente, écrire une fonction existe_chemin(plan, i, j) qui renvoie True si il existe un trajet TGV entre la ville i et la ville j, False sinon.

Pour aller plus loin⚓︎

Re écrire la fonction parcours à l'aide du parcours en profondeur, et écrire une fonction trouve_chemin(plan, i, j) qui retourne le chemin le plus court pour aller de la ville i à la ville j.

Solution