Os trechos de código desta página precisam das seguintes importações se você estiver fora do console do pyqgis:

```from qgis.core import (
QgsVectorLayer,
QgsPointXY,
)
```

# 18. Biblioteca de análise de rede¶

A biblioteca de análise de rede pode ser usada para:

• criar gráfico matemático a partir de dados geográficos (camadas vetoriais de polilinhas)

• implementar métodos básicos da teoria dos gráficos (atualmente apenas o algoritmo de Dijkstra)

A biblioteca de análise de rede foi criada exportando funções básicas do complemento principal RoadGraph e agora você pode usar seus métodos em complementos ou diretamente do console do Python.

## 18.1. Informação Geral¶

Resumidamente, um caso típico pode ser descrito assim:

1. criar gráfico para geodata (camada vetorial polígono usual)

2. rodar análise gráfica

3. usar resultados das análises (por exemplo, visualizá-los)

## 18.2. Elaborando um gráfico¶

A primeira coisa que você deve fazer — é preparar os dados de entrada, que é converter uma camada vetor em um gráfico. Todas as próximas ações irão usar este gráfico e não a camada.

Como fonte, podemos usar qualquer camada vetorial de polilinha. Os nós das polilinhas se tornam vértices do gráfico e os segmentos das polilinhas são arestas do gráfico. Se vários nós tiverem as mesmas coordenadas, serão o mesmo vértice do gráfico. Portanto, duas linhas que possuem um nó comum se conectam.

Além disso, durante a criação do gráfico, é possível “fixar” (“vincular”) à camada vetorial de entrada qualquer número de pontos adicionais. Para cada ponto adicional, uma correspondência será encontrada - o vértice do gráfico mais próximo ou a aresta do gráfico mais próxima. Neste último caso, a aresta será dividida e um novo vértice será adicionado.

Vector layer attributes and length of an edge can be used as the properties of an edge.

Converting from a vector layer to the graph is done using the Builder programming pattern. A graph is constructed using a so-called Director. There is only one Director for now: QgsVectorLayerDirector. The director sets the basic settings that will be used to construct a graph from a line vector layer, used by the builder to create the graph. Currently, as in the case with the director, only one builder exists: `QgsGraphBuilder`, that creates `QgsGraph` objects. You may want to implement your own builders that will build a graphs compatible with such libraries as BGL or NetworkX.

To calculate edge properties the programming pattern strategy is used. For now only QgsNetworkDistanceStrategy strategy (that takes into account the length of the route) and QgsNetworkSpeedStrategy (that also considers the speed) are availabile. You can implement your own strategy that will use all necessary parameters. For example, RoadGraph plugin uses a strategy that computes travel time using edge length and speed value from attributes.

It’s time to dive into the process.

First of all, to use this library we should import the analysis module

```from qgis.analysis import *
```

Then some examples for creating a director

 ``` 1 2 3 4 5 6 7 8 9 10``` ```# don't use information about road direction from layer attributes, # all roads are treated as two-way director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) # 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 = QgsVectorLayerDirector(vectorLayer, 5, 'yes', '1', 'no', QgsVectorLayerDirector.DirectionBoth) ```

To construct a director we should pass a vector layer, that will be used as the source for the graph structure and information about allowed movement on each road segment (one-way or bidirectional movement, direct or reverse direction). The call looks like this

 ```1 2 3 4 5 6``` ```director = QgsVectorLayerDirector(vectorLayer, directionFieldId, directDirectionValue, reverseDirectionValue, bothDirectionValue, defaultDirection) ```

Aqui segue uma lista de todos os significados dos parâmetros:

• `vectorLayer` — vector layer used to build the graph

• `directionFieldId` — index of the attribute table field, where information about roads direction is stored. If `-1`, then don’t use this info at all. An integer.

• `directDirectionValue` — field value for roads with direct direction (moving from first line point to last one). A string.

• `reverseDirectionValue` — field value for roads with reverse direction (moving from last line point to first one). A string.

• `bothDirectionValue` — field value for bidirectional roads (for such roads we can move from first point to last and from last to first). A string.

• `defaultDirection` — default road direction. This value will be used for those roads where field `directionFieldId` is not set or has some value different from any of the three values specified above. Possible values are:

• `QgsVectorLayerDirector.DirectionForward` — One-way direct

• `QgsVectorLayerDirector.DirectionBackward` — One-way reverse

• `QgsVectorLayerDirector.DirectionBoth` — Two-way

It is necessary then to create a strategy for calculating edge properties

 ```1 2 3 4 5 6 7``` ```# The index of the field that contains information about the edge speed attributeId = 1 # Default speed value defaultValue = 50 # Conversion from speed to metric units ('1' means no conversion) toMetricFactor = 1 strategy = QgsNetworkSpeedStrategy(attributeId, defaultValue, toMetricFactor) ```

```director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', 3)
```

Now we can use the builder, which will create the graph. The `QgsGraphBuilder` class constructor takes several arguments:

• `crs` — coordinate reference system to use. Mandatory argument.

• `otfEnabled` — use “on the fly” reprojection or no. By default const:True (use OTF).

• `topologyTolerance` — topological tolerance. Default value is 0.

• `ellipsoidID` — ellipsoid to use. By default “WGS84”.

```# only CRS is set, all other values are defaults
builder = QgsGraphBuilder(vectorLayer.crs())
```

Também podemos definir vários pontos, que serão usados na análise. Por exemplo

```startPoint = QgsPointXY(1179720.1871, 5419067.3507)
endPoint = QgsPointXY(1180616.0205, 5419745.7839)
```

Now all is in place so we can build the graph and “tie” these points to it

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

Building the graph can take some time (which depends on the number of features in a layer and layer size). `tiedPoints` is a list with coordinates of “tied” points. When the build operation is finished we can get the graph and use it for the analysis

```graph = builder.graph()
```

With the next code we can get the vertex indexes of our points

```startId = graph.findVertex(tiedPoints)
endId = graph.findVertex(tiedPoints)
```

## 18.3. Análise de Gráficos¶

Networks analysis is used to find answers to two questions: which vertexes are connected and how to find a shortest path. To solve these problems the network analysis library provides Dijkstra’s algorithm.

Dijkstra’s algorithm finds the shortest route from one of the vertexes of the graph to all the others and the values of the optimization parameters. The results can be represented as a shortest path tree.

The shortest path tree is a directed weighted graph (or more precisely a tree) with the following properties:

• only one vertex has no incoming edges — the root of the tree

• todos os outros vértices têm apenas uma borda chegando

• if vertex B is reachable from vertex A, then the path from A to B is the single available path and it is optimal (shortest) on this graph

To get the shortest path tree use the methods `shortestTree` and `dijkstra` of the `QgsGraphAnalyzer` class. It is recommended to use the `dijkstra` method because it works faster and uses memory more efficiently.

The `shortestTree` method is useful when you want to walk around the shortest path tree. It always creates a new graph object (QgsGraph) and accepts three variables:

• `source` — input graph

• `startVertexIdx` — index of the point on the tree (the root of the tree)

• `criterionNum` — number of edge property to use (started from 0).

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

The `dijkstra` method has the same arguments, but returns two arrays. In the first array element n contains index of the incoming edge or -1 if there are no incoming edges. In the second array element n contains the distance from the root of the tree to vertex n or DOUBLE_MAX if vertex n is unreachable from the root.

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

Here is some very simple code to display the shortest path tree using the graph created with the `shortestTree` method (select linestring layer in Layers panel and replace coordinates with your own).

Aviso

Use this code only as an example, it creates a lot of `QgsRubberBand` objects and may be slow on large datasets.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29``` ```from qgis.core import * from qgis.gui import * from qgis.analysis import * from qgis.PyQt.QtCore import * from qgis.PyQt.QtGui import * vectorLayer = QgsVectorLayer('testdata/network.gpkg|layername=network_lines', 'lines') director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) strategy = QgsNetworkDistanceStrategy() director.addStrategy(strategy) builder = QgsGraphBuilder(vectorLayer.crs()) pStart = QgsPointXY(1179661.925139,5419188.074362) tiedPoint = director.makeGraph(builder, [pStart]) pStart = tiedPoint graph = builder.graph() idStart = graph.findVertex(pStart) tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0) i = 0 while (i < tree.edgeCount()): rb = QgsRubberBand(iface.mapCanvas()) rb.setColor (Qt.red) rb.addPoint (tree.vertex(tree.edge(i).fromVertex()).point()) rb.addPoint (tree.vertex(tree.edge(i).toVertex()).point()) i = i + 1 ```

Same thing but using the `dijkstra` method

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` ```from qgis.core import * from qgis.gui import * from qgis.analysis import * from qgis.PyQt.QtCore import * from qgis.PyQt.QtGui import * vectorLayer = QgsVectorLayer('testdata/network.gpkg|layername=network_lines', 'lines') director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) strategy = QgsNetworkDistanceStrategy() director.addStrategy(strategy) builder = QgsGraphBuilder(vectorLayer.crs()) pStart = QgsPointXY(1179661.925139,5419188.074362) tiedPoint = director.makeGraph(builder, [pStart]) pStart = tiedPoint graph = builder.graph() idStart = graph.findVertex(pStart) (tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0) for edgeId in tree: if edgeId == -1: continue rb = QgsRubberBand(iface.mapCanvas()) rb.setColor (Qt.red) rb.addPoint (graph.vertex(graph.edge(edgeId).fromVertex()).point()) rb.addPoint (graph.vertex(graph.edge(edgeId).toVertex()).point()) ```

### 18.3.1. Encontrando os caminhos mais curtos¶

To find the optimal path between two points the following approach is used. Both points (start A and end B) are “tied” to the graph when it is built. Then using the `shortestTree` or `dijkstra` method we build the shortest path tree with root in the start point A. In the same tree we also find the end point B and start to walk through the tree from point B to point A. The whole algorithm can be written as:

 ```1 2 3 4 5 6 7``` ```assign T = B while T != B add point T to path get incoming edge for point T look for point TT, that is start point of this edge assign T = TT add point A to path ```

At this point we have the path, in the form of the inverted list of vertexes (vertexes are listed in reversed order from end point to start point) that will be visited during traveling by this path.

Here is the sample code for QGIS Python Console (you may need to load and select a linestring layer in TOC and replace coordinates in the code with yours) that uses the `shortestTree` method

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48``` ```from qgis.core import * from qgis.gui import * from qgis.analysis import * from qgis.PyQt.QtCore import * from qgis.PyQt.QtGui import * vectorLayer = QgsVectorLayer('testdata/network.gpkg|layername=network_lines', 'lines') builder = QgsGraphBuilder(vectorLayer.sourceCrs()) director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) startPoint = QgsPointXY(1179661.925139,5419188.074362) endPoint = QgsPointXY(1180942.970617,5420040.097560) tiedPoints = director.makeGraph(builder, [startPoint, endPoint]) tStart, tStop = tiedPoints graph = builder.graph() idxStart = graph.findVertex(tStart) tree = QgsGraphAnalyzer.shortestTree(graph, idxStart, 0) idxStart = tree.findVertex(tStart) idxEnd = tree.findVertex(tStop) if idxEnd == -1: raise Exception('No route!') # Add last point route = [tree.vertex(idxEnd).point()] # Iterate the graph while idxEnd != idxStart: edgeIds = tree.vertex(idxEnd).incomingEdges() if len(edgeIds) == 0: break edge = tree.edge(edgeIds) route.insert(0, tree.vertex(edge.fromVertex()).point()) idxEnd = edge.fromVertex() # Display rb = QgsRubberBand(iface.mapCanvas()) rb.setColor(Qt.green) # This may require coordinate transformation if project's CRS # is different than layer's CRS for p in route: rb.addPoint(p) ```

And here is the same sample but using the `dijkstra` method

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48``` ```from qgis.core import * from qgis.gui import * from qgis.analysis import * from qgis.PyQt.QtCore import * from qgis.PyQt.QtGui import * vectorLayer = QgsVectorLayer('testdata/network.gpkg|layername=network_lines', 'lines') director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) strategy = QgsNetworkDistanceStrategy() director.addStrategy(strategy) builder = QgsGraphBuilder(vectorLayer.sourceCrs()) startPoint = QgsPointXY(1179661.925139,5419188.074362) endPoint = QgsPointXY(1180942.970617,5420040.097560) tiedPoints = director.makeGraph(builder, [startPoint, endPoint]) tStart, tStop = tiedPoints graph = builder.graph() idxStart = graph.findVertex(tStart) idxEnd = graph.findVertex(tStop) (tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0) if tree[idxEnd] == -1: raise Exception('No route!') # Total cost cost = costs[idxEnd] # Add last point route = [graph.vertex(idxEnd).point()] # Iterate the graph while idxEnd != idxStart: idxEnd = graph.edge(tree[idxEnd]).fromVertex() route.insert(0, graph.vertex(idxEnd).point()) # Display rb = QgsRubberBand(iface.mapCanvas()) rb.setColor(Qt.red) # This may require coordinate transformation if project's CRS # is different than layer's CRS for p in route: rb.addPoint(p) ```

### 18.3.2. Areas of availability¶

The area of availability for vertex A is the subset of graph vertexes that are accessible from vertex A and the cost of the paths from A to these vertexes are not greater that some value.

More clearly this can be shown with the following example: “There is a fire station. Which parts of city can a fire truck reach in 5 minutes? 10 minutes? 15 minutes?”. Answers to these questions are fire station’s areas of availability.

To find the areas of availability we can use the `dijkstra` method of the `QgsGraphAnalyzer` class. It is enough to compare the elements of the cost array with a predefined value. If cost[i] is less than or equal to a predefined value, then vertex i is inside the area of availability, otherwise it is outside.

A more difficult problem is to get the borders of the area of availability. The bottom border is the set of vertexes that are still accessible, and the top border is the set of vertexes that are not accessible. In fact this is simple: it is the availability border based on the edges of the shortest path tree for which the source vertex of the edge is accessible and the target vertex of the edge is not.

Aqui está um exemplo

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44``` ```director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth) strategy = QgsNetworkDistanceStrategy() director.addStrategy(strategy) builder = QgsGraphBuilder(vectorLayer.crs()) pStart = QgsPointXY(1179661.925139, 5419188.074362) delta = iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1 rb = QgsRubberBand(iface.mapCanvas(), True) rb.setColor(Qt.green) rb.addPoint(QgsPointXY(pStart.x() - delta, pStart.y() - delta)) rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() - delta)) rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() + delta)) rb.addPoint(QgsPointXY(pStart.x() - delta, pStart.y() + delta)) tiedPoints = director.makeGraph(builder, [pStart]) graph = builder.graph() tStart = tiedPoints idStart = graph.findVertex(tStart) (tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0) upperBound = [] r = 1500.0 i = 0 tree.reverse() while i < len(cost): if cost[i] > r and tree[i] != -1: outVertexId = graph.edge(tree [i]).toVertex() if cost[outVertexId] < r: upperBound.append(i) i = i + 1 for i in upperBound: centerPoint = graph.vertex(i).point() rb = QgsRubberBand(iface.mapCanvas(), True) rb.setColor(Qt.red) rb.addPoint(QgsPointXY(centerPoint.x() - delta, centerPoint.y() - delta)) rb.addPoint(QgsPointXY(centerPoint.x() + delta, centerPoint.y() - delta)) rb.addPoint(QgsPointXY(centerPoint.x() + delta, centerPoint.y() + delta)) rb.addPoint(QgsPointXY(centerPoint.x() - delta, centerPoint.y() + delta)) ```