Routing-Graph Topology QA

A routing engine never complains about bad topology — it just quietly returns “no route found,” or worse, an implausible detour, and the mapper who reported the bug gets told the data is fine. That is the trap this guide addresses. When an OSM extract is converted into a routable graph, geometric correctness and topological correctness are two different properties: a road can render perfectly on a tile yet be unreachable in the graph because its endpoint sits two centimetres away from the junction it was meant to join. Every one of these defects passes a visual review, passes geometry validation, and still poisons shortest-path queries. This section belongs to the wider OSM Data Quality & Validation discipline, and it narrows the lens to the connectivity invariants a graph must satisfy before anyone trusts a route computed on it.

Six routing-graph topology defects that silently break OSM routing Six labelled panels. Disconnected component shows a main cluster of connected nodes and a separate isolated pair. Near-miss endpoints shows two polylines whose ends stop just short with a gap. One-way trap shows three arrows entering a central node and none leaving. Dangling stub shows a road ending at a free degree-one node. Self-loop shows a node with an edge returning to itself. Turn restriction shows a junction with a crossed-out turn arc. Six ways a routable graph fails without a geometry error Disconnected component unreachable subgraph Near-miss endpoints gap < tolerance endpoints need snapping One-way trap / sink sink node — no exit Dangling stub degree-1 dead stub Self-loop way loops to itself Turn restriction restriction not modeled

Prerequisites

Three foundations make the rest of this guide actionable. First, you need a mental model of how ways become edges — a road is a chain of node references, and two roads only share a graph vertex when they share an OSM node, a fact rooted in the Node-Way-Relation Data Model. Second, you need a graph in hand: the translation from tagged ways to a directed, weighted networkx object is the job of OSMnx Graph Conversion Techniques, and topology QA runs on that output rather than on raw primitives. Third, this connectivity work sits beside — not on top of — Geometry Validation and Repair: a geometry can be perfectly valid (a closed, non-self-intersecting ring) while its role in the network is still broken, so run both classes of check, not one as a substitute for the other.

The Defect Catalogue: What Breaks Routing

Topology QA is a bounded problem because the failure modes are enumerable. Each defect below has a precise graph-theoretic signature, which is what makes it detectable without human review.

Defect Graph signature Routing symptom
Disconnected component A weakly connected component containing a tiny fraction of nodes Trips to/from the region return “no route”
Near-miss endpoint Two degree-1 nodes within a small distance but not identical Two roads that visually touch never join
One-way trap (sink) Node with in-degree > 0 and out-degree 0 Vehicles route in but can never leave
One-way island Strongly connected component you can enter but not exit Region reachable one way, unreachable the other
Dangling stub Degree-1 node not a legitimate cul-de-sac terminus Harmless alone; noise that hides real breaks
Self-loop Edge whose source and target are the same node Zero-length cycle; distorts turn logic
Unmodeled turn restriction restriction relation with no edge-level penalty Engine plans an illegal turn

The distinction between weak and strong connectivity is the crux of directed-graph QA. A weakly connected component ignores edge direction — treat every one-way as bidirectional and ask “is this reachable at all?” A strongly connected component respects direction — “can I get here and leave following the arrows?” A one-way trap is invisible to weak-component analysis (the sink is weakly connected to everything around it) but stands out immediately under strong-component analysis, where it collapses into a singleton or a small island. Running only weak-component checks is the single most common reason a one-way defect ships to production.

Turn restrictions are a category apart. They are not encoded in node references at all; they live in type=restriction relations whose members carry from, via, and to roles. A plain node-and-edge graph has nowhere to store “no left turn from this way onto that way,” so unless the graph builder expands restricted junctions into penalty edges or a line-graph, the restriction is simply absent — and the router will happily plan the illegal manoeuvre.

Step-by-Step: Auditing a Routing Graph

The pass below loads a drivable network with osmnx, then applies a battery of networkx connectivity checks. It uses Python 3.10+ type hints and the project logger convention, and it is written to report defects rather than silently mutate the graph — remediation is a deliberate second step, never a side effect of detection.

  1. Build the directed graph. Convert the extract into a MultiDiGraph where one-ways are single directed edges and bidirectional roads are reciprocal pairs. Preserve edge geometry and length so distance-based checks have real coordinates to work with.
  2. Rank weakly connected components. Sort components by node count; the largest is your main network, and everything below a size threshold is a candidate island to flag.
  3. Test strong connectivity for direction faults. Find strongly connected components and locate nodes with an out-degree of zero (sinks) or in-degree of zero (sources) — the fingerprints of one-way traps.
  4. Degree-scan for stubs and self-loops. Enumerate degree-1 nodes and self-loop edges directly from the degree view.
  5. Range-search for near-miss endpoints. Index the coordinates of degree-1 nodes and query for pairs closer than a snapping tolerance but not already joined.
python 
import logging

import networkx as nx
import osmnx as ox

logger = logging.getLogger(__name__)


def load_drive_graph(place: str) -> nx.MultiDiGraph:
    """Download and build a drivable routing graph for a place name."""
    graph = ox.graph_from_place(place, network_type="drive")
    logger.info(
        "graph built: %d nodes, %d edges",
        graph.number_of_nodes(),
        graph.number_of_edges(),
    )
    return graph


def rank_weak_components(graph: nx.MultiDiGraph, min_fraction: float = 0.01) -> list[set[int]]:
    """Return weakly connected components smaller than min_fraction of the graph."""
    total = graph.number_of_nodes()
    components = sorted(nx.weakly_connected_components(graph), key=len, reverse=True)
    islands = [c for c in components[1:] if len(c) < min_fraction * total]
    logger.info(
        "%d weak components; largest holds %d nodes; %d small islands flagged",
        len(components), len(components[0]), len(islands),
    )
    return islands

Directional faults come from the strong-component and degree views. A sink has out-degree zero after collapsing parallel edges, so query the directed degree views rather than the undirected .degree():

python 
def find_directional_traps(graph: nx.MultiDiGraph) -> dict[str, list[int]]:
    """Locate one-way sinks (no exit) and sources (no entry)."""
    sinks = [n for n, deg in graph.out_degree() if deg == 0]
    sources = [n for n, deg in graph.in_degree() if deg == 0]
    strong = list(nx.strongly_connected_components(graph))
    reachable = max(strong, key=len)
    islands = [c for c in strong if c is not reachable and len(c) < 25]
    logger.warning(
        "%d sinks, %d sources, %d one-way islands",
        len(sinks), len(sources), len(islands),
    )
    return {"sinks": sinks, "sources": sources, "islands": [n for c in islands for n in c]}

Stubs and self-loops fall straight out of the graph structure, and near-miss endpoints need a spatial range query over the degree-1 node coordinates:

python 
from scipy.spatial import cKDTree


def find_stubs_and_loops(graph: nx.MultiDiGraph) -> dict[str, list]:
    """Degree-1 dead ends and zero-length self-loop edges."""
    undirected = graph.to_undirected()
    stubs = [n for n, deg in undirected.degree() if deg == 1]
    loops = list(nx.selfloop_edges(graph, keys=True))
    return {"stubs": stubs, "self_loops": loops}


def find_near_miss_endpoints(
    graph: nx.MultiDiGraph, stubs: list[int], tol_m: float = 2.0
) -> list[tuple[int, int]]:
    """Pairs of dead-end nodes closer than tol_m metres but not connected."""
    # osmnx stores lon/lat in x/y; project so the tolerance is in metres.
    projected = ox.project_graph(graph)
    coords = [(projected.nodes[n]["x"], projected.nodes[n]["y"]) for n in stubs]
    if len(coords) < 2:
        return []
    tree = cKDTree(coords)
    pairs = tree.query_pairs(r=tol_m)
    near_miss: list[tuple[int, int]] = []
    for i, j in pairs:
        a, b = stubs[i], stubs[j]
        if not graph.has_edge(a, b) and not graph.has_edge(b, a):
            near_miss.append((a, b))
    logger.warning("%d near-miss endpoint pairs within %.1f m", len(near_miss), tol_m)
    return near_miss
Connectivity-check pipeline from extract to defect report An OSM extract feeds osmnx graph construction, producing a MultiDiGraph. The graph feeds four parallel analyses — weak connected components, strong connected components, degree scan, and KD-tree near-miss search — which all converge into one consolidated defect report. One graph, four connectivity checks, one report OSM extract .osm.pbf osmnx build MultiDiGraph Weak components small islands Strong components sinks · one-way islands Degree scan stubs · self-loops KD-tree search near-miss endpoints Defect report GeoJSON · CSV

Validation & Detection Matrix

Each defect maps to a check, a detection expression, and a remediation that must never run blind — snapping the wrong pair of endpoints invents a road that does not exist, so every automated fix needs a tolerance and a review gate.

Defect Root cause Detection Remediation
Disconnected component Extract clip severed a road; missing bridge way Weak component below size threshold Re-clip larger; add the missing connecting way upstream
Near-miss endpoint Two ways digitized without a shared node Degree-1 nodes within tolerance, unconnected Snap to a shared node if gap < tolerance and review confirms
One-way trap (sink) oneway direction reversed or over-applied Out-degree 0 on a non-terminal node Correct the oneway tag or add the missing reverse edge
One-way island A ring of one-ways all oriented the same way Small strongly connected component Re-tag one segment; verify entry and exit both exist
Dangling stub Legitimate cul-de-sac vs. truncated road Degree-1 node not tagged as terminus Distinguish real dead ends; join truncated ends
Self-loop Way whose first node ref equals its last nx.selfloop_edges non-empty Split the way at an interior node or drop the loop edge
Unmodeled turn restriction Restriction relation dropped in graph build restriction relation with no penalty edge Rebuild with turn-penalty expansion enabled

Performance & Scale Considerations

Connected-component analysis is linear in the size of the graph — networkx computes weak and strong components in roughly O(V + E) — so the component checks are cheap even on a national road network of millions of edges. The expensive operations are the ones you add around them. Projecting the graph so a tolerance is expressed in metres (ox.project_graph) copies every coordinate and is the slowest single step; do it once and reuse the projected graph for all distance checks rather than reprojecting per query. The near-miss search scales with the number of degree-1 nodes, not the whole graph, and a cKDTree query_pairs over even a few hundred thousand dead ends completes in well under a second because the candidate set is small and the radius tight.

Two levers keep large runs bounded. First, partition by administrative area: run the audit per region and reconcile at the boundaries, so a planet-scale check becomes an embarrassingly parallel batch rather than one monolithic graph in RAM. Second, cache the built graph: the conversion from PBF to MultiDiGraph dominates wall-clock time, so serialize the graph once and re-run only the detection functions when you iterate on thresholds. For genuinely planet-scale topology work, hold only node degree and component labels in memory and stream edge geometry from disk when a specific defect needs inspection.

Failure Modes & Gotchas

  • Undirected degree hides one-way faults. graph.degree() sums in- and out-edges, so a sink node looks like a normal degree-2 vertex. Always use in_degree() and out_degree() separately when hunting directional traps.
  • Every legitimate cul-de-sac is a degree-1 node. A raw stub count is mostly false positives; filter against highway values and noexit=yes before treating a dead end as a defect.
  • Tolerance is a physical quantity, not a coordinate delta. Comparing raw lon/lat differences conflates a metre near the equator with far less near the poles. Project to a metric CRS before any distance threshold, or the same tolerance means different things across the extract.
  • osmnx may pre-simplify away the nodes you want. Graph simplification collapses interstitial degree-2 nodes into single edges; if you need to test snapping at the original vertices, build with simplify=False or work from the unsimplified geometry.
  • Bridges and tunnels look disconnected in 2D. A road crossing over another shares no node by design (layer differs). Do not snap endpoints that are near in plan but separated by layer or bridge/tunnel tags.
  • Turn restrictions survive only if the builder expands them. A standard node-edge graph discards via-node restrictions; verify your routing library models them before trusting turn-by-turn output.

Integration Points: Feeding the Router

The audit’s output is a defect manifest, and the clean boundary is that the routing stage consumes a repaired graph while the QA stage consumes the raw one. The wiring below runs the full battery and emits a single structured report, routing each finding to the reviewer who can fix it upstream in the source data:

python 
def audit_topology(place: str) -> dict[str, object]:
    """Run every connectivity check and return a consolidated report."""
    graph = load_drive_graph(place)
    stubs_loops = find_stubs_and_loops(graph)
    report = {
        "islands": rank_weak_components(graph),
        "directional": find_directional_traps(graph),
        "stubs": stubs_loops["stubs"],
        "self_loops": stubs_loops["self_loops"],
        "near_miss": find_near_miss_endpoints(graph, stubs_loops["stubs"]),
    }
    logger.info("topology audit complete for %s", place)
    return report

A green audit is the precondition for graph conversion downstream: only once components, direction, and endpoint snapping are clean does the graph produced by OSMnx Graph Conversion Techniques yield routes a user will trust. Feed the manifest back to whoever authors the source fixes, and re-run the audit after each edit so regressions surface immediately.

Examine Topology QA in Depth

This reference expands into a focused walkthrough of its highest-leverage check:

  • Finding Disconnected Road-Network Components — a complete, runnable procedure that builds a graph, computes weak and strong components, ranks them by size, and reports the isolated islands so unreachable areas can be flagged for repair.

Frequently Asked Questions

What is the difference between weakly and strongly connected components for routing?

A weakly connected component ignores edge direction: it answers whether two nodes are joined at all if you treat every one-way as bidirectional. A strongly connected component respects direction: it answers whether you can travel from one node to another and back following the arrows. One-way traps and islands are invisible to weak-component checks but stand out under strong-component analysis, so a directed routing graph needs both.

Why do two roads that touch on the map still fail to route?

Because rendering and topology are independent. Two ways can be drawn so their endpoints overlap visually while their OSM nodes are distinct points a short distance apart. The router joins edges only where they share a node, so the un-snapped gap means there is no graph vertex linking them. Detect these as degree-1 node pairs closer than a snapping tolerance in a projected coordinate system.

How do I tell a real dead end from a broken road?

Both appear as degree-1 nodes, so a raw count is dominated by legitimate cul-de-sacs. Filter using tags and context: a genuine terminus is often on a residential or service road and may carry noexit=yes, while a truncated road frequently sits near another dead end within a snapping tolerance or ends abruptly on a major highway. Treat the near-miss pairs as the actionable subset rather than every stub.

Why does my router plan an illegal turn even though the data has a restriction?

Turn restrictions live in type=restriction relations with from, via, and to members, not in node references. A plain node-and-edge graph has nowhere to store them, so unless the graph builder expands restricted junctions into penalty edges or a line-graph, the restriction is simply absent and the engine treats the manoeuvre as legal. Rebuild the graph with turn-penalty expansion enabled to model them.

Should topology QA modify the graph automatically?

Detection and repair should be separate. Snapping the wrong pair of endpoints or deleting a real one-way invents or destroys roads, so automated fixes must be gated by a tolerance and human review. The audit should emit a manifest of findings; corrections belong upstream in the source data where they persist across rebuilds rather than as a silent mutation of one derived graph.

Up one level: OSM Data Quality & Validation.