Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:graphes:implementation [2021/12/09 20:26] – ↷ Page déplacée de graphes:implementation à nsi:terminales:graphes:implementation goupillwiki
+++ nsi:terminales:graphes:implementation [2021/12/16 18:51] (Version actuelle) – goupillwiki
@@ Ligne 145: / Ligne 145: @@
 <code python linenums:4>
 class Graph:
-    def __init__(self, oriented:bool=False):
+    def __init__(self, **options):
         self.__vertex = {}
         self.__edges = {}
-        self.__oriented = oriented
+        # vérification des options
+        for key in options:
+            assert key in ("oriented"), f"option {key} inconnue"
+        self.__oriented = (options.get("oriented") is "True")
 </code>
-Quand ''oriented == False'', le graphe n'est pas orienté. Quand ''oriented = True'', il est orienté.
-<WRAP box>Modifiez la méthode ''add_edge'' pour tenir compte de l'attribut ''%%__oriented%%''. Si besoin, modifiez aussi ''%%__str__%%''.</WRAP>
+Le ''%%**options%%'' est appelé //kwargs//. Il permettra d'écrire directement l'option désirée, par exemple ''Graph(oriented = True)'' ce qui produira automatiquement le dictionnaire ''%%options = {"oriented": True}%%''.
-<WRAP tip>Choisir de rendre ''__oriented'' privé empêche toute modification incontrôlée de l'attribut. Ainsi, un graphe créé orienté ne peut pas devenir non orienté en cours d'utilisation.</WRAP>
+Voici quelques exemples d'utilisation :
-===== Graphe pondéré =====
+<code python>
+>>> g = Graph()                 # c'est un graphe non-orienté
+>>> g = Graph(oriented = False) # idem
+>>> g = Graph(oriented = True)  # c'est un graphe orienté
+>>> g = Graph(machin = True)
+AssertionError, option machin inconnue
+</code>
-L'ajout d'une pondération est plus compliqué et ne va pas se résoudre simplement par une option.
+<WRAP box>
+  * Modifiez la méthode ''add_edge'' pour tenir compte de l'attribut ''%%__oriented%%''. Si besoin, modifiez aussi ''%%__str__%%''.
+  * Prévoir l'ajout d'un argument ''out'', par défaut à ''True'', à la méthode ''degree''. Quand ''out'' est ''True'', le degré renvoyé est le degré sortant. Quand ''out'' est ''False'', il s'agit du degré entrant. ''out'' ne doit pas avoir d'effet dans le cas non-orienté.
+</WRAP>
-On souhaite alors créer une nouvelle classe ''WGraph'', variante pondérée de ''Graph''. On peut bien sûr recopier tout le code de la classe ''Graph'' et faire les adaptations nécessaires . Mais c'est un mauvaise méthode : Supposez que vous souhaitiez faire un rectificatif. Vous risquez de devoir faire la correction dans les deux classes, donc double travail.
+<WRAP tip>Choisir de rendre ''%%__oriented%%'' privé empêche toute modification incontrôlée de l'attribut. Ainsi, un graphe créé orienté ne peut pas devenir non orienté en cours d'utilisation.</WRAP>
-Je vous propose d'exploiter l'**héritage** des classes.
+===== Graphe pondéré =====
-<code python linenums:1>
+Nous allons procéder de même pour la pondération en prévoyant une option ''weighted''.Cette fois c'est un peu plus compliqué.
-# module wgraph
-from graph import Graph #import de la classe déjà créée
+== L'existant ==
-class WGraph(Graph):
+''%%__edges%%'' est un dictionnaire où apparaissent les sommets en tant que clés, associés à des tableaux. Par exemple ''%%{"A":["B", "D"], ...}%%'' pour les connexions A->B, A->D.
-    '''
-    WGraph hérite de Graph.
-    On est libre de modifier ou d'ajouter des attributs / méthodes
-    '''
-    def add_edge(self, label_start:str, label_end:str, weight:int) -> None:
-        '''Cette méthode est différente. On la redéfinit'''
-        # à compléter
-</code>
-Dans ce code, ''WGraph'' hérite de ''Graph'' : tout ce qui est défini dans ''Graph'' se retrouve à l'identique dans ''WGraph''. Si on modifie quelque chose dans ''Graph'', la modification est répercutée automatiquement dans ''WGraph''. Bien sûr, ''WGraph'' ne doit pas rester identique à ''Graph'' -- sinon quel intérêt ? -- et on peut écrire dans ''WGraph'' de nouveaux attributs ou méthodes.
+De plus, nous utilisons dans le programme des ''in'' et des ''for ... in'' pour parcourir les éléments des tableaux comme ''%%["B", "D"]%%''.
-Dans cette nouvelle classe, il ne suffit plus d'indiquer quel sommet est connecté à quel autre, il faut aussi donner une pondération. Je propose de procéder ainsi (avec un exemple) :
+== Ce qu'il faudrait ==
-<code python>
+Il faudrait pouvoir associer à chaque connexion un poids. Donc au lieu de juste écrire ''%%["B", "D"]%%'', on voudrait que soit associé un poids à ''%%"B"%%'' et un poids à ''%%"D"%%''.
-{'A':{'B':50, 'C':10}, 'B':{'A':50, 'D':20}, 'C':{'A':10}, 'D':{'B':20}}
-</code>
+Il faut donc un dictionnaire. Au lieu de ''%%"A":["B", "D"]%%'' on aura ''%%"A":{"B":1, "D":10}%%'' (par exemple).
-Dans cet exemple, A et B sont reliés par une arête de poids 50.
+Grâce à la syntaxe très régulière de Python, on n'aura pas grand chose à changer. En effet, un ''in'' ou un ''for ... in'' ou même un ''len'' sur ''%%{"B":1, "D":10}%%'' portera sur les clés et aura donc le même effet que sur ''%%["B", "D"]%%''.
-<WRAP box>Complétez la classe ''WGRaph'' en ne redéfinissant que le strict nécessaire.</WRAP>
+<WRAP box>
+  * Modifiez la classe ''Graph'', notamment la structure de ''%%__edges%%'' pour permettre l'ajout de pondération,
+  * La pondération par défaut sera ''1'',
+  * prévoir l'ajout d'une option ''weighted'' dans l'initialisation,
+  * modifiez ''add_edge'' en adoptant cette signature :\\ ''add_edge(self, label_start:str, label_end:str, w = 1)''\\ on ne permettra pas un poids différent de ''1'' si le graphe n'est pas pondéré.
+  * Adaptez la réponse de ''successors'' qui doit toujours rester un tableau.
+  * Adaptez la fonction ''%%__str__%%''.
+</WRAP>