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é.

Je n'indique pas ici les éventuels attributs ou méthodes privées.

Remarque : par any comprendre n'importe quel type.

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.

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.

# 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)

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

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é.

__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"].

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"].