Synthetic Network & Graph Topology Generation

Most synthetic spatial work generates things that sit in space. A network is different: it generates the thing that other things move along, and its correctness is defined by traversal rather than by geometry. This page is part of Spatial Distribution & Pattern Generation, and it covers the sub-problem of producing road, utility and transit graphs that a router, a flow model or a Markov-chain routing model can actually use.

The distinction matters because every check that works for points and polygons fails here. A network can be geometrically flawless — every line valid, every coordinate inside the envelope, the density statistics matching a reference perfectly — and still be useless, because two halves of it are not connected to each other and no journey can cross between them. Geometry validation cannot see that. Only traversal can.

Problem Framing: Four Ways a Plausible Network Is Unusable

Each of these produces a network that looks correct on a basemap and fails the first time something tries to route across it.

Disconnection. The graph has more than one connected component. A router asked for a path between two of them returns nothing, and the failure surfaces as an unexplained gap in the results rather than as an error — the request simply produced no route, and a pipeline that treats “no route” as a legitimate answer will silently drop those trips.

Orphan and dangling edges. An edge whose endpoint coincides with nothing, usually because two segments that should share a node have coordinates differing by a floating-point epsilon. The line is drawn, the intersection is not created, and traffic that should turn there cannot.

Missing junction nodes at crossings. Two edges cross geometrically and share no node. This is the same defect as the last one seen from the other side, and it is what makes a generated grid behave like a set of overpasses.

Implausible degree distribution. The graph is fully connected, every junction exists, and the network still does not behave like a road network — because real street networks have a characteristic distribution of junction degrees, dominated by three- and four-way intersections with very few of anything else, and a generator that places edges at random produces a degree histogram no city has.

Four network defects against five checks, showing the blind spot of geometric validation Rows are defects: the graph having more than one connected component, orphan and dangling edges whose endpoints coincide with nothing, missing junction nodes where two edges cross, and an implausible junction-degree distribution. Columns are checks. Geometry validity passes every one of the four, because every line involved is a perfectly valid linestring. Envelope containment passes all four for the same reason. Edge-count parity against a reference passes all four, because none of the defects changes how many edges exist. The connected-component count catches disconnection and nothing else. The un-noded crossing count catches missing junctions and, indirectly, the orphan edges that share their cause. Nothing in the row for degree distribution is caught by any of the five, which is why a fifth check — comparing the degree histogram against a reference — has to exist separately. The conclusion drawn underneath is that a pipeline running only geometric gates on a network has no coverage at all of the property the network exists to have. Every geometric check passes all four defects Defect geom. valid in envelope edge count components crossings disconnected components ✓ passes ✓ passes ✓ passes ✗ catches ✓ passes orphan / dangling edges ✓ passes ✓ passes ✓ passes ✓ passes ✗ catches missing junction nodes ✓ passes ✓ passes ✓ passes ✓ passes ✗ catches implausible degree profile ✓ passes ✓ passes ✓ passes ✓ passes ✓ passes The last row is caught by none of the five. A degree-histogram comparison against a reference is a separate check, and it is the one that separates a routable network from one that routes like a real place. Geometry gates are necessary and blind here — topology is a validation dimension of its own.
Which check catches which defect: every geometric validation passes all four, and the topological ones each see exactly one.

The table above is the argument for treating topology as a validation dimension of its own. Geometry gates are necessary and they are blind here, and a pipeline that runs only geometry gates on a network has no coverage of the property the network exists to have.

Prerequisites & Toolchain

networkx==3.3           # the graph model and the connectivity algorithms
shapely==2.0.4          # geometry, and the noding operations
geopandas==0.14.4       # the I/O boundary

One decision precedes all of these: the network is a graph with geometry, not a geometry collection that happens to be linear. Holding it as a GeoDataFrame of LineStrings and computing topology on demand means the topology is re-derived — and re-derived slightly differently — at every stage that needs it. Holding it as a graph whose edges carry geometry means the topology is the artifact, and the geometry is an attribute of it.

Core Concept: Node Identity Is the Whole Problem

Nearly every defect above reduces to one question: when do two coordinates refer to the same node?

Answering it by exact floating-point equality guarantees orphans, because coordinates that arrive from different computations are almost never bit-identical. Answering it by proximity within a tolerance creates a different problem — the relation is not transitive, so three points pairwise within tolerance can chain into a cluster wider than the tolerance, and the resulting node placement depends on the order the points were processed in.

The stable answer is a precision grid: snap every coordinate to a fixed grid, and define node identity as equality of the snapped coordinates. That relation is transitive, order-independent and reproducible, and the grid step is a declared parameter rather than an emergent property of the data.

python
from dataclasses import dataclass

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


def node_key(x: float, y: float, grid: float = GRID) -> tuple[int, int]:
    """Node identity: a pair of integers, not a pair of floats."""
    return (round(x / grid), round(y / grid))

The choice of grid step is the same trade-off as in fixing sliver polygons: too fine and coincident endpoints stay distinct, too coarse and genuinely separate junctions merge. The difference is that here the consequence of merging is a road that connects two places it should not, which is worse than a sliver, and worse in a way no geometric check will report.

Three node-identity rules against the four properties a topology build requires Rows are rules. Exact float equality is transitive, order-independent and reproducible, and it has no parameter to declare — but it fails in practice, because coordinates arriving from different computations are almost never bit-identical, so it guarantees orphan edges. Proximity within a tolerance finds the coincident endpoints that exact equality misses, and it is not transitive: three points pairwise within tolerance can chain into a cluster wider than the tolerance, so the resulting node placement depends on the order the points were processed in and the result is not reproducible between runs. Snapping to a precision grid and comparing the snapped integers is transitive by construction, independent of processing order, reproducible, and its grid step is an explicit declared parameter rather than an emergent property of the data. A closing note records what makes the grid step a genuine decision rather than a formality: too fine and coincident endpoints stay distinct, too coarse and two junctions that should be separate merge into one — which produces a road connecting two places it should not, and no geometric check will report it. Node identity decides everything else — so make it a declared rule Rule transitive order-independent reproducible declared parameter exact float equality ✓ ✓ ✓ none — and it never matches proximity within a tolerance ✗ ✗ ✗ a tolerance, applied pairwise snapped to a precision grid ✓ ✓ ✓ the grid step, in the contract The grid step is the decision, and it cuts both ways. Too fine and coincident endpoints stay distinct, producing orphans. Too coarse and two junctions merge — a road that connects two places it should not, which no geometric check reports.
Three node-identity rules against the properties a topology build needs — only the grid rule is transitive and order-independent.

Step-by-Step Implementation

Step 1 — Node the geometry before building the graph

python
from shapely.ops import unary_union, linemerge
from shapely import segmentize


def node_network(lines: list) -> list:
    """Split every line at every intersection, so crossings become endpoints."""
    # unary_union of a linear collection splits at intersections — this is the whole
    # operation, and skipping it is what produces overpasses.
    return list(linemerge(unary_union(lines)).geoms)

unary_union over a set of lines splits them at every point where they cross. It is one call, it is where junctions come from, and a pipeline that builds a graph directly from source geometry without it produces a network in which every crossing is a flyover.

Step 2 — Build the graph on snapped node keys

python
import networkx as nx


def build_graph(lines: list, grid: float = GRID) -> nx.MultiGraph:
    g = nx.MultiGraph()
    for line in lines:
        coords = list(line.coords)
        a, b = node_key(*coords[0], grid), node_key(*coords[-1], grid)
        if a == b and line.length < grid * 4:
            continue                                # a degenerate stub, not an edge
        g.add_node(a, x=coords[0][0], y=coords[0][1])
        g.add_node(b, x=coords[-1][0], y=coords[-1][1])
        g.add_edge(a, b, geometry=line, length=line.length)
    return g

The degenerate-stub guard matters more than it looks. A zero-length or sub-grid edge creates a self-loop that a router will happily traverse forever, and it arrives from noding operations rather than from the source data, so it is not something a source-data check would have caught.

Step 3 — Reduce to the largest connected component, and record what was dropped

python
def keep_largest_component(g: nx.MultiGraph) -> tuple[nx.MultiGraph, dict]:
    components = sorted(nx.connected_components(g), key=len, reverse=True)
    kept = g.subgraph(components[0]).copy()
    dropped = {
        "components_dropped": len(components) - 1,
        "nodes_dropped": g.number_of_nodes() - kept.number_of_nodes(),
        "edges_dropped": g.number_of_edges() - kept.number_of_edges(),
        "largest_dropped_component": len(components[1]) if len(components) > 1 else 0,
    }
    return kept, dropped

Returning the drop record rather than logging it is deliberate. The size of the largest dropped component is a diagnostic: a handful of one- and two-node fragments is normal noding residue, while a dropped component with hundreds of nodes means the network was generated as two separate networks and the connection between them was never made.

Step 4 — Calibrate the degree distribution, not just the edge count

python
from collections import Counter


def degree_profile(g: nx.MultiGraph) -> dict[int, float]:
    counts = Counter(d for _, d in g.degree())
    total = sum(counts.values())
    return {k: v / total for k, v in sorted(counts.items())}


REFERENCE = {1: 0.14, 3: 0.42, 4: 0.38, 5: 0.05, 6: 0.01}   # a typical urban grid

Degree one is the dead-end share, and it is the entry that most often reveals a generator has been tuned on the wrong thing: real street networks have a substantial dead-end fraction from cul-de-sacs, and a generator penalised for producing them will produce a network that is unnaturally well connected and routes too efficiently.

Junction-degree distributions for three generation strategies against an urban reference Junction degrees one through six run along the horizontal axis; the vertical axis is the share of nodes at each degree. Four series are plotted. The urban reference is dominated by degree three and degree four — ordinary T-junctions and crossroads — with a substantial degree-one share from cul-de-sacs and very little else. A pure lattice produces almost exclusively degree four with a thin edge effect and essentially no dead ends, which is why a generated grid routes far more efficiently than a real city. Random edge placement spreads mass across every degree including implausibly high ones, because nothing constrains how many streets meet at a point. A growth process fitted to the reference structure tracks it closely at every degree. All four have the same edge count over the same extent, so no edge-count or density check distinguishes them. The note underneath picks out the entry that most often reveals a mis-tuned generator: the degree-one share, because a generator penalised for producing dead ends yields a network that is unnaturally well connected and systematically underestimates travel time. Same edge count, same extent — only the degree histogram separates them 1 2 3 4 5 6 0% 20% 40% 60% junction degree (streets meeting at a node) share of nodes reference (urban) pure lattice random edges structure-fitted growth The degree-one share is the entry that most often reveals a mis-tuned generator: a generator penalised for producing dead ends yields a network that is unnaturally well connected, routes too efficiently, and makes every model trained on it underestimate travel time.
Measured degree distributions for four generation strategies against an urban reference — the edge count matches in all four, and only one matches the shape.

Validation & Testing

python
def test_network_is_one_component(graph):
    assert nx.number_connected_components(graph) == 1


def test_no_isolated_or_stub_edges(graph):
    assert not [n for n, d in graph.degree() if d == 0]
    assert not [(u, v) for u, v, k in graph.edges(keys=True) if u == v]


def test_every_crossing_has_a_node(lines, graph):
    """No two edges may cross except at a shared node."""
    crossings = 0
    for i, a in enumerate(lines):
        for b in lines[i + 1:]:
            if a.crosses(b):
                crossings += 1
    assert crossings == 0, f"{crossings} un-noded crossings"


def test_degree_profile_within_tolerance(graph, reference=REFERENCE, tol=0.05):
    got = degree_profile(graph)
    for degree, share in reference.items():
        assert abs(got.get(degree, 0.0) - share) < tol, (degree, got.get(degree, 0.0))


def test_random_pairs_are_routable(graph, rng, n=200):
    nodes = sorted(graph.nodes())
    for _ in range(n):
        a, b = rng.choice(nodes), rng.choice(nodes)
        assert nx.has_path(graph, a, b)
Six stages of a network build with the closing gate for each The stages run left to right. Snap rounds every coordinate onto the declared precision grid and is closed by asserting that re-snapping changes nothing. Node splits every line at every intersection and is closed by a zero un-noded-crossing count. Build assembles the graph on snapped node keys and is closed by asserting that no edge is a self-loop and none is shorter than the grid step. Reduce keeps the largest connected component and is closed by asserting that the largest dropped component is small enough to be noding residue rather than a district. Restrict attaches turn restrictions and one-way flags and is closed by asserting every junction's permitted manoeuvres are enumerable. Profile measures the structural statistics and is closed by comparing them against the contract's declared profile. A footer notes that each gate is cheap and each is only meaningful after its predecessor has run, which is why the order is the same as the dependency order. Six stages, six gates, and each only meaningful after the last snap onto the grid GATE re-snapping changes nothing node split at crossings GATE zero un-noded crossings build graph on node keys GATE no self-loops, no sub-grid edges reduce largest component GATE largest dropped ≤ 8 nodes restrict turns and one-ways GATE manoeuvres enumerable per junction profile structural statistics GATE matches the contract profile Each gate is one assertion and each is only meaningful once its predecessor has run — a component check before noding reduces a graph whose junctions do not exist yet, and a profile check before restriction measures a network that permits manoeuvres it should not.
Each gate is one assertion, and each is only meaningful once its predecessor has run.

The last of these is the one worth running even when the component check already passed, because it exercises the graph through the same API a consumer will. A graph that is connected in networkx and unroutable in the consumer’s engine usually differs in how one-way restrictions or turn restrictions are represented, and only a routing test finds that.

Performance & Scale Considerations

The crossing test above is quadratic and is fine for a few thousand edges and unusable beyond that. Replace it with a spatial index once the network is large:

python
from shapely import STRtree

def crossings(lines: list) -> int:
    tree = STRtree(lines)
    count = 0
    for i, a in enumerate(lines):
        for j in tree.query(a):
            if j > i and a.crosses(lines[j]):
                count += 1
    return count

Noding is the other cost, and it is superlinear in the number of intersections rather than in the number of edges — a dense urban grid nodes far more slowly than a sparse rural network of the same edge count. Where a network is generated tile by tile, node within each tile and then node again across the seams only, rather than noding the whole assembled set: the second pass touches a tiny fraction of the geometry and produces the same result, provided the tiles were cut on a fixed grid origin so the seams are in the same place on every run.

What a Network Release Should Carry Beyond the Geometry

A network artifact that is only geometry forces every consumer to rebuild the topology, and every consumer will rebuild it slightly differently. Three things belong in the release alongside the lines, and all three are cheap.

The precision grid step is first, because it is the parameter that decides node identity and therefore the entire topology. A consumer who re-snaps at a different step gets a different graph from the same file. Declaring it means a consumer can reproduce the producer’s topology exactly, and it means a defect in the choice is attributable rather than mysterious.

The structural profile is second — intersection density, block-area median and spread, orientation entropy, dead-end share and the degree histogram. These are the numbers a validation gate compares against, and shipping them turns “does this network look right” from a judgement into a check. They are also the honest way to describe what the network resembles, since six numbers carry no address while a perturbed copy of real geometry carries every one.

The restriction coverage is third and most often omitted. A network whose turn restrictions are ninety per cent complete behaves very differently from one that is thirty per cent complete, and a consumer matching traces against it will attribute the difference to the traces. Record the share of junctions carrying at least one restriction, and record where the restrictions came from, so a discrepancy with a consumer’s better-informed network is explicable.

None of the three is expensive to produce, and all three are impossible for a consumer to recover from the geometry alone. The pattern is the same one that governs the rest of this area: the things worth shipping are the things that were known at generation time and cannot be inferred afterwards.

Failure Modes & Troubleshooting

  • The router finds no path between two obviously connected places. Check the component count first. If it is one, check for a one-way restriction encoded in a direction the router reads differently from the writer.
  • The graph has thousands of degree-one nodes. Noding produced fragments. Almost always a grid step finer than the coordinate agreement of the source geometry; measure the agreement and set the step above it.
  • Two roads that should not connect are connected. The grid step is coarser than the smallest genuine separation in the network — usually a road passing under another with a small vertical clearance and a small horizontal offset. Either refine the step or carry an explicit level attribute and key node identity on it.
  • The degree profile matches and routes are unrealistically short. The dead-end share is too low. Real networks route less efficiently than well-connected synthetic ones, and a model trained on the synthetic version will underestimate travel time systematically.
  • Noding never finishes. Almost always a self-intersecting input line. Validate and repair the individual geometries before the union rather than after it.
Can I generate a network without a source city at all?

Yes, and it is often the right choice. Pick a structural profile that describes the kind of place you need — a dense grid, an organic core, a low-density suburb — and generate against it. The result carries no relationship to any real network, which removes the disclosure question entirely, and it is perfectly adequate for anything that needs a plausible network rather than a particular one. Fitting to a real city only earns its cost when a consumer’s model has to transfer to that city specifically.

Frequently Asked Questions

Should a synthetic network be planar?

For a street network at the scale most simulations use, yes — and enforcing planarity is what noding does. Real networks are not planar, because bridges and tunnels exist, but they are planar almost everywhere, and the exceptions are far better modelled as an explicit level attribute on the node key than as un-noded crossings. The reason is diagnostic: with a level attribute, an unconnected crossing is a deliberate statement, and without one it is indistinguishable from a bug.

How do I generate a network that matches a real city's structure without copying it?

Fit the structural statistics and generate from them: the degree distribution, the block-size distribution, the orientation entropy — how uniformly street bearings are distributed, which separates a gridded city from an organic one — and the intersection density per square kilometre. Those four capture most of what makes a network look like a particular kind of place, and none of them carries a specific street. Copying geometry and perturbing it is the approach to avoid, for the same reason it is avoided everywhere else in this area: the perturbed version is still linkable to the original.

Do I need turn restrictions?

If anything downstream routes vehicles, yes. Without them a router will generate journeys through turns that are physically or legally impossible, and the traces that result are exactly the ones a map-matching consumer will reject. Represent them as a restriction on node-edge-edge triples rather than as a property of the node, since the same junction permits some turns and forbids others.