Skip to article frontmatterSkip to article content

Licence CC BY-NC-ND, Thierry Parmentelat

introduction

dans ce TP nous allons

et pour cela nous aurons besoin

comme nous n’avons pas encore étudié les classes, nous allons nous restreindre à utiliser uniquement les types de base de Python - listes, tuples, dictionnaires et ensembles

formalisation

nous nous intéressons aux graphes valués, qu’on peut définir formellement comme un triplet G=(V,E,W)G =(V, E, W), où

familles de problèmes

dans la littérature, les problèmes de plus court chemin participent de plusieurs niveaux de complication, selon qu’on cherche la distance la plus courte

en toute généralité on peut aussi considérer le cas où les poids peuvent être négatifs

pour notre part et dans la suite, on se placera dans le cas usuel où toutes les distances sont strictement positives, et on va se concentrer sur le single pair problem, c’est-à-dire avec une source et une destination spécifiques.

structure de données

pour ce TP, on va se limiter à des sommets qui soient des chaines de caractères

quelles options voyez-vous pour modéliser un graphe par un objet Python ?

liste de listes

# par exemple
graph_as_list = [
  ['a', 14, 'c'],
  ['a', 9, 'd'],
  ['a', 7, 'b'],
  ['a', 7, 'b'],
  ['b', 10, 'd'],
  ...
]

matrice

si on veut coder le graphe comme une matrice, on a besoin aussi de garder les noms des sommets

# par exemple
import numpy as np
graph_as_matrix = (
    np.array([
        [0, 7,14, 9, 0, 0],
        [0, 0, 0,10,15, 0],
        [0, 0, 0, 2, 0, 9],
        [0, 0, 0, 0,11, 0],
        [0, 0, 0, 0, 0, 6],
        [0, 0, 0, 0, 0, 0]]),
    ['a', 'b', 'c', 'd', 'e', 'f'])

autres idées ?

# comment feriez-vous ?
my_graph = ...
indice

les algorithmes qui suivent sont des algorithmes de parcours;
cela signifie que l’on a besoin de pouvoir parcourir rapidement les voisins d’un noeud, c’est-à-dire les arêtes qui sortent du noeud;
de la même façon, on a besoin de localiser rapidement un noeud à partir de son nom

lecture d’un fichier

la plupart du temps on va aller chercher ces données sur Internet auprès de dépôts de type Open-Data, et sur Internet on ne trouve pas des objets Python (matrice ou liste ou dictionnaire ou ...), on trouve seulement du texte (même quand c’est du HTML ou du XML ou du JSON ou du CSV, c’est toujours du texte, plus ou moins facile à transformer en objets Python)

donc pour pouvoir stocker / échanger les données de type graphe, on a besoin aussi d’un format textuel
c’est quoi un format textuel ? simplement un ensemble de conventions qui décrivent comment on peut écrire un graphe sous forme de texte

dans notre cas, nous allons choisir la forme la plus simple possible :

ce qui donnerait (par exemple) pour notre graphe témoin le fichier (ouvrez-le sous vs-code) data/graph.csv

graph.csv
a,b,7
a,d,9
a,c,14
b,d,10
b,e,15
c,d,2
c,f,9
d,e,11
e,f,6

exo #1: parse_graph

notre premier exercice va donc consister à écrire une fonction qui

mais en fait, on a choisi quoi comme structure de données ?
pour éviter les inconvénients des listes et des matrices, on va représenter un graphe comme

# ce qui donnerait pour notre graphe témoin

G = {
    'a': {'b': 7, 'd': 9, 'c': 14},
    'b': {'d': 10, 'e': 15},
    'c': {'d': 2, 'f': 9},
    'd': {'e': 11},
    'e': {'f': 6},
    'f' : {},
}
# rappel: pour découper une chaine

'a,b,12'.split(',')
['a', 'b', '12']
# rappel: pour convertir une chaine en entier

int('12 ')
12
# rappel: pour nettoyer une chaine

' a,b,12\n'.strip()
'a,b,12'
# ou si on préfère

' a,b,12\n'.rstrip()
' a,b,12'

à vous de jouer

# à vous d'écrire cette fonction

def parse_graph(filename):
    ...

pour vérifier, inspectez visuellement votre résultat
vérifiez aussi/surtout que les poids sont bien des entiers et pas des chaines

# ceci doit vous afficher un dictionnaire de dictionnaires

parse_graph("data/graph.csv")
# et ceci doit être True

parse_graph("data/graph.csv") == G
False
# et ceci doit être True aussi

import json

with open("data/graph-2.json") as f:
    g2ref = json.load(f) 
g2ref == parse_graph("data/graph-2.csv")
False
# et ceci doit être True aussi

with open("data/graph-3.json") as f:
    g3ref = json.load(f) 
g3ref == parse_graph("data/graph-3.csv")
False

nombre de sommets

exo #2: number_vertices

écrivez une fonction qui retourne le nombre de sommets du graphe

def number_vertices(graph):
    """
    returns number of vertices
    
    Parameters:
      graph: implemented as a dictionary of adjacency dictionaries
      
    Returns:
      int: number of vertices
    """
    ...

pour vérifier

# pour vérifier: doit retourner True

(   number_vertices(G) == 6
and number_vertices(g2ref) == 6
and number_vertices(g3ref) == 7)
False

atteignabilité

maintenant que nous avons une structure de données, nous allons pouvoir en faire quelque chose d’utile
le premier algorithme que nous allons voir consiste à calculer l’ensemble des sommets que l’on peut atteindre en partant d’un sommet donné

commençons par voir un exemple

# un graphe voisin de notre graphe témoin, mais avec des boucles
# parce que sinon c'est pas drôle

reach = parse_graph("data/reach.csv")
# pour le visualiser:
# installer graphviz avec 
# conda install graphviz
# (sinon ce n'est pas du tout critique)

try:
    from IPython.display import display
    from data.graphs import to_graphviz
    with open("data/reach.json") as f:
        reach = json.load(f)
    display(to_graphviz(reach, "neato"))
except Exception as exc:
    print("graphical output not available, but no worries....")
    # print(f"{type(exc)}: {exc}")
Loading...
# voilà ce qu'on doit trouver sur ce graphe comme sommets atteignables:

import pickle

with open("data/reach.pickle", 'rb') as f:
    reach_reachables = pickle.load(f)
reach_reachables
{'a': {'a', 'b', 'c', 'd', 'e', 'f'}, 'b': {'a', 'b', 'c', 'd', 'e', 'f'}, 'd': {'a', 'b', 'c', 'd', 'e', 'f'}, 'c': {'a', 'b', 'c', 'd', 'e', 'f'}, 'e': {'e', 'f'}, 'f': {'e', 'f'}}
for vertex, expected_reachables in reach_reachables.items():
    print(f"en partant de {vertex} → {expected_reachables}")
en partant de a → {'a', 'c', 'f', 'b', 'd', 'e'}
en partant de b → {'a', 'c', 'f', 'b', 'd', 'e'}
en partant de d → {'a', 'c', 'f', 'b', 'd', 'e'}
en partant de c → {'a', 'c', 'f', 'b', 'd', 'e'}
en partant de e → {'f', 'e'}
en partant de f → {'f', 'e'}

la difficulté

l’anti-loop

si on parlait d’arbres et non pas de graphes, on pourrait s’en sortir très simplement avec un parcours récursif en profondeur

mais ici on a des graphes, avec possiblement des cycles, et donc il faut faire un peu attention, notamment à ne pas boucler à l’infini

quelles méthodes est-ce que vous voyez pour éviter justement de boucler (pour éviter de repasser plusieurs fois au même endroit ?)

indice soyez attentifs à la performance; on veut pouvoir utiliser cet algorithme avec des graphes très gros…

quand est-ce qu’on s’arrête ?

comment fait-on pour décider de s’arrêter ?

ne pas modifier le sujet de la boucle

sans transition, mais c’est sans doute le bon moment pour signaler une limitation de Python, qui est qu’on ne peut pas modifier un objet sur lequel on est en train de faire une boucle

illustration :

# on ne peut pas modifier un objet sur lequel on boucle
# ici un dictionnaire pour commencer

D = {'a': 'b', 'c': 'd'}

try:
    for k, v in D.items():
        D[k+v] = v+k
except Exception as exc:
    print(f"OOPS {type(exc)} {exc}")
OOPS <class 'RuntimeError'> dictionary changed size during iteration

S = {'a', 'b'}

# c'est vrai pour tous les containers - ici un ensemble
# et c'est vrai que ce soit pour ajouter ou pour enlever

try:
    for s in S:
        S.remove(s)
except Exception as exc:
    print(f"OOPS {type(exc)} {exc}")
OOPS <class 'RuntimeError'> Set changed size during iteration

exo #3: reachables

je ne vous donne pas davantage d’indices, je vous laisse écrire ceci

# votre code 

def reachables(graph, s):
    """
    computes the set of reachable vertices in a graph from source s

    Parameters:
      graph: a graph implemented as a dict of adjacency dicts
      s: the source vertex
    Returns:
      a set of vertices in graph
    """
    ...

pour vérifier

vous pouvez vérifier visuellement en comparant vos résultats avec ceux qu’on a vus dans l’exemple

# pour le debug

for s in reach:
    print(f"depuis {s} → {reachables(reach, s)}")
depuis a → None
depuis b → None
depuis d → None
depuis c → None
depuis e → None
depuis f → None

# pareil mais orienté test et pas debug
# on teste le résultat sur chaque sommet

for vertex, expected_reachables in reach_reachables.items():
    print(f"en partant de {vertex} → {expected_reachables == reachables(reach, vertex)}")
en partant de a → False
en partant de b → False
en partant de d → False
en partant de c → False
en partant de e → False
en partant de f → False

# pareil sur le graphe témoin du départ
# on énumère à la main les sommets à tester 
# et les résultats attendus

G_expected_reachables = [
    ('a', {'a', 'b', 'c', 'd', 'e', 'f'}),
    ('b', {'b', 'd', 'e', 'f'}),
    ('c', {'c', 'd', 'e', 'f'}),
    ('d', {'d', 'e', 'f'}),
    ('e', {'e', 'f'}),
    ('f', {'f'}),
]

# on vérifie pour chacun qu'on
# obtient bien le résultat attendu
for (vertex, expected_reachables) in G_expected_reachables:
    computed = reachables(G, vertex)
    if computed != expected_reachables:
        print(f"ERROR since {vertex}: found {computed} != {expected_reachables}")
    else:
        print(f"OK since {vertex} → {computed}")
ERROR since a: found None != {'a', 'b', 'd', 'c', 'f', 'e'}
ERROR since b: found None != {'b', 'd', 'f', 'e'}
ERROR since c: found None != {'c', 'd', 'f', 'e'}
ERROR since d: found None != {'d', 'f', 'e'}
ERROR since e: found None != {'f', 'e'}
ERROR since f: found None != {'f'}

plus courte distance

on va pouvoir aussi calculer le plus court chemin entre deux noeuds d’un graphe
pour cela nous allons utiliser un algorithme très classique, connu sous le nom d’algorithme de Dijkstra

c’est un algorithme très utilisé; lorsque vous demandez à une app de vous calculer un itinéraire par exemple, c’est bien sûr comme ça que c’est calculé, et il y a de fortes chances pour que l’algorithme utilisé soit basé sur Dijkstra; remarquez que ce qu’on a appelé distance jusqu’ici, ça peut être aussi une durée, ou n’importe quoi d’autre bien entendu.

l’idée générale est assez simple :

et du coup si/quand on arrive au sommet d’arrivée, on a forcément trouvé le plus court chemin entre les deux

illustration

voici une illustration de cet algorithme, sur notre graphe témoin, entre les noeuds a et f

l’algorithme

en français :

question

terminaison d’un algo avec les notebooks

ceci est une digression, mais c’est facile d’écrire par accident un algo qui boucle (i.e. qui ne termine jamais)

  • lorsque ça arrive dans un notebook, l’affichage ressemble à In [*] comme ci-contre

  • il faut alors interrompre le kernel

  • on peut le faire par le menu Kernel → Interrupt

  • ou encore en tapant 2 fois la touche i en mode Commande

Rappel :

  • la cellule courante a un bandeau bleu en mode Commande, et un bandeau vert en mode Édition

  • le mode Édition c’est pour insérer du texte, donc si vous tapez i i en mode édition, ça insère ii dans votre notebook, évidemment

pour les forts

à ce stade si vous êtes relativement confortable avec Python, vous devez pouvoir écrire une fonction qui calcule la distance la plus courte entre deux noeuds du graphe
n’hésitez pas alors à passer directement à la section “exo #4”, quitte à remonter voir les indices ensuite

des indices pour les autres

je décortique un peu pour ceux qui sont moins à l’aise

comment itérer sur le graphe

quelques rappels/astuces qui peuvent servir dans ce contexte :

# on rappelle comment itérer sur un dictionnaire
# d'abord pour lister toutes les arêtes sortant d'un sommet
# il faut itérer sur le dictionnaire d'adjacences

s = 'b'           # s pour source
adj = G[s]        # adj pour adjacency

# voici comment on itère sur les arêtes sortant du vertex
# d pour destination, et w pour weight

for d, w in adj.items():
    print(s, '→', w, '→', d)
b → 10 → d
b → 15 → e

# du coup pour itérer sur toutes les arêtes

for s, adj in G.items():
    for d, w in adj.items():
        print(f"{s=} → {d=}")
s='a' → d='b'
s='a' → d='d'
s='a' → d='c'
s='b' → d='d'
s='b' → d='e'
s='c' → d='d'
s='c' → d='f'
s='d' → d='e'
s='e' → d='f'

# math.inf matérialise l'infini
import math

10**6 < math.inf
True

structure générale de l’algorithme

pour commencer la structure générale de la fonction ressemble à ceci

à ne pas prendre au pied de de la lettre, vous pouvez/devez changer/renommer/faire autrement comme vous le sentez...

def shortest_distance(graph, v1, v2):

    # initialisation
    # on se définit une variable locale à la fonction
    # qui matérialise le marquage

    visited = ...

    # ensuite on fait une boucle jusqu'à ce qu'une certaine condition soit remplie
    # souvenez-vous qu'on peut sortir d'un while avec 'break' - ou aussi 'return' d'ailleurs
    while True:

        # on va calculer les arêtes qui font partie de la bordure
        edges = set()

        # on énumère toutes les arêtes, et on ajoute dans
        # edges celles qui satisfont le critère
        # for ...
        #    for ...
        #      if ...
        #         edges.add(...)
        #  

        # si on n'a aucune arête c'est que c'est raté
        if not edges:
            return

        # sinon on trouve la meilleure
        shortest_length = math.inf
        shortest_vertex = None
        for edge in edges:
            ... # trouver la plus courte
                # et mémoriser le sommet correspondant

        # marquer le sommet correspondant

        # regarder si c'est le sommet 
        if shortest_vertex == v2:
            return ...

exo #4: shortest_distance

# à vous d'écrire une fonction
# comme ceci

def shortest_distance(graph, v1, v2):
    """
    this function computes the length of the shortest path
    in graph between v1 and v2
    
    Parameters:
      graph: a graph described as a dictionary of dictionaries
      v1: the source vertex
      v2: the destination vertex
    Returns:
      int: the length of the shortest path, or None 
    """
    ...

vérifications

pour vérifier si votre code fonctionne :

# vérifiez que G est bien toujours notre graphe de référence
G
{'a': {'b': 7, 'd': 9, 'c': 14}, 'b': {'d': 10, 'e': 15}, 'c': {'d': 2, 'f': 9}, 'd': {'e': 11}, 'e': {'f': 6}, 'f': {}}
# doit renvoyer True

shortest_distance(G, 'a', 'f') == 23
False
shortest_distance(G, 'a', 'e') == 20
False
shortest_distance(G, 'c', 'b') is None
True

vérification avec un autre graphe en entrée

G2 = parse_graph('data/graph-2.csv')

G2
to_graphviz(G2, "dot")
oops: 'NoneType' object has no attribute 'items'

shortest_distance(G2, 'v1', 'v6')

avec quelques graphes denses

c’est l’occasion de parler un peu de l’instruction assert:

GD2 = parse_graph("data/dense-2.csv")
assert shortest_distance(GD2, "1x1", "2x2") == 4
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[38], line 2
      1 GD2 = parse_graph("data/dense-2.csv")
----> 2 assert shortest_distance(GD2, "1x1", "2x2") == 4

AssertionError: 
GD3 = parse_graph("data/dense-3.csv")
assert shortest_distance(GD3, "1x1", "3x3") == 6
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[39], line 2
      1 GD3 = parse_graph("data/dense-3.csv")
----> 2 assert shortest_distance(GD3, "1x1", "3x3") == 6

AssertionError: 
GD4 = parse_graph("data/dense-4.csv")
assert shortest_distance(GD4, "1x1", "4x4") == 8
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[40], line 2
      1 GD4 = parse_graph("data/dense-4.csv")
----> 2 assert shortest_distance(GD4, "1x1", "4x4") == 8

AssertionError:

exo #5 : shortest_path

comment pourriez-vous adapter cet algorithme pour retourner aussi le chemin par lequel il faut passer ?

def shortest_path(graph, v1, v2):
    """
    same as shortest_distance but returns a tuple
    (distance, path)
    path being a list of vertices
    """
    # of course to write this function you will start
    # from your code for shortest_distance
    ...

pour vérifier

# je vous laisse le soin d'écrire le code pour tester

un graphe un peu plus réaliste

dans cette section on va se contenter d’utiliser ce qui précède, mais sur un graphe un peu plus gros
on est allé chercher les données dans ce dépôt sur github
il s’agit des relations entre les personnages d’un roman qui se situe dans le monde de Game of Thrones
on a choisi ces données car le graphe est de taille moyenne (71 sommets) mais reste suffisamment petit pour qu’on puisse vaguement le dessiner
remarquez que les données sont issues d’un dépôt 100% Java; le format de données ne dépend pas du tout du langage qu’on utilise pour les traiter, bien entendu

thrones_url = "https://raw.githubusercontent.com/pupimvictor/NetworkOfThrones/master/stormofswords.csv"

on va profiter de l’occasion pour voir comment aller chercher des données sur Internet

aller chercher et transformer la donnée

# si nécessaire, installer requests avec 
# $ pip install requests 

import requests
# voici l'idiome qui permet d'aller chercher 
# une page web à partir de son URL

get_request = requests.get(thrones_url)
text_data = get_request.text
# voilà à quoi ressemble le (début du) texte
# vous pouvez vérifier en pointant une nouvelle fenêtre 
# de votre navigateur vers l'url en question
text_data[:200]
'Source,Target,Weight\nAemon,Grenn,5\nAemon,Samwell,31\nAerys,Jaime,18\nAerys,Robert,6\nAerys,Tyrion,5\nAerys,Tywin,8\nAlliser,Mance,5\nAmory,Oberyn,5\nArya,Anguy,11\nArya,Beric,23\nArya,Bran,9\nArya,Brynden,6\nAry'

maintenant le texte de la page Web est dans une variable Python (de type str donc)
il se trouve toutefois que

donc bref, pour ne pas nous compliquer la vie, on va créer un fichier local avec le contenu du texte, moins la première ligne

une autre approche aurait pu être de re-factorer le code de parse_graph, pour permettre le parsing à partir d’une chaine, mais bon on ne va pas se compliquer la vie ici…; en plus ça nous donne une occasion d’utiliser ce qu’on a appris sur la création des fichiers

# écrivez le code qui sauve le contenu
# de la page web, sans la première ligne, 
# dans le fichier data/thrones.csv
# (le répertoire data/ existe déjà)

pour vérifier le contenu, regardez les 5 premières lignes qui devraient être

Aemon,Grenn,5
Aemon,Samwell,31
Aerys,Jaime,18
Aerys,Robert,6
Aerys,Tyrion,5
...
pour voir le début d’un fichier

  • on peut bien sûr utiliser vs-code

  • pour voir le début du fichier depuis le terminal bash, on peut aussi faire simplement

    head -5 data/thrones.csv

  • ou depuis IPython ou un notbook, on ajoute un ! pour dire que c’est un travail pour le terminal

    !head -5 data/thrones.csv

  • enfin on peut aussi écrire un petit bout de code en Python
    sauriez-vous le faire ?
    on verra bientôt enumerate() qui peut s’avérer utile pour faire ça

charger le graphe thrones

# une fois que le fichier local est OK, on peut utiliser notre
# code pour faire des calculs dans ce graphe

thrones = parse_graph("data/thrones.csv")

# should be True

number_vertices(thrones) == 107
False

on peut maintenant voir un peu à quoi il ressemble; enfin, si on a graphviz installé, et sinon, eh bien ce n’est pas grave !

oops: 'NoneType' object has no attribute 'items'
too bad: 'NoneType' object has no attribute 'attr'

et maintenant on peut faire des calculs dans ce graphe

atteignabilité

# ce personnage semble assez central

len(reachables(thrones, 'Eddard')) == 88
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[50], line 3
      1 # ce personnage semble assez central
----> 3 len(reachables(thrones, 'Eddard')) == 88

TypeError: object of type 'NoneType' has no len()
# pas mal non plus

len(reachables(thrones, 'Bran')) == 42
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[51], line 3
      1 # pas mal non plus
----> 3 len(reachables(thrones, 'Bran')) == 42

TypeError: object of type 'NoneType' has no len()
# plus secondaire déjà

len(reachables(thrones, 'Davos')) == 3
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[52], line 3
      1 # plus secondaire déjà
----> 3 len(reachables(thrones, 'Davos')) == 3

TypeError: object of type 'NoneType' has no len()
# pas trop populaire non plus

len(reachables(thrones, 'Shireen')) == 4
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[53], line 3
      1 # pas trop populaire non plus
----> 3 len(reachables(thrones, 'Shireen')) == 4

TypeError: object of type 'NoneType' has no len()

plus court chemin

# des plus courts chemins
d, path = shortest_path(thrones, 'Eddard', 'Doran')
d == 15 and len(path) == 4 and 'Catelyn' in path
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[54], line 2
      1 # des plus courts chemins
----> 2 d, path = shortest_path(thrones, 'Eddard', 'Doran')
      3 d == 15 and len(path) == 4 and 'Catelyn' in path

TypeError: cannot unpack non-iterable NoneType object
d, path = shortest_path(thrones, 'Eddard', 'Margaery')
d == 17 and set(path) == {'Eddard', 'Sansa', 'Renly', 'Margaery'}
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[55], line 1
----> 1 d, path = shortest_path(thrones, 'Eddard', 'Margaery')
      2 d == 17 and set(path) == {'Eddard', 'Sansa', 'Renly', 'Margaery'}

TypeError: cannot unpack non-iterable NoneType object
(d, path) = shortest_path(thrones, 'Daenerys', 'Karl')
d == 38 and path == ['Daenerys', 'Viserys', 'Tyrion', 'Janos', 'Mance', 'Craster', 'Karl']
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[56], line 1
----> 1 (d, path) = shortest_path(thrones, 'Daenerys', 'Karl')
      2 d == 38 and path == ['Daenerys', 'Viserys', 'Tyrion', 'Janos', 'Mance', 'Craster', 'Karl']

TypeError: cannot unpack non-iterable NoneType object
shortest_path(thrones, 'Margaery', 'Eddard') is None
True

optimisation (optionnel / avancé)

quelque chose de louche

l’algorithme de plus court chemin que nous avons écrit jusqu’ici a surtout des avantages pédagogiques
l’intérêt est d’écrire un code qui s’écrit et se lit facilement

par contre, le lecteur affuté aura remarqué la chose suivante :

ce qui peut nous laisser penser que, dans le cas de graphes plus substanciels que nos exemples jusqu’ici, l’algorithme risque d’avoir des performances sous-optimales (c’est une litote)

un graphe plus gros

pour n=4:

exercice: pour un entier nn, écrire une fonction planar(n)
qui construit un graphe:

from data.graphs import planar1 as planar
planar(4)
{(1, 1): {(2, 1): 1, (1, 2): 1}, (1, 2): {(2, 2): 1, (1, 3): 2}, (1, 3): {(2, 3): 1, (1, 4): 3}, (1, 4): {(2, 4): 1}, (2, 1): {(3, 1): 2, (2, 2): 1}, (2, 2): {(3, 2): 2, (2, 3): 2}, (2, 3): {(3, 3): 2, (2, 4): 3}, (2, 4): {(3, 4): 2}, (3, 1): {(4, 1): 3, (3, 2): 1}, (3, 2): {(4, 2): 3, (3, 3): 2}, (3, 3): {(4, 3): 3, (3, 4): 3}, (3, 4): {(4, 4): 3}, (4, 1): {(4, 2): 1}, (4, 2): {(4, 3): 2}, (4, 3): {(4, 4): 3}, (4, 4): {}}

%timeit

on va utiliser la magic timeit:

en l’occurrence, timeit nous permet de mesurer le temps que prend une instruction
celle-ci est exécutée plusieurs fois, on prend ensuite la moyenne

pour faire la même chose en Python pur, voyez .. le module timeit

mesurons: n=10 et plus

# ça passe pas trop mal
# mais 3ms c'est quand même beaucoup pour 100 sommets

N = 10
P = planar(N)
%timeit shortest_path(P, (1, 1), (N, N))
436 ns ± 20.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

# 4 fois plus de sommets,
# trajet environ deux fois plus long
# de l'ordre de 45 ms
# et c'est de l'ordre de 16 fois plus..

N = 20
P = planar(N)
%timeit shortest_path(P, (1, 1), (N, N))
381 ns ± 25.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

# je change encore d'échelle - cette fois c'est de l'ordre de 11s ! 
# (je le commente du coup..., mais vous pouvez le réactiver)
# bref cet algo est inutilisable en vrai !

N = 80
P = planar(N)
#%timeit shortest_path(P, (1, 1), (N, N))

la notion de profiling

ce qui nous donne l’occasion de parler un peu de profiling
de quoi s’agit-il ? principalement:

la doc de référence est ici
https://docs.python.org/3/library/profile.html
cherchez la phrase

The files cProfile and profile can also be invoked as a script to profile another script. For example:

profilons

il existe aussi des magic pour cela, mais par expérience elles sont d’un abord plus aride (un comble!)

aussi on va avoir recours au terminal et à l’interpréteur;
on écrit un script slow.py qui contient ceci

slow.py
from graphs import shortest_path1, planar1

N = 30
P = planar1(N)
print(shortest_path1(P, (1, 1), (N, N)))

et maintenant on peut lancer le profiler avec cette phrase

python -m cProfile slow.py

je vous invite à lire la documentation du profiler (lien ci-dessus) pour comprendre la signification des différentes colonnes

si on veut trier le résultat selon un critère particulier on fera par exemple

python -m cProfile -s tottime slow.py

exo #6 : challenge

une fois qu’on a vu ça, voyez-vous une façon de récrire shortest_path pour ne plus tomber dans cet inconvénient ?

voici les résultats que j’obtiens à présent avec une implémentation alternative et plus efficace:

# on va voir que cette version 2 est bien plus efficace

from data.graphs import shortest_path2
# environ 500 µs, vs 3ms

N = 10
P = planar(N)
%timeit shortest_path2(P, (1, 1), (N, N))
2.28 ms ± 183 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# 3ms vs 45 ms

N = 20
P = planar(N)
%timeit shortest_path2(P, (1, 1), (N, N))
10.6 ms ± 2.13 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

# 250 ms vs 11s !
# ça devient utilisable

N = 80
P = planar(N)
%timeit shortest_path2(P, (1, 1), (N, N))
369 ms ± 84.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# 1.5s pour un graphe de 22500 noeuds
# c'est long, mais mieux que la v1 en tous cas

N = 150
P = planar(N)
%timeit shortest_path2(P, (1, 1), (N, N))
1.52 s ± 352 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
TPs classes
un petit langage d’expressions
TPs graphes
le réseau du métro parisien