Étude d’un algorithme de parcours de graphes¶

Définitions¶

Soit \(G\) un graphe.

un chemin est une suite de sommets \((v_0, v_1, v_2, ...)\) tel qu’il existe une arête entre chaque paire de sommets \(v_i\) et \(v_{i+1}\)
la distance entre deux sommets \(u\) et \(v\) est la longueur du plus court chemin entre \(u\) et \(v\) (ou la somme des poids des arêtes).
On suppose ici que \(G\) est non orienté. La composante connexe d’un sommet \(u\) de \(G\) est l’ensemble des sommets atteignables depuis \(u\) en suivant un chemin dans \(G\).

L’algorithme¶

L’objectif de cette feuille est d’étudier l’algorithme suivant:

def parcours(G, u):
    """
    INPUT:
    - 'G' - un graphe
    - 'u' - un sommet du graphe
    
    OUTPUT: la liste des sommets `v` de `G`
            tels qu'il existe un chemin de `u` à `v`
    """
    marked = {u} # L'ensemble des sommets déjà rencontrés
    todo   = {u} # L'ensemble des sommets déjà rencontrés, mais pas encore traités
    
    while todo:
        # Invariants:
        # - Si `v` est dans `marked`, alors il y a un chemin de `u` à `v`
        # - Si `v` est dans `marked` et pas dans `todo`
        #   alors tous les voisins de `v` sont dans dans `marked`
        v = todo.pop()
        for w in G.neighbors_out(v):
            if w not in marked:
                marked.add(w)
                todo.add(w)
    return marked

Étude sur un exemple¶

Nous allons commencer par étudier le comportement de cet algorithme sur le graphe suivant:

from graph import examples
G = examples.parcours_directed()
G.show()

Note: Si votre classe Graph n’est pas au point, remplacez graph par graph_networkx ci-dessus.

Exercice

Copiez le graphe ci-dessus sur une feuille de papier;
Uniquement en consultant la documentation, prédire quel devrait être le résultat de l’algorithme appliqué au graphe ci-dessus avec u="D";
Vérifiez en exécutant la fonction parcours ci-dessous.

### BEGIN SOLUTION
parcours(G, "D")
### END SOLUTION

{'D', 'F', 'G', 'H'}

Visualisation¶

Nous allons maintenant visualiser l’exécution de notre algorithme. Pour cela, nous allons:

instrumenter le code en insérant des observations des variables locales aux endroits clé (comme lorsque l’on débogue avec print)
définir une visualisation de ses variables locales

Exécutez les cellules ci-dessous, jusqu’à l’appel à la fonction parcours, puis jouez avec la «télécommande» pour exécuter le code pas à pas, revenir en arrière, etc.

Note: il y a encore deux boggues: la marche arrière en continu ne fonctionne pas et les valeurs ne sont mises à jour que en pas à pas.

import copy

def parcours_visualisation(G, u):
    """
    INPUT:
    - 'G' - un graphe
    - 'u' - un sommet du graphe
    
    OUTPUT: la liste des sommets `v` de `G`
            tels qu'il existe un chemin de `u` à `v`
    """
    marked = {u} # L'ensemble des sommets déjà rencontrés
    todo   = {u} # L'ensemble des sommets déjà rencontrés, mais pas encore traités
    
    player.player.reset(copy.deepcopy(locals()))
    
    while todo:
        # Invariants:
        # - Si `v` est dans `marked`, alors il y a un chemin de `u` à `v`
        # - Si `v` est dans `marked` et pas dans `todo`
        #   alors tous les voisins de `v` sont dans dans `marked`
        v = todo.pop()
        # Observation des variables locales
        player.set_value(copy.deepcopy(locals()))
        for w in G.neighbors_out(v):
            if w not in marked:
                marked.add(w)
                todo.add(w)
                # Observation des variables locales
                player.set_value(copy.deepcopy(locals()))
        v = None
        # Observation des variables locales
        player.set_value(copy.deepcopy(locals()))
    return marked

import graph_algorithm_player
variables = [{'name':'marked', 'type':'list', 'color': 'green'},
             {'name':'todo',   'type':'list', 'color': 'red'},
             {'name':'v',      'type':'node', 'color': 'yellow'}]
player = graph_algorithm_player.GraphAlgorithmPlayer(G, variables=variables)
player

parcours_visualisation(G, "A")

{'A', 'B', 'C', 'D', 'F', 'G', 'H'}

Analyse théorique et invariants¶

Exercice: Complexité

Majorer la complexité de l’algorithme. Pour cela, choisir un modèle de complexité: opération(s) élémentaires et métrique(s) pour la taille des données en entrée. Puis considérer combien de fois chaque sommet est manipulé, combien de fois chaque arête est manipulée. Donner votre réponse ci-dessous.

L’exercice précédent a confirmé qu’il s’agissait bien d’un algorithme: il termine en un temps fini. Il reste à démontrer qu’il est correct.

Vous avez remarqué les invariants marqués en commentaires dans le code. Ce sont des propriétés qui sont sensées être vérifiées à toutes les itérations de la boucle.

Exercice Preuve de correction

Vérifiez que les invariants sont respectés à l’initialisation
Vérifiez que, à chaque itération de la boucle while, si les invariants sont respectés au début de l’itération, alors ils le sont encore à la fin
Qu’en déduisez vous par récurence?
Concluez en montrant que, s’il y a un chemin de u à v, alors v est dans marked à la fin de l’exécution de l’algorithme

Conclusion¶

Dans cette feuille, nous avons étudié un algorithme au moyen de deux outils:

L’instrumentation du code pour observer visuellement son exécution
Les invariants pour démontrer la correction de l’algorithme

Nous utiliserons systématiquement ces outils dans la suite du cours.

Les invariants sont des outils très puissants pour le programmeur. Ils jouent le même rôle que les hypothèses de récurences dans les démonstrations. Ils permettent de se convaincre après coup que les programmes sont corrects. Au moins aussi important, ce sont des guides précieux sur lesquels s’appuyer au moment de la programmation elle même. En fait, bien souvent, une fois que l’on a choisis ses invariants, l’écriture du programme est quasiment imposée.

Recommandations:

Écrivez vos programmes dans l’ordre suivant: documentation, tests, invariants, puis seulement code.

C’est l’analogue exact de la démarche en mathématiques: énoncé du théorème, exemples, hypothèse de récurence, reste de la preuve.
Dans l’exemple ci-dessus, les invariants étaient écrits dans des commentaires. Lisibles par l’homme, donc, mais inexploitable par la machine. Chaque fois que possible, exprimez vos invariants sous une forme exécutable tout en restant lisible. Cela se fait typiquement avec:
```
assert ...
```
Dans la phase de mise au point, cette forme permet de vérifier systématiquement les invariants, et d’arêter l’exécution du programme le plus tôt possible en cas de problème. Lors de la mise en production, il est possible de désactiver la vérification des asserts (option -O en Python) pour ne pas pénaliser la vitesse d’exécution.

ICMS 2020 Session: The Jupyter Environment for Computational Mathematics