NSI Terminale
Après toutes ces notions de base, place à la manipulation de graphes en Python.
Il n'y a pas de liste "figée" de primitives pour le TAD GRAPHE, tout dépend de ce dont on a besoin...
Par exemple :
GRAPHEBon, nous n'allons par réinventer la roue :
le type dict de Python est parfaitement adapté en l'état pour implémenter le TAD GRAPHE sous forme de listes d'adjacence : :
De même, un tableau de tableaux ( = matrice ) sera idéal pour implémenter un graphe sous forme de matrice d'adjacence.
Création de sommets, liste de ceux-ci, liste des sommets voisins, etc...Toutes ces fonctionnalités font partie des manipulations de base d'un dictionnaire/d'un tableau de tableaux; pas la peine de dégainer la POO ici 😎...
Nous rajouterons simplement, dans un module graphe à part, les deux fonctionnalités bien pratiques suivantes :
Comme toute implémentation de TAD, ce n'est bien entendu pas la seule possibilité; on pourrait également implémenter une liste d'adjacence par :
Disposant d'un dictionnaire représentant les listes d'adjacence d'un graphe, comment en tirer la matrice d'adjacence de ce graphe ?
Ce problème n'est pas si évident...voici un algorithme qui devrait vous aider un peu :
sommets ← liste des sommets
adjacence ← liste de listes de n x n éléments tous égaux à 0 ( n = nombre de sommets dans le graphe )
pour chaque ligne de adjacence :
id1 ← sommet correspondant à la ligne ( comment le trouver ? )
pour chaque colonne de adjacence :
id2 ← sommet correspondant à la colonne ( comment le trouver ? )
si id2 est voisin de id1 :
adjacence[ligne][colonne] = 1
Oui, c'est du O(n2) ! Pour une très grande matrice, il faudrait sans doute trouver mieux ( ça existe, mais les maths là-derrière ne sont pas au programme...).
Écrire une fonctiondict_vers_matrice qui renvoie la matrice d'adjacence d'un graphe, donné en paramètre sous forme de dictionnaire de listes d'adjacence.
Tester la fonction avec des exemples de graphes pris dans la page précédente ( par exemple ).
graphvizCe module fournit deux classes : Graph pour un graphe non orienté, et Digraph pour un graphe orienté.
from graphviz import Graph # ou Digraph
On peut alors créer un objet Graph ( ou Digraph ) :
g = Graph() # ou : g = Digraph()
Ces deux classes ont de nombreux attributs qui gèrent les propriétés du graphe, notamment le modèle de rendu du graphe qui affectera son aspect ( certains modèles donnent un
meilleur résultat visuel sur certains graphes ) ou alors le type de sortie ( format PDF ( par défaut ), PNG ou SVG par exemple avec Pyzo ).
vous pouvez consulter l'API de ces deux classes sur cette page pour plus d'informations sur les deux classes, ainsi que
celle-ci pour la présentation des différents modèles de rendu.
On peut ensuite définir la liste des sommets du graphe, passée en argument à la méthode nodes(), ou alors les définir un par un avec la méthode node():
g.nodes(['A', 'B', 'C', 'D'])
g.node('E')
Chaque sommet doit avoir un identifiant unique dans le graphe, obligatoirement sous forme d'une chaîne de caractère(s), qui constituera de plus l'étiquette par défaut du sommet lors de l'affichage du graphe.
De la même manière, on définira la liste des arêtes/des arcs avec les méthodes edges ou edge :
g.edges(['AB', 'CD']) # crée un arc A->B et un arc C->D ( des arêtes pour un objet Graph bien sûr...)
g.edge('E', 'A') # pour cette méthode, les sommets doivent être séparés.
L'ordre d'écriture des identifiants des nœuds indique le sens de l'arc dans le cas d'un graphe orienté.
Graphviz est très tolérant : la liste seule des arêtes/des arcs peut suffire pour définir le graphe !
Pour afficher le graphe, on utilise alors la méthode view :
g.view()
Cela créera le graphe et lancera le programme adapté au format de sortie choisi ( pour Pyzo, le lecteur PDF par défaut, ou en ligne, un affichage à droite de l'éditeur ).
Vous pouvez essayer ce petit code et le modifier pour prendre en main le module :
Le modèle de disposition peut être spécifié par l'argument engine de la méthode view(); par défaut, c'est le moteur dot qui est utilisé
si l'on ne précise rien.
Pour Pyzo, utilisez help() pour connaître les autres modèles; en ligne, les modèles disponibles sont circo, dot, fdp, neato, osage et twopi.
Écrire une fonction dessine_graphe qui utilise le module Graphviz pour visualiser une instance de la classe.
On partira du principe que le graphe est représenté par un dictionnaire de listes d'adjacence.
On utilisera la classe Digraph pour représenter le graphe sous forme de graphe orienté ( une arête sera donc composé de deux arcs en sens opposé entre les deux mêmes sommets ).
On pourra traiter le cas du graphe pondéré, mais dans ce cas, il faut pouvoir identifier si l'information dans les listes d’adjacence est un simple sommet, ou alors un tuple (sommet, poids).
Pour cela, on peut utiliser la fonction Python isinstance, qui renvoie un booléen indiquant si une donnée est de tel(s) type(s) ou non :
print(isinstance("abc", str))
>>> True
print(isinstance("abc", tuple))
>>> False