Modélisation d'un graphe à l'aide de la programmation objet

Le but est d'implémenter un graphe sous forme d'un dictionnaire où :

• chaque clé est un sommet,

• chaque valeur est la liste des sommets adjacents, ces sommets étant pondérés par le poids de l'arête (ou de l'arc) ; chaque sommet sera donc présenté dans cette liste sous la forme d'un tuple ("nom",poids).

1. Créer une classe nommé Graphes et la documenter rapidement.

   L'attribut caché __graphe contiendra les données d'un graphe sous forme d'un dictionnaire.

2. Créer le constructeur __init__(self, graphe = None) qui permet de créer soit un graphe vide par défaut, soit un graphe initialisé avec le graphe saisi comme deuxième paramètre.

3. Rajouter la méthode suivante à votre classe ; cette méthode permettra d'afficher une représentation de l'objet sur lequel s'appliquera cette méthode.

      def __repr__(self):
       """
       permet d'afficher une représentation du graphe objet (sous forme de dictionnaire).
       """
       return repr(self.__graphe)  #utilisation de la fonction native repr qui permet ceci.
                                       

4. Créer la méthode ajouter_sommet qui prend en paramètre sommet de type chaîne de caractères. cette méthode doit rajouter ce sommet comme clé du dictionnaire graphe sur lequel s'applique cette méthode si cette clé n'était pas présente dans le dictionnaire.
   Attention ! Ici, on ne rajoute que le sommet, donc la valeur de la clé rajoutée est par défaut une liste vide !

5. Créer la méthode ajouter_arc prend en paramètres :

   • sommet_origine, la clé correspondant au sommet d'origine de l'arc, de type chaîne de caractères,

   • sommet_cible, chaine de caractères correspondant au sommet de l'extrémité de l'arc,

   • poids, flottant correspondant au poids de l'arc ; par défaut, ce poids vaut 1.

   Cette méthode doit rajouter :

   • rajouter au dictionnaire graphe sur lequel s'applique cette métgode, les sommets donnés en paramètres qui ne figureraient pas encore comme clé,

   • rajouter à la clé sommet_origine comme valeur le tuple (sommet_cible,poids).

6. Tester le code déjà fait en mettant en tout fin de programme le test suivant :

   if __name__ == "__main__":
       # Point d'entrée en exécution.
       graph = Graphes()
       graph.ajouter_sommet("A")
       graph.ajouter_sommet("B")
       graph.ajouter_sommet("C")
       graph.ajouter_sommet("D")
       graph.ajouter_sommet("E")
       graph.ajouter_sommet("F")
   
       graph.ajouter_arc("A","C",5)
       graph.ajouter_arc("A","E",1)
       graph.ajouter_arc("A","F",3)
       graph.ajouter_arc("B","A",2)
       graph.ajouter_arc("B","D",5)
       graph.ajouter_arc("C","A",4)
       graph.ajouter_arc("D","A",5)
       graph.ajouter_arc("D","C",1)
       graph.ajouter_arc("D","F",3)
       graph.ajouter_arc("E","D",2)
       graph.ajouter_arc("E","F",9)
       graph.ajouter_arc("F","B",7)
   
       print("graphe initial")
       print(graph.__repr__())
                       

   Lors le l'exécution du code vous devez voir apparaître, à l'ordre près des facteurs :

   graphe initial
   {'C': [('A', 4)], 'F': [('B', 7)], 'E': [('D', 2), ('F', 9)], 'A': [('C', 5), ('E', 1), ('F', 3)], 'D': [('A', 5), ('C', 1), ('F', 3)], 'B': [('A', 2), ('D', 5)]}
                       

7. Voici ci-dessous une méthode myst :

   def myst(self,sommet_origine,sommet_cible):
           """
           supprime tous les arcs reliant sommet_origine à sommet_cible du dictionnaire représentant le graphe.
           """
           temp = self.__graphe[sommet_origine].copy()   # liste des valeurs de la clé sommet_origine
           n= len(temp)
           for elt in temp:                              # balayage de tous les valeurs de la liste : attention  tuple ("nom", poids)
               if sommet_cible == elt[0]:
                   self.__graphe[sommet_origine].remove(elt)
                       

   Déterminer le rôle de cette méthode puis changer son nom myst en un nom explicitant son rôle.

8. Proposer le destructeur suivant : une méthode supprimer_sommet qui prend en paramètres :

   • sommet, chaine de caractères correspondant au sommet à supprimer,

   • sommet_cible, chaine de caractères correspondant au sommet de l'extrémité de l'arc.

   méthode qui supprime le sommet saisi ainsi que toutes les valeurs associées à ce sommet dans le dictionnaire représentant le graphe.

   Attention ! Cette méthode doit aussi enlever les tuple où le sommet à supprimer apparaît et ce pour pour toutes les clés.

9. Tester le code déjà fait en mettant désormais en tout fin de programme le test suivant :

   if __name__ == "__main__":
       # Point d'entrée en exécution.
       graph = Graphes()
       graph.ajouter_sommet("A")
       graph.ajouter_sommet("B")
       graph.ajouter_sommet("C")
       graph.ajouter_sommet("D")
       graph.ajouter_sommet("E")
       graph.ajouter_sommet("F")
   
       graph.ajouter_arc("A","C",5)
       graph.ajouter_arc("A","E",1)
       graph.ajouter_arc("A","F",3)
       graph.ajouter_arc("B","A",2)
       graph.ajouter_arc("B","D",5)
       graph.ajouter_arc("C","A",4)
       graph.ajouter_arc("D","A",5)
       graph.ajouter_arc("D","C",1)
       graph.ajouter_arc("D","F",3)
       graph.ajouter_arc("E","D",2)
       graph.ajouter_arc("E","F",9)
       graph.ajouter_arc("F","B",7)
   
       print("graphe initial")
       print(graph.__repr__())
       print("graphe sans C")
       graph.enlever_sommet("C")
       graph.__repr__()
                       

   Lors le l'exécution du code vous devez voir apparaître, à l'ordre près des facteurs :

   graphe initial
   {'A': [('C', 5), ('E', 1), ('F', 3)], 'B': [('A', 2), ('D', 5)], 'C': [('A', 4)], 'D': [('A', 5), ('C', 1), ('F', 3)], 'E': [('D', 2), ('F', 9)], 'F': [('B', 7)]}
   graphe sans C
   {'A': [('E', 1), ('F', 3)], 'B': [('A', 2), ('D', 5)], 'D': [('A', 5), ('F', 3)], 'E': [('D', 2), ('F', 9)], 'F': [('B', 7)]}
                       

10. Proposer une méthode get_matrice qui :

    1. commence par créer la liste des sommets l_sommets du graphe, liste qui sera triée par ordre croissant.

    2. crée la matrice d'adjacence où les sommets sont rangés par ordre croissant et dont les termes correspondent au poids de l'arc éventuel partant du sommet lié à la ligne et pointant vers le sommet lié à la colonne, avec la convention de mettre 0 si un tel arc n'existe pas.

    3. renvoie la matrice d'adjacence associée au graphe sur lequel s'applique la méthode sous forme de liste de listes.

11. Tester le code déjà fait en mettant désormais en tout fin de programme le test suivant :

    if __name__ == "__main__":
        # Point d'entrée en exécution.
        graph = Graphes()
        graph.ajouter_sommet("A")
        graph.ajouter_sommet("B")
        graph.ajouter_sommet("C")
        graph.ajouter_sommet("D")
        graph.ajouter_sommet("E")
        graph.ajouter_sommet("F")
    
        graph.ajouter_arc("A","C",5)
        graph.ajouter_arc("A","E",1)
        graph.ajouter_arc("A","F",3)
        graph.ajouter_arc("B","A",2)
        graph.ajouter_arc("B","D",5)
        graph.ajouter_arc("C","A",4)
        graph.ajouter_arc("D","A",5)
        graph.ajouter_arc("D","C",1)
        graph.ajouter_arc("D","F",3)
        graph.ajouter_arc("E","D",2)
        graph.ajouter_arc("E","F",9)
        graph.ajouter_arc("F","B",7)
    
        print("graphe initial")
        print(graph.__repr__())
        print(graph.get_matrice())
        print("graphe sans C")
        graph.enlever_sommet("C")
        graph.__repr__()
        print(graph.get_matrice())
                        

    Lors le l'exécution du code vous devez voir apparaître, à l'ordre près des facteurs :

    graphe initial
    {'A': [('C', 5), ('E', 1), ('F', 3)], 'B': [('A', 2), ('D', 5)], 'C': [('A', 4)], 'D': [('A', 5), ('C', 1), ('F', 3)], 'E': [('D', 2), ('F', 9)], 'F': [('B', 7)]}
    [[0, 0, 5, 0, 1, 3], [2, 0, 0, 5, 0, 0], [4, 0, 0, 0, 0, 0], [5, 0, 1, 0, 0, 3], [0, 0, 0, 2, 0, 9], [0, 7, 0, 0, 0, 0]]
    graphe sans C
    {'A': [('E', 1), ('F', 3)], 'B': [('A', 2), ('D', 5)], 'D': [('A', 5), ('F', 3)], 'E': [('D', 2), ('F', 9)], 'F': [('B', 7)]}
    [[0, 0, 0, 1, 3], [2, 0, 5, 0, 0], [5, 0, 0, 0, 3], [0, 0, 2, 0, 9], [0, 7, 0, 0, 0]]