====== Implémentation graphes ======
Je propose d'utiliser une classe pour implémenter un graphe. Il existe plusieurs possibilités. On pourrait travailler avec des nœuds reliés comme ceux d'un arbre. D'ailleurs un arbre est un graphe particulier. Dans l'exemple qui suit je propose d'utiliser plutôt un objet pour l'arbre dans son ensemble, contenant la totalité des informations surs les sommets et les arêtes.
Nous allons commencer par un graphe **non orienté** et **non pondéré** et il sera intéressant de voir ce qu'il faut changer pour obtenir un graphe orienté et / ou pondéré.
Rappel : //vertex// = sommet et //edge// = arête.
===== Diagramme UML de la classe =====
Je n'indique pas ici les éventuels attributs ou méthodes privées.
^ Graphe ^
|**Attributs**|
| //vide// |
|**Méthodes**|
| + int: order() |
| + add_vertex(label:str, data:any = None) |
| + add_edge(label_start:str, label_end:str) |
| + int: degree(label:str) |
| + list[str]: successors(label:str) |
| + list[str]: antecedents(label:str) |
| + set_data(label:str, data:any = None) |
| + any:get_data(label:str) |
| + str:%%__str__%%() |
**Remarque :** par //any// comprendre n'importe quel type.
===== Stockage des sommets =====
Je vous propose que la création d'un sommet nécessite toujours l'attribution d'une étiquette à ce sommet. Cette étiquette devra rester unique. Par ailleurs, un sommet pourra contenir des données de n'importe quel type. On pourra stocker les sommets dans un dictionnaires, par exemple :
{'A':47, 'B':85, 'C':63}
Cela correspond à un graphe avec 3 sommets étiquetés A, B, C. Ces sommets sont associés à des données qui sont ici de simple nombres.
Si on ne souhaite pas associer de donnée à un sommet, on pourra le laisser à ''None''.
===== Stockage des arêtes =====
Je vous propose d'utiliser là aussi un dictionnaire.
{'A':['B', 'C'], 'B':['A', 'D'], 'C':['A'], 'D':['B']}
''%%'A':['B','C']%%'' signifie qu'une arête A -> B et une arête A -> C. Puisque le graphe est non orienté, on a donc aussi une arête B -> A et une arête C -> A.
Il y a donc ici 4 sommets avec des arêtes A--B, A--C, B--D.
===== Le code Python =====
J'indique le type dans quelques cas. Ces indications sont optionnelles mais sont bienvenues pour faciliter la compréhension du code et aident aussi au développement. Cependant, Python dans sa version 3.7, n'est pas encore très fort pour cela. Pour indiquer qu'une fonction renvoie une ''list'' de ''str'', il faut inclure un module ''typing''. Je le fais pour l'exemple.
# module graphe
from typing import List, Any
class Graph:
def __init__(self):
self.__vertex = {}
self.__edges = {}
def order(self) -> int:
'''Renvoie l'ordre du graphe'''
# à compléter
def add_vertex(self, label:str, data:Any = None) -> None:
'''ajoute un sommet
label: étiquette du sommet
data: données à associer
précondition: cette étiquette n'est pas déjà présente
'''
# à compléter
def add_edge(self, label_start:str, label_end:str) -> None:
'''ajoute une arête, à double sens, entre deux sommets
label_start: étiquette d'un premier sommet
label_end: étiquette d'un second sommet
précondition: les deux sommets existent et ne sont pas déjà connectés
'''
# à compléter
def degree(self, label:str) -> int:
'''renvoie le degré sortant d'un sommet,
c'est à dire le nombre d'arêtes quittant un sommet
label: étiquette du sommet
précondition: le sommet existe
'''
# à compléter
def successors(self, label:str) -> List[str]:
'''successeurs d'un sommets, c'est à dire des sommets
pouvant être atteints par une arête quittant le sommet considéré.
label: étiquette du sommet dont on veut les successeurs
renvoie le tableau des étiquettes des successeurs
précondition: le sommet existe
'''
# à compléter
def antecedents(self, label:str) -> List[str]:
'''antécédents d'un sommets, c'est à dire des sommets
pouvant atteindre le sommet considéré.
label: étiquette du sommet dont on veut les successeurs
renvoie le tableau des étiquettes des successeurs
précondition: le sommet existe
'''
# à compléter
def set_data(self, label:str, data:Any=None) -> None:
'''écrit une donnée dans un sommet
label: étiquette du sommet
data: donnée à écrire. Si rien, revient à effacer.
précondition: le sommet existe
'''
# à compléter
def get_data(self, label:str) -> Any:
'''lit la donnée associée à un sommet
label: étiquette du sommet
renvoie la donnée
précondition: le sommet existe
'''
# à compléter
def __str__(self) -> str:
'''Renvoie une version texte du graphe'''
# à compléter
def __repr__(self) -> str:
'''__repr__ sert pour la console. Pour faciliter les choses,
__repr__ renverra la même chose que __str__'''
return str(self)
À vous ! Complétez ce module qui nous servira dans les travaux à venir.
===== Un graphe orienté =====
La seule différence entre un graphe orienté et un non orienté est que dans le graphe non orienté, l'ajout d'une arête A -> B entraîne automatiquement l'ajout de B -> A.
Nous allons ajouter une option à notre classe.
class Graph:
def __init__(self, **options):
self.__vertex = {}
self.__edges = {}
# vérification des options
for key in options:
assert key in ("oriented"), f"option {key} inconnue"
self.__oriented = (options.get("oriented") is "True")
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}%%''.
Voici quelques exemples d'utilisation :
>>> 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
* 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é.
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.
===== Graphe pondéré =====
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é.
== L'existant ==
''%%__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.
De plus, nous utilisons dans le programme des ''in'' et des ''for ... in'' pour parcourir les éléments des tableaux comme ''%%["B", "D"]%%''.
== Ce qu'il faudrait ==
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"%%''.
Il faut donc un dictionnaire. Au lieu de ''%%"A":["B", "D"]%%'' on aura ''%%"A":{"B":1, "D":10}%%'' (par exemple).
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"]%%''.
* 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__%%''.