C12.3 : Une classe pour les graphes

Dans les activités qui suivent, on travaillera avec la classe suivante.

class Graphe:
    """ Graphe orienté implémenté avec un dictionnaire d'adjacence"""

    def __init__(self):
        self.dicadj = {}

    def ajout_sommet(self, s):
        if s not in self.dicadj:
            self.dicadj[s] = []

    def ajout_arc(self, s1, s2):
        self.ajout_sommet(s1)
        self.ajout_sommet(s2)
        self.dicadj[s1].append(s2)

    def existe_arc(self, s1, s2):
        return s2 in self.dicadj[s1]

    def liste_sommets(self):
        return list(self.dicadj)

    def liste_voisins(self, s): # successeurs si le graphe est orienté
        return self.dicadj[s]

    def __str__(self):
        """
        Démarche pour visualiser le graphe :
            - faire un print de votre graphe
            - copier le code (qui est au format dot) qui s'affiche
            - ouvrir le lien : https://viz-js.com/
            - coller le code dans la page.
        """
        chaine = "digraph {\n"
        chaine = chaine + "\tnode [shape=circle color=\"#000\" fontname=\"arial\" fontcolor=\"#000\"]\n"
        chaine = chaine + "\tedge [color=\"#000\"]\n"
        for (sommet1,liste) in self.dicadj.items():
            for sommet2 in liste:
                chaine = chaine + "\t" + str(sommet1) + " -> " + str(sommet2) + "\n"
        chaine = chaine + "}"
        return chaine

1) Identifier l'implémentation qui a été choisie pour cette classe pour stocker les informations concernant le graphe.

2) Déterminer le rôle de chaque méthode de cette classe.

3.a) Copier/coller le code de cette classe dans un fichier qui servira de module.

3.b) Dans un fichier à part, écrire le code permettant d'importer le module puis celui permettant de créer une instance de la classe Graphe correspondant au graphe ci-dessous.

Graphe A