Implémentation des graphes

Il existe de multiples manières de représenter un graphe, selon la nature du graphe mais aussi selon la nature des opérations que l'on souhaite effectuer sur ce graphe. Quelque soit le choix retenu, on souhaite pouvoir :

utiliser des opérations de construction du graphe. Il faut pouvoir ajouter/supprimer des sommets, des arcs…
utiliser des opérations de parcours du graphe : parcourir la liste des sommets, des arcs, ou bien des arcs issus d'un sommet donné…

On commence dans un premier temps par implémenter les graphes orientés. On ne considérera que les \(1\)-graphes, c'est à dire les graphes dans lesquelles l'arc \((u, v) \in S^2\) est présent une fois au plus.

Matrices d'adjacence¶

Les sommets du graphe sont les nombres \(0, 1, \ldots, n - 1\), pour un certain entier \(n\in \mathbb{N}\). On représente le graphe à l'aide d'une matrice adj de taille \(n \times n\) (un tableau constitué de \(n\) lignes et \(n\) colonnes). Il existe un arc entre les sommets \(i\) et \(j\) du graphe si et seulement si adj[i][j] vaut True.

Matrice d'adjacence adj de \(G_1\).

On donne ci-dessous le code python du constructeur de la classe Graphe.

###

class Graphe:bksl-nl """ Un graphe représenté par une matrice d'adjacence.bksl-nl Les sommets sont les nombres 0, 1, ..., n - 1. """bksl-nl def py-undpy-undinitpy-undpy-und(self, n):bksl-nl self.n = nbksl-nl self.adj = [[False]py-strn for py-und in range(n)]bksl-nlbksl-nl def ajouterpy-undsommet(self):bksl-nl """ Graphe -> Nonetypebksl-nl Ajoute un sommet au graphe """bksl-nl passbksl-nlbksl-nl def ajouterpy-undarc(self, source, destination):bksl-nl """ Graphe, int, int -> intbksl-nl Ajoute l'arc source -> destination """bksl-nl passbksl-nlbksl-nl def supprimerpy-undsommet(self, i):bksl-nl """ Graphe, int -> Nonetypebksl-nl Supprime le sommet i du graphe. Les sommets j > i sont renommés en j - 1. """bksl-nl passbksl-nlbksl-nl def supprimerpy-undarc(self, source, destination):bksl-nl """ Graphe, int, int -> Nonetypebksl-nl Supprime l'arc source -> destination """bksl-nl passbksl-nlbksl-nl def estpy-undvoisin(self, source, destination):bksl-nl """ Graphe, int, int -> boolbksl-nl Détermine si source et destination sont voisins """bksl-nl passbksl-nlbksl-nl def sommets(self):bksl-nl """ Graphe -> [int]bksl-nl Renvoie la liste des sommets du graphe self """bksl-nl passbksl-nlbksl-nl def voisins(self, sommet):bksl-nl """ Graphe, int -> [int]bksl-nl Renvoie la liste des voisins de sommet """bksl-nl passbksl-nlbksl-nl def listepy-undarcs(self):bksl-nl """ Graphe -> [(int, int)]bksl-nl Renvoie la liste des arcs du graphe """bksl-nl passbksl-nlbksl-nl def ordre(self):bksl-nl """ Graphe -> intbksl-nl Renvoie l'ordre du graphe """bksl-nl passbksl-nlbksl-nl def taille(self):bksl-nl """ Graphe -> intbksl-nl Renvoie la taille du graphe """bksl-nl passbksl-nlbksl-nl def decrire(self):bksl-nl """ Graphe -> Nonetypebksl-nl Affiche une description du graphe self """bksl-nl passbksl-nlbksl-nl

1. Initialiser une variable g1 de type Graphe, représentant un graphe constitué des 4 somments \(0\), \(1\), \(2\), et \(3\). Initialement, aucun arc n'est présent dans le graphe g1.
2. Écrire une méthode sommets de la classe Graphe qui étant donné un graphe self renvoie la liste des sommets qui le constituent.
  1 2 3 4
  def sommets(self): """ Graphe -> [int] Renvoie la liste des sommets du graphe self """ pass
  1
  print(g1.sommets())
```
[0, 1, 2, 3]
```

Écrire une méthode ajouter_arc de la classe Graphe qui étant donné deux sommets source et destination du graphe self ajoute l'arc source \(\to\) destination au graphe self.

def ajouter_arc(self, source, destination):
    """ Graphe, int, int -> Nonetype
    Ajoute l'arc source -> destination """
    pass

À l'aide de la méthode ajouter_arcs, construire le graphe g1 de l'énoncé.

for row in g1.adj:
    print(row)          

[False, True, False, True]
[False, False, False, True]
[False, True, False, False]
[False, False, True, False]

Écrire une méthode est_voisin de la classe Graphe qui étant donné deux sommets source et destination du graphe self renvoie True si et seulement si il existe un arc reliant source à destination dans le graphe self.

def est_voisin(self, source, destination):
    """ Graphe, int, int -> bool
    Détermine si source et destination sont voisins """
    pass

print(g1.est_voisin(0, 1))          
print(g1.est_voisin(1, 0))          

True
False

Écrire une méthode voisins de la classe Graphe qui étant donné un sommet du graphe self renvoie la liste des voisins de sommet.

def voisins(self, sommet):
    """ Graphe, int -> [int]
    Renvoie la liste des voisins de sommet """
    pass

print(g1.voisins(0))          
print(g1.voisins(1))          

[1, 3]
[3]

Écrire une méthode liste_arcs de la classe Graphe qui renvoie la liste des couples (source, destination) correspondants à des arcs du graphe self.

def liste_arcs(self):
    """ Graphe -> [(int, int)]
    Renvoie la liste des arcs du graphe """
    pass

print(g1.liste_arcs())          

[(0, 1), (0, 3), (1, 3), (2, 1), (3, 2)]

Écrire une méthode ordre de la classe Graphe qui renvoie l'ordre du graphe.

Rappel. L'ordre d'un graphe est le nombre de sommets qui composent le graphe.

def ordre(self):
    """ Graphe -> int
    Renvoie l'ordre du graphe  """
    pass

print(g1.ordre())         

Écrire une méthode taille de la classe Graphe qui renvoie la taille du graphe.

Rappel. La taille d'un graphe est le nombre d'arêtes qui composent le graphe.

def taille(self):
    """ Graphe -> int
    Renvoie la taille du graphe """
    pass

print(g1.taille())          

Écrire une méthode decrire qui affiche les informations du graphe self sur le modèle donné ci-dessous.

def decrire(self):
    """ Graphe -> Nonetype
    Affiche une description du graphe self """
    pass

g1.decrire()          

Graphe d'ordre 4 et de taille 5
Sommet 0 -> 1 3
Sommet 1 -> 3
Sommet 2 -> 1
Sommet 3 -> 2

1. Écrire une méthode ajouter_sommet de la classe Graphe qui ajoute un sommet au graphe. Ainsi, si le graphe g est constitué de \(n\) sommets, alors après l'application de la méthode ajouter_sommet le graphe est constitué de \(n + 1\) sommets (le sommet ajouté est \(n\)) : la méthode ajouter_sommet modifiera à la fois l'attribut n et l'attribut adj du graphe self. Aucun arc ne sera ajouté par cette méthode.
  1 2 3 4
  def ajouter_sommet(self): """ Graphe -> Nonetype Ajoute un sommet au graphe """ pass
  1 2
  g1.ajouter_sommet() g1.decrire()
```
Graphe d'ordre 5 et de taille 5
Sommet 0 -> 1 3
Sommet 1 -> 3
Sommet 2 -> 1
Sommet 3 -> 2
Sommet 4 -> 
```
2. Écrire une méthode supprimer_arc de la classe Graphe qui supprime (si présent) l'arc reliant source à destination dans le graphe self. Cette méthode ne produira pas d'erreur dans le cas où le graphe ne contient pas l'arc (source) \(\to\) (destination).
  1 2 3 4
  def supprimer_arc(self, source, destination): """ Graphe, int, int -> Nonetype Supprime l'arc source -> destination """ pass
3. Écrire une méthode supprimer_sommet de la classe Graphe qui supprime le sommet i du graphe self. La méthode supprimer_sommet modifiera l'attribut n et l'attribut adj. Si \(j > i\) est un sommet du graphe, alors son numéro sera \(j - 1\) après application de la méthode supprimer_sommet, les sommets \(j < i\) conserveront le même numéro.
  1 2 3 4
  def supprimer_sommet(self, i): """ Graphe, int -> Nonetype Supprime le sommet i du graphe. Les sommets j > i sont renommés en j - 1. """ pass
  1 2
  g1.supprimer_sommet(2) g1.decrire()
```
Graphe d'ordre 4 et de taille 3
Sommet 0 -> 1 2
Sommet 1 -> 2
Sommet 2 -> 
Sommet 3 -> 
```

Dictionnaire d'adjacence¶

Les sommets du graphe sont quelconques (des nombres, non forcément consécutifs, des lettres, des mots, etc). On représente un graphe à l'aide d'un dictionnaire d'adjacence, noté adj. Si \(G = (S, A)\), alors les clés du dictionnaire adj seront les éléments de \(S\). La valeur associée à la clé source sera la liste des sommets destination de telles que (source, destination) \(\in A\).

Par exemple si \(G_2\) est le graphe :

Alors le dictionnaire correspondant est :

adj = {'A': ['B', 'C', 'D'],
       'B': ['D'],
       'C': ['A', 'D'],
       'D': ['E'],
       'E': ['F']
       'F': ['E', 'F']}    

On donne ci-dessous le code python du constructeur de la classe Graphe.

###

class Graphe:bksl-nl """ Un graphe représenté par un dictionnaire d'adjacence. """bksl-nl def py-undpy-undinitpy-undpy-und(self, n):bksl-nl self.n = nbksl-nl self.adj = [[False]py-strn for py-und in range(n)]bksl-nlbksl-nl def ajouterpy-undsommet(self, s):bksl-nl """ Graphe, str -> Nonetypebksl-nl Ajoute le sommet s au graphe self """bksl-nl passbksl-nlbksl-nl def ajouterpy-undarc(self, source, destination):bksl-nl """ Graphe, str, str -> Nonetypebksl-nl Ajoute l'arc source -> destination au graphe self """bksl-nl passbksl-nlbksl-nl

Toutes les questions de cette partie concernent cette classe Graphe. Les sommets seront ici des chaînes de caractère.

1. Initialiser une variable g2 de type Graphe représentant un graphe initialement vide.
2. Écrire une méthode ajouter_sommet qui ajoute un sommet s au graphe self. Initialement, aucun arc ne sort du sommet ajouté. Si le sommet est déjà présent dans le graphe, alors cette méthode ne fait rien.
  1 2 3 4
  def ajouter_sommet(self, s): """ Graphe, str -> Nonetype Ajoute le sommet s au graphe self """ pass
3. Écrire une méthode ajouter_arc de la classe Graphe qui étant donné deux sommets source et destination du graphe self ajoute l'arc source \(\to\) destination au graphe self.
  1 2 3 4
  def ajouter_arc(self, source, destination): """ Graphe, str, str -> Nonetype Ajoute l'arc source -> destination au graphe self """ pass
4. À l'aide des méthodes ajouter_sommet et ajouter_arc, construire le graphe g2 de l'énoncé.
  1
  print(g2.adj)
```
{'A': ['B', 'C', 'D'], 'B': ['D'], 'C': ['A', 'D'], 'D': ['E'], 'E': ['F'], 'F': ['E', 'F']}
```

Écrire les méthodes est_voisin, sommets, voisins, liste_arcs, ordre, taille, decrire, supprimer_arc, supprimer_sommet (dans cet ordre) de la classe Graphe (ainsi que leur signature et leur documentation).

VOUS TESTEREZ VOS MÉTHODES.

g2.decrire()       

Graphe d'ordre 6 et de taille 10
Sommet A -> B C D
Sommet B -> D
Sommet C -> A D
Sommet D -> E
Sommet E -> F
Sommet F -> E F

g2.supprimer_sommet('D')       
g2.decrire()       

Graphe d'ordre 5 et de taille 6
Sommet A -> B C
Sommet B -> 
Sommet C -> A
Sommet E -> F
Sommet F -> E F

Rappels.

Si l est un objet de type list, i un indice compatible avec la taille de la liste, et e1 un élément présent dans la liste l, e2 un élément non présent dans la liste l :

l.copy() renvoie une copie indépendante de l
e1 in l s'évalue à True ; e2 in l s'évalue à False
l.pop() supprime le dernier élément de la liste, l.pop(i) supprime l'élément d'indice i de la liste.
l.remove(e1) supprime la première occurrence de e1 dans l ; l.remove(e2) soulève une erreur
l.append(e2) ajoute l'élément e2 à la fin de la liste ; l.insert(i, e2) insère l'élément e2 à l'indice i.
enumerate(l) renvoie la liste [(i, l[i]) for i in range(len(l))]

Si d est un objet de type dict, k1 une clé présente dans le dictionnaire, v1 la valeur associée à la clé k1, k2 une clé non présente dans le dictionnaire :

d[k1] renvoie v1 ; d[k2] soulève une erreur ; d.get(k1) renvoie v1, d.get(k2) renvoie None ;
k1 in d s'évalue à True ; k2 in d s'évalue à False
d.pop(k1) supprime k1 de d et renvoie v1 ; d.pop(k2) soulève une erreur ;
d.setdefault(k1, "valeur par defaut") ne fait rien car k1 est déjà présent dans le dictionnaire, d.setdefault(k2, "valeur par défaut") associe à k2 la valeur "valeur par défaut"
d.keys() renvoie la liste des clés du dictionnaire ; d.values() renvoie la liste des valeurs du dictionnaire ; d.items() renvoie la liste des couples (clé, valeur) du dictionnaire ;

Documents¶

Implémentation des graphes (sujet)
Fichiers python :
- templates