Tutoriel Simple-PyGraph¹

---

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 simple-pygraph 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.

• Télécharger via le dépôt gitlab du projet : gitlab.com/sebhoa/pygraph/
• Télécharger via Pypi : pypi.org/project/simple-pygraph/
• Installer directement : pip3 install simple-pygraph

Création d'un graphe et visualisation

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

import PyGraph.pygraph as pg

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 :

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

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  

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

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  

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):

Supprimons 4 arètes :

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

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(...)}

où 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 :

neatodottwopicirco

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

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

Disposition radiale des sommets

Disposition en cercle

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 :

Sans positionnementAvec positionnement

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

>>> 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

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

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

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

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

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 faire¹ :

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

label_off()

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

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

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

Avec un numéro de couleur

>>> CG.color_on(4, 2)
>>> CG.view

Avec un nom de couleur

>>> CG.color_on(4, 'aquamarine3')
>>> CG.view

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

Attention

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

Masquer les couleurs

>>> CG.color_off()
>>> CG.view

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

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

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

Copions...

>>> DH = DG.copy()
>>> DH.view

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

Ajouter une seule arète...

>>> G.add_edge(0, 1)
>>> G.view

ou plusieurs :

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

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...

auquel on retire le sommet 1 :

>>> G.remove(1)
>>> G.view

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 :

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

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

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

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. Les caractères unicode peuvent ne pas apparaître avec certains navigateurs. On les trouve par exemple sur cette page : unicode-table.com ↩↩