Bibliothèque d’analyse de réseau¶

Information générale¶

Voici un résumé d’un cas d’utilisation typique:

1. créer un graphe depuis les données géographiques (en utilisant une couche vecteur de polylignes)

2. lancer une analyse de graphe

3. utiliser les résultats d’analyse (pour les visualiser par exemple)

Construire un graphe¶

La première chose à faire est de préparer les données d’entrée, c’est à dire de convertir une couche vecteur en graphe. Les actions suivantes utiliseront ce graphe et non la couche.

Comme source de données, on peut utiliser n’importe quelle couche vecteur de polylignes. Les nœuds des polylignes deviendront les sommets du graphe et les segments des polylignes seront les arcs du graphes. Si plusieurs nœuds ont les mêmes coordonnées alors ils composent le même sommet de graphe. Ainsi, deux lignes qui ont en commun un même nœud sont connectées ensemble.

Pendant la création d’un graphe, il est possible de “forcer” (“lier”) l’ajout d’un ou de plusieurs points additionnels à la couche vecteur d’entrée. Pour chaque point additionnel, un lien sera créé: le sommet du graphe le plus proche ou l’arc de graphe le plus proche. Dans le cas final, l’arc sera séparé en deux et un nouveau sommet sera ajouté.

Les attributs de la couche vecteur et la longueur d’un segment peuvent être utilisés comme propriétés du segment.

La conversion d’une couche vecteur en graphe est réalisée en utilisant un Constructeur de motifs de programmation. Un graphe est construit en utilisant un élément appelé Directeur. Pour l’instant, il n’y a qu’un seul Directeur: QgsLineVectorLayerDirector. Le directeur créé les paramètres de base qui seront utilisés pour la construction d’un graphe à partir d’une couche vecteur de ligne, utilisée par le Constructeur pour créer le graphe. Pour l’instant, comme pour le cas du directeur, il n’existe qu’un seul constructeur: QgsGraphBuilder, qui créé des objets QgsGraph. Vous pouvez implémenter vos propres constructeurs qui produiront des graphes compatibles avec des bibliothèques telles que BGL ou NetworkX.

Pour calculer les propriétés des arcs, une stratégie basée sur les motifs de programmation est employée. Pour l’instant, seule la stratégie QgsDistanceArcProperter est disponible; elle prend en compte la longueur de la route. Vous pouvez implémenter votre propre stratégie qui utilisera tous les paramètres nécessaires. Par exemple, l’extension RoadGraph utilise une stratégie qui détermine le temps de trajet en utilisant les longueurs d’arc et la vitesse à partir d’attributs.

Il est temps de plonger dans le processus.

D’abord, nous devrions importer le module networkanalysis pour utiliser la bibliothèque

from qgis.networkanalysis import *

Ensuite, quelques exemples pour créer un directeur

# don't use information about road direction from layer attributes,
# all roads are treated as two-way
director = QgsLineVectorLayerDirector(vLayer, -1, '', '', '', 3)

# use field with index 5 as source of information about road direction.
# one-way roads with direct direction have attribute value "yes",
# one-way roads with reverse direction have the value "1", and accordingly
# bidirectional roads have "no". By default roads are treated as two-way.
# This scheme can be used with OpenStreetMap data
director = QgsLineVectorLayerDirector(vLayer, 5, 'yes', '1', 'no', 3)

Pour construire un directeur, il faut lui fournir une couche vecteur qui sera utilisée comme source pour la structure du graphe ainsi que des informations sur les mouvements permis sur chaque segment de route (sens unique ou déplacement bidirectionnel, direct ou inversé). L’appel au directeur se fait de la manière suivante

director = QgsLineVectorLayerDirector(vl, directionFieldId,
                                      directDirectionValue,
                                      reverseDirectionValue,
                                      bothDirectionValue,
                                      defaultDirection)

Voici la liste complète de la signification de ces paramètres:

• vl — couche vecteur utilisée pour construire le graphe

• directionFieldId — index du champ de la table d’attribut où est stocké l’information sur la direction de la route. Si -1 est utilisé, cette information n’est pas utilisée. Un entier.

• directDirectionValue — valeur du champ utilisé pour les routes avec une direction directe (déplacement du premier point de la ligne au dernier). Une chaîne de caractères.

• reverseDirectionValue — valeur du champ utilisé pour les routes avec une direction inverse (déplacement du dernier point de la ligne au premier). Une chaîne de caractères.

• bothDirectionValue — valeur du champ utilisé pour les routes bidirectionelles (pour ces routes, on peut se déplacer du premier point au dernier et du dernier au premier). Une chaîne de caractères.

• defaultDirection — direction par défaut de la route. Cette valeur sera utilisée pour les routes où le champ directionFieldId` n'est pas paramétré ou qui a une valeur différente des trois valeurs précédentes. Un entier ``1 indique une direction directe, 2 indique une direction inverse et 3 indique les deux directions.

Il est ensuite impératif de créer une stratégie de calcul des propriétés des arcs:

properter = QgsDistanceArcProperter()

Et d’informer le directeur à propos de cette stratégie:

director.addProperter(properter)

Nous pouvons maintenant utiliser le constructeur qui créera le graphe. Le constructeur de la classe QgsGraphBuilder utilise plusieurs arguments:

• crs — système de coordonnées de référence à utiliser. Argument obligatoire.

• otfEnabled — utiliser ou non la projection “à la volée”. La valeur par défaut est const:True (oui, utiliser OTF).

• topologyTolerance — la tolérance topologique. La valeur par défaut est 0.

• ellipsoidID — ellipsoïde à utiliser. Par défaut “WGS84”.

# only CRS is set, all other values are defaults
builder = QgsGraphBuilder(myCRS)

Nous pouvons également définir plusieurs points qui seront utilisés dans l’analyse, par exemple:

startPoint = QgsPoint(82.7112, 55.1672)
endPoint = QgsPoint(83.1879, 54.7079)

Maintenant que tout est en place, nous pouvons construire le graphe et lier ces points dessus:

tiedPoints = director.makeGraph(builder, [startPoint, endPoint])

La construction du graphe peut prendre du temps (qui dépend du nombre d’entités dans la couche et de la taille de la couche). tiedPoints est une liste qui contient les coordonnées des points liés. Lorsque l’opération de construction est terminée, nous pouvons récupérer le graphe et l’utiliser pour l’analyse:

graph = builder.graph()

Avec le code qui suit, nous pouvons récupérer les index des arcs de nos points:

startId = graph.findVertex(tiedPoints[0])
endId = graph.findVertex(tiedPoints[1])

Analyse de graphe¶

L’analyse de graphe est utilisée pour trouver des réponses aux deux questions: quels arcs sont connectés et comment trouver le plus court chemin ? Pour résoudre ces problèmes la bibliothèque d’analyse de graphe fournit l’algorithme de Dijkstra.

L’algorithme de Dijkstra trouve le plus court chemin entre un des arcs du graphe par rapport à tous les autres en tenant compte des paramètres d’optimisation. Ces résultats peuvent être représentés comme un arbre du chemin le plus court.

L’arbre du plus court chemin est un graphe pondéré de direction (plus précisément un arbre) qui dispose des propriétés suivantes:

• Seul un arc n’a pas d’arcs entrants: la racine de l’arbre.

• Tous les autres arcs n’ont qu’un seul arc entrant.

• Si un arc B est atteignable depuis l’arc A alors le chemin de A vers B est le seul chemin disponible et il est le chemin optimal (le plus court) sur ce graphe.

Pour obtenir l’arbre du chemin le plus court, utilisez les méthodes shortestTree() et dijkstra() de la classe QgsGraphAnalyzer. Il est recommandé d’utiliser la méthode dijkstra() car elle fonctionne plus rapidement et utilise la mémoire de manière plus efficace.

La méthode shortestTree() est utile lorsque vous voulez approcher l’arbre du chemin le plus court. Elle créé toujours un nouvel objet de graphe (QgsGraph) et elle accepte trois variables:

• source — graphe en entrée

• startVertexIdx — index du point sur l’arbre (la racine de l’arbre)

• criterionNum — nombre de propriétés d’arc à utiliser (en partant de 0).

tree = QgsGraphAnalyzer.shortestTree(graph, startId, 0)

La méthode dijkstra() dispose des mêmes arguments mais retourne deux tableaux. Dans le premier, l’élément i contient l’index de l’arc à suivre ou -1 s’il n’y a pas d’arc à suivre. Dans le second tableau, l’élément i contient la distance depuis la racine de l’arbre jusqu’au sommet i ou la valeur DOUBLE_MAX si le sommet est inaccessible depuis la racine.

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, startId, 0)

Voici un exemple de code très simple pour afficher l’arbre du chemin le plus court en utilisant un graphe créé avec la méthode shortestTree() (sélectionnez la couche de polylignes dans la table des matières et remplacez les coordonnées avec les vôtres). Attention, ce code est juste un exemple, il crée de nombreux objets QgsRubberBand et il reste très lent sur les jeux de données volumineux.

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.743804, 0.22954)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

i = 0;
while (i < tree.arcCount()):
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (tree.vertex(tree.arc(i).inVertex()).point())
  rb.addPoint (tree.vertex(tree.arc(i).outVertex()).point())
  i = i + 1

Même chose mais en utilisant la méthode dijkstra().

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-1.37144, 0.543836)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

(tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

for edgeId in tree:
  if edgeId == -1:
    continue
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (graph.vertex(graph.arc(edgeId).inVertex()).point())
  rb.addPoint (graph.vertex(graph.arc(edgeId).outVertex()).point())

assign Т = B
while Т != A
    add point Т to path
    get incoming edge for point Т
    look for point ТТ, that is start point of this edge
    assign Т = ТТ
add point А to path

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

idStart = tree.findVertex(tStart)
idStop = tree.findVertex(tStop)

if idStop == -1:
  print "Path not found"
else:
  p = []
  while (idStart != idStop):
    l = tree.vertex(idStop).inArc()
    if len(l) == 0:
      break
    e = tree.arc(l[0])
    p.insert(0, tree.vertex(e.inVertex()).point())
    idStop = e.outVertex()

  p.insert(0, tStart)
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
idStop = graph.findVertex(tStop)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

if tree[idStop] == -1:
  print "Path not found"
else:
  p = []
  curPos = idStop
  while curPos != idStart:
    p.append(graph.vertex(graph.arc(tree[curPos]).inVertex()).point())
    curPos = graph.arc(tree[curPos]).outVertex();

  p.append(tStart)

  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(65.5462, 57.1509)
delta = qgis.utils.iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1

rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
rb.setColor(Qt.green)
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() + delta))
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() + delta))

tiedPoints = director.makeGraph(builder, [pStart])
graph = builder.graph()
tStart = tiedPoints[0]

idStart = graph.findVertex(tStart)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

upperBound = []
r = 2000.0
i = 0
while i < len(cost):
  if cost[i] > r and tree[i] != -1:
    outVertexId = graph.arc(tree [i]).outVertex()
    if cost[outVertexId] < r:
      upperBound.append(i)
  i = i + 1

for i in upperBound:
  centerPoint = graph.vertex(i).point()
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
  rb.setColor(Qt.red)
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() + delta))
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() + delta))