TD Graphes
Non Orientés, Non Pondérés, Non Étiquetés⚓︎

Introduction⚓︎

La classe Graphe de ce TD modélise un graphe Non Orienté, Non Pondéré, et Non Étiqueté (les noms des sommets sont des nombres entiers de 0 à n-1, où n désigne le nombre total de sommets, au lieu de porter des étiquettes/noms).

Modélisation d'un graphe Non Orienté, Non Pondéré Exemple de Graphe Non Orienté, Non Pondéré, Non étiqueté

Col

Graphe G

Col

\(mat=\begin{pmatrix} 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0\\ \end{pmatrix} \)

Matrice d'adjacence du Graphe G
Non Orienté, Non Pondéré, Non étiqueté :
La Matrice est Symétrique
Les entiers de la matrice sont des 0 ou des 1
Les Sommets sont des nombres entiers

Col

# Liste de Voisins en Liste de Listes :
# pour graphes NON étiquetés exclusivement
    voisins = [[1, 2],
               [0, 2, 3, 4],
               [0, 1, 3],
               [1, 2, 4],
               [1, 3]]

# Liste de Voisins en Dictionnaire :
# pour des graphes NON étiquetés, mais
# "Généralisable" à des graphes Étiquetés
# en changeant les listes par des dicos
    voisins = {0 : [1, 2],
               1 : [0, 2, 3, 4],
               2 : [0, 1, 3],
               3 : [1, 2, 4],
               4 : [1, 3]}

Remarque

Notation Matrice d'Adjacence

Dans ce TD, les lignes de la matrice d'adjacence seront notées s, les colonnes seront notées v, ainsi : mat[s][v] = 0 ou 1
par exemple :

mat[0][2] = 1 signifie qu'il existe une arête du sommet 0 au sommet 2 et
mat[4][2] = 0 signifie qu'il n'existe pas d'arête du sommet 4 au sommet 2

Classe `Graphe` en POO⚓︎

On donne la classe incomplète Graphe suivante (à compléter) :

class Graphe:
  def __init__(self, mat=[]):
    self.m = mat
  # ... à compléter ...

if __name__ == "__main__":
  m1 = [[0,1,1,0],
        [1,0,1,1],
        [1,1,0,1],
        [0,1,1,0]]
  g1 = Graphe(m1)
  m2 = [[0,1,1,0,0],
        [1,0,1,1,1],
        [1,1,0,1,0],
        [0,1,1,0,1],
        [0,1,0,1,0]]
  g2 = Graphe(m2)

Remarque

Convention dans les questions du TD On ne précisera jamais, dans les méthodes suivantes, s'il faut inclure l'instance self, ou pas. A vous de vous adapter. Seuls les paramètres autres que self sont précisés.

Matrice d'Adjacence⚓︎

Créer une méthode afficher_matrice() qui affiche la matrice d'adjacence dans un Terminal
Créer une méthode admet_mat_symetrique() qui renvoie en sortie un booléen :
- True si la matrice d'adjacence de l'instance courante (self) est symétrique
- False sinon
Créer une méthode check_symetrie_matrice() qui :
- lève une erreur (raise) si la matrice n'est pas symétrique
- ne fait rien sinon
Modifier le constructeur __init__(mat=[]) afin que celui-ci renvoie un message d'erreur lorsque l'utilisateur tente d'intancier un objet graphe (Non Orienté) dont la matrice d'Adjacence n'est pas symétrique.

Sommets⚓︎

Créer une méthode qui renvoie l' ordre()->int du graphe (son nombre n de sommets)
Créer une méthode sommets()->list qui renvoie la liste des n sommets : une liste d'entiers de 0 à n-1
Créer une méthode voisins(s:int)->list qui renvoie la liste de tous les sommets voisins de s, mais sans les poids (menant vers ces voisins)
Créer une méthode ajouter_sommet()->None qui permet de créer un nouveau sommet. Par défaut, ce nouveau sommet ne devra être relié à aucun autre.
Créer une méthode supprimer_sommet(s:int)->None qui permet de supprimer un sommet s déjà existant.
Remarque :
- Cette méthode supprime également toutes les arêtes menant vers le sommet s à supprimer
- Cette méthode renumérote automatiquement tous les autres sommets (afin de pas créer de trous dans la numérotation des sommets).
- En cas de non existence du sommet, on pourra choisir entre deux stratégies:
  - ou bien lever une erreur (avec raise)
  - ou bien simplement ne rien faire...

Arêtes⚓︎

Créer une méthode admet_arete(s:int, v:int)->bool qui accepte en argument deux entiers/sommets s et v , et qui renvoie un booléen :
- True si les sommets s et v sont reliés par une arête
- False sinon
Créer une méthode aretes()->list de tuples qui renvoie la liste de tous les tuples (s,v) pour lesquels l'arête (s,v) existe (sans doublons)
Créer une méthode ajouter_arete(s:int, v:int)->None qui permet de créer une nouvelle arête entre les sommets s et v.
Créer une méthode supprimer_arete(s:int, v:int)->None qui permet de supprimer une arête déjà existante entre les sommets s et v. Remarque : En cas de non existence de l'arête, on pourra choisir entre deux stratégies:
- ou bien lever une erreur (avec raise)
- ou bien ne rien faire...
Créer une méthode poids(s:int,v:int)->int qui accepte en entrée deux sommets s et v, et qui renvoie en sortie le poids de l'arête s -- v (en particulier : elle renvoie 0 si l'arête s -- v n'existe pas)
Créer une méthode degre(s:int)->int qui accepte en entrée un sommet s, et qui renvoie en sortie son degré (le nombre d'arêtes reliées à s)

Liste de Voisins⚓︎

Modifier le constructeur __init__(mat=[], liste_voisins=[]), de sorte que :
- un graphe puisse être également instancié par une liste_voisins=[]. Syntaxe g1 = Graphe(liste_voisins=lv1) où lv1 est une variable contenant la liste des voisins de g1
- Configurer ensuite le constructeur de sorte qu'on ne puisse instancier un objet graphe qu'avec un seul paramètre, mais pas les deux paramètres simultanément :
  - soit par une matrice d'adjacence : Syntaxe g = Graphe(mat = [...])
  - soit par une liste de voisins : Syntaxe g = Graphe(liste_voisins = [...])
Créer une méthode afficher_liste_voisins() qui affiche la liste des voisins dans un Terminal
Créer une méthode liste_vers_matrice(liste_voisins=[]) qui reçoit en entrée la liste des voisins de l'instance self, et qui est en charge de peupler la matrice d'adjacence de l'instance self. Configurer le contructeur __init__() pour que la matrice d'adjacence soit automatiquement calculée, lorsque le paramètre choisi pour l'instanciation du graphe est la liste_voisins(). On en profite pour vérifier la symétrie de la matrice d'adjacence.
Créer une méthode mat_vers_liste_voisins() qui peuple la liste des voisins de l'instance courante self, à partir de la matrice d'adjacence

Dictionnaire de Voisins⚓︎

Modifier le constructeur __init__(mat=[], liste_voisins=[], dico_voisins={}), de sorte que :
- un graphe puisse être également instancié par une dico_voisins={}. Syntaxe g1 = Graphe(dico_voisins=d1) où d1 est une variable contenant le dictionnaire des voisins de g1
- Configurer ensuite le constructeur de sorte qu'on ne puisse instancier un objet graphe qu'avec un seul paramètre, mais pas les trois paramètres simultanément :
  - soit par une matrice d'adjacence : Syntaxe g = Graphe(mat = m1)
  - soit par une liste de voisins : Syntaxe g = Graphe(liste_voisins = lv1)
  - soit par un dictionnaire de voisins : Syntaxe g = Graphe(liste_voisins = d1)
Créer une méthode afficher_dico_voisins() qui affiche le dictionnaire des voisins dans un Terminal
Créer une méthode dico_vers_matrice() qui convertit le dictionnaire des voisins de l'instance self, en la matrice d'adjacence de l'instance self
Créer une méthode mat_vers_dico_voisins() qui convertit la matrice d'adjacence de l'instance self, en le dictionnaire des voisins de l'instance self

Synchroniser toutes les modélisations⚓︎

Modifier le constructeur __init__() et de sorte que les 3 attributs suivants soient tous initialement calculés de manière automatique et synchronisée lors de l'instanciation d'un graphe (par n'importe laquelle des 3 méthodes)
- matrice d'ajacence : self.m
- liste des voisins : self.liste_voisins
- dictionnaire des voisins : self.dico_voisins
Modifier la classe Graphe, de sorte que les attributs self.m, self.liste_voisins et self.dico_voisins soient toujours synchronisés, quelle que soit la modification (actuelle ou future) effectuée sur le graphe, en particulier :
- à chaque fois qu'une arête est créée et/ou supprimée
- à chaque fois qu'un sommet est créé et/ou supprimé

Créer une image `.png` d'un graphe, avec le Langage `dot`⚓︎

Créer une méthode toDot(filename="test.dot") qui écrit/sauvegarde un graphe G dans un fichier texte {name}.dot (par défaut test.dot), en suivant la syntaxe du langage DOT.

Exemple de Syntaxe avec le Langage DOT, et de Rendu associé, pour un graphe non orienté, non pondéré, non étiqueté:

Col

graph G {
  node [shape=circle] # pour que les noeuds du graphe
                      # soient entourés par des cercles
  5;                  # pour afficher un sommet séparé
  0 -- 1;             # pour afficher une arête
  0 -- 2;
  1 -- {2; 4};        # Syntaxe alternative
}

Code en langage dot

Col

Rendu Image du code dot précédent

Créer une méthode extraire_nom_sans_extension(filename="test.dot":str)->str, qui accepte en entrée une chaîne de caractère filename qui doit être sous la forme nom_de_fichier.dot et qui renvoie en sortie la même chaîne de caractère nom_de_fichier mais sans l'extension.dot Cette méthode extraire_nom_sans_extension(filename="test.dot":str)->str devra en outre :
- vérifier que le filename transmis en argument est bien un objet de type str, sinon lever une erreur (par exemple avec un assert)
- vérifier que l'extension de la chaîne est bien de la forme, .dot, ou renvoyer un message d'erreur adpaté pour corriger cela

(aucun code à produire dans cette question) Cette question fait la supposition que PyQt5 est installé sur votre ordinateur (c'est le cas au Lycée)
La méthode suivante, nommée renderPicture(filename="test.dot"), est une méthode offerte gracieusement qui :

Transforme le fichier texte filename={name}.dot (par défaut filename=test.dot) en une image {name}.png (par défaut test.png).
Affiche/Visualise le fichier image test.png du graphe, en lançant automatiquement la fenêtre graphique.

def renderPicture(self, filename="test.dot"):
  name = self.extraire_nom_sans_extension(filename)
  import os
  os.system(f"dot -Tpng {name}.dot -o {name}.png")
  from PyQt5 import QtGui, QtWidgets
  app = QtWidgets.QApplication([])
  window = QtWidgets.QWidget()
  HLayout = QtWidgets.QHBoxLayout()
  pixmap = QtGui.QPixmap(name)
  label = QtWidgets.QLabel()
  label.setPixmap(pixmap)
  HLayout.addWidget(label)
  window.setLayout(HLayout)
  window.setWindowTitle("Mon Beau Graphe!")
  window.show()
  app.exec_()

Créer une méthode show(name="test") qui fait le-tout-en-un :
- la méthode show() crée le fichier {name}.dot (par défaut test.dot), grâce à la méthode toDot()
- puis, la méthode show() convertit le fichier {name}.dot (par défaut test.dot) en {name}.png (par défaut test.png), grâce à la méthode renderPicture()
- Elle affiche donc un graphe avec la syntaxe suivante:
```
m1 = [[0,1,1,0],
      [1,0,1,1],
      [1,1,0,1],
      [0,1,1,0]]
g1 = Graphe(m1)
g1.show()   # va générer une image 'test.png' et la montre
```