Build a Network Graph with QgsGraphBuilder

Every routing answer QGIS gives you is a property of the graph, not of the line layer. If a road is missing from the graph no algorithm will find it, and nothing about the build reports that it happened. Learning to inspect the graph you built — how many vertices, how many edges, how much of it is connected to how much else — is what separates routing that works from routing that produces a confident wrong answer.

This recipe belongs to Network Analysis & Routing in PyQGIS. It covers the builder's arguments in detail, the topology tolerance and how to choose it, reading the graph back, auditing connectivity, and what a large network costs.

Endpoints become vertices; segments become edge pairsThree line features meet near a junction. Their endpoints are separate vertices when the tolerance is zero, so nothing connects. Raising the tolerance merges the three nearby endpoints into a single vertex and the junction becomes traversable. Each two-way segment then contributes two directed edges to the graph.The tolerance decides whether this is a junctiontolerance 0 — three vertices18 cm apart — no route passes throughtolerance 0.5 m — one vertexmerged — all three directions traversabletoo small and nothing connects; too large and a bridge welds to the road beneath itmatch it to the digitising precision, not to your patience

Prerequisites

  • QGIS 3.34 LTR or newer. The qgis.analysis network classes have been stable for many releases.
  • A line layer in a projected CRS. Tolerances and lengths in degrees are meaningless.
  • Lines split at junctions — native:splitwithlines against the layer itself, or native:explodelines.

The builder's arguments

from qgis.analysis import QgsGraphBuilder

builder = QgsGraphBuilder(
    roads.sourceCrs(),   # CRS the graph works in
    True,                # otfEnabled — reproject features into that CRS
    0.5,                 # topology tolerance, in CRS units
    "WGS84",             # ellipsoid for geodesic length, when otf is on
)

Breakdown: The CRS is what the resulting vertex coordinates are expressed in, so it should be the CRS you want to ask questions in. The on-the-fly flag lets you feed a layer in a different projection and have the builder transform as it walks, which is convenient and slower than reprojecting the layer once beforehand. The tolerance is the argument that matters and it is covered below. The ellipsoid affects length computation and is irrelevant when you are already in a metric projected CRS, which you should be.

Choosing a tolerance

The tolerance is a distance within which two endpoints are treated as the same vertex. Choose it from the data's digitising precision, not by trial and error:

  • Zero for a network you generated programmatically or that came from a topologically clean source — snapping was already exact, and a non-zero tolerance can only cause damage.
  • A few centimetres for a professionally digitised network with snapping enabled during capture.
  • Half a metre to a metre for a road centreline layer of ordinary quality.
  • Never more than the narrowest real gap you want preserved. On an urban layer with a footbridge two metres above a road, a two-metre tolerance connects them.
from qgis.core import QgsProject

roads = QgsProject.instance().mapLayersByName("roads")[0]

builder = QgsGraphBuilder(roads.sourceCrs(), True, 0.5)
director.makeGraph(builder, [])
graph = builder.graph()

print("vertices:", graph.vertexCount())
print("edges:", graph.edgeCount())

Breakdown: Passing an empty list to makeGraph builds the graph without tying any points to it, which is exactly what you want while tuning the tolerance. The two counts are the fastest diagnostic available: build the graph at tolerance 0 and again at your chosen value, and compare. A tolerance that merges nothing has produced identical counts and is doing no work; a tolerance that drops the vertex count by more than a few per cent is merging aggressively and deserves a look at what it joined.

Reading the graph back

What a vertex and an edge actually holdA vertex stores its map coordinate and two lists of edge identifiers, one for edges arriving and one for edges leaving. An edge stores the identifiers of the vertices it runs between and a cost for each strategy that was added to the director, indexed in the order the strategies were added.Everything is an integer idgraph.vertex(id).point() → QgsPointXY.incomingEdges() → [int].outgoingEdges() → [int]a dead end has an emptyoutgoing listgraph.edge(id).fromVertex() → int.toVertex() → int.cost(criterion) → floatcriterion 0 is the first strategyadded to the directornothing here points back at a feature — the link to the source layer is gone

vertex = graph.vertex(0)
print(vertex.point().asWkt(1))
print("out:", vertex.outgoingEdges(), "in:", vertex.incomingEdges())

edge = graph.edge(vertex.outgoingEdges()[0])
print(edge.fromVertex(), "→", edge.toVertex(), "cost", edge.cost(0))

Breakdown: cost(0) is the first strategy added to the director, cost(1) the second, and so on — the index is positional, so reordering the addStrategy calls silently changes what every query means. fromVertex() and toVertex() are the modern accessor names; QGIS before 3.24 used inVertex() and outVertex() with the opposite-sounding semantics, which is a well-known source of reversed routes in older code. Where a script must run on both, getattr(edge, "fromVertex", edge.inVertex)() is the pragmatic bridge.

Finding a vertex from a coordinate uses findVertex, which is an exact match rather than a nearest-neighbour search:

from qgis.core import QgsPointXY

index = graph.findVertex(QgsPointXY(445120, 187330))
print(index)  # -1 if no vertex sits exactly there

Breakdown: This returns -1 for anything that is not precisely a vertex position, which is why you never pass your own coordinates to it. Pass the points through makeGraph's tie list and look up the returned positions instead — those are guaranteed to be on the graph.

Auditing connectivity before you trust it

A network in fragments routes perfectly within each fragment and reports failure between them, which reads as "no route exists" rather than "your data is broken".

from qgis.analysis import QgsGraphAnalyzer

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

reached = sum(1 for edge_id in tree if edge_id != -1)
total = graph.vertexCount()
print(f"{reached}/{total} vertices reachable from vertex 0 "
      f"({100 * reached / total:.1f}%)")

Breakdown: Testing reachability on tree rather than on costs is the robust form — unreachable vertices carry a sentinel cost that is large but finite, and comparing against a magic threshold works until someone routes across a continent. The seed vertex is itself excluded from the count (its tree entry is -1), which is a one-vertex discrepancy not worth correcting. Anything under about 95% on a road network means real fragmentation; write the unreachable vertices out and look at where they are:

from qgis.core import QgsVectorLayer, QgsFeature, QgsGeometry

orphans = QgsVectorLayer("Point?crs=" + roads.sourceCrs().authid(), "orphans", "memory")
provider = orphans.dataProvider()

features = []
for vertex_id, edge_id in enumerate(tree):
    if edge_id == -1 and vertex_id != seed:
        feature = QgsFeature()
        feature.setGeometry(QgsGeometry.fromPointXY(graph.vertex(vertex_id).point()))
        features.append(feature)

provider.addFeatures(features)
QgsProject.instance().addMapLayer(orphans)

Breakdown: Batching the features into one addFeatures call rather than adding them one at a time is the difference between instant and slow on a large network. Looking at the result on the map is far more informative than any statistic: orphans clustered along one road mean a single break, orphans scattered evenly mean the tolerance is too tight everywhere, and orphans forming a neat separate town mean the extract simply does not include the road that joins them.

What a large network costs

The build dominates; the queries are cheapAs the number of line segments grows from ten thousand to a million, graph build time rises steeply and memory use rises with it, while the time to answer a single shortest-path query grows only slowly. This is why building once and querying many times is the right structure for anything beyond a single route.Build once. Query as often as you like.line segments in the networkcostgraph buildone query10k100k1Mclip the network to the study area and the whole curve moves left

The graph lives entirely in memory and holds a vertex per merged endpoint and an edge per traversable direction, so a two-way network produces roughly two edges per segment. As a rough guide, a few hundred thousand segments builds in seconds and fits comfortably; a few million builds in minutes and will exhaust a modest machine. The fix is always the same and always available: clip the network to the area you are actually working in, with a buffer wider than the longest route you will ask for.

QGIS version compatibility

The qgis.analysis network classes have been stable since QGIS 3.0 with one notable change: QgsGraphEdge.fromVertex() and toVertex() were introduced in 3.24, deprecating inVertex() and outVertex(). QgsVectorLayerDirector.DirectionBoth moved into a scoped Direction enum in newer releases while remaining accessible at the old location, so existing code keeps working.

Troubleshooting

  • graph.edgeCount() is zero. No strategy was added to the director, or the layer has no line features.
  • Everything is disconnected. Lines are not split at junctions, or the tolerance is zero on a hand-digitised layer.
  • The build never finishes. The layer is enormous, or the tolerance is huge, which makes endpoint merging quadratic in the worst case.
  • findVertex always returns −1. You passed your own coordinate rather than the tied point returned by makeGraph.
  • Routes run backwards. Old inVertex/outVertex code, or a direction field whose forward and backward values are swapped.
  • Memory use explodes. Two edges per segment plus per-vertex edge lists. Clip the network first.

Conclusion

Build in a projected CRS, choose the tolerance from the data's precision rather than from frustration, compare vertex counts before and after to see what the tolerance actually did, and run a reachability audit before believing a single route. Once the graph is right, everything built on it — shortest paths, service areas, matrices — is straightforward.

Frequently Asked Questions

Can I save a built graph and reload it later? No — there is no serialisation for QgsGraph. Rebuild it, and if the build is the bottleneck, keep the process alive rather than the graph, or clip the network smaller.

Does the builder respect a layer's selection or subset string? It reads the features the layer exposes, so a subset string does restrict it. A selection does not — the director iterates all visible features regardless.

How do I add my own per-edge cost? Through a strategy. QgsNetworkStrategy can be subclassed in Python, with cost() returning whatever you compute per feature, which is how penalties for surface type or gradient get modelled.

Is the graph directed even when everything is two-way? Yes. A two-way segment becomes two edges pointing opposite ways, which is why edge counts are about double what people expect.