12. Des graphes avec classes

On va chercher à représenter un graphe, comme structure de données en la munissant de l’interface suivante :

• une méthode voisins qui renvoie les voisins d’un sommet donné

• une méthode arete qui ajoute un arc entre \(e_i\) et \(e_j\), les créant si nécessaire.

• une méthode sommet qui renvoie la liste des sommets.

class Graph:
    def __init__(self):
        self.sommetList = dict()

    def voisins(self, n):
        if n in self.sommetList:
            return self.sommetList[n]
        else:
            return None

    def ajout_arete(self,o,e):
        if o not in self.sommetList:
            self.sommetList[o] = {e: 1}
        else:
            self.sommetList[o][e] = 1
        if e not in self.sommetList:
            self.sommetList[e] = {}

    def sommet(self):
        return list(self.sommetList.keys())

    def __contains__(self,n):
        return n in self.sommetList

    def __iter__(self):
        return iter(self.sommetList.keys)

    def __repr__(self):
        return str(self.sommetList)

    def __getitem__(self, n):
        return self.voisins(n)

g = Graph()

g.ajout_arete('A','B')

g

{'A': {'B': 1}, 'B': {}}

g.ajout_arete('A','E')

g.addArete('B','C')

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[6], line 1
----> 1 g.addArete('B','C')

AttributeError: 'Graph' object has no attribute 'addArete'

g.ajout_arete('C','D')

g.ajout_arete('C','E')

g.ajout_arete('D','A')

g.ajout_arete('E','D')

g.ajout_arete('E','B')

g

{'A': {'B': 1, 'E': 1}, 'B': {}, 'E': {'D': 1, 'B': 1}, 'C': {'D': 1, 'E': 1}, 'D': {'A': 1}}

g.sommet()

['A', 'B', 'E', 'C', 'D']

g.voisins('A')

{'B': 1, 'E': 1}

g['A']

{'B': 1, 'E': 1}

'F' in g

False

g['F']