Python API

The modules most worth reading, with their public functions and classes. Generated from the docstrings.

ridegraph.graph

Road network storage and the weighted routing graph built from it.

Two layers, kept separate on purpose:

• RoadNetwork is the raw map: where nodes are, which segments join them, how long each segment is and what kind of road it is. It is what the data pipeline produces and what gets saved to disk.
• Graph is what algorithms run on: a compact directed graph whose edge weights are travel times. Changing the cost model (traffic, time of day) means building a new Graph from the same RoadNetwork.

Edges are stored in CSR (compressed sparse row) form: all outgoing edges of node u live in head[first_out[u]:first_out[u + 1]]. It is the layout production routing engines use, being cache friendly and trivially serialised.

RoadNetwork dataclass

Raw directed road segments, before any cost model is applied.

Two-way streets appear as two edges, one per direction. maxspeed_kph is NaN where OSM has no usable limit. traffic_signals marks nodes with lights; networks saved before it existed load as all-False.

Graph

Directed graph in CSR form with travel-time weights in seconds.

out_edges(u)

Yield (neighbour, seconds) for each edge leaving u.

nearest_node(lat, lon)

Index of the node closest to a coordinate (equirectangular, fine at city scale).

edge_between(u, v)

Index of the cheapest edge u -> v; raises if none exists.

OffNetworkError

Bases: ValueError

A coordinate too far from any road in the network.

haversine_m(lat1, lon1, lat2, lon2)

Great-circle distance in metres.

csr_sorted(network)

The same network with edges stored in CSR order (stably sorted by source).

After this, an edge's index in the network equals its index in Graph, so edge-indexed data (turn graphs, exports) lines up without remapping.

free_flow_speeds_kph(network)

Free-flow speed per edge, vectorised (same rule as speeds.free_flow_speed_kph).

free_flow_cost(network)

Seconds per edge at free-flow speed (no traffic).

snap(network, lat, lon, max_m=500.0)

Nearest junction to a coordinate; raises OffNetworkError beyond max_m.

ridegraph.dijkstra

Dijkstra's algorithm: the correctness baseline every faster method is tested against.

It grows a ball of settled nodes around the source in order of travel time, so by the time the target is settled its time is provably optimal. The cost is that the ball covers everything closer than the target in every direction, which is exactly the waste A* and Contraction Hierarchies remove.

Implementation notes:

• Binary heap with lazy deletion. Instead of a decrease-key operation, a better distance is simply pushed again and stale entries are skipped when popped. In Python this beats any hand-rolled indexed heap.
• Distances live in a dict touched only for reached nodes, so a short query on a big graph does not pay to initialise an array of every node.

dijkstra(graph, source, target)

Quickest route from source to target (node indices).

one_to_all(graph, source)

Travel time from source to every node (inf if unreachable).

ridegraph.ch

Contraction Hierarchies: the preprocessing trick behind production routing engines.

Idea

Rank every node by "importance", then remove (contract) them one at a time, least important first. Removing node v can break quickest routes that pass through it, so for each neighbour pair u -> v -> w we check whether some other route from u to w is at least as quick (a witness). If not, we add a shortcut edge u -> w with the combined cost and remember it skips v.

After all nodes are contracted, every quickest route in the original graph has an equivalent route in the augmented graph that only goes up the ranking from the source and then only down the ranking into the target. A query is therefore a bidirectional Dijkstra in which each side may only climb. Each side sees a tiny "upward cone" of the graph instead of a ball of the city, which is where the orders-of-magnitude speedup comes from.

Implementation choices

• Node order by lazy priority updates: priority is the edge difference (shortcuts added minus edges removed) plus the number of already-contracted neighbours, which spreads contraction evenly across the map. A node's priority is recomputed when it reaches the top of the queue; if it is no longer the minimum it goes back in.
• Witness search is a local Dijkstra capped by cost and settled count. If the cap is hit we add the shortcut anyway: an unneeded shortcut costs a little space, never correctness.
• Stall-on-demand at query time: if a node can be reached more cheaply through a higher-ranked node the search has already seen, its upward distance is provably not optimal and its edges are not expanded.
• Path unpacking: each shortcut stores its middle node, so a route of shortcuts expands recursively back into real road segments.

ContractionHierarchy

A contracted road graph that answers quickest-route queries fast.

up_* arrays hold, for each node u, edges u -> v to higher-ranked nodes. down_* arrays hold, for each node v, edges u -> v from higher-ranked nodes, indexed at v so the backward search can climb from the target.

query(source, target)

Quickest route from source to target.

upward_search(start, *, backward=False)

Exhaustive search up the hierarchy from start, with stall-on-demand.

Returns the settled, unstalled nodes and their distances. Every quickest route meets at a node that both ends' upward searches settle correctly, which is what makes bucket-based many-to-many queries work.

target_buckets(targets)

Backward upward searches from each target, filed by the node they reach.

many_to_many(sources, targets, buckets=None)

Travel time from every source to every target (inf if unreachable).

Bucket-based many-to-many (Knopp et al., 2007): one backward upward search per target files its distances in buckets at the nodes it reaches; one forward upward search per source then reads the buckets of the nodes it reaches. Cost grows with sources + targets, not their product, which is what lets a dispatcher price every driver against every waiting rider at once. Reuse buckets when targets repeat.

unpack(hierarchy_path)

Expand a route over shortcut edges into the original road nodes.

ridegraph.cch

Customizable Contraction Hierarchies: preprocessing once, new traffic in milliseconds.

Ordinary Contraction Hierarchies (ch.py) choose which shortcuts to add by running witness searches with the current travel times. Change the times (a closure, a jam) and the whole hierarchy is stale. Customizable CH (Dibbelt, Strasser and Wagner, 2016) splits the work in three:

1. Metric-independent preprocessing (slow, once per map). Order the junctions by nested dissection: cut the city in two along a thin separator, order each half recursively, and put the separator last. Then contract in that order without witness searches: every pair of higher neighbours gets a shortcut. The result is a fixed "chordal" graph whose size does not depend on travel times.
2. Customization (fast, whenever times change). Give every original road its current time, then sweep the lower triangles bottom-up: for a shortcut u-w over a lower junction v, u->w = min(u->w, u->v + v->w). Every shortcut now holds the true quickest time between its ends using only lower junctions, which is exactly what the CH query needs.
3. Queries as in CH: two upward searches meeting at the top.

Because step 1 never looks at travel times, the separators come from the road layout alone: a geometric cut picks the direction (north-south, east-west or a diagonal) that crosses the fewest roads, the way rivers and parks make natural cuts in a real city.

CustomizableCH dataclass

Chordal graph from contracting in a fixed order, with per-metric weights.

customize(road_seconds)

Load travel times for every original road and sweep the lower triangles.

query(source, target)

Quickest time and junction path; customize must have run.

nested_dissection_order(network, leaf_size=LEAF_SIZE)

Rank of every junction; separators are ranked above the parts they split.

ridegraph.router

One entry point for routing under a scenario: time of day, weekday or weekend, turns.

The algorithms only know about graphs and node ids. Router builds the right graph for a scenario and translates both ways, so callers think in intersections and coordinates while the search runs on whichever graph (plain or turn-expanded) the scenario needs.

Scenario dataclass

file_tag()

Distinguishes cached hierarchies built for different scenarios.

Trip dataclass

A route expressed in intersections of the original road network.

Router

nearest(lat, lon)

Nearest intersection to a coordinate.

search_nodes(origin, destination)

Graph node ids to search between for two intersections.

trip(origin, destination, algorithm='bidirectional', ch=None)

Quickest trip between two intersections.

ridegraph.alternatives

Alternative routes: a few genuinely different ways to make the same trip.

A map app that shows only the quickest route hides useful choices: a route a minute slower that avoids a charge, or stays on main roads. Good alternatives must be (Abraham et al., "Alternative routes in road networks"):

• different: share at most max_overlap of their length with any route already offered;
• not much slower: at most max_stretch times the quickest;
• sensible: no pointless detours.

This module uses the penalty method: find the quickest route, make every road on it a little slower, search again, and repeat. Each search is pushed off the roads already used, so it finds the next most natural corridor. Candidates are judged on the real travel times, not the penalised ones. A detour check then rejects candidates that leave a road only to rejoin it: every short stretch of the route must be close to the quickest way between its ends.

The same machinery avoids an area: roads into it cost infinity, so every route found keeps out. That is how the Congestion Charge zone is avoided.

shortest(graph, source, target, weight)

Dijkstra on custom weights, returning (seconds, CSR edge ids).

zone_weights(graph, zone)

Travel times with every road into the zone closed.

is_locally_sensible(graph, alt, window_s, tolerance, weight, samples=8)

Stretches of about window_s are within tolerance of their quickest way.

Checks samples stretches spread along the route, which catches the detours the penalty method produces (leaving a road only to rejoin it) without a search from every junction.

alternatives(graph, source, target, *, count=3, penalty=1.4, max_stretch=1.3, max_overlap=0.65, attempts=8, zone=None, avoid_zone=False, local_check=True)

Up to count routes, quickest first; avoid_zone keeps them out of zone.

ridegraph.live

Live road disruptions from Transport for London, matched onto the graph.

TfL's open Unified API lists current roadworks, closures and incidents on London's streets, each as a polyline with a severity and a closure state (/Road/all/Street/Disruption). This module

1. fetches and parses that feed (standard library only, no key needed for light use),
2. map-matches each disrupted stretch onto graph edges: an edge is on the stretch when both its ends and its midpoint lie within MATCH_M metres of the polyline, and
3. turns the result into a time multiplier per edge: infinity for a closed road, a slowdown for the rest by severity.

The multipliers are applied to the time-of-day weights, and a Customizable Contraction Hierarchy (cch.py) re-customises in milliseconds, so the quickest-route queries stay instant with live closures in force.

fetch(timeout=30.0)

Current street disruptions as parsed JSON.

parse(payload)

Every disrupted stretch in the feed, wherever it sits in the JSON.

match(network, disruptions)

Time multiplier per edge (1 where clear), and how many edges each stretch hit.

ridegraph.reach

Travel-time maps: everywhere reachable within a time budget.

An isochrone answers "where can I get to in 20 minutes from here?" (or, for someone choosing where to live, "from where can I get to my office in 20 minutes?"). It is a single-source search that settles every junction in time order and stops at the budget, so it touches only the reachable part of the city. Run on the reverse graph, the same search measures journeys into a point.

Reachable area is reported by counting 250 m squares that contain a reached junction, which tracks what a map reader sees better than a convex hull would around a river or a park.

times_within(graph, origin, budget_s, *, arriving=False)

Seconds from origin (or to it, if arriving) for every junction within budget.

ridegraph.tour

Multi-stop routes: the best order to visit a list of addresses.

A courier with a van and ten drops wants the order that gets them all done soonest: the travelling salesman problem, on real one-way streets, so the time from A to B is not the time from B to A. The pipeline:

1. One matrix of travel times. A many-to-many Contraction Hierarchies query prices every stop against every other stop at the chosen time of day.
2. Exact for small jobs. Held-Karp dynamic programming finds the provably best order in O(n^2 2^n) time, which is instant up to about a dozen stops.
3. Heuristics for comparison and for larger jobs. Nearest-next-stop construction, then 2-opt and Or-opt improvement (re-evaluating whole tours, since reversing a stretch of an asymmetric tour changes its cost).

The first stop is the depot. Tours either return to it or end at the last drop.

improve(matrix, order, *, return_to_start)

2-opt and Or-opt moves until no move shortens the tour (depot stays first).

held_karp(matrix, *, return_to_start)

Provably optimal order starting at stop 0 (Held-Karp dynamic programming).

plan_matrix(matrix, *, return_to_start=True)

Compare visiting orders for a travel-time matrix (stop 0 is the depot).

plan(ch, stops, *, return_to_start=True)

Compare visiting orders for stops (depot first).

ridegraph.matching

Assigning drivers to riders.

Given a matrix of pickup times (driver x rider), find the assignment that minimises the total. This is the linear assignment problem; the Hungarian algorithm solves it exactly in O(n^2 m) using dual potentials, here in the compact shortest-augmenting-path form.

Rectangular inputs are fine: with more drivers than riders every rider is matched; with more riders than drivers every driver is. Pairs that must not be matched (pickup too far away) carry FORBIDDEN and are dropped from the result afterwards.

hungarian(cost)

Minimum-cost assignment as (row, col) pairs, one per row or column.

optimal_matches(cost, limit)

Minimum total cost matching that never uses a pair above limit.

Pairs over the limit (or infinite) cost FORBIDDEN, so the assignment first matches as many pairs as it can, then minimises their total.

greedy_matches(cost, limit)

Riders in arrival order (columns) each take the nearest free driver (rows).

ridegraph.eta

Learned ETA: correcting the router's estimate from how trips actually go.

Production ride-hailing systems do not trust the routing engine's ETA as is. The graph knows road speeds, but not the queue that always forms at a particular junction, how long lights really hold you at 8:30, or that the evening peak arrives later than the timetable says. The approach popularised by Uber's DeepETA keeps the routing engine and trains a model to predict the residual: the gap between the engine's ETA and the trip time actually observed, from features of the route and the moment.

Real trip logs for London are not public, so this module also provides the observations: World is a hidden ground truth, a city that differs from the router's model in ways a real one would. It has congestion hotspots, a later and stronger peak, extra slowdown on main roads, waits at turns and lights, occasional incidents and noise. Trips are routed with the router, timed by the world, and models learn the correction from route features alone. They are judged on trips they never saw.

Everything a feature uses is something a production system would know at request time: the route, its geometry and road mix, its manoeuvres and the time. Nothing reads the hidden world.

The model runs in the browser too: the gradient-boosted trees export to JSON and web/js/eta.js computes the same features and walks the same trees.

RouteContext

Everything needed to describe a route, built once per network.

The network is put in CSR order so edge ids match Graph and the turn graph, exactly as in the browser export.

edge_times(hour, weekend)

Router's seconds per edge at a time of day (same model as traffic.py).

path_edges(path, times)

Cheapest edge between each consecutive pair of junctions.

turns_along(edges)

Turn kind of each manoeuvre between consecutive edges of a route.

light_sets(path, edges)

Sets of traffic lights a route passes.

OpenStreetMap often tags lights on each approach to a junction and on nearby crossings, so signal nodes closer than LIGHT_SET_GAP_M along the route count as one set.

World dataclass

The hidden ground truth that trip times are drawn from.

None of this is visible to the router or to the features; the models must infer its effects from routes and outcomes.

field_at(x_km, y_km)

Hidden hotspot intensity at a point (km from the network's centre).

class_group(road_class)

0 for major roads, 1 for secondary/tertiary, 2 for minor roads.

simulate_trips(ctx, world, hierarchies, count, *, seed=1, min_crow_km=0.4, log=lambda msg: None)

Route random trips with the router and time them in the hidden world.

Trips are routed with the hierarchy of the nearest preset time, like an app whose routes are refreshed a few times a day, then timed at their own hour.

export_trees(model, features=FEATURES)

Gradient-boosted trees as compact arrays the browser can walk.

predict_from_json(model_json, x)

Reference implementation of the browser's tree walk, used in tests.

train(network, *, trips=20000, hierarchies=None, seed=0, gnn_epochs=25, log=lambda msg: None)

Simulate trips, train and compare ETA models, return the best for export.

gnn_hotspot_correlation(model, ctx, world)

Correlation of the GNN's per-road slowdown at 08:30 with the hidden truth.

slowdown_at(model_json, x_km, y_km, hour, weekend)

Model's expected slowdown for a typical trip placed at a point (as in the map).

learned_hotspot_correlation(model_json, ctx, world, *, hour=8.5)

Pearson correlation between the model's slowdown map and the hidden hotspots.

The model never sees the hotspots; a strong correlation means it recovered where they are from trip outcomes alone.

conformal_margin(low, high, y, *, coverage=0.8)

Widening (in log space) that gives coverage on new data.

Conformalized quantile regression (Romano et al., 2019): score each calibration trip by how far it falls outside the predicted range (negative when inside), and widen both ends by the right quantile of those scores.

interval_metrics(low, high, middle, observed)

How often observed times fall inside the window, and how wide it is.

ridegraph.gnn

A graph neural network ETA: learn a slowdown for every road, from trips alone.

The gradient-boosted model (eta.py) sees a route as one row of summary features. A graph neural network instead works on the roads themselves, the way DeepMind's model for Google Maps does: it learns a representation of every road segment from the segment and its neighbourhood in the network, predicts how much slower than the router each segment really is at a given time, and adds the segments of a route up.

Architecture (numpy only, gradients written out by hand):

• Message passing, precomputed. Each road segment starts with its own features: road class, length, traffic lights, junction size, and its position encoded with sines and cosines. Features are then averaged over the line graph (segments are neighbours when one leads into the other) for 1, 2, 4 and 8 hops with symmetric normalisation, and all hops are concatenated. Precomputing the propagation is the SIGN approach (Frasca et al., 2020): it scales to every road in a city, and a learned network on top decides which hop to trust for each road.
• A segment network. A two-layer MLP reads a segment's representation together with the time of day and predicts g, the log of its slowdown.
• A route readout. Predicted time is the sum over the route's segments of router seconds x exp(g), plus a learned wait for each kind of turn and each set of traffic lights, also by time of day.

The loss is the squared error of log(predicted / observed), trained with Adam on minibatches of trips.

TripBatch dataclass

Trips as segment occurrences: which trip, which segment, router seconds.

SegmentGNN dataclass

segment_log_slowdown(edges, tau)

g for given segments at one time of day.

segment_features(network, graph, group, x_km, y_km)

Own features of every segment (CSR edge order).

line_graph(graph)

Normalised adjacency of segments: e follows f when f ends where e starts.

propagate(features, adjacency)

Concatenate the features averaged over 0, 1, 2, 4 and 8 hops.

batch(trips, idx)

Gather selected trips (edges, router seconds, counts, time features, observed).

ridegraph.osrm

A head-to-head with OSRM, the open-source routing engine used in production.

Agreeing with yourself proves little: every algorithm here is tested against Dijkstra, but all of them share this package's map parsing and speed model. OSRM (Open Source Routing Machine) shares neither. It parses OpenStreetMap with its own C++ code and routes with Multi-Level Dijkstra, the engine behind many commercial map products.

To compare like with like, OSRM is given the same roads and the same speeds:

• write_osm_xml writes the ways this package treats as drivable, with their tags, as OSM XML for osrm-extract;
• write_segment_speeds writes this package's free-flow speed for every road segment as an OSRM segment speed file, which osrm-customize loads in place of OSRM's own speed guesses;
• the CI workflow switches off OSRM's turn and traffic-light penalties, since the free-flow router here has none.

compare then asks both engines the same random questions and reports how often the travel times agree, how much of the two routes coincide, and how long each takes to answer. Differences that remain come from the parts that are genuinely independent: OSM parsing, which ways each engine accepts, how coordinates snap to roads, and OSRM storing times in tenths of a second.

write_osm_xml(payload, path)

Drivable ways and the nodes they use, as OSM XML; returns (nodes, ways).

write_segment_speeds(network, path)

from_osm_id,to_osm_id,speed_kmh for every directed road segment.

osrm_route(base_url, a, b)

One OSRM route request (coordinates are (lat, lon)).

compare(network, route, ask_osrm, *, queries=1000, seed=7, min_km=1.0)

Ask both engines the same questions and summarise how they agree.

ridegraph.validation

How realistic is the simulated London? A check against published speeds.

The learned ETA is trained and scored on trips timed in a hidden simulated city (eta.World), because real trip data is not available to a personal project. That makes one question unavoidable: are its speeds plausible for central London? This module times random trips in the simulated city at several times of day and sets the results beside independent published figures:

• Department for Transport, Travel time measures for local 'A' roads, 2022 (tables CGN0503b and CGN0503d): average speed on local A roads in the City of London 7.7 mph and Camden 8.1 mph, the two slowest local authorities in England, and 14.4 mph across Greater London.
• TomTom Traffic Index 2023: London's city centre averaged about 10 mph, falling to 8.5 mph at peak hours.

The definitions differ (DfT measures A roads only, TomTom whole trips in its own city-centre area), so the comparison is about the range, not a single target.

simulated_speeds(network, hours=(3.0, 8.0, 13.0, 17.5), trips=300, *, min_km=2.0, seed=3)

Distance-weighted average speed of random trips at each hour (weekday).

ridegraph.api

An HTTP routing service: the engine behind a JSON API.

The map runs in the browser; a product would also want a backend. This module wraps the package as a FastAPI application:

• GET /route: the quickest route at any time of day, optionally with alternatives and Congestion Charge avoidance, as GeoJSON, with the learned ETA and its arrival window when a model is loaded.
• GET /reach: area reachable within some minutes, leaving or arriving.
• POST /tour: the best order for a round of stops.
• GET /health: what is loaded.

Any time of day, not just presets. Queries run on a Customizable Contraction Hierarchy (cch.py) built once at start-up. A request for 08:15 loads that quarter-hour's travel times into it, which takes tens of milliseconds, and the result is kept in a small cache, so later requests in the same quarter-hour pay nothing. A plain CH would need seconds of preprocessing per time.

Searches share one hierarchy, so they run under a lock; each takes a few milliseconds, and the service scales by running more worker processes.

RoutingService

Everything the endpoints need, loaded once.

TourRequest

Bases: BaseModel

Stops as [lat, lon] pairs, depot first.

create_app(service)

The FastAPI application around a loaded RoutingService.

app_from_env()

App factory for uvicorn --factory and multi-worker serving.

Reads RIDEGRAPH_NETWORK (default data/central-london.npz) and the optional RIDEGRAPH_ETA_MODEL.