10 janvier 2017 : Analyse de graphe avec QGis

La prochaine séance du groupe fmr aura lieu le mardi 10 janvier 2017 à 10h, au 13 rue du four, 5e étage, bibliothèque, Paris. Elle portera sur l’analyse de graphes planaires (mais pas seulement) avec QGIS,
Séance animée par Ryma Hachi et Serge Lhomme.

Cette séance sera décomposée en deux parties : une première partie présentera l’extension nommée « Network_analysis » (http://serge.lhomme.pagesperso-orange.fr/dev.html) ; une deuxième partie sera consacrée à l’extension « Spatial Design Network Analysis » (sDNA) (http://www.cardiff.ac.uk/sdna/).
Dans les deux cas, il faudra bien entendu vous munir d’une version de QGIS (http://www.qgis.org/fr/site/forusers/download.html). A titre d’information, la version 2.14 est parfaitement adaptée.

Pour la partie consacrée à l’extension « Network_analysis », il faudra télécharger le dossier zippé suivant : http://serge.lhomme.pagesperso-orange.fr/data/network_analysis_1_2.zip. Attention, si votre version de QGIS est un peu datée (inférieure à la version2.4), veuillez aussi télécharger ce dossier : http://serge.lhomme.pagesperso-orange.fr/data/network_analysis_1_1.zip. Pour l’installation de cette extension, c’est simple et rapide, elle pourra donc être effectuée juste avant le début de la séance (à 9h45). Les données de cette partie sont téléchargeables en suivant ce lien : https://faust.u-pec.fr/get?k=2slxm3mKYoxMmJY6L1WCette première partie permettra d’aborder les questionnements liés à la différenciation entre effets réseaux et effets spatiaux, de tester les propriétés scale-free d’un graphe, de générer et de « simplifier » des graphes spatialisés (planaires ou non planaires) à partir de données diverses.

La deuxième partie permettra d’aborder plus particulièrement le cas des réseaux intra-urbains (le réseau de rues en l’occurrence), avec la présentation de l’extension sDNA, particulièrement adaptée aux données type OpenStreetMap.
Sur cette page : http://www.cardiff.ac.uk/sdna/software/download/ vous pourrez demander un numéro de série (gratuit), puis télécharger l’extension. Il n’existe pas de version Mac, et il faut a minima QGIS 2.8.
Une fois l’extension téléchargée, son installation est relativement simple (elle pourra également être effectuée juste avant la séance).
L’extension sDNA requiert des données au format SIG (shapefile). Nous ferons un test sur le réseau de rues de Paris au XIXe siècle (données téléchargeables ici : https://filex.univ-paris1.fr/get?k=nsOl3HqSpK0ydOmKjDr). Nous verrons comment préparer le réseau, calculer des indicateurs (de centralité…), puis nous discuterons les résultats.

Pigale, logiciel pour l’analyse des graphes planaires

Logo du logiciel PigaleSi les logiciels d’analyse de graphes sont très nombreux, les logiciels dédiés à l’analyse des graphes planaires le sont beaucoup moins.

Le logiciel Pigale (Public Implementation of a Graph Algorithm Library and Editor), développé par H. de Fraysseix  et P. Ossona de Mendez, fait partie de cette catégorie peu fournie. Libre et multi-plates-formes, il présente une autre originalité : son interface est en français (voir image ci-dessous).

 

Interface du logiciel Pigale

 Il est possible soit d’importer un graphe (formats .tgf, .txt ou .graphml) soit de le dessiner directement dans la fenêtre (Fichier > Nouveau graphe). L’exportation est possible dans les 3 formats cités précédemment. Les visualisations peuvent être exportées en format image ou vectoriel (.png, .jpg, .pdf, .svg, .ps). 

 Pour dessiner un graphe, cocher l’option Ajout/Eff du menu Boutons gauche  puis cliquer dans la fenêtre graphique pour ajouter les sommets. Pour tracer un lien, cliquer sur un sommet et maintenir la pression jusqu’au sommet cible. Les liens créés sont par défaut non orientés : il est possible dans un second temps de les orienter en cochant l’option Oriente avant de cliquer sur le sommet récepteur du lien. Ainsi, pour obtenir la figure ci-dessous, je crée deux sommets (Ajout/Eff), coche le bouton Oriente puis clique sur le sommet numéro 6.

L’orientation des liens peut être générée (ou supprimée) pour l’ensemble du graphe à l’aide du menu déroulant Orienter (commandes Tout orienter et Désorienter les arêtes). Les caractéristiques du graphe dessiné s’actualisent à chaque tracé dans la fenêtre Propriétés du graphe. Les analyses possibles en fonction du graphe tracé s’actualisent également : les options en noir sont accessibles, celles en rouge ne le sont pas.

Pour supprimer un sommet ou un lien, cliquer sur l’objet en maintenant Shift enfoncé. Il est possible de modifier l’aspect du graphe (liens courbes ou lignes brisées – voir les deux représentations du même graphe ci-dessous). Enfin, trois épaisseurs de ligne sont possibles (bouton Col/Thick).

Il est également possible de générer de nombreux types de graphes dont l’image ci-dessous ne donne qu’un petit échantillon.

Générer des graphes avec Pigale

 Je n’ai pas l’impression qu’il soit possible d’allouer des attributs aux sommets et/ou aux liens. Quant à savoir si la panoplie d’outils proposée est suffisamment complète ou si elle souffre de graves lacunes, j’avoue ne pas être capable de le déterminer, n’ayant qu’exceptionnellement travaillé sur des graphes planaires. En tout cas, l’outil est facile à prendre en main et constitue sans nul doute un bon support pédagogique pour des cours sur ce type de graphes.

La version de Pigale testée ici est  la version 1.3.11 (une version 3.12 est disponible mais l’installation sous Windows est un peu pénible).

Pigale : http://sourceforge.net/projects/pigale/