Introduction
Les graphes sont :
- au programme de CPGE
- visuels et adaptés à des activités débranchées chez les plus jeunes
- d’excellents supports à des activités de programmation niveau 1re et Terminale
Pour préparer cours, activités et autres supports, il faut pouvoir construire des graphes, les visualiser, les modifier, les sauver dans des fichiers pour les imprimer ou les importer dans d’autres documents.
PyGraph est un module Python permettant tout cela de façon simple surtout à travers un notebook jupyter.
PyGraph se base sur deux modules de graphes :
- networkx pour le modèle des sommets et des arcs
- graphviz pour la partie visualisation
Dans un notebook, la visualisation d’un graphe à la graphviz est très simple : il suffit de demander à ipython de nous dire ce qu’est cet objet :
Pour cela il faut bien sûr avoir installé les outils graphviz et le module python éponyme. Pour ceux et celles qui sont sous windows et anaconda la lecture de cette page devrait vous aider.
Pour les autres tout s’installe simplement via la commande pip.
Puis vous pouvez télécharger :
Téléchargements
Vous pouvez maintenant suivre le notebook.
Vous pouvez aussi lire la documentation de pygraph.
Un premier exemple...
A la rentrée universitaire 2021-2022, j’ai donné aux étudiant-es une première activité de coloration de graphe (en débranché). Le but était de réaliser une petite étude sur le type de parcours que le novice en graphe utilise.
Chaque étudiant-e avait donc une feuille de ce genre avec 6 graphes à colorier :
Au-delà de la visualisation des graphes dans mon notebook, pour, par exemple ajuster le placement des sommets, ou en vérifier la 2-coloration :
Il me fallait pouvoir manipuler mes graphes dans un script, ici pour contrôler les parcours effectués par les quelques 120 étudiant-es s’étant livré-es à l’exercice.
Grâce à un fichier json stokant les infos sur les graphes (le nombre de sommets et les arètes) :
On peut créer une liste de tous les graphes à colorier (16 au total) qui ont servi pendant cette activité :
def create_list_of_graphs():
l_graphs = [None]
with open('graphes.json') as file_in:
datas = json.load(file_in)
for nodes_count, edges in datas:
g = pygraph.Graph(nodes_count)
g.add_edges_from(edges)
l_graphs.append(g)
return l_graphs
G = create_list_of_graphs()Et manipuler ses graphes avec des fonctions pour tester divers éléments :
- Lancer la coloration des graphes :
for i in range(17):
G[i].colorise()- calculer les différents niveaux d’un parcours en largeur et vérifier que la solution de l’étudiant-e est bien un parcours en largeur :
def is_bfs(ordre, g):
ordre = [int(e, 16)-1 for e in ordre]
niveaux = g.bfs(ordre[0])
return verifier(ordre, niveaux)
>>> is_bfs('4217653', G[2])
True- Vérifier qu’une solution de coloration est correcte :
>>> verif_solution(G[8], 'B815A3', '76924') True
Un deuxième exemple...
Dans l’article Les jeux de Lewthwaite Alain nous parle de jeux dont l’une des variantes peut se modéliser et se visualiser via un graphe orienté :
La modélisation repose essentiellement sur un graphe orienté de pygraph, et de quelques méthodes pour jouer un coup.
En supposant que vous ayez téléchargé les fichiers pygraph.py et lewthwaite.py alors vous pouvez lancer (dans un notebook) :
>>> jeu = Lewthwaite(5)
>>> jeu.start()
>>> jeu.view
Jaune commence au centre, et joue 13 :
>>> jeu.play(13)
Conclusion et suite
- Pour vous lancer, comme on l’a vu il vous faut télécharger la dernière version de pygraph depuis dépôt gitlab.
- Installer notebook jupyter et les modules networkx et graphviz pour python
Suivre le tuto se trouvant sur la page gitlab tout en faisant, est probablement la meilleure solution.
Ce qu’il manque à pygraph :
- la modélisation de graphes pondérés ; pour pouvoir modéliser les algorithmes de plus court chemin notamment
- la modélisation d’autres algorithmes
Un travail d’étude et de recherche (TER) a été proposé pour le second semestre universitaire 2021—2022 avec comme buts principaux :
- Finaliser le module et en proposer une version pip
- Étudier son utilisation pour l’enseignement, notamment en proposant un certain nombre d’activités pédagogiques.
Les résultats de ce TER feront l’objet d’une communication ultérieure.
Commentaires