Aller au contenu

logo

Tutoriel Simple PyGraph1⚓︎


⚠ Ce travail est en cours de modification sur pypi -- une étude est en cours pour intégrer le module à Capytale

Introduction et téléchargement⚓︎

Dès qu'on souhaite jouer un peu avec les graphes, on a envie, de façon simple :

  • créer un graphe en spécifiant le nombre de sommets
  • rajouter des arètes/arcs, aléatoirement ou pas ; en retirer
  • afficher ce graphe ie le dessiner
  • sauver le dessin de notre graphe dans un fichier
  • bouger les sommets pour améliorer le dessin
  • utiliser un algorithme connu sur notre graphe
  • ...

Cette liste n'est pas exhaustive.

Il existe deux ténors parmi les modules Python traitant de graphes :

Networkx

networkx qui est un formidable outil de manipulation de graphe au sens structure mathématique. On peut par exemple manipuler des graphes prédéfinis (aléatoires, de Petersen), connaître le degré d'un sommet, ajouter et retirer sommets et arcs etc. Appliquer des algorithmes connus (recherche de plus court chemin, coloration, etc.). On peut même faire des opérations comme l'union de graphes etc. Bref c'est un module extrêmement riche, trop dans bien des cas.

Graphviz

graphviz est le portage sous Python de l'outil Graphviz qui est un outil de dessin de graphes utilisant le langage DOT. Mais graphviz ne sert pas du tout à modéliser un graphe au sens structure mathématique.

L'idée de ce module simplepygraph est de créer un objet Graph qui soit la réunion de deux objets :

  • un model qui est un graphe au sens de networkx
  • une view qui est un graphe au sens de graphviz

Ajouté à cela un (petit) ensemble de méthodes permettant les opérations usuelles sur les graphes et en essayant de rester simple. L'outil devrait pouvoir aider tout enseignant souhaitant préparer une ressource pédagogique sur le thème des graphes.

Attention, avant d'installer ce module, il faut au préalable avoir installé l'outil GraphViz (pas le module python, l'outil, basé sur le langage dot) : graphviz. Ensuite, le plus simple reste l'installation via la commande pip :

pip3 install simplepygraph

Vous pouvez aussi télécharger le projet :

Création d'un graphe et visualisation⚓︎

Après installation, l'import du module pour utilisation se fait comme ceci :

import simplepygraph as sp

Graph(...), DiGraph(...) et BiPartite(...)⚓︎

Notre modèle propose trois type de graphes :

  • Graph : graphe non orienté aléatoire ou pas
  • DiGraph : graphe orienté
  • BiPartite : graphe bi-partie

Dans la suite nous parlerons d'un objet graphe (en italique) pour nous référer à l'un quelconque de nos trois objets. De façon analogue nous parlerons d'un objet graphviz ou networkx pour faire référence à une des versions orientée ou non orientée des graphes de ces modules.

La visualisation se fait via la propriété view qui est l'objet graphviz associé. Dans un Jupyter notebook, demander à l'interprète ipython de nous afficher le graphe va effectivement dessiner le graphe dans une cellule de sortie, ce qui est très pratique :

graphviz notebook

write(filename='output', format='svg')⚓︎

Sinon, il faut appeler la méthode qui écrit le graphe dans un fichier. Cette méthode s'appelle write, elle prend un paramètre facultatif qui est le nom du fichier. On peut aussi préciser le format d'enregistrement ('svg' qui est la valeur par défaut, 'png', 'jpg' etc.). Si on ne précise aucun nom de fichier, le fichier se nommera output.xxx ; xxx étant le format choisi.

Pour le dessin de votre graphe, l'objet graphviz se sert d'un moteur de rendu et gère seul le placement des sommets et des arcs/arètes. Nous verrons les diverses possibilités d'intervention.

Exemples⚓︎

Les graphes ci-dessous ne sont pas en tailles réelles mais réduits pour ne pas prendre trop de place.

Graphe à 5 sommets, aléatoire
>>> G1 = Graph(5, random=True)
>>> G1.view  # ou G1.write() si on n'est pas dans un notebook

G1

Nous verrons comment réorganiser la position des sommets, par exemple pour afficher ce graphe plutôt à l'horizontale.

Graphe à 4 sommets, manuel

Ici un graphe vide, pour le moment...

>>> G2 = Graph(4)
>>> G2.view  

G2 sans arètes

Ajoutons quelques arètes (nous verrons en détail plus tard cette fonctionnalité) :

>>> G2.add_edges_from([(0,1), (0,3), (1,2), (2,3)])
>>> G2.view

G2

Graphe orienté à 6 sommets, manuel

Pour l'instant, les graphes orientés ne peuvent pas être aléatoires, on doit ajouter explicitement les arcs. La raison est que mes graphes aléatoires s'appuient sur le modèle erdos_renyi_graph du module networkx qui génère un graphe non orienté.

>>> DG3 = DiGraph(6)
>>> DG3.add_edges_from([(0,1), (0,4), (1,3), (2,3), (2,4), (5,2), (4,2), (3,0)])
>>> DG3.view  

DG3

Graphe bi-partie 3, 5

Un graphe bi-partie (bipartite graph en anglais) se construit en 2 temps :

  1. construire du bi-partie complet en spécifiant le nombre de sommets de chacune des parties
  2. supprimer un certain nombre d'arètes
>>> B35 = BiPartite(6)
>>> B35.view

Le moteur par défaut n'affiche pas très bien le bi-partie complet (mais ne nous préoccupons pas de cela pour le moment):

B35 complet

Supprimons 4 arètes :

>>> B35.remove_random_edges(4)
>>> B35.view  

B35

Principe général⚓︎

Nous l'avons vu, un objet graphe repose sur un modèle et une vue. Si G désigne un graphe, alors G.model est l'objet networkx associé et G.view l'objet graphviz associé.

Dans le modèle networkx, lors de la création des sommets, on peut leur attacher des informations complémentaires via un dictionnaire. C'est ce que nous faisons. Le dictionnaire étant :

{'view': NodeView(...)}

NodeView est un objet permettant la gestion des informations pour la visualisation des sommets. On y trouvera par exemple l'étiquette du sommet, sa couleur de remplissage, les coordonnées de sa position etc.

Ensuite, toute modification du modèle du graphe va entraîner une mise à jour de la vue via cet objet NodeView.

L'attribut engine⚓︎

Il s'agit d'un attribut important des objets graphviz c'est lui qui détermine l'algorithme utilisé pour l'affichage du graphe. Par défaut le moteur utilisé par notre objet graphe sera neato. On peut préciser à la création du graphe :

>>> mon_graphe = Graph(7, random=True, engine='circo')

ou alors lors de la réinitialisation de la vue :

>>> mon_graphe.reset_view(engine='dot')

Les moteurs les plus connus sont :

Essaye de donner la même longueur à chaque arête.

neato

Essaye de faire un tri topologique donc fait des graphes allongés

dot

Disposition radiale des sommets

twopi

Disposition en cercle

circo

Positionner les sommets sur une grille⚓︎

position(iterable, ech=1), scale(ech)⚓︎

Graphviz permet de positionner les sommets de notre graphe en fournissant des coordonnées \((x, y)\) pour chacun des points.

Une méthode position exploite cette possibilité. Voici un exemple :

>>> G = Graph(6, random=True)
>>> G.view 

sans positionnement

>>> G.position([(1, -0.5, 0), (5, 0.5, 0), (0, -1.5, 0), (3, 1.5, 0), (2, -0.5, -1), (4, 0.5, -1)])
>>> G.view
positionnement 1

Un autre positionnement :

>>> G.position([(5, -0.5, 0), (1, 0.5, 1), (0, -1.5, 0), 
... (3, 0.5, 0), (2, -0.5, -1), (4, 1.5, -1)])
>>> G.view

positionnement 2

On peut changer l'écartement des sommets en utilisant le paramètre nommé ech, qui par défaut vaut 1 :

>>> G.position([(5, -0.5, 0), (1, 0.5, 1), (0, -1.5, 0), 
... (3, 0.5, 0), (2, -0.5, -1), (4, 1.5, -1)], ech=0.7)
>>> G.view

positionnement 3

La méthode position fait appelle à scale qui prend ech en paramètre et que l'on peut utiliser directement pour écarter ou resserrer un graphe déjà positionné :

>>> G.scale(1.2)
>>> G.view

positionnement 4

Attention

Le positionnement des sommets ne fonctionne pas avec le moteur dot.

Changer les étiquettes⚓︎

set_labels(str_labels), label_on()⚓︎

Par défaut, l'étiquette d'un sommet est son id version chaîne de caractère (l'id étant un entier). Par la méthode set_labels qui accepte une chaîne de caractères en paramètre, on peut personnaliser l'étiquette de chacun des sommets.

Une fois le changement fait, il faut actualiser les étiquettes en appelant la méthode label_on().

Prenons par exemple le graphe suivant :

>>> reseau = Graph(8)
>>> reseau.add_edges_from([(1, 3), (3, 2), (2, 0), (0, 3), (2, 1), 
... (4, 5), (5, 7), (7, 6), (6, 4), (7, 4), (6, 5), (2, 4), (5, 3)])
>>> reseau.position([(0,-3,1), (2, -1, 1), (4, 1, 1), (6, 3, 1), 
... (1,-3,-1), (3, -1, -1), (5, 1, -1), (7, 3, -1)], 0.5) 
>>> reseau.view

reseau anonyme

Ce graphe représentant un réseau social, un ami m'a suggérer des étiquettes plus sympas, suggérant le côté social du graphe. Voici comment faire2 :

>>> PEOPLE = '🧑🧒🧓🧔👦👧👨👩👴👵👶'
>>> reseau.set_labels(PEOPLE)
>>> reseau.label_on()
>>> reseau.view

reseau humain

label_off()⚓︎

On peut aussi masquer les étiquettes à l'affichage :

>>> reseau.label_off()
>>> reseau.view

reseau humain masque

Changer la couleur⚓︎

Chaque sommet possède dans son NodeView un numéro de couleur color_id (de type int). Par défaut, à la création du NodeView, la valeur est -1, pour la couleur blanche.

Associé à cet numérotation des couleurs, une constante COLORS est un tuple de noms de couleurs (voir par exemple la page de la documentation de graphviz à propos des couleurs). On veillera à ce que ce tuple ait toujours la couleur white en dernière valeur.

color_on(s, color), color_off()⚓︎

color_on permet à la fois d'afficher les couleurs de tous les sommets, chacun utilisant la couleur déterminée par son propre color_id et à la fois de changer la couleur d'un sommet.

Pour changer la couleur d'un sommet on peut utiliser un numéro de couleur (il s'agira de l'indice dans la constante COLORS ou un nom).

Un graphe tout blanc
>>> CG = Graph(6, random=True)
>>> CG.view

CG white

Avec un numéro de couleur
>>> CG.color_on(4, 2)
>>> CG.view

aquamarine3 sur noeud 4

Avec un nom de couleur
>>> CG.color_on(4, 'aquamarine3')
>>> CG.view

aquamarine3 sur noeud 4

Si les sommets ont une couleur (color_id différent de -1), on peut allumer les couleurs avec un appel sans argument à color_on().

On peut modifier à la main la valeur de color_id pour un nœud node_id comme ceci :

Changer le color_id d'un nœud
>>> GC.node_view(0).color_id = 3

On peut aussi utiliser un outil de colorisation du graphe. Par exemple, on pourra dans le module algorithms utiliser la méthode dsatur de la classe Coloring pour réaliser une coloration du graphe en utilisant l'algorithme DSATUR :

Colorer tout le graphe
>>> from Pygraph.algorithms import Coloring
>>> coloring = Coloring(CG)
>>> coloring.dsatur()
>>> CG.view

CG après coloration

Attention

color_on(...) ne change pas la valeur de color_id d'un sommet.

Masquer les couleurs
>>> CG.color_off()
>>> CG.view

CG blanc

Comme color_on, cette méthode ne change pas la valeur des color_id. Et un simple appel à color_on affiche les couleurs mémorisées par les color_id :

>>> CG.color_on()
>>> CG.view

CG après coloration

Le modèle⚓︎

Nous l'avons déjà évoqué en introduction, le modèle PyGraph repose sur 3 objets :

  • un graphe networkx via l'attribut model
  • un graphe graphviz via l'attribut view
  • un objet maison appelé NodeView qui sert à mémoriser les propriétés utilisées par la view lors de l'affichage. L'attribut qui référence cet objet pour chaque sommet se nomme view tout simplement. C'est cet objet pour le sommet s d'un graphe g que retourne l'appel g.node_view(s).

Les propriétés sauvegardées pour chaque sommet dans l'objet NodeView sont :

  • label la chaîne de caractère servant d'étiquette au sommet (par défaut str(node_id))
  • color_id l'identifiant de la couleur (par défaut -1)
  • pos les coordonnées de la position (par défaut None)
  • ech l'échelle à appliquer lors de placement (par défaut 1)

La création⚓︎

Nous ne reviendrons pas sur les façons de créer un graphe, nous l'avons déjà explicité dans la section Création et Visualisation

Notons tout de même la création par copie, qui conserve le positionnement et l'échelle du graphe copié :

Copie de graphe

Créons un graphe orienté...

>>> DG = DiGraph(5)
>>> DG.add_edges_from([(0,1), (1,0), (1,3), (2,3), (3,4), (4,2)])
>>> DG.view
copie graphe 1

Repositionnons les sommets...

>>> DG.position([(0, 0, 0), (1, -1, 0), (3, -2, 0), (2, -3, -0.5), (4, -3, 0.5)], 0.7)
>>> DG.view
copie graphe 2

Copions...

>>> DH = DG.copy()
>>> DH.view
copie graphe 3

Le graphe model⚓︎

Lorsqu'on crée un PyGraph, G on a alors accès à G.model qui est un graphe networkx. L'interface PyGraph utilise ce graphe et une partie des outils disponibles via networkx.

>>> G = DiGraph(5)
>>> G.model
<networkx.classes.digraph.DiGraph at 0x26d132981c0>
Autres informations sur le graphe
>>> G.number_of_nodes()
5
>>> G.number_of_edges()
0
>>> list(G.node_ids())
[0, 1, 2, 3, 4]

Ajouter des liens et des sommets⚓︎

add_edge(s1, s2), add_edges_from(iterable)⚓︎

Ajoute soit un lien spécifié par les deux sommets \(s_1\) et \(s_2\) concernés soit une série de liens pour tous les couples de l'itérable passé en paramètre.

Ajouter des arètes

>>> G = Graph(4)
>>> G.view
graphe vide

Ajouter une seule arète...

>>> G.add_edge(0, 1)
>>> G.view
ajout une arete

ou plusieurs :

>>> G.add_edges_from([(0, 2), (1, 3)])
>>> G.view
ajout d'aretes

add_nodes(nodes_count)⚓︎

L'ajout de sommets se fait en indiquant le nombre de sommets à ajouter. L'outil se charge de leur donner un identifiant en partant de l'identifiant max déjà utilisé et en incrémentant de 1 à chaque sommet ajouté. Si un sommet d'identifiant inférieur a, entre-temps été retiré, cet identifiant n'est pas réutilisé. Pour l'instant on ne peut pas non plus ajouter un sommet en spécifiant l'identifiant.

Retrait⚓︎

remove_node(s), remove_nodes_from(iterable)⚓︎

On peut spécifier un sommet ou un itérable de sommets. Les sommets sont retirés ainsi que tous les liens qui concernent les sommets retirés.

Retrait de sommets

On repart de ce graphe...

ajout d'aretes

auquel on retire le sommet 1 :

>>> G.remove(1)
>>> G.view
ajout d'aretes

On peut retirer tous les sommets :

>>> G.remove_nodes_from(list(G.node_ids()))
>>> G.number_of_nodes()
0

remove_edge(s1, s2), remove_edges_from(iterable)⚓︎

On passe un ou des couples et les arètes ou les arcs concernés sont retirés. Attention, s'il s'agit d'un graphe orienté, l'ordre dans lequel on donne les éléments du couple pour les liens a bien entendu une importance :

Retrait d'arc

On considère à nouveau le graphe orienté suivant :

graphe orienté

>>> DG.remove_edge(0, 1)
>>> DG.view
retrait arc

>>> DG.remove_edges_from([(2, 3), (3, 4)])
>>> DG.view
retraits arcs

Les algorithmes⚓︎

⚠ modification de section en cours

Le sous-module algorithms permet de manipuler deux algorithmes pour le moment : - un algorithme de coloration de graphe (DSATUR) - un algorithme de recherche de plus court chemin (DIJKSTRA)

Pour importer le sous-module :

import PyGraph.algorithms as algo

Coloration⚓︎

L'objet permettant de jouer avec la coloration de graphe se nomme Coloring.

La méthode dsatur()⚓︎

L'implantation maison de l'algorithme DSATUR.

>>> coloring = Coloring(CG)
>>> coloring.dsatur()
>>> CG.view

CG après coloration

greedy_color(strategy)⚓︎

La version networkx de l'algorithme de coloration. Une stratégie doit être choisie parmi : cette liste. Le choix DSATUR correspond à l'algorithme du même nom.


  1. Attention le projet pygraph existait avant le mien, je ne le savais pas et j'ai du changer de nom ; d'où l'apparition du suffixe simple : le nom du module est donc : simplepygraph 

  2. Les caractères unicode peuvent ne pas apparaître avec certains navigateurs. On les trouve par exemple sur cette page : unicode-table.com