ENPC TD1 : Python (NetworkX) et analyse de réseaux

Dans le cadre d’un enseignement sur les risques à l’Ecole Nationale des Ponts et Chaussées, j’ai élaboré une séquence de cours concernant plus spécifiquement les réseaux techniques. Ce billet propose le résumé d’une séance qui est en lien direct avec les préoccupations de ce blog, puisqu’elle traite de l’analyse de réseaux avec une bibliothèque Python nommée NetworkX. Pour reproduire ce billet, il conviendra bien entendu d’installer Python, puis les bibliothèques : Numpy, Scipy et NetworkX 1.7.

Pour ce billet, nous disposons d’un fichier Python définissant trois listes (ici). Ces listes correspondent à une modélisation simplifiée d’un graphe du réseau autoroutier français. Il convient tout d’abord d’ouvrir ce fichier dans l’IDLE Python, puis d’exécuter ce code. Il est alors possible de construire le graphe du réseau à étudier.

import networkx as nx # import de la bibliothèque networkx
g=nx.Graph() # création du graphe g
g.add_edges_from(arcs) # ajout des arcs de la liste arc au graphe
print(g.nodes()) # consultation des nœuds du graphe g

print(g.edges()) # consultation des arcs du graphe g

Plusieurs indicateurs pouvant nous servir par la suite peuvent être calculés. Pour chaque nœud, on peut ainsi calculer le degré, la centralité intermédiaire ou l’intermédiarité (betweenness), l’éloignement moyen.

deg=nx.degree(g) # calcul des degrés des nœuds du graphe g
bet=nx.betweenness_centrality(g)  # calcul des centralités
aspl=nx.average_shortest_path_length(g)

print(aspl) # consultation des éloignements moyens

Si l’on souhaite afficher le nom des villes suivant leur niveau de centralité intermédiaire, il est possible d’utiliser la bibliothèque Operator :

import operator # import de la bibliothèque operator
tri=sorted(bet.items(), reverse=True, key=operator.itemgetter(1))
for i in range(len(tri)): # boucle affichant le nom des villes

    print(villes[int(tri[i][0])])# en fonction de l’opération de tri

Pour analyser les forces et les faiblesses d’un réseau, il faut le mettre à l’épreuve. Pour cela, il existe un moyen radical : supprimer des éléments du réseau et recalculer des indicateurs calculés au préalable afin de comparer les résultats obtenus. Pour un réseau transport, l’éloignement moyen peut être considéré comme un indicateur pertinent. Afin de conserver un graphe « intact », il peut être pertinent de travailler sur un deuxième graphe créé pour être perturbé.

g2=nx.Graph() # création du graphe g2 créé pour être perturbé
g2.add_edges_from(arcs) # le graphe g2 est au départ identique au graphe g
g2.remove_node(20) # suppression du nœud 20
aspl2=nx.average_shortest_path_length(g2) # calcul sur le graphe perturbé
vul20=aspl2-aspl # comparaison des valeurs obtenues pour un même indicateur

print(vul20) # affichage du résultat correspondant à la perturbation engendrée par la suppression du nœud 20

Dès lors, il est possible de généraliser ce calcul pour l’ensemble des nœuds du réseau étudié :

vul=[] # création du tableau qui contiendra les résultats
for i in range(len(g.nodes())): # boucle de la taille du nombre de nœuds
   g2=nx.Graph() # à chaque itération, création du graphe g2 qui sera perturbé
   g2.add_edges_from(arcs) # le graphe g2 est au départ identique au graphe g
   g2.remove_node(i) # à chaque itération, suppression d’un nœud (le numéro i)
   aspl2=nx.average_shortest_path_length(g2) # calcul sur le graphe perturbé
   dif=aspl2-aspl # à chaque itération on calcule la perturbation engendrée

   vul=vul+[(i,dif)] # ajout dans le tableau de la valeur obtenue pour un nœud supprimé

Néanmoins, à partir du 8ème élément (print(vul)), une erreur se produit. En effet, retirer un ou plusieurs éléments à un réseau n’est pas une opération neutre. En l’occurrence, certains éléments, s’ils sont retirés, peuvent notamment engendrer des ruptures de connexité (des pertes de connectivité). Ici, les ruptures de connexité engendrent l’impossibilité de calculer l’éloignement moyen puisque certaines distances deviennent incalculables (ces distances tendent en fait vers l’infini). Il faut alors créer des exceptions.

vul=[] # création du tableau qui contiendra les résultats
for i in range(len(g.nodes())): # même code que ci-dessus
   if (i!=8 and i!=53): # on rajoute juste deux exceptions
      g2=nx.Graph()
      g2.add_edges_from(arcs)
      g2.remove_node(i)
      aspl2=nx.average_shortest_path_length(g2)
      dif=aspl2-aspl

      vul=vul+[(i,dif)]

Comme précédemment, il est possible de trier les résultats obtenus afin d’identifier les éléments les plus problématiques. Il apparaît alors que ces éléments sont presque identiques à ceux apparaissant comme les plus centraux.

On peut alors chercher à mesurer le degré d’intensité de la relation existant entre la « vulnérabilité » et la « centralité » d’un nœud. Pour cela, il convient de trouver un indicateur de vulnérabilité pouvant se calculer pour tous les nœuds. NetworkX propose un indicateur qui fonctionne comme nous avons procédé, mais en utilisant un indicateur de proximité (closeness) et non d’éloignement, ce qui permet de palier au problème de rupture de connexité (en effet, en s’appuyant sur les inverses des distances, les valeurs tendant vers l’infini tendent vers zéro).

import numpy
vul2=nx.closeness_vitality(g) # calcul de vulnérabilité avec networkx
mvul2=list(vul2.items()) # transforme la bibliothèque en une liste
avul2=numpy.array(mvul2) # transforme cette liste en une array
x=avul2[:,1] # la variable x correspondant à la vulnérabilité des nœuds
mbet=list(bet.items()) # transforme la bibliothèque en une liste
abet=numpy.array(mbet) # on transforme cette liste en une array
y=abet[:,1] # la variable y correspondant à la centralité des nœuds
from scipy import stats
slope, intercept, r_value, p_value, std_err = stats.linregress(x,y)
r2=r_value*r_value # calcul du r2

print(r2) # affichage du r2

A la fin, on obtient un code propre que vous pouvez télécharger ici. S’il existe un lien entre vulnérabilité et centralité, celui-ci est imparfait. On essaiera de le montrer dans un prochain billet relatif à ces enseignements.

Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website

Analyse de réseau avec QGIS 2.x

Voici un cinquième billet concernant l’analyse de réseau et QGIS (billet 1, billet 2, billet 3, billet 4), car une certaine demande semble apparemment exister. En effet, lorsque que l’on consulte les statistiques du site, les pages relatives à QGIS et à la programmation Python apparaissent parmi les pages les plus visitées (pas autant que les pages relatives à R, mais quand même…). Les plugins présentés dans ces billets sont donc régulièrement téléchargés. En outre, comme quelques mises à jour ont été effectuées (les trois premiers plugins ont notamment été regroupés et complétés), il semble nécessaire de vous proposer un nouveau lien pour le télécharger (cliquez ici pour la télécharger).

Si vous voulez disposer à tout moment de la version la plus récente du plugin, je vous conseille de télécharger la version disponible sur mon site personnel (http://serge.lhomme.pagesperso-orange.fr/dev.html). Pour installer cette extension, il vous faudra tout d’abord dézipper le dossier téléchargé, puis copier le dossier « network_analysis » dans « C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\ ». Lancez QGIS et le tour est joué !

Une seule chose est à vérifier. Lorsque vous dézippez un dossier sous Windows, il vous est proposé de l’envoyer vers un dossier du même nom. Ainsi, votre dossier « network_analysis » est lui-même dans un dossier « network_analysis ». Il faut éviter cette redondance. Ainsi, après avoir copié le dossier, vérifiez bien que votre arborescence est la suivante «C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\network_analysis» et pas «C:\Program Files\QGIS xxxx\apps\qgis\python\plugins\network_analysis\network_analysis».

Pour effectuer les calculs, il est nécessaire de disposer de deux couches d’information géographique : une première couche contenant les nœuds et une deuxième couche contenant les arcs. La couche des nœuds doit impérativement contenir les identifiants des nœuds. Il est conseillé de choisir comme identifiant des valeurs numériques allant de 1 à n (vous pouvez télécharger un exemple ici). De même, la couche des arcs doit posséder un champ « identifiant ». De surcroît, cette couche doit impérativement comporter deux champs qui renvoient aux identifiants des nœuds formant les extrémités des arcs (vous pouvez télécharger un exemple ici).

Le fonctionnement de cette extension est très simple. Premièrement, elle repose sur une décomposition en trois familles d’algorithmes : les algorithmes de base (Degree ; Closeness ; Betweenness ; Eloignement ; Clustering ; Eigenvector ; Square_clustering ; Eccentricity ; Page rank ; Average neighbor degree ; Hub_dependence) ; les algorithmes de vulnérabilité (Allongement moyen ; Closeness vitality ; Dynamique ; Combinatoire) ; un algorithme de détection de communautés (Méthode de Louvain). Vous avez accès à ces familles d’algorithmes via le menu QGIS dans « Extension → Analyse de graphe… ».

qgisv2

Après avoir choisi votre famille d’algorithmes, une boite de dialogue s’ouvre vous demandant de sélectionner votre couche contenant les nœuds et votre couche contenant les arcs. Puis, après avoir appuyé sur OK, une deuxième boite de dialogue s’ouvre permettant de renseigner les principales propriétés de votre graphe. Il est alors possible de sélectionner le champ correspondant aux nœuds de départ, le champ correspondant aux nœuds d’arrivée, d’indiquer si le graphe est orienté ou non et si le réseau est valué ou non. Si le réseau est valué, il vous faudra indiquer le champ correspondant à cette valuation. Enfin, il faut choisir l’algorithme que vous souhaitez appeler et si les résultats doivent être normalisés ou non.

boite

A l’heure actuelle tous les calculs se font sur les nœuds. A l’avenir, les calculs sur les liens seront proposés. Ainsi, une fois que vos choix ont été validés, puis les calculs exécutés, les résultats sont stockés dans la table comportant les nœuds. Grâce à QGIS, vous pouvez alors effectuer des discrétisations ou des caractérisations à partir du champ créé.

A noter que seul le calcul de vulnérabilité combinatoire diffère de ce fonctionnement général avec une boite de dialogue supplémentaire à compléter et des résultats stockés sous la forme d’une image.

Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website

Analyse (et visualisation) de réseaux avec NetworkX – 1

NetworkX est un module python dédié à l’analyse de réseaux. Déconseillé comme outil d’apprentissage, il pourrait s’avérer utile pour des personnes plus expertes, notamment pour l’analyse des réseaux bipartis où le choix reste limité (y compris dans R, le package bipartite n’intégrant guère de mesures récentes). Avant de découvrir NetworkX, il est indispensable de savoir utiliser Python (écriture et exécution d’un script .py). Il exige des centaines de ressources en ligne sur le sujet et je n’ai pas les compétences permettant d’en recommander une en particulier. Mais j’insiste : soit vous cherchez des mesures non existantes ailleurs (ex. plus courts chemins dans des graphes bipartis), vous avez des notions en programmation et l’investissement peut être rentable ; soit vous vous en sortez très bien avec vos logiciels préférés et, à moins d’animer un blog sur l’analyse de réseaux, l’investissement n’est peut-être pas tout à fait nécessaire… Je précise pour finir que je suis encore très loin de maîtriser l’outil (je n’arrive par exemple pas encore à importer des attributs pour les sommets) et que ce billet est très perfectible. Les phrases suivies d’un * sont à considérer comme de possibles erreurs de ma part…

Comment ça marche ?

Le principe est simple : écrire un script python utilisant les commandes du module NetworkX et l’exécuter. Le graphe analysé peut être créé à l’intérieur même du script ou généré à partir d’une liste de liens, et l’importation de fichiers d’autres formats sont également possibles (GEXF, GraphML, Pajek, JSON etc. voir la liste complète ici). Les résultats et les sorties graphiques peuvent être exportés pour être utilisés dans un environnement logiciel autre (format image ou vectoriel).

Comme souvent, il est possible de générer directement son réseau (sommets, liens et attributs éventuels pour les deux) dans NetworkX. Et comme presque toujours, cette option (longuement développé dans tous les tutoriels disponibles) n’a à peu près aucun intérêt dans la mesure où nos données sont déjà existantes dans un format quelconque… Je vais prendre ici le cas le plus simple – ou en tout cas, l’un des plus répandus – dans la mesure où les données sont sous la forme d’une liste de liens possédant un attribut (intensité). Représenter un sommet isolé oblige à créer une boucle.  NetworkX permet également de lire des fichiers structurés sous la forme :

a b c

b d e  etc. où le premier sommet est l’origine du lien et les sommets suivants ses voisins (fonction networkx.read_adjlist).

J’ai utilisé un format .txt et des espaces comme séparateurs pour créer un fichier liens.txt. Les attributs doivent être indiqués entre accolades. S’il n’y a pas d’attribut pour les liens, n’importe quel séparateur semble utilisable (j’ai testé avec des virgules et des points-virgules) ; par contre, s’il y a un attribut, l’espace semble être le séparateur à utiliser*. Le nom des attributs est entre apostrophes, suivi de :, puis de la valeur. S’il y a plusieurs attributs, les séparer par une virgule comme dans l’exemple ci-dessous.

a b {'weight':2, 'color':'green'}
a c {'weight':3, 'color':'green'}

Par défaut, NetworkX considère que le graphe est non orienté. Le script suivant permet d’importer le fichier, de le visualiser, d’effectuer des mesures standards, de le rendre non-orienté puis d’effectuer une nouvelle série de mesures. Le script et le fichier des liens sont téléchargeables sur github à l’adresse https://github.com/beauguitte/NetworkX_1. Je le reproduis in extenso pour les personnes ne souhaitant pas s’inscrire sur le git en question…

Exemple type

# coding: utf8
import networkx as nx
import matplotlib.pyplot as plt #pour la visualisation

#lecture d'une liste de liens
G=nx.read_edgelist("liens.txt", create_using=nx.DiGraph())

#visualisation
pos=nx.spring_layout(G)               #choix de l'algorithme
nx.draw(G, pos, with_labels=True)
plt.show()
#plt.savefig("edge_colormap.png")     #export dans un format donné

Ce qui donne à peu près ça.

plot_ networkx

#analyse
print "number of nodes : %s" % G.number_of_nodes()
print "number of edges : %s" % G.number_of_edges()
print G.in_degree()
print G.out_degree()

#passage en graphe non orienté
G=G.to_undirected()

print "degree of node a : %s" % G.degree("a") #sommet spécifique
print "degree (undirected) %s" % G.degree()   #ensemble des sommets
print "betweenness centrality %s" % nx.betweenness_centrality(G)
print "degree (normalized) %s" % nx.degree_centrality(G)

#transformer les mesures en attributs
deg = G.degree()
nx.set_node_attributes(G, 'degree', deg)

#visualisation
pos=nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
plt.show()

#recherche des cliques
cl = list(nx.find_cliques(G))
print "cliques %s" % cl

#plus courts chemins
pathlengths=[]

print("source vertex {target:length, }")
for v in G.nodes():
   spl=nx.single_source_shortest_path_length(G,v)
    print('%s %s' % (v,spl))
    for p in spl.values():
        pathlengths.append(p)
print('')
print("moyenne des plus court chemins %s" % (sum(pathlengths)/len(pathlengths)))

#distribution des plus courts chemins
dist={}
for p in pathlengths:
    if p in dist:
        dist[p]+=1
    else:
        dist[p]=1

print('')
print("length #paths")

print("densité : %s" % nx.density(G))
print("diamètre: %d" % nx.diameter(G))
print("eccentricity: %s" % nx.eccentricity(G))
print("centre : %s" % nx.center(G))
print("péripherie : %s" % nx.periphery(G))

En attendant la suite…

Sur le papier, NetworkX est plutôt séduisant pour l’analyse des graphes bipartites et/ou valués. En pratique, le coût d’entrée pour un programmateur peu avancé est assez élevé. Je compte m’acharner dessus dans les semaines à venir et proposer un billet un peu moins approximatif que celui-ci aussi vite que mes capacités d’apprentissage le permettront.

Et pour aller plus loin

Site : https://networkx.github.ioe/

La documentation disponible en ligne est exclusivement en anglais : voir par exemple la très bonne présentation de Derek Greene à cette adresse : http://mlg.ucd.ie/files/summer/tutorial.pdf

Communautés, QGIS, R (igraph) et Python…

Toujours dans la continuité des billets précédents (billet 1) (billet 2) qui présentent des plugins d’analyse de réseaux spatiaux, ce billet présente un plugin permettant d’identifier des communautés au sein de ces réseaux. En effet, ce billet permet d’aborder d’une part un sujet important de l’analyse de réseaux, l’identification de communautés, et d’autre part les relations possibles entre R et QGIS via Python, puisque la bibliothèque choisie pour ces analyses est igraph.

igraph, qui est un package réputé sous R pour l’analyse de réseaux, dispose d’une extension Python. Dans un premier temps, il s’agit d’utiliser cette extension qui permet de travailler sous QGIS avec igraph et ce indépendamment de R. Pour utiliser igraph avec Python et par conséquent QGIS, c’est néanmoins un peu plus compliqué qu’avec NetworkX, car il faut cette fois-ci compiler la bibliothèque en question. Le plus simple consiste à télécharger l’installateur Windows pour Python 2.7 (http://igraph.sourceforge.net/download.html). Une fois l’installateur lancé, il suffit de bien préciser l’emplacement de Python dans QGIS « C:/Program Files/Quantum GIS Lisboa/apps/Python27 ». Normalement, dès le premier lancement de QGIS, tout fonctionne. Il est alors possible d’importer igraph via la console Python de QGIS.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Il convient ensuite de télécharger le nouveau plugin (cliquer ici pour l’obtenir). Il faut le dézipper, puis placer le dossier dans le répertoire suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ». Il suffit alors de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de Graphe… -> Detection de communautes ». S’il n’apparaît pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Detection de communautes (version 0.1) ». Après avoir lancé le plugin, une boîte de dialogue s’ouvre. Elle permet de sélectionner les nœuds et les arcs du graphe à étudier. Après avoir validé cette première boîte de dialogue, une deuxième boîte de dialogue apparaît. Elle permet de sélectionner les champs des extrémités des arcs, de préciser si le graphe est orienté ou non, de préciser si le graphe est pondéré ou non (et si oui, quel est le champ de cette pondération : distance, flux, importance…). Enfin, différents algorithmes sont proposés afin d’identifier les communautés au sein du réseau étudié.

Présentation de la deuxième boite de dialogue.

Présentation de la deuxième boite de dialogue.

Les différents algorithmes proposés par le plugin utilisant igraph sont les suivants :

  • Walktrap, algorithme développé par Latapy et Pons et fondé sur des marches aléatoires ;
  • Betweenness, algorithme fondé sur la centralité des arcs. Les arcs les plus centraux sont retirés progressivement, chaque nouvelle composante connexe définissant alors une nouvelle communauté ;
  • Multilevel, algorithme fonctionnant par agrégation de nœuds à une communauté afin d’améliorer la modularité ;
  • Eigenvector, algorithme séparant progressivement les communautés à partir des valeurs propres du graphe ;
  • Infomap, deuxième algorithme fondé sur des marches aléatoires.

Pour chaque algorithme, seule la solution optimale est retenue (c’est-à-dire celle offrant la modularité la plus forte). C’est pourquoi le nombre de communautés n’est pas demandé avant le calcul. La valeur finale de la modularité est indiquée afin de comparer les résultats obtenus par les différents algorithmes. Une fois le calcul terminé, les valeurs stockées correspondent aux communautés auxquelles appartiennent les nœuds. Il est alors possible d’afficher ces communautés :

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Le fait d’utiliser l’extension Python de igraph interrogera sans doute quelques utilisateurs invétérés de R. Faut-il recoder en Python tous ses codes R et trouver une extension Python pour éventuellement les utiliser sous QGIS ? La réponse est non, puisqu’il est possible de faire interagir QGIS et R à l’aide notamment de la bibliothèque RPy. En effet, RPy est une interface Python pour R. Ainsi, cette interface permet en utilisant le langage Python d’interagir avec R et de bénéficier de l’ensemble des développements réalisés sous R. L’inverse est aussi possible. Pour cela, il faut repartir pour une opération de téléchargement (http://sourceforge.net/projects/rpy/files/OldFiles/) et de compilation. En partant du principe que le package igraph est bien installé sous R (il faut notamment vérifier sa présence dans « C:\Program Files\R\R-(x.xx.x)\library\ »), il est très simple d’exécuter des codes R sous QGIS et par conséquent de les exploiter. Par exemple, on va exécuter à partir de QGIS le code R suivant :

test <- function () {
library(igraph)
g <- barabasi.game(100,m=2)
eb <- edge.betweenness.community(g)
return(eb$bridges)
}

Ce code peut être sauvegardé comme étant le fichier test.r. Pour appeler ce fichier sous QGIS, il est possible d’utiliser la console Python de QGIS. Plus précisément, il suffit de taper les lignes de code suivantes :

>>> from rpy import * # Import de la bibliothèque Rpy
>>> r.source('C:/Users/serge.lhomme/Documents/R/test.r') # Chargement du fichier test.r
{'visible': False, 'value': <Robj object at 0x0CBBDA00>}
>>> resultat=r.test() # Exécution de la fonction test
Message d'avis :
package 'igraph' was built under R version 2.12.2
>>> resultat # Affichage du résultat
[198.0, 196.0, 194.0, 192.0, 190.0, 188.0, 186.0, 184.0, 182.0, 180.0, 178.0, 176.0, 174.0, 
172.0, 170.0, 169.0, 168.0, 167.0, 166.0, 165.0, 164.0, 163.0, 162.0, 161.0, 160.0, 159.0, 
158.0, 157.0, 156.0, 155.0, 154.0, 153.0, 151.0, 150.0, 149.0, 148.0, 147.0, 145.0, 144.0, 
143.0, 140.0, 138.0, 137.0, 136.0, 135.0, 134.0, 133.0, 132.0, 131.0, 130.0, 128.0, 126.0, 
124.0, 122.0, 121.0, 119.0, 118.0, 117.0, 115.0, 114.0, 112.0, 111.0, 110.0, 109.0, 108.0, 
106.0, 105.0, 104.0, 102.0, 101.0, 100.0, 98.0, 96.0, 94.0, 92.0, 90.0, 89.0, 87.0, 85.0, 
83.0, 81.0, 79.0, 77.0, 75.0, 73.0, 71.0, 69.0, 67.0, 65.0, 64.0, 62.0, 61.0, 59.0, 57.0, 
56.0, 52.0, 51.0, 47.0, 45.0]

A partir de ces simples commandes, il est possible d’appliquer ses codes R sous QGIS. Ce qui sera sans doute utile pour certains et ce qui augmente encore les possibilités offertes par QGIS.

Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website

QGIS et l’analyse de graphe

Dans un précédent billet, il a été signalé qu’il existe peu d’outils intégrés au sein des SIG permettant d’analyser les réseaux. Néanmoins, les SIG libres peuvent être combinés à d’autres logiciels, programmes ou bibliothèques accroissant ainsi leur potentialité initiale. De plus, Grass (SIG libre qui, il est vrai, n’est pas des plus commodes à appréhender) permet d’effectuer différentes mesures sur des réseaux spatiaux.
Ce billet va présenter d’une part, comment réaliser un programme sur QGIS permettant d’analyser des réseaux spatiaux en ayant recours à des bibliothèques existantes d’analyse de réseaux (en l’occurrence, des bibliothèques développées en Python). D’autre part, ce billet va présenter un plugin réalisé à cet effet.

Utiliser une bibliothèque Python avec QGIS

Le SIG libre QGIS propose une console Python permettant d’interagir avec l’ensemble des outils de QGIS et par conséquent de développer de petits programmes automatisant plusieurs tâches. Dans les faits, il est plus souvent intéressant d’utiliser les nombreuses bibliothèques Python existantes afin d’étendre les capacités de QGIS. Par exemple, il existe de nombreuses bibliothèques permettant de réaliser de l’analyse de graphe (igraph, NetworkX…). Dans ce billet, nous allons utiliser NetworkX, bibliothèque développée originalement par Aric Hagberg, Dan Schult, et Pieter Swart (http://networkx.github.com/).

Pour utiliser une bibliothèque Python dans QGIS, il faut la télécharger (voici le lien pour la télécharger [1]), puis la dézipper et enfin la placer dans le répertoire des bibliothèques Python de QGIS. Ainsi, pour la version 1.8 (Lisboa) de QGIS, le répertoire se situe dans : « C:\Program Files\Quantum GIS Lisboa\apps\Python27\Lib\site-packages » (attention cette version de QGIS n’a pas été choisie par hasard, en effet elle implémente Python 2.7 qui est nécessaire pour la dernière version de NetworkX). Toutes les bibliothèques Python déjà présentes dans QGIS se trouvent dans ce répertoire (MapPlotLib, PyQt4…). La bonne complémentarité entre QGIS et Python est ici illustrée, car il n’y a plus rien à faire. Tout est installé et il est alors possible de réaliser de l’analyse de graphe avec QGIS, alors même qu’initialement ce n’était pas le cas.

Pour vérifier, il suffit d’ouvrir QGIS, d’aller dans « Extension -> Console Python », puis de taper les lignes de code suivantes :

>>> import networkx as nx  # Import de la bibliothèque NetworkX
>>> G=nx.Graph()  # Création d’un graphe G
>>> G.add_edges_from([(1,2),(1,3)])  # Création des arcs du graph G
>>> nx.clustering(G)  # Calcul les clustering coefficient des noeuds
{1: 0.0, 2: 0.0, 3: 0.0}
>>> nx.degree(G)  # Calcul les degrés des noeuds
{1: 2, 2: 1, 3: 1}

Analyser des graphes spatiaux dans QGIS avec Python

Cette étape est un peu plus complexe que la précédente. En effet, sans même avoir une grande connaissance de Python et de QGIS, il est possible d’utiliser la bibliothèque NetworkX dans QGIS en étudiant les tutoriels (voici le lien vers les tutoriels [2]). Faire interagir Python et QGIS ajoute un niveau de difficulté supplémentaire. Ainsi, partons du fait que deux couches ont été chargées dans QGIS. La première couche est composée de nœuds caractérisés par leur identifiant (vous pouvez télécharger un exemple ici). La deuxième couche est composée d’arcs caractérisés par leur identifiant, les deux identifiants des nœuds situés aux extrémités de l’arc et leur longueur (vous pouvez télécharger un exemple ici).

L’enjeu est alors de créer le graphe « NetworkX » à partir de ces deux couches. Pour cela, il faut récupérer les attributs des couches à l’aide de Python :

>>> canvas=qgis.utils.iface.mapCanvas() # Interaction avec la carte et les couches
>>> allLayers = canvas.layers() # Récupère les deux couches chargées dans QGIS
>>> couche_noeud = allLayers[0] # Récupère la couche supérieure
>>> couche_arc = allLayers[1]  # Récupère la couche inférieure
>>> provider = couche_arc.dataProvider() # Interaction avec la couche arc
>>> field=provider.fields() # Récupère les champs de la couche arc
>>> startind=provider.fieldNameIndex(‘depart’) # Index du champ « départ »
>>> endind=provider.fieldNameIndex(‘arrivee’)   # Index du champ « arrivée »
>>> distind=provider.fieldNameIndex(‘distance_K’) # Index du champ « distance_K »
>>> feat = QgsFeature()   # Permet de manipuler les entités des couches
>>> allAttrs = provider.attributeIndexes()   # Récupère les index des entités
>>> provider.select(allAttrs)   # Sélectionne toutes les entités 
>>> table=[]  # Création d’une table qui va récupérer les informations
>>> while provider.nextFeature(feat):  # Boucle parcourant l’ensemble des entités
…     attrs = feat.attributeMap()   # Récupère tous les attributs des entités
…     attrsstart=attrs.values()[startind].toInt()[0]  # Attribut nœud de départ
…     attrsend=attrs.values()[endind].toInt()[0]  # Attribut nœud d’arrivée
…     attrsdist=attrs.values()[distind].toInt()[0] # Attribut distance
…     table=table+[(attrsstart,attrsend,attrsdist)] # Ajoute les attributs récupérés à la table

Une fois les attributs des couches permettant de créer le graphe récupérés et après les avoir collectés dans un tableau, il est possible d’analyser ce graphe à l’aide la bibliothèque NetworkX :

>>> import networkx as nx  # Import de la bibliothèque NetworkX
>>> G=nx.Graph() # Création d’un graphe G
>>> G.add_weighted_edges_from(table) # Ajout des entités de la table au graphe G
>>> b=nx.betweenness_centrality(G,weight=’weight’) # Calcul de la centralité des noeuds du graphe G

Enfin, il est possible de récupérer les résultats obtenus pour les implémenter dans la couche nœuds :

>>> provider2 = couche_noeud.dataProvider() # interaction avec les données
>>> nbcol=int(provider2.fieldCount()) # Récupère le nombre de champs de la couche
>>> from PyQt4.QtCore import *   # Import de la bibliothèque PyQt4
>>> from PyQt4.QtGui import *   # Import de la bibliothèque PyQt4
>>> provider2.addAttributes([QgsField(« centralite », QVariant.Double)])
>>> taille=len(b)  # Récupère le nombre de nœuds
>>> couche_noeud.startEditing()  # Permet l’édition de la couche nœuds
>>> for k in range(taille):  # Boucle qui parcoure l’ensemble des nœuds
…      couche_noeud.changeAttributeValue(k,nbcol,b[k+1]) # Attribution des valeurs
>>> couche_noeud.commitChanges() # Enregistrement des changements

Toutes ces lignes de commande peuvent être récupérées et réorganisées pour créer un petit programme permettant de calculer les centralités des nœuds d’un graphe spatial (lien vers un fichier zip contenant un exemple ici) :

>>> execfile(« C:/Users/XXXXX/Desktop/centralite.py »)       # Appelle le programme à exécuter

Utiliser un plugin QGIS pour analyser des graphes spatiaux

Pour développer un plugin en Python dans QGIS, des connaissances supplémentaires en programmation sont nécessaires. Elles ne seront pas développées dans ce billet. Elles peuvent être trouvées sur ce site internet. Je vais plutôt introduire un petit plugin que j’ai développé. Il n’est pas très exhaustif, mais a pour objectif de montrer ce que l’on peut obtenir en combinant QGIS et une bibliothèque Python d’analyse de graphe.

Le dossier zip à télécharger se trouve ici. Une fois le dossier téléchargé et dézippé, il faut le placer dans le répertoire des plugins Python de QGIS. Pour la version Lisboa, le répertoire est le suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ». Le plugin est alors installé. Ensuite, il suffit de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de graphe ». S’il n’apparait pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Analyse de graphe version 0.1 ». Après avoir lancé le plugin, une boite de dialogue s’ouvre. Elle permet de sélectionner les nœuds et les arcs du graphe à étudier.

Après avoir validé cette première boite de dialogue, une deuxième boite de dialogue apparait. Elle permet de sélectionner les champs des extrémités des arcs, de préciser si le graphe est orienté ou non, de préciser si le graphe est pondéré ou non (et si oui, quel est le champ de cette pondération : distance, flux, importance…). Enfin, différents indicateurs sont proposés (ceux-ci peuvent être normalisés ou non).

Le tour est joué. Ainsi, un champ a été créé dans la couche des nœuds afin de stocker les résultats de la requête. Il est alors possible de réaliser une carte thématique finale.

Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website