Connectivity damage is the failure mode that reaches production most often, because it produces no error anywhere in the build. A severed junction yields a graph that loads, serves queries, and returns perfectly good routes everywhere except the district it cut off — where it returns no route at all, or a route the long way round. This page covers the audit that catches it, as part of graph fragmentation prevention in OSM data within OSM Graph Architecture & Network Modeling.

The audit itself is a few lines. What makes it useful is running it on every build, comparing against the previous one, and failing rather than warning.

When to use this approach

Every build, without exception. The audit costs seconds on a metro graph and a couple of minutes on a national one, which is negligible against any build it gates.

It matters most after the three operations that most often sever things: a change to the routable highway-class set, a change to snapping tolerance, and an extract re-clip. All three are routine and all three can quietly disconnect a region.

Why coverage alone is not the gate Between two builds the largest component's coverage falls from 99.81 to 99.74 percent, which passes any reasonable threshold. The component diff shows a new isolated component of 214 nodes covering a named suburb, which is the actual regression. The same regression, seen two ways coverage threshold at 99.5 % build 41 99.81 % build 42 99.74 % — still passes no signal at all component diff against build 41 + new component, 214 nodes Marsh Lane, Old Mill Rd, Quarry Cl − 0 components merged named, located, and actionable A threshold catches catastrophic damage. Local damage — one suburb, one industrial estate — moves coverage by less than the noise between builds. Keep both: the threshold as a floor, the diff as the thing that actually fires.

Implementation

# requires: networkx (pip install networkx)
import networkx as nx


def component_report(G: nx.DiGraph, *, min_report_nodes: int = 20) -> dict:
    """Strongly connected components, coverage, and the reportable fragments."""
    comps = sorted(nx.strongly_connected_components(G), key=len, reverse=True)
    if not comps:
        return {"coverage": 0.0, "components": 0, "fragments": []}

    total = G.number_of_nodes()
    fragments = []
    for comp in comps[1:]:
        if len(comp) < min_report_nodes:
            continue                    # cul-de-sacs and parking aisles are normal
        names = sorted({
            d.get("name") for _, _, d in G.edges(comp, data=True) if d.get("name")
        })
        fragments.append({
            "nodes": len(comp),
            "roads": names[:5],
            "signature": min(comp),     # stable id for diffing across builds
        })
    return {
        "coverage": round(len(comps[0]) / total, 5),
        "components": len(comps),
        "fragments": fragments,
    }

Collecting road names is what turns the report from a number into something a person can act on. “A new 214-node component exists” prompts an investigation; “Marsh Lane and Old Mill Road are now unreachable” prompts a fix.

The signature — the minimum node id in the component — gives a stable identity across builds so the diff can distinguish a genuinely new fragment from one that has existed for months.

# requires: none beyond the standard library
def diff_reports(previous: dict, current: dict) -> dict:
    """New and resolved fragments between two builds."""
    prev = {f["signature"]: f for f in previous.get("fragments", [])}
    curr = {f["signature"]: f for f in current.get("fragments", [])}
    return {
        "new": [curr[s] for s in curr.keys() - prev.keys()],
        "resolved": [prev[s] for s in prev.keys() - curr.keys()],
        "coverage_delta": round(
            current["coverage"] - previous.get("coverage", current["coverage"]), 5
        ),
    }

Reporting resolved fragments as well as new ones is worth the extra line. A build that repairs a long-standing gap is good news, and seeing it confirms the audit is measuring what you think it is.

The gate itself should be blunt:

# requires: none beyond the standard library
def gate(current: dict, previous: dict, *, floor: float = 0.99) -> None:
    """Fail the build on new fragments or a coverage floor breach."""
    d = diff_reports(previous, current)
    problems = []
    if current["coverage"] < floor:
        problems.append(f"coverage {current['coverage']:.5f} below floor {floor}")
    if d["new"]:
        for f in d["new"]:
            roads = ", ".join(f["roads"]) or "unnamed ways"
            problems.append(f"new isolated component: {f['nodes']} nodes — {roads}")
    if problems:
        raise SystemExit("connectivity audit failed:\n  " + "\n  ".join(problems))

Raising rather than logging is the entire point. A connectivity warning in a build log is a connectivity warning nobody reads.

One question comes up whenever this gate is proposed: what about the legitimate fragments? Every real extract has them. An island served only by ferry, a pedestrianised city centre, a private industrial estate behind a barrier — all are correctly isolated in a drive graph, and all will appear in the fragment list on the very first run.

The answer is a baseline rather than an exception list. Run the audit once against a build you have inspected and accepted, store its component signatures, and treat that as the starting state. Thereafter the gate fires only on components that were not in the baseline, which is exactly the set that represents change. Legitimate fragments never fire again, and they do not need individually maintaining — they simply sit in the baseline until something merges them, at which point the audit reports them as resolved and you learn that a ferry connector was added upstream.

The baseline needs refreshing whenever a fragment is accepted deliberately, which in practice means a small review step attached to the same pull request that changed the extract or the routable class set. That keeps the accept decision next to the change that caused it rather than in a separate configuration file nobody revisits.

Key parameters and tuning

Parameter Recommended value Notes
Connectivity kind strongly connected Weak connectivity passes one-way traps
Coverage floor just below a known-good build An adopted number is either too loose or fires constantly
min_report_nodes 20 Below this, fragments are cul-de-sacs and parking aisles
Component signature minimum node id Stable across builds, so the diff means something
Names per fragment 5 Enough to locate it; more makes the report unreadable
Failure mode raise A warning in a build log is not a gate
Baseline storage alongside the graph artefact Travels with the build it describes

Integration points

In the build pipeline. The audit runs after topology assembly and before weight computation, so a severed graph never reaches the expensive stages. It is the same position in the pipeline as the gate described in detecting breaking tag changes between PBF snapshots, and the two together cover the topology and semantic halves of build regression.

With incremental rebuilds. A partition-scoped rebuild must run the audit on the stitched result, not per partition. Boundary damage is invisible inside a partition by construction — see incremental graph rebuilds without full reprocessing.

With repair. A confirmed new fragment feeds the snapping and connector work in repairing ferry and tunnel connectivity gaps, which covers the structural cases the ordinary snap tolerance cannot reach.

Audit placement in the build pipeline Topology assembly is followed immediately by the connectivity audit, which gates the weight computation and contraction stages. Failing early means a severed graph never consumes the hours those later stages take. Fail before the expensive stages, not after them topology assembly ~8 min connectivity audit ~20 s weight computation ~35 min contraction / tiles ~2 h fail — nothing downstream runs Running the audit last would still catch the defect, three hours later and after the artefact had already been written. Twenty seconds early is worth two hours late, every time. What the audit costs relative to the build it gates Strongly connected component analysis takes just over a second on a city graph and about seventy-four seconds on a country graph, against a full build time of nearly three hours. Audit runtime against graph size city, 180 k nodes 1.2 s metro, 1.4 M nodes 9 s country, 12 M nodes 74 s full build it gates 2 h 40 min Under one percent of build time for the only check that catches a severed district. There is no size at which skipping it is a reasonable economy. Tarjan is linear in nodes plus edges, so the runtime scales predictably and will not surprise you as the extract grows.

Validation checklist

  • A deliberately severed edge is caught. Delete a bridge from a copy of the graph and confirm the audit reports a new component containing the far side.
  • The audit is strong, not weak. Reverse one edge of a two-way pair on a dead-end street and confirm the audit reports it. A weak audit will not.
  • Signatures are stable. Run the audit twice on the same graph and confirm identical signatures. Unstable ids make every build look like it introduced new fragments.
  • Road names appear. Confirm the report names ways rather than only counting nodes. A report without names is a report nobody acts on.
  • The gate actually fails the build. Introduce a fragment in CI and confirm the pipeline stops. A gate that has never fired has never been tested.