Implémentation des graphes en Python

Comme nous l'avons vu dans le cours, il existe deux manières de représenter les graphes :

• en utilisant les listes d'adjacence (ou listes de successeurs),
• en utilisant des matrices d'adjacence.

Dans cette partie, nous implémenterons la structure de graphe en Python en choisissant comme paradigme la programmation orientée objet (POO).

Nous proposerons une première implémentation en utilisant une liste d'adjacence que l'on implémentera en Python sous la forme d'un dictionnaire. Nous élaborerons ensuite une seconde implémentation en utilisant une matrice d'adjacence, implémentée sous la forme d'une liste de listes.

On distinguera une structure de graphe non-orienté, et une structure de graphe orienté.

Graphe non-orienté

Type abstrait

Avant d'implémenter notre structure de graphe en Python, définissons tout d'abord le type abstrait Graphe, ainsi que les opérations qui y sont associées.

Type abstrait Graphe

Utilise : Sommet, Entier, Booléen, Liste
Opérations de base :
     \(nouveau\_graphe :~\rightarrow Graphe\)
     \(ajouter\_sommet :~Graphe \times Sommet \rightarrow Graphe\)
     \(ajouter\_arete :~Graphe \times Sommet \times Sommet \rightarrow Graphe\)
     \(supprimer\_sommet :~Graphe \times Sommet \rightarrow Graphe\)
     \(supprimer\_arete :~Graphe \times Sommet \times Sommet \rightarrow Graphe\)
Autres opérations :
     \(est\_sommet :~Graphe \times Sommet \rightarrow Booléen\)
     \(est\_arete :~Graphe \times Sommet \times Sommet \rightarrow Booléen\)
     \(ordre :~Graphe \rightarrow Entier\)
     \(degre :~Graphe \times Sommet \rightarrow Entier\)
     \(voisins :~Graphe \times Sommet \rightarrow Liste\)

Implémentation avec un dictionnaire

À faire 1

Téléchargez le fichier Python ci-dessous :

Télécharger graphe.py

Complétez chaque méthode de la classe Graphe (à l'exception de la méthode affiche qui vous est donnée.)

Test de votre classe

Dans le bloc en bas de script if __name__ == "__main__", ajoutez les instructions suivantes :

graphe = Graphe()  # création d'un nouveau graphe
graphe.ajouter_arete('A', 'B')  # ajout d'une arête entre A et B
graphe.ajouter_arete('B', 'C')  # ajout d'une arête entre B et C
graphe.ajouter_arete('C', 'D')  # ajout d'une arête entre C et D
graphe.ajouter_arete('D', 'A')  # ajout d'une arête entre D et A
graphe.ajouter_arete('A', 'C')  # ajout d'une arête entre A et C
graphe.affiche()  # afficher le graphe

Si votre programme est correct, vous devriez obtenir la visualisation suivante en exécutant votre programme :

Parcours de graphes

À faire 2

Dans votre fichier graphe.py, ajoutez une fonction parcours_largeur(self, s: str) -> list qui prend un sommet en entrée et renvoie la liste des sommets parcourus avec un parcours en largeur.
Vous écrirez cette fonction de manière itérative.

À faire 3

Ajoutez une fonction parcours_profondeur(self, s: str) -> list qui prend un sommet en entrée et renvoie la liste des sommets parcourus avec un parcours en profondeur.
Vous écrirez cette fonction de manière itérative.

À faire 4

Écrivez maintenant une fonction parcours_profondeur_rec(self, s: str) -> list qui effectue le même parcours en profondeur, mais de manière récursive.

Aide - À faire 4

    def parcours_profondeur_rec(self, s: str, visites=None) -> list:
        ''' Effectue un parcours en profondeur de manière récursive. '''

        if visites is None:  # si c'est le premier appel de la fonction,
            visites = []  # on initialise la liste des sommets visités
        ...  # ajouter le sommet s aux sommets visités
        for ... in ...:  # pour chaque sommet voisin du sommet s
            if ... not in ...:  # si le voisin courant n'a pas déjà été visité
                ...  # on parcourt récursivement ce sommet
        return ...  # on renvoie la liste des sommets visités

À faire 5

Écrire une fonction distances(self, s: str) -> dict qui renvoie le dictionnaire des distances entre un sommet s donné et chaque autre sommet du graphe, après avoir effectué un parcours en largeur.

On procédera de la manière suivante :

1. initialiser le dictionnaire des distances, contenant initialement le sommet s, auquel on associera la distance 0,
2. initialiser une file contenant initialement le sommet s,
3. tant que la file n'est pas vide :
   1. on défile la file pour récupérer un sommet,
   2. on récupère la distance associée à ce sommet,
   3. pour chaque sommet voisin du sommet défilé :
      1. si le sommet n'a pas déjà été visité, on l'ajoute au dictionnaire en lui associant la distance appropriée, et on l'enfile dans la file.
4. on renvoie le dictionnaire des distances.

Connexité, cycles et arbre

On souhaite ajouter une méthode à notre classe Graphe permettant de déterminer si un graphe est un arbre.

On rappelle qu'il faut pour cela vérifier :

• que le graphe soit connexe,
• que le graphe ne contienne aucun cycle.

À faire 6

Écrivez une fonction est_connexe(self) -> bool qui renvoie True si le graphe est connexe, et False sinon.

Pour la détection des cycles, on utilisera l'algorithme suivant, basé sur le parcours en profondeur :

On adaptera cet algorithme pour qu'il puisse fonctionner avec des sommets autres que des entiers de 0 à n, en utilisant non pas une liste de prédecesseurs mais un dictionnaire des prédecesseurs.

À faire 7

Recopiez et complétez la fonction detection_cycle suivante :

def detection_cycle(self, s: str) -> bool:
    ''' Renvoie true si un cycle atteignable par s est détecté, False sinon. '''

    pile = [s]  # création d'une pile contenant uniquement le sommet s
    pred = {s: s}  # création du dictionnaire des prédecesseurs
    # À compléter
    pass

Puisque l'on utilise un dictionnaire au lieu d'un tableau, l'instruction Si Pred[v] = -1 dans le pseudo-code, qui permet de vérifier si le sommet v n'a pas déjà été visité, sera remplacé par Si v EST DANS pred.

Graphe orienté

Type abstrait

Nous allons définir cette fois un type abstrait GrapheO, représentant un graphe orienté, ainsi que les opérations qui y seront associées.

Type abstrait Graphe

Utilise : Sommet, Entier, Booléen, Liste
Opérations de base :
     \(nouveau\_graphe :~\rightarrow Graphe\)
     \(ajouter\_sommet :~Graphe \times Sommet \rightarrow Graphe\)
     \(ajouter\_arc :~Graphe \times Sommet \times Sommet \rightarrow Graphe\)
     \(supprimer\_sommet :~Graphe \times Sommet \rightarrow Graphe\)
     \(supprimer\_arc :~Graphe \times Sommet \times Sommet \rightarrow Graphe\)
Autres opérations :
     \(est\_sommet :~Graphe \times Sommet \rightarrow Booléen\)
     \(est\_arc :~Graphe \times Sommet \times Sommet \rightarrow Booléen\)
     \(ordre :~Graphe \rightarrow Entier\)
     \(degre :~Graphe \times Sommet \rightarrow Entier\)
     \(voisins :~Graphe \times Sommet \rightarrow Liste\)

Implémentation avec une matrice d'adjacence

À faire 1

Téléchargez le fichier Python ci-dessous :

Télécharger grapheo.py

Complétez chaque méthode de la classe Graphe (à l'exception de la méthode affiche qui vous est donnée.)