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

Introduction⚓︎

La classe Graphe de ce TD modélise un graphe Non Orienté, 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é, Pondéré Exemple de Graphe Non Orienté, Pondéré, Non Étiqueté

Col

Graphe G

Col

\(mat=\begin{pmatrix} 0 & 5 & 2 & 4 & 0\\ 5 & 0 & 1 & 3 & 0\\ 2 & 1 & 0 & 1 & 2\\ 4 & 3 & 1 & 0 & 1\\ 0 & 0 & 2 & 1 & 0\\ \end{pmatrix} \)

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

Col

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

# Liste de Voisins en Dictionnaire V1 :
# pour des graphes NON étiquetés, mais
# Généralisable à des graphes Étiquetés
voisins = {0 : {1:5, 2:2, 3:4},
           1 : {0:5, 2:1, 3:3},
           2 : {0:2, 1:1, 3:1, 4:2},
           3 : {0:4, 1:3, 2:1, 4:1},
           4 : {2:2, 3:1} }

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, les poids p, ainsi :
mat[s][v] = p par exemple :

mat[0][2] = 5 signifie qu'il existe une arête du sommet 0 à 2, avec un poids 5
mat[2][4] = 0 signifie qu'il n'existe pas d'arête du sommet 2 à 4

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,2,3,0], 
        [2,0,4,1], 
        [3,4,0,5], 
        [0,1,5,0]]
  g1 = Graphe(m1)
  m2 = [[0,5,2,4,0],
        [5,0,1,3,0],
        [2,1,0,1,2],
        [4,3,1,0,1],
        [0,0,2,1,0]]
  g2 = Graphe(m2)

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 de tous les n sommets du graphe : 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 (la ligne) et v (la colonne), 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,p) (sans doublons) pour lesquels l'arête (s,v) existe et son poids vaut p
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 max_poids()->int (ou float..) qui renvoie le poids maximal d'une arête dans tout le graphe
Créer une méthode degre(s: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 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 affiche_liste_voisins() qui affiche la liste des voisins dans un Terminal
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

Dictionnaires 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 affiche_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é, Pondéré, Non Étiqueté:

Col

graph G {
#size="3"    --> commentaire
node [shape=circle]
5;                   # pour afficher un sommet séparé
0 -- 1 [label=2];    # pour afficher une arête avec poids
0 -- 2 [label=3];
1 -- 2 [style=bold,label=4];
1 -- 4 [style=bold,color=red,label=5];
{rank=same; 1, 2}    # sommets 1 et 2 à la même hauteur
}

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)
  print("name = ",name)
  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.dot), 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éénrer une image 'test.png' et la montre
```