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

Introduction⚓︎

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

Col

Graphe G

Col

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

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

Col

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

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

Comment reconnaître, en ne regardant que la matrice d'adjacence, quels sont les sommets du graphe :

ayant uniquement des arcs sortants?
ayant uniquement des arcs entrants?

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 un arc 0 --> 2 de poids 5, du sommet 0 vers le sommet 2
mat[2][4] = 0 signifie qu'il n'existe pas d'arc du sommet 2 vers le sommet 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], 
        [0,0,0,1], 
        [0,4,0,5], 
        [0,0,1,0]]
  g1 = Graphe(m1)
  m2 = [[0,0,2,0,0],
        [3,0,0,5,0],
        [0,1,0,0,0],
        [4,0,1,0,5],
        [0,6,0,0,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
Autoriser le constructeur __init__(mat=[]) à instancier un objet graphe Orienté avec une matrice d'Adjacence non 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 successeurs(s:int)->list qui renvoie la liste de tous les sommets v successeurs de s, mais sans les poids (menant vers ces voisins) : c'est-à-dire la liste des sommets v pour lesquels il existe un arc sortant de s : s -> v
Créer une méthode predecesseurs(s:int)->list qui renvoie la liste de tous les sommets v predecesseurs de s, mais sans les poids (menant vers ces voisins) : c'est-à-dire la liste des sommets v pour lesquels il existe un arc entrant vers s : v -> s
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 tous les arcs, entrants ou sortants, 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...

Arcs Orientés⚓︎

Créer une méthode admet_arc(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 le graphe admet un arc (orienté) s -> v du sommet s vers v (quel que soit le poids)
- False sinon
Créer une méthode arcs()->list de tuples qui renvoie la liste de tous les tuples (s,v) pour lesquels s -> v est un arc qui existe
Créer une méthode ajouter_arc(s:int, v:int)->None qui permet de créer un nouvel arc s -> v du sommet s vers v
Créer une méthode supprimer_arc(s:int, v:int)->None qui permet de supprimer un arc s -> v déjà existant du sommet s vers v.
Remarque : En cas de non existence de l'arc, 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'arc s -> v (en particulier : elle renvoie 0 si l'arc s -> v n'existe pas)
Créer une méthode max_poids()->int (ou float..) qui renvoie le poids maximal d'un arc dans tout le graphe
Degré(s) d'un sommet
- Créer une méthode degre_plus(s:int)->int qui accepte en entrée un sommet s, et qui renvoie en sortie le degré positif de s : càd le nombre d'arcs sortants de s
- Créer une méthode degre_moins(s:int)->int qui accepte en entrée un sommet s, et qui renvoie en sortie le degré négatif de s : càd le nombre d'arcs entrants vers s
- Créer une méthode degre(s:int)->int qui accepte en entrée un sommet s, et qui renvoie en sortie son degre = degré_plus + degre_moins càd le nombre d'arcs sortants de s plus le nombre d'arcs entrants vers s

Liste de Successeurs⚓︎

Modifier le constructeur __init__(mat=[], liste_successeurs=[]), de sorte que :
- un graphe puisse être également instancié par une liste_successeurs=[]. Syntaxe g1 = Graphe(liste_successeurs=lv1) où lv1 est une variable contenant la liste des successeurs 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 : Sytanxe g = Graphe(mat = [...])
  - soit par une liste de successeurs : Syntaxe g = Graphe(liste_successeurs = [...])
Créer une méthode afficher_liste_successeurs() qui affiche la liste des successeurs dans un Terminal
Créer une méthode liste_vers_matrice(liste_successeurs=[]) qui reçoit en entrée la liste des successeurs 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_successeurs(). On en profite pour vérifier la symétrie de la matrice d'adjacence.
Créer une méthode mat_vers_liste_successeurs() qui peuple la liste des successeurs de l'instance courante self, à partir de la matrice d'adjacence

Dictionnaires de Successeurs⚓︎

Modifier le constructeur __init__(mat=[], liste_successeurs=[], dico_successeurs={}), de sorte que :
- un graphe puisse être également instancié par une dico_successeurs={}. Syntaxe g1 = Graphe(dico_successeurs=d1) où d1 est une variable contenant le dictionnaire des successeurs 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 : Sytanxe g = Graphe(mat = m1)
  - soit par une liste de successeurs : Syntaxe g = Graphe(liste_successeurs = lv1)
  - soit par un dictionnaire de successeurs : Syntaxe g = Graphe(liste_successeurs = d1)
Créer une méthode afficher_dico_successeurs() qui affiche le dictionnaire des successeurs dans un Terminal
Créer une méthode dico_vers_matrice() qui convertit le dictionnaire des successeurs de l'instance self, en la matrice d'adjacence de l'instance self
Créer une méthode mat_vers_dico_successeurs() qui convertit la matrice d'adjacence de l'instance self, en le dictionnaire des successeurs 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 successeurs : self.liste_successeurs
- dictionnaire des successeurs : self.dico_successeurs
Modifier la classe Graphe, de sorte que les attributs self.m, self.liste_successeurs et self.dico_successeurs soient toujours synchronisés, quelle que soit la modification (actuelle ou future) effectuée sur le graphe, en particulier :
- à chaque fois qu'une arc 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 Orienté, Pondéré, Non Étiqueté:

Col

digraph G {
  #size="3"    --> commentaire
  node [shape=circle] # pour que les noeuds du graphe
                      # soient entourés par des cercles
  5;                  # pour afficher un sommet séparé
  0 -> 1 [label=2];             # pour afficher une arête
  0 -> 2 [label=3];
  1 -> 2 [style=bold,label=4];        # Syntaxe alternative
  1 -> 2 [style=bold,color=red,label=5];        # Syntaxe alternative
  {rank=same; 1, 2}
}

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 bien renvoyer un message d'erreur adapté 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,2,3,0], 
      [0,0,0,1], 
      [0,4,0,5], 
      [0,0,1,0]]
g1 = Graphe(m1)
g1.show()   # va géénrer une image 'test.png' et la montre
```