SD5 TP Corrige

TP sur les graphes - Corrigé¶

On représente le réseau autoroutier entre les villes de Rennes (R), Angers (A), Tours (T), Le Mans (M), Paris (P), Lyon (L) et Grenoble (G) à l’aide d’un graphe. Les villes sont les sommets du graphe et les routes sont représentées par les arêtes du graphe. On a indiqué les distances entre les villes sur les arêtes. Les sommets seront rangés par odre alphabétique.

1 - Matrice d'adjacence¶

Ecrire la matrice d'adjacence de ce graphe :

La matrice sera représentée par un tableau à 2 dimensions la variable s'appellera matrice1

In [6]:

matrice1 = [[  0,   0,   0, 100,   0, 120, 120],
            [  0,   0, 110,   0,   0,   0,   0],
            [  0, 110,   0,   0, 440,   0, 490],
            [100,   0,   0,   0, 190, 150, 105],
            [  0,   0, 440, 190,   0,   0, 220],
            [120,   0,   0, 150,   0,   0,   0],
            [120,   0, 490, 105, 220,   0,   0]]

sommets = ['A', 'G', 'L', 'M', 'P', 'R', 'T']

matrice1 = [[ 0, 0, 0, 100, 0, 120, 120], [ 0, 0, 110, 0, 0, 0, 0], [ 0, 110, 0, 0, 440, 0, 490], [100, 0, 0, 0, 190, 150, 105], [ 0, 0, 440, 190, 0, 0, 220], [120, 0, 0, 150, 0, 0, 0], [120, 0, 490, 105, 220, 0, 0]] sommets = ['A', 'G', 'L', 'M', 'P', 'R', 'T']

Vérification¶

Exécuter l'instruction suivante afin de vérifier votre travail

In [7]:

# Vérification de la réponse
assert matrice1[sommets.index('A')][sommets.index('T')] == 120

# Vérification de la réponse assert matrice1[sommets.index('A')][sommets.index('T')] == 120

2 - Liste d'adjacence¶

Ecrire une fonction matrice2liste(matrice, noms)

• matrice : matrice d'adjacence
• noms : noms des sommets dans l'ordre de la matrice
• renvoi : un dictionnaire dont les clés sont les sommets et les valeurs sont un tableau de tuples au format ('Nom', distance).

Exemple : A est reliée à M, R et T. le dictionnaire commencera par
{'A':[('M',100), ('R', 120), ('T', 120)] ...}

In [20]:

def matrice2liste(matrice, noms):
    """Renvoie la liste d'adjacence sous format dictionnaire"""
    
    liste={}    # Initialisation d'un dictionnaire vide
    
# Parcours des lignes de la matrice    
    for ligne in range(len(noms)):  
        voisins=[]   # Initialisation d'une liste vide qui contiendra les voisins d'un sommet

# Parcours des colonnes dans la ligne de la matrice
        for voisin in range(len(matrice[ligne])):    
            # Si l'arête existe
            if matrice[ligne][voisin] != 0:    
                # Ajout à voisins le couple (Sommet, poids) 
                voisins.append((noms[voisin], matrice[ligne][voisin])) 
        # Ajout à liste de la clé {sommet: [liste de voisins]}
        liste.update({noms[ligne]: voisins}) 
    return liste

def matrice2liste(matrice, noms): """Renvoie la liste d'adjacence sous format dictionnaire""" liste={} # Initialisation d'un dictionnaire vide # Parcours des lignes de la matrice for ligne in range(len(noms)): voisins=[] # Initialisation d'une liste vide qui contiendra les voisins d'un sommet # Parcours des colonnes dans la ligne de la matrice for voisin in range(len(matrice[ligne])): # Si l'arête existe if matrice[ligne][voisin] != 0: # Ajout à voisins le couple (Sommet, poids) voisins.append((noms[voisin], matrice[ligne][voisin])) # Ajout à liste de la clé {sommet: [liste de voisins]} liste.update({noms[ligne]: voisins}) return liste

Vérification¶

Exécuter l'instruction suivante afin de vérifier votre travail

In [27]:

matrice = [[0, 1, 0, 4],
           [1, 0, 0, 0],
           [2, 3, 0, 1],
           [1, 2, 1, 0]]

test = matrice2liste(matrice, ['A', 'B', 'C', 'D'])

assert test['B'] == [('A', 1)]
assert ('B', 1) in test['A']
assert ('D', 0) not in test['D']

matrice = [[0, 1, 0, 4], [1, 0, 0, 0], [2, 3, 0, 1], [1, 2, 1, 0]] test = matrice2liste(matrice, ['A', 'B', 'C', 'D']) assert test['B'] == [('A', 1)] assert ('B', 1) in test['A'] assert ('D', 0) not in test['D']

Comparaison du temps d'exécution des différentes solutions¶

In [10]:

%timeit matrice2liste(matrice, ['A', 'B', 'C', 'D'])

%timeit matrice2liste(matrice, ['A', 'B', 'C', 'D'])

9.03 µs ± 3.06 µs per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [11]:

# Solution avec une liste par compréhension (voisins)

def matrice2liste_b(matrice, noms):
    """Renvoie la liste d'adjacence sous format dictionnaire"""
    
    liste={}    # Initialisation d'un dictionnaire vide
    
# Parcours des lignes de la matrice    
    for ligne in range(len(noms)):  

# Parcours des colonnes dans la ligne de la matrice
        voisins = [(noms[voisin], matrice[ligne][voisin]) for voisin in range(len(matrice[ligne]))
                                      if matrice[ligne][voisin] != 0]
        # Ajout à liste de la clé {sommet: [liste de voisins]}
        liste.update({noms[ligne]: voisins}) 
    return liste

# Solution avec une liste par compréhension (voisins) def matrice2liste_b(matrice, noms): """Renvoie la liste d'adjacence sous format dictionnaire""" liste={} # Initialisation d'un dictionnaire vide # Parcours des lignes de la matrice for ligne in range(len(noms)): # Parcours des colonnes dans la ligne de la matrice voisins = [(noms[voisin], matrice[ligne][voisin]) for voisin in range(len(matrice[ligne])) if matrice[ligne][voisin] != 0] # Ajout à liste de la clé {sommet: [liste de voisins]} liste.update({noms[ligne]: voisins}) return liste

In [12]:

%timeit matrice2liste_b(matrice, ['A', 'B', 'C', 'D'])

%timeit matrice2liste_b(matrice, ['A', 'B', 'C', 'D'])

9.14 µs ± 1.69 µs per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [13]:

# Solution avec une liste par compréhension (voisins) et un dictionnaire par compréhension (liste)

def matrice2liste_c(matrice, noms):
    """Renvoie la liste d'adjacence sous format dictionnaire"""
    
    liste = dict((noms[ligne], [(noms[voisin], matrice[ligne][voisin]) 
                                for voisin in range(len(matrice[ligne]))
                                if matrice[ligne][voisin] != 0]) 
                 for ligne in range(len(noms)))  

    return liste

# Solution avec une liste par compréhension (voisins) et un dictionnaire par compréhension (liste) def matrice2liste_c(matrice, noms): """Renvoie la liste d'adjacence sous format dictionnaire""" liste = dict((noms[ligne], [(noms[voisin], matrice[ligne][voisin]) for voisin in range(len(matrice[ligne])) if matrice[ligne][voisin] != 0]) for ligne in range(len(noms))) return liste

In [14]:

%timeit matrice2liste_c(matrice, ['A', 'B', 'C', 'D'])

%timeit matrice2liste_c(matrice, ['A', 'B', 'C', 'D'])

9.26 µs ± 2.27 µs per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

3 - Liste d'adjacence vers matrice¶

On considère à présent le graphe représentant les mêmes villes mais les sommets sont pondérés par le temps de parcours en minutes. Voici sa liste d'adjacence au format dictionnaire tel que décrit plus haut:

{'A': [('M', 65), ('R', 90), ('T', 80)],
 'G': [('L', 70)],
 'L': [('G', 70), ('P', 230), ('T', 260)],
 'M': [('A', 65), ('P', 95), ('R', 90), ('T', 55)],
 'P': [('L', 230), ('M', 95), ('T', 130)],
 'R': [('A', 90), ('M', 90)],
 'T': [('A', 80), ('L', 260), ('M', 55), ('P', 130)]}

Ecrire une fonction liste2matrice(dico) prenant en paramètre un graphe donné par une liste d'adjacence sous format dictionnaire comme ci-dessus et renvoyant la matrice d'adjacence de ce graphe ainsi que un tableau des sommets.

En d'autre termes, la fonction liste2matrice est l'inverse de la fonction matrice2liste précédente.

In [15]:

def liste2matrice(dico):
    """Converti une liste d'adjacence en matrice d'adjacence"""
    # liste des sommets de la liste d'adjacence
    sommets = list(dico.keys())
    #Initialisation d'une matrice aux bonnes dimensions remplie de 0
    matrice = [[0 for i in range(len(sommets))] for j in range(len(sommets))]

    # pour chaque sommet de la liste des sommets
    for sommet in sommets:
        # pour chaque voisin du sommet
        for voisin in dico[sommet]:
            # remplit la matrice avec son poids
            # sommets.index(sommet) est la ligne de la matrice correspondante au sommet traité
            # sommets.index(voisin[0]) est la colonne de la matrice correspondante au voisin traité
            matrice[sommets.index(sommet)][sommets.index(voisin[0])] = voisin[1]

    return matrice, sommets

def liste2matrice(dico): """Converti une liste d'adjacence en matrice d'adjacence""" # liste des sommets de la liste d'adjacence sommets = list(dico.keys()) #Initialisation d'une matrice aux bonnes dimensions remplie de 0 matrice = [[0 for i in range(len(sommets))] for j in range(len(sommets))] # pour chaque sommet de la liste des sommets for sommet in sommets: # pour chaque voisin du sommet for voisin in dico[sommet]: # remplit la matrice avec son poids # sommets.index(sommet) est la ligne de la matrice correspondante au sommet traité # sommets.index(voisin[0]) est la colonne de la matrice correspondante au voisin traité matrice[sommets.index(sommet)][sommets.index(voisin[0])] = voisin[1] return matrice, sommets

Vérification¶

Exécuter l'instruction suivante afin de vérifier votre travail

In [16]:

test = {'A': [('A', 1), ('B', 2), ('C', 1)],
 'B': [('A', 2), ('B', 3), ('D', 1)],
 'C': [('A', 1)],
 'D': [('B', 1), ('D', 4)]}

l, n = liste2matrice(test)

assert n == ['A', 'B', 'C', 'D']
assert l == [[1, 2, 1, 0], [2, 3, 0, 1], [1, 0, 0, 0], [0, 1, 0, 4]]

test = {'A': [('A', 1), ('B', 2), ('C', 1)], 'B': [('A', 2), ('B', 3), ('D', 1)], 'C': [('A', 1)], 'D': [('B', 1), ('D', 4)]} l, n = liste2matrice(test) assert n == ['A', 'B', 'C', 'D'] assert l == [[1, 2, 1, 0], [2, 3, 0, 1], [1, 0, 0, 0], [0, 1, 0, 4]]

In [ ]:

pip install tutormagic

pip install tutormagic

In [18]:

%load_ext tutormagic

%load_ext tutormagic

Visualisation avec Python Tutor¶

La visualisation exécute le test de vérification précédent et démarre à la ligne 9 de la fonction (après la création de la matrice remplie de '0')

In [19]:

%%tutor --lang python3 --verticalStack -h 2000 --curInstr 45

def liste2matrice(dico):
    """Converti une liste d'adjacence en matrice d'adjacence"""
    # liste des sommets de la liste d'adjacence
    sommets = list(dico.keys())
    #Initialisation d'une matrice aux bonnes dimensions remplie de 0
    matrice = [[0 for i in range(len(sommets))] for j in range(len(sommets))]

    # pour chaque sommet de la liste des sommets
    for sommet in sommets:
        # pour chaque voisin du sommet
        for voisin in dico[sommet]:
            # remplit la matrice avec son poids
            # sommets.index(sommet) est la ligne de la matrice correspondante au sommet traité
            # sommets.index(voisin[0]) est la colonne de la matrice correspondante au voisin traité
            matrice[sommets.index(sommet)][sommets.index(voisin[0])] = voisin[1]

    return matrice, sommets

test = {'A': [('A', 1), ('B', 2), ('C', 1)],
 'B': [('A', 2), ('B', 3), ('D', 1)],
 'C': [('A', 1)],
 'D': [('B', 1), ('D', 4)]}

l, n = liste2matrice(test)

%%tutor --lang python3 --verticalStack -h 2000 --curInstr 45 def liste2matrice(dico): """Converti une liste d'adjacence en matrice d'adjacence""" # liste des sommets de la liste d'adjacence sommets = list(dico.keys()) #Initialisation d'une matrice aux bonnes dimensions remplie de 0 matrice = [[0 for i in range(len(sommets))] for j in range(len(sommets))] # pour chaque sommet de la liste des sommets for sommet in sommets: # pour chaque voisin du sommet for voisin in dico[sommet]: # remplit la matrice avec son poids # sommets.index(sommet) est la ligne de la matrice correspondante au sommet traité # sommets.index(voisin[0]) est la colonne de la matrice correspondante au voisin traité matrice[sommets.index(sommet)][sommets.index(voisin[0])] = voisin[1] return matrice, sommets test = {'A': [('A', 1), ('B', 2), ('C', 1)], 'B': [('A', 2), ('B', 3), ('D', 1)], 'C': [('A', 1)], 'D': [('B', 1), ('D', 4)]} l, n = liste2matrice(test)

In [ ]: