Simplifying an OSMnx Graph Without Losing Geometry

A routing graph built naively from OSM has a node at every shape point, which is ten times more nodes than junctions. Contracting them speeds routing enormously — and does so safely only if the geometry they described moves onto the edge rather than disappearing.

Prerequisites

Conceptual minimum

An OSM way is a sequence of nodes, most of which exist only to describe the road’s shape. A graph that keeps them all has a node of degree two wherever the road merely bends, and every routing algorithm pays for those nodes despite there being no decision to make at them.

Contraction removes a chain of degree-two nodes and replaces it with a single edge between the junctions at its ends. The speed-up is large because routing cost scales with node count.

Three things must survive the contraction.

Geometry. The removed nodes described the road’s shape, and that shape is needed to draw the route and to measure distance honestly. It moves onto the edge as a linestring attribute.

Length. The contracted edge’s length is the sum of the segments it replaced, not the straight-line distance between its endpoints. On a winding road the difference is substantial.

Attributes. A chain may span segments with different speed limits or surfaces. Contracting across such a change either loses information or requires the chain to be split at the change, and which you choose is a modelling decision.

The critical safety rule is that a node is only contractable if it is genuinely degree two in the undirected sense and carries no routing-relevant tags. A node with a traffic signal, a barrier or a turn restriction is a decision point even when only two ways meet there.

Three things a contraction must preserve, and what is lost without each Three panels. Geometry moves from the removed nodes onto the edge as a linestring; without it the route renders as straight lines between junctions and cuts across corners. Length becomes the sum of the replaced segments rather than the straight-line distance; without it every winding road is reported shorter than it is and routing prefers it wrongly. Attributes must be constant along the chain or the chain must be split; contracting across a speed limit change silently averages two different roads into one. Three things to preserve, three losses if not Geometry Moves onto the edge A linestring attribute Without it: straight lines Routes cut corners Length Sum of the segments Not endpoint distance Without it: roads shorten Winding routes preferred Attributes Constant along the chain Or split the chain Without it: values merge Two roads become one The second loss is the one that changes routing decisions rather than merely the drawing, which makes it the most damaging.
All three are cheap to preserve and none of them is preserved by a contraction that only removes nodes.

Runnable solution

python 
from __future__ import annotations

import logging
from collections.abc import Iterable

import networkx as nx
from shapely.geometry import LineString

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.graph.simplify")

# Tags that make a node a decision point even at degree two.
JUNCTION_TAGS = {"highway", "railway", "barrier", "traffic_calming",
                 "crossing", "stop", "give_way", "traffic_signals"}
# Edge attributes that must be constant across a contracted chain.
INVARIANT = ("highway", "oneway", "maxspeed", "access", "surface", "tunnel",
             "bridge")


def is_contractable(graph: nx.MultiDiGraph, node: int) -> bool:
    """Degree two in the undirected sense, and carrying no decision tags."""
    data = graph.nodes[node]
    if JUNCTION_TAGS & set(data):
        return False
    if data.get("street_count", 0) > 2:
        return False
    neighbours = set(graph.predecessors(node)) | set(graph.successors(node))
    neighbours.discard(node)
    # Exactly two distinct neighbours, and no self-loop.
    return len(neighbours) == 2


def edge_signature(data: dict) -> tuple:
    return tuple(str(data.get(key)) for key in INVARIANT)


def chain_from(graph: nx.MultiDiGraph, start: int,
               contractable: set[int]) -> list[int] | None:
    """Follow a chain of contractable nodes outward from a junction."""
    for first in graph.successors(start):
        if first not in contractable:
            continue
        chain = [start, first]
        while True:
            current = chain[-1]
            forward = [n for n in graph.successors(current) if n != chain[-2]]
            if not forward:
                return None                  # dangling; leave it alone
            nxt = forward[0]
            chain.append(nxt)
            if nxt not in contractable:
                return chain                 # reached the far junction
            if nxt in chain[:-1]:
                return None                  # a loop; contracting it is unsafe
    return None


def contract(graph: nx.MultiDiGraph) -> nx.MultiDiGraph:
    """Collapse degree-two chains, carrying geometry, length and attributes."""
    contractable = {n for n in graph.nodes if is_contractable(graph, n)}
    logger.info("%d of %d node(s) are contractable", len(contractable),
                graph.number_of_nodes())

    out = graph.copy()
    processed: set[int] = set()
    contracted = split = 0

    for junction in [n for n in graph.nodes if n not in contractable]:
        chain = chain_from(graph, junction, contractable)
        if chain is None or any(n in processed for n in chain[1:-1]):
            continue

        # Attributes must be constant along the chain, or it must be split.
        signatures = set()
        coords: list[tuple[float, float]] = []
        total_length = 0.0
        for a, b in zip(chain, chain[1:]):
            data = min(graph[a][b].values(), key=lambda d: d.get("length", 0.0))
            signatures.add(edge_signature(data))
            total_length += float(data.get("length", 0.0))
            geom = data.get("geometry")
            points = list(geom.coords) if geom else [
                (graph.nodes[a]["x"], graph.nodes[a]["y"]),
                (graph.nodes[b]["x"], graph.nodes[b]["y"])]
            coords.extend(points if not coords else points[1:])

        if len(signatures) > 1:
            # A speed limit or surface changes mid-chain: leave it alone rather
            # than averaging two genuinely different roads into one edge.
            split += 1
            continue

        first_edge = min(graph[chain[0]][chain[1]].values(),
                         key=lambda d: d.get("length", 0.0))
        attributes = {k: v for k, v in first_edge.items()
                      if k not in {"length", "geometry"}}
        attributes["length"] = total_length          # summed, not straight-line
        attributes["geometry"] = LineString(coords)  # the shape survives
        attributes["contracted_nodes"] = len(chain) - 2

        out.add_edge(chain[0], chain[-1], **attributes)
        out.remove_nodes_from(chain[1:-1])
        processed.update(chain[1:-1])
        contracted += 1

    logger.info("contracted %d chain(s); left %d chain(s) with varying "
                "attributes; %d node(s) remain", contracted, split,
                out.number_of_nodes())
    return out


if __name__ == "__main__":
    logger.info("contract, then verify junction count and total length")

Step-by-step walkthrough

  1. Define contractable strictly. Degree two in the undirected sense, no self-loop, and no tag that makes the node a decision point. A traffic signal between two road segments is a junction even though only two ways meet.
  2. Use the street count where available. OSM graph builders record how many streets meet at a node, which is a better junction test than graph degree alone on a directed multigraph.
  3. Walk outward from junctions. Starting a chain at a junction and following contractable nodes guarantees the chain ends at junctions on both sides.
  4. Refuse loops. A chain that returns to a node it has already visited is a roundabout or a loop road, and contracting it produces an edge from a node to itself.
  5. Sum the lengths. The contracted edge’s length is the total of the segments replaced. Using the endpoint distance shortens every winding road and biases routing towards them.
  6. Concatenate geometry without duplicating shared points. Each segment’s first coordinate is the previous segment’s last, and including both puts a zero-length step in the linestring.
  7. Refuse to contract across an attribute change. A chain whose speed limit or surface varies describes two different roads, and merging them loses the distinction silently. Leaving it uncontracted costs a node and preserves the truth.
  8. Record how many nodes were removed. That attribute is what lets somebody later confirm the contraction did what they think, and it costs one integer.
Node and edge counts before and after contraction on a city network Four counts for a city-scale drive network. The raw graph built from OSM holds a large number of nodes, most of which merely describe road shape. After contraction the node count falls by roughly eighty percent, leaving close to the number of real junctions. Edge count falls correspondingly. Routing time falls faster than node count because shortest-path cost grows worse than linearly with the number of nodes explored. Contraction on a city drive network Raw nodes baseline Contracted nodes about 21% Contracted edges about 26% Routing time about 14% Routing improves more than the node count alone suggests, because search cost grows faster than linearly with graph size.
The uncontracted graph is not wrong, merely ten times larger than the decisions it encodes require.
Whether a degree-two node may be contracted away A decision node examining one degree-two node, with three outcomes. A node carrying a tag that represents a decision or a constraint, such as traffic signals or a barrier, is a junction and must be kept regardless of its degree. A node where an edge attribute changes on either side marks a boundary between two different roads, so the chain is split there rather than contracted through it. A node that is merely a shape point, with no tags and identical attributes on both sides, is contracted away and its coordinate moves into the edge geometry. Is this degree-two node really just a shape point? Tags, or an attribute change? Two checks before contracting Either one keeps the node Keep: it is a junction Carries signals, a barrier or another decision tag Keep: attributes change Speed limit or surface differs on either side Contract it away A pure shape point; its coordinate joins the edge geometry Both checks are cheap and both are commonly skipped, which is why contracted graphs so often lose signals and speed limits.
Only the third branch removes anything, and it removes nothing a router or a renderer needed.

Verification

  • Junction count is preserved. Count nodes with a street count above two before and after; the two must match exactly.
  • Total length is preserved. Summing edge lengths across the graph should give the same figure within floating-point tolerance.
  • Geometry is present on contracted edges. Every edge with a non-zero contracted-node count must carry a linestring.
  • No self-loops appeared. An edge from a node to itself means a loop was contracted.
  • A route matches. Route between two points on both graphs; the geometry should be identical and the distance equal.

Common errors and fixes

Symptom Root cause One-line fix
Routes cut across corners Geometry not carried onto the edge Concatenate segment geometry into a linestring attribute
Winding roads look shorter Length taken as endpoint distance Sum the replaced segments’ lengths
Traffic signals disappear Node tags not checked Treat decision-carrying tags as junction markers
Speed limits averaged away Contracted across an attribute change Refuse chains whose invariant attributes vary
Self-loops in the output A loop road contracted Detect a repeated node and abandon the chain
Zero-length steps in geometry Shared endpoints duplicated Skip the first coordinate of each subsequent segment
Junction count changed Degree tested on the directed graph Test degree on the undirected neighbour set

Specification reference

OSM ways contain both junction nodes and interstitial nodes that exist only to describe geometry. Graph simplification contracts chains of non-junction nodes into single edges, and a correct implementation transfers the removed geometry onto the edge and sums the segment lengths. See the OSMnx simplification documentation for the library’s own implementation and the attributes it preserves.

Frequently Asked Questions

Why is edge length not the distance between the endpoints?

Because the road between them is not straight. A contracted chain may follow a curve, a switchback or a winding valley road, and the straight-line distance between its junctions can be a fraction of the distance actually travelled. Using it makes every winding road look shorter than it is, which biases routing towards exactly the roads that take longest to drive.

What makes a degree-two node a junction anyway?

A tag that represents a decision or a constraint: traffic signals, a barrier, a gate, a crossing, a stop line. Two road segments meeting at a gate is still a place where something happens to a traveller, and contracting it away removes that from the graph entirely. Which tags count depends on the routing mode, so the list is a configuration rather than a constant.

Should I contract across a speed limit change?

No, unless you are prepared to lose the distinction. A chain spanning a change describes two roads with different properties, and one edge can carry only one value. Splitting the chain at the change keeps both, at the cost of one extra node; merging them silently applies one road’s speed limit to the other. Refusing to contract is the conservative default, and the count of refusals tells you how often it matters.

How much does contraction actually speed up routing?

More than the node reduction alone suggests, because shortest-path search cost grows faster than linearly with the number of nodes explored. An eighty percent reduction in nodes typically produces a larger reduction in routing time, and the effect compounds when many routes are computed. It also reduces memory, which matters when a graph is held for a continent rather than a city.

Up one level: OSMnx Graph Conversion Techniques.