Generating Connected Road Networks Without Orphan Edges

A generated street network renders beautifully and routes badly: a router finds no path between two places a few hundred metres apart, and inspecting the geometry shows two roads that appear to meet and do not.

Part of Synthetic Network & Graph Topology Generation: that page covers topology as a validation dimension in general. This one is the specific recipe for the defect that produces most of the reports — an edge whose endpoint coincides with nothing, and the disconnected fragments that follow from it.

Root Cause: Two Coordinates That Should Be One

Every orphan has the same origin. Two segments that logically share a junction carry coordinates that differ in their least significant bits, because they arrived from different computations — one from a projection, one from an interpolation, one read back from a file whose precision was truncated on write.

Nothing about the geometry is wrong. Both lines are valid, both endpoints are inside the envelope, and the two points are a fraction of a micron apart. But a graph builder comparing coordinates for equality sees two distinct nodes, creates two degree-one nodes instead of one degree-four junction, and the network silently acquires a hole.

The defect compounds in a way that makes it worse than it first appears. One orphan produces two dead ends. A handful of orphans along the boundary between two generated tiles disconnects everything on one side from everything on the other, so a defect measured in nanometres produces a routing failure measured in kilometres.

Unroutable node pairs against orphan rate, for uniform and seam-concentrated orphans The horizontal axis is the share of edges that are orphaned, from zero to ten per cent. The vertical axis is the share of node pairs for which no route exists. The lower curve models orphans distributed uniformly across the network: the unroutable share rises roughly in step with the orphan rate, which is the intuition most people bring to the problem. The upper curve models the same orphans concentrated on the seams between generated tiles, which is where they actually occur, because a seam is exactly where two coordinate computations meet. A seam carries only a handful of edges, so a small orphan rate severs whole seams and disconnects entire tiles; the curve rises far more steeply and reaches a large unroutable share while the orphan rate is still a fraction of a per cent. The gap between the two curves is the point: an orphan rate measured per edge understates the routing damage by roughly an order of magnitude, and the number worth gating on is the routable-pair share rather than the orphan count. An orphan rate per edge understates the damage by an order of magnitude 0% 2% 4% 6% 8% 10% 0% 25% 50% 75% 100% orphaned edges (% of all edges) node pairs with no route (%) a quarter of pairs unroutable at 6.0% orphans orphans concentrated on tile seams — the real case orphans spread uniformly — the intuition A 6×6 tile layout, 90 edges per tile, fixed seed. A seam carries only a handful of edges, so a small orphan rate severs whole seams and disconnects entire tiles. Gate on the routable-pair share, not on the orphan count.
Measured on generated tiles: the share of node pairs left unroutable rises far faster than the orphan rate, because orphans concentrate on tile seams.

Minimal Reproducer: Manufacture an Orphan

python
from shapely.geometry import LineString
import networkx as nx

# Two roads that meet at (100, 100) — computed two different ways.
a = LineString([(0.0, 100.0), (100.0, 100.0)])
b = LineString([(100.0 + 1e-9, 100.0), (200.0, 100.0)])   # a projection round-trip

g = nx.Graph()
for line in (a, b):
    coords = list(line.coords)
    g.add_edge(coords[0], coords[-1])

print("nodes:", g.number_of_nodes())                  # 4, not 3
print("components:", nx.number_connected_components(g))   # 2, not 1
print("degree-1 nodes:", [n for n, d in g.degree() if d == 1])   # all four

Four nodes where there should be three, two components where there should be one, and every node a dead end. Nothing raised, and a map of these two lines is indistinguishable from a map of a correctly connected pair.

Fix: Node on a Precision Grid, Then Reduce

The fix has three parts and they must run in this order, because each depends on the previous one having happened.

1 — Snap coordinates onto a declared grid before anything else

python
from shapely import set_precision

GRID = 1e-6        # ≈ 0.11 m at the equator — declare it in the data contract


def snap(lines: list) -> list:
    """Round every coordinate onto the grid, so 'nearly equal' becomes 'equal'."""
    return [set_precision(line, GRID) for line in lines]

set_precision is doing exactly the job of the node_key function on the parent page, but inside the geometry rather than alongside it, which means every downstream operation sees the snapped values rather than having to remember to snap again. Choosing the grid step is the one real decision here: measure the coordinate disagreement between endpoints that should coincide, and set the step an order of magnitude above it while staying an order of magnitude below the smallest genuine separation in the network.

2 — Node the whole set, so crossings become junctions

python
from shapely.ops import unary_union, linemerge


def node(lines: list) -> list:
    """Split every line at every intersection. Crossings become endpoints."""
    merged = unary_union(lines)
    return list(linemerge(merged).geoms) if merged.geom_type != "LineString" else [merged]

This is where junctions are created. A pipeline that snaps but does not node still has flyovers at every crossing, because snapping makes coincident endpoints equal and does nothing about two lines that cross in their interiors.

3 — Drop degenerate stubs, then reduce to the largest component

python
def build(lines: list, min_length: float = GRID * 4) -> nx.MultiGraph:
    g = nx.MultiGraph()
    for line in node(snap(lines)):
        if line.length < min_length:
            continue                                   # noding residue, not a road
        a, b = line.coords[0], line.coords[-1]
        if a == b:
            continue                                   # a closed loop with no junction
        g.add_edge(a, b, geometry=line, length=line.length)
    return g


def reduce_to_largest(g: nx.MultiGraph) -> tuple[nx.MultiGraph, dict]:
    comps = sorted(nx.connected_components(g), key=len, reverse=True)
    kept = g.subgraph(comps[0]).copy()
    report = {
        "components_before": len(comps),
        "nodes_dropped": g.number_of_nodes() - kept.number_of_nodes(),
        "largest_dropped": len(comps[1]) if len(comps) > 1 else 0,
    }
    return kept, report

The largest_dropped figure is the diagnostic worth watching. A few one- and two-node fragments are ordinary noding residue and reducing them away is correct. A dropped component with hundreds of nodes means something structural — usually that the network was generated as separate tiles and the seams were never joined — and reducing it away silently deletes a district.

The three-step orphan fix, its ordering, and the failure produced by each reordering Three steps run left to right. Snapping to a declared precision grid turns coordinates that are nearly equal into coordinates that are equal, which fixes coincident endpoints; it leaves crossings in line interiors untouched, and running it after noding means the noding compared unsnapped coordinates and created the orphans this step was meant to prevent. Noding splits every line at every intersection so crossings become endpoints, which creates the junctions; it leaves behind sub-grid fragments as residue, and running it before snapping produces the failure just described. Dropping degenerate stubs and reducing to the largest component removes the residue and guarantees a single component; it leaves nothing for a later step, and running it before noding reduces a graph whose junctions do not yet exist, which deletes real districts as though they were fragments. A footer records the diagnostic that distinguishes correct residue removal from damage: the size of the largest dropped component. A handful of one- and two-node fragments is ordinary; a dropped component of hundreds of nodes is structural and means the reduction has just deleted a district. Three steps, and each reordering fails in a different way 1 · snap to the grid nearly equal becomes equal fixes: coincident endpoints leaves: interior crossings out of order: noding compares unsnapped coordinates and makes the orphans 2 · node the whole set split at every intersection fixes: missing junctions leaves: sub-grid fragments out of order: the failure above 3 · drop stubs, reduce residue out, one component fixes: stubs and fragments leaves: nothing out of order: reduces a graph whose junctions do not exist yet The diagnostic: the size of the largest dropped component. A handful of one- and two-node fragments is ordinary noding residue. A dropped component of hundreds of nodes is structural — the reduction has just deleted a district. Reduction is the step that hides the evidence, which is why it runs last and reports what it removed.
The three steps and what each one leaves behind — running them out of order produces a graph that passes the check the previous step was supposed to satisfy.

Verification Step: Assert Routability, Not Just Connectivity

python
import pytest


def test_single_component(graph):
    assert nx.number_connected_components(graph) == 1


def test_no_dead_end_explosion(graph, max_share=0.20):
    """A plausible network has cul-de-sacs. It does not have 60% of them."""
    dead = sum(1 for _, d in graph.degree() if d == 1)
    share = dead / graph.number_of_nodes()
    assert share < max_share, f"{share:.1%} of nodes are dead ends — check the grid step"


def test_dropped_component_is_residue(report, max_nodes=8):
    assert report["largest_dropped"] <= max_nodes, (
        f"dropped a component of {report['largest_dropped']} nodes — this is structural"
    )


def test_sampled_pairs_route(graph, rng, n=300):
    nodes = sorted(graph.nodes())
    for _ in range(n):
        a = nodes[rng.integers(len(nodes))]
        b = nodes[rng.integers(len(nodes))]
        assert nx.has_path(graph, a, b)

The dead-end share check is the one that catches a grid step set too fine, and it catches it before anything downstream does. A network whose grid is finer than its coordinate agreement does not fail the component check — reducing to the largest component hides the problem by deleting the evidence — but it does end up with an implausible number of degree-one nodes, because every orphan contributes two.

Why the Symptom Is Usually Reported as Something Else

The reason this defect takes so long to identify is that nobody reports it as a topology problem. The reports that arrive describe three unrelated-sounding symptoms, and all three are this.

The first is missing demand. A routing or assignment step silently produced no result for a subset of origin-destination pairs, and the totals came out low. Nobody looked at the routing step, because it did not fail — it returned an empty path, which the pipeline treated as a legitimate answer, and the loss appears as a demand shortfall in a district rather than as an error anywhere.

The second is an implausible flow pattern. Traffic that should distribute across two parallel corridors is entirely on one, because the other is not reachable from the origins. The pattern looks like a modelling problem — a badly calibrated route-choice model, an unrealistic cost function — and every attempt to fix it in the model fails, because the model is correct and the graph is not.

The third is a matcher that assigns traces to the wrong road. Fixes along an orphaned segment are matched to whatever is reachable, which is a different street, and the result is reported as a noise-model problem. Widening or narrowing the noise changes nothing, for the same reason.

All three resolve the moment somebody counts the connected components, which takes one line and is worth running before any of the more interesting hypotheses.

Edge Cases & Gotchas

Roundabouts become single nodes. If the grid step is coarser than a small roundabout’s diameter, its entire ring collapses to one node and every approach becomes a spoke. The symptom is a cluster of degree-five and degree-six nodes where the network should have degree-three junctions; the fix is a finer grid, or modelling small roundabouts as junctions deliberately and recording that choice.

Lower and upper bounds on the precision-grid step, with the usable window A logarithmic scale runs from a nanodegree to a hundredth of a degree. Two bounds are marked. The lower bound is the largest coordinate disagreement measured between endpoints that ought to coincide — below it, coincident endpoints stay distinct and orphan edges survive. The upper bound is the narrowest genuine separation in the network, typically the gap between two divided carriageways or between a road and its service road — above it, two junctions that should stay separate merge, which creates a road connecting places it should not. The shaded band between them is the usable window, and it is annotated with its width in orders of magnitude. Three reference values are marked along the scale for context: a typical projection round-trip disagreement, a typical divided-carriageway separation, and the recommended step, placed an order of magnitude above the lower bound. A note records what to do when the two bounds cross: the fix is upstream, in how the geometry was constructed, rather than in the choice of step. Both bounds are measurable — so the step is a measurement, not a taste 1e-9° 1e-8° 1e-7° 1e-6° 1e-5° 1e-4° 1e-3° 1e-2° lower bound largest measured disagreement between endpoints that should coincide upper bound narrowest genuine separation — divided carriageways recommended step an order of magnitude above the disagreement usable window — 2 orders of magnitude Measure both before choosing: the disagreement from endpoints that ought to be identical, and the separation from the closest pair of features that must stay distinct. If the bounds cross, the fix is upstream in how the geometry was constructed — no step will work.
Both bounds are measurable before the step is chosen — and if they cross, the fix is upstream.

Bridges and tunnels get noded into junctions. Noding is a planar operation and it will happily create a junction where a motorway passes over a lane. Carry a level attribute and include it in the node key, so that two lines at different levels never share a node however close their coordinates are.

Divided carriageways connect through the median. Two parallel carriageways within a grid step of each other merge. This is the case where a coarse grid does real damage, because the resulting network permits U-turns that do not exist. Measure the narrowest genuine separation in the source before choosing the step, and treat that number as the ceiling.

The reduction is not idempotent. Running the whole build twice on its own output should change nothing. If it does, something is not snapping — usually a geometry that was reconstructed from a WKT round trip at a different precision between the two runs.