Location Intelligence Retail Site Selection Automation

Validating Routable Network Topology Before Isochrone Runs

This page solves one exact task: running a topology validation suite against a newly built routing graph, so a batch of ten thousand contours is never computed on a network that is quietly broken.

The reason this needs its own gate is that a broken graph does not fail. It returns polygons — smaller ones, or oddly shaped ones, or perfectly normal ones everywhere except the market whose bridge was severed by a clip. Nothing raises, nothing logs, and the error surfaces weeks later as a candidate site that scored badly for no reason anyone can reconstruct.

Prerequisites

  • A built graph from preparing OSM network extracts for routing, not yet promoted to serving.
  • Python packages: networkx or scipy.sparse.csgraph for component analysis, geopandas for the store layer, httpx for probing the engine. Install with pip install networkx geopandas httpx scipy.
  • The store estate with validated coordinates, so snapping can be checked against real locations rather than synthetic points.
  • A fixed route set — a few hundred origin-destination pairs with known durations from the previous build.

Configuration and execution parameters

Parameter Value for this task Notes
min_giant_component_share 0.985 Share of edges in the largest component
max_components_over 50 edges Count of non-trivial islands
snap_tolerance_m 250 Store to nearest routable node
probe_pairs 400 Fixed origin-destination set
duration_tolerance_pct 5 Per-route change that triggers review
contour_sample 200 stores Areas compared build to build
contour_tolerance_pct 8 Area change that triggers review
fail_action block promotion Never a warning that a human must notice

The two tolerance rows exist because a rebuild should change things. A gate set at zero fires every month and gets disabled; a gate set generously never fires at all. Five and eight per cent are starting points to be tuned from a few builds’ worth of observed variation.

Four checks, four distinct failures Component analysis catches a severed network; store snapping catches a store stranded on an island or a service road that vanished; route probes catch a profile or speed change; and contour area comparison catches everything else that moves a catchment without moving a single route in the probe set. Each check has one job and one characteristic failure check catches typical cause component analysis a severed network a clip that was too tight store snapping stores on islands a service road excluded by the profile route probes durations shifting an edited speed table contour areas everything else a turn-restriction flag flipped The last row is the catch-all and the slowest, which is why it runs on a sample rather than the estate. Running all four takes a few minutes against a built graph and replaces the alternative, which is discovering the problem after ten thousand contours have been computed and cached. Order them cheap-first: a failed component check makes the rest moot.

Annotated implementation

The suite below runs against the built graph before promotion and returns a structured result the gate can act on.

python
from __future__ import annotations

from dataclasses import dataclass

import geopandas as gpd
import httpx
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components

MIN_GIANT_SHARE = 0.985
SNAP_TOLERANCE_M = 250.0
DURATION_TOL = 0.05


@dataclass
class TopologyReport:
    giant_share: float
    components_over_50: int
    stores_off_giant: list[str]
    unsnapped_stores: list[str]
    route_regressions: list[tuple[str, float]]

    @property
    def passed(self) -> bool:
        return (self.giant_share >= MIN_GIANT_SHARE
                and not self.stores_off_giant
                and not self.unsnapped_stores
                and not self.route_regressions)


def components(edges: np.ndarray, n_nodes: int) -> tuple[float, int, np.ndarray]:
    """Edges as an (m, 2) array of node indices. Undirected for this purpose:
    a one-way pair still means the two nodes are in the same component."""
    data = np.ones(len(edges), dtype=np.int8)
    graph = coo_matrix((data, (edges[:, 0], edges[:, 1])), shape=(n_nodes, n_nodes))
    n_comp, labels = connected_components(graph, directed=False)
    sizes = np.bincount(labels)
    giant = sizes.argmax()
    return sizes[giant] / n_nodes, int((sizes > 50).sum() - 1), labels == giant


def check_stores(stores: gpd.GeoDataFrame, engine: str,
                 in_giant: np.ndarray) -> tuple[list[str], list[str]]:
    """Every store must snap within tolerance AND land in the giant component."""
    unsnapped, off_giant = [], []
    with httpx.Client(base_url=engine, timeout=20.0) as client:
        for row in stores.itertuples():
            lon, lat = row.geometry.x, row.geometry.y
            r = client.get(f"/nearest/v1/driving/{lon},{lat}")
            r.raise_for_status()
            wp = r.json()["waypoints"][0]
            if wp["distance"] > SNAP_TOLERANCE_M:
                unsnapped.append(row.store_id)
            elif not in_giant[wp["nodes"][0]]:
                off_giant.append(row.store_id)
    return unsnapped, off_giant

Treating the graph as undirected for component analysis is deliberate. A pair of one-way streets forming a loop is perfectly routable, and a strict strongly-connected-component analysis would flag legitimate one-way systems as unreachable. Directed reachability matters and belongs in the route probes, where it can be measured against a known answer rather than inferred from structure.

Failure modes and debugging

Stores that snap far from the road. A store snapping two hundred metres away is usually a service road that the profile excluded rather than a bad coordinate — retail parks are full of them. The tell is a cluster of such stores in similar formats; checking whether the profile admits service ways resolves most of them at once.

A giant-component share that is high and still wrong. A network can be 99 per cent connected and have the missing one per cent be a whole market. Reporting the share alone hides that; reporting components by their geographic extent, or simply checking store membership, finds it. This is why the store check exists alongside the structural one.

Probe routes that all fail. Almost always the engine pointing at the previous graph rather than the new one, which is a deployment question rather than a topology one. Querying the engine for its build version at the start of the suite eliminates a surprising amount of confusion.

A tolerance that never fires. If the gate has passed on every build for a year, it may be well-tuned or it may be measuring nothing. Feeding it a deliberately damaged graph once a quarter — a clip with no buffer, a profile with turn restrictions disabled — proves it still rejects, in the same spirit as every other assertion in the pipeline.

The same market, two builds, two component profiles A healthy build puts 99.2 per cent of edges in the largest component with twelve islands over fifty edges and no stores stranded. A build from a tight clip puts 94.1 per cent in the largest component with 214 islands and nine stores stranded — all nine within fifteen kilometres of the clip boundary. Five per cent of edges missing is nine stores that cannot be scored healthy build largest component 99.2% 12 islands over 50 edges · 0 stores stranded · promote build from a tight clip largest component 94.1% 214 islands · 9 stores stranded, all within 15 km of the clip edge · block The geographic pattern in the stranded stores is the diagnosis: clustered at the boundary means the clip, scattered across the market means the profile.

Verification

  • Damage a graph on purpose and confirm the suite blocks it. A clip with zero buffer is the easiest damage to produce and exercises the component and store checks together.
  • Confirm the engine under test is serving the candidate build, by asserting its reported version before any probe runs.
  • Check the probe set still covers the estate. Routes chosen two years ago may all sit in markets that have since become a small share of the business; refreshing the set annually keeps it representative.
  • Record every run’s measurements, not only its verdict. The trend in giant-component share across builds is what shows a clip slowly becoming inadequate as markets expand.
The measurement worth trending, not just gating Giant-component share sits between 99.1 and 99.3 per cent for nine builds, then drifts to 98.8, 98.6 and 98.4 over the last three as new markets were added to the clip without widening the buffer. Every build passed the gate; the trend is what shows the clip needs revisiting. Every build passed — and the trend is still telling you something 99.4% 99.0% 98.6% gate 98.5% three markets added, buffer unchanged The last point is one build away from blocking, and it will block on a Sunday night unless the clip is widened first — which is the entire argument for trending a gate's measurements rather than its verdicts.

Frequently Asked Questions

Should validation run against the graph files or against a running engine?

Both, for different checks. Component analysis reads the graph structure directly and does not need a service; store snapping and route probes need an engine because they exercise the query path, which has its own failure modes — a graph that loads fine and a service configured to a different profile look identical structurally. Running a temporary engine instance against the candidate build gives both without touching production.

How many probe routes are enough?

Enough to cover every market and every road class the business depends on, which in practice means a few hundred rather than a few thousand. What matters more than the count is the spread: routes that all sit within one metro tell you nothing about a rural rebuild, and routes chosen at random tend to over-represent wherever the stores are densest. Choosing them deliberately — a handful per market, spanning short urban and long interurban trips — is a one-off exercise with a long payoff.

What if a genuine road change fails the gate?

Then the gate did its job and the answer is to promote deliberately rather than to loosen the threshold. A motorway opening changes durations across a whole market, and that is exactly the kind of change the analytics team should hear about before catchments move. Recording the override — what changed, who approved it, which routes moved — keeps the gate meaningful for the next build.

Can this suite replace the checks inside the contour pipeline?

No, they answer different questions. This suite asks whether the graph is sound; the contour checks ask whether an individual polygon is plausible — that it contains its origin, that its area is in a sensible band, that nested bands nest. A sound graph still produces bad contours from bad inputs, and a good contour can be produced from a graph that is broken somewhere else. Both layers are cheap and neither subsumes the other.

Who should receive the validation report?

Whoever can act on each part of it. The component and snapping results belong to whoever owns the extract and the profile; the route and contour regressions belong to the analytics team, because they describe how the world changed rather than whether the build worked. Sending the whole report to one channel produces a document nobody reads; splitting it along those lines produces two short messages that each land with someone who can do something.

Can the suite run against a subset to keep it fast?

The structural checks cannot usefully be sampled — a component analysis on part of the graph is a different question — but the store, route and contour checks can, and sampling them well is what keeps the suite to a few minutes. Stratify the sample so every market and density band is represented, keep it fixed between builds so comparisons are like-for-like, and refresh it only when the estate changes materially. A rotating random sample makes every build’s numbers incomparable with the last, which defeats the purpose.

← Back to Preparing OSM Network Extracts for Routing