Network analysis allows you to find the most efficient route between two points along a defined network of connected lines. These lines might represent streets, pipes in a water system, the Internet, or any number of connected systems. Network analysis abstracts this common problem so that the same techniques and algorithms can be applied across a wide variety of applications. In this recipe, we'll use a generic line network to perform analysis using the Dijkstra algorithm, which is one of the oldest algorithms used to find the shortest path. QGIS has all of this functionality built in.
First, download the vector dataset from the following link, which includes two shapefiles, and unzip it to a directory named shapes in your qgis_data directory:
We will create a network graph by defining the beginning and end of our network of lines, and then use this graph to determine the shortest route along the line network between our two points. To do this, we need to perform the following steps:
- In the QGIS Python Console, we'll first import the libraries we'll need, including the QGIS Network Analyzer:
from qgis.core import * from qgis.gui import * from qgis.networkanalysis import * from PyQt4.QtCore import *
- Next, we'll load our line network shapefile and the shapefile containing the points along the network we want the Network Analyzer to consider when selecting a route:
network = QgsVectorLayer("/Users/joellawhead/qgis_data/shapes/Network.shp", "Network Layer", "ogr") waypoints = QgsVectorLayer("/Users/joellawhead/qgis_data/shapes/ NetworkPoints.shp", "Waypoints", "ogr")
- Now, we will create a graph director to define the properties of the graph. The
directorobject accepts our line shapfile, a field ID for direction information, and some other documented integer codes involving direction properties in the network. In our example, we're going to tell the director to ignore directions. Theproperterobject is a basic algorithm for a routing strategy that gets added to the network graph and considers line length:director = QgsLineVectorLayerDirector(network, -1, '', '', '', 3) properter = QgsDistanceArcProperter() director.addProperter(properter) crs = network.crs()
- Now, we create the
GraphBuilderobject to actually convert the line network into a graph:builder = QgsGraphBuilder(crs) - We define the two points that are the start and end of our route:
ptStart = QgsPoint(-0.8095638694, -0.1578175511) ptStop = QgsPoint(0.8907435677, 0.4430834924)
- Then, we tell the director to turn our point layer into tie points in our network, which define the waypoints along our network and can also optionally provide resistance values:
tiePoints = director.makeGraph(builder, [ptStart, ptStop]) - Now, we can use the following code to build the graph:
graph = builder.graph() - We now locate our start and end points as tie points in the graph:
tStart = tiePoints[0] tStop = tiePoints[1] idStart = graph.findVertex(tStart) idStop = graph.findVertex(tStop)
- Then, we can tell the Analyzer to use our start point in order to find the shortest route through the network:
(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0) - Next, we loop through the resulting tree and grab the points along the output route:
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)
- Now, we'll load our two input shapefiles onto the map and create a rubber band in order to visualize the route:
QgsMapLayerRegistry.instance().addMapLayers([network,waypoints]) rb = QgsRubberBand(iface.mapCanvas()) rb.setColor(Qt.red)
- Finally, we'll add the route points to the rubber band in order to see the output of the Network Analyzer:
for pnt in p: rb.addPoint(pnt)
This recipe is an extremely simple example to be used as a starting point for the investigation of a very complex and powerful tool. The line network shapefiles can have a field defining each line as one-way in a certain direction or bi-directional. The point shapefile provides waypoints along the network, as well as resistance values, which might represent elevation, traffic density, or other factors that will make a route less desirable. The output will look similar to the following image:
More information and examples of the network analysis tool are available in the QGIS documentation at http://docs.qgis.org/testing/en/docs/pyqgis_developer_cookbook/network_analysis.html.