osm-katana/src/graph.rs
//! **The road and rail networks as a GRAPH — adjacency cut out of `node_refs`.**
//!
//! [`crate::network`] stores the networks as their own tables instead of duplicating them
//! into every tile. That fixed the size, not the *shape*: a table of geometries answers
//! **"which lines cross this box"** and nothing else. It cannot answer "what meets at this
//! node", "what is cut off if this stretch closes", or "which crossing is nearest **along
//! the network**". This module is the missing half.
//!
//! Nothing new is read to build it. A way's `node_refs` is an ordered list of OSM node
//! ids, and two ways are adjacent iff they share one — **the graph is already in the data,
//! it was simply never indexed.**
//!
//! # What a graph node is, and the measurement that chose it
//!
//! Not every OSM node. MEASURED on `~/.korp/work/sweden/ways.parquet`, 2026-08-04, all
//! 32 row groups:
//!
//! | | roads (`highway=*`) | rails (`railway=*`) |
//! |---|---|---|
//! | ways | 2 272 263 | 29 519 |
//! | node refs | 28 454 707 | 390 715 |
//! | distinct nodes | 25 213 693 | 354 337 |
//! | shared by ≥2 ways | 2 770 954 (11.0 %) | 31 993 (9.0 %) |
//! | distinct endpoints | 3 412 721 | 39 154 |
//! | **shared ∪ endpoints** | **3 632 410 (14.4 %)** | **40 813 (11.5 %)** |
//!
//! So **85.6 % of the nodes in the road network are shape points** — a bend in the road,
//! with exactly one way through them and no choice to make. Keeping them would make the
//! node table 6.9× larger and every routing step 6.9× longer for no answer it could not
//! already give. The graph node set is therefore **shared ∪ endpoints ∪ forced joints**
//! ([`JOINT_CLASSES`]).
//!
//! The union is taken **across both networks at once**, and that is load-bearing: a
//! `railway=level_crossing` is one node with one road way and one rail way through it, so
//! it is shared only if roads and rails are counted together. Counted per network it is
//! an ordinary shape point in each and the two graphs never touch.
//!
//! # What an edge is
//!
//! The stretch of ONE way between two consecutive graph nodes — not the whole way.
//! MEASURED: **4 601 027 road edges vs 2 272 263 whole-way edges (2.02×)**, 47 672 rail
//! edges vs 29 519 (1.61×). The 2× is the price of being routable: a whole-way edge
//! cannot express "turn off half way along", which is what a junction in the middle of a
//! way means, and the middle is where most junctions are.
//!
//! Edge geometry is **sliced out of the way's own WKB by index**, not looked up in a
//! coordinate store: convert writes one point per `node_refs` entry — a `LineString` for
//! an open way, a one-ring `Polygon` for a closed one (see [`line_points`]). MEASURED on
//! the whole cut, 2026-08-04: **320 of 2 301 931 ways (0.014 %)** do not line up, and
//! those fall back to a single whole-way edge and are COUNTED
//! ([`GraphStats::whole_way_fallback`]), never dropped silently.
//!
//! # Direction
//!
//! A graph that ignores `oneway` lies about what is drivable. MEASURED on the road
//! network: `oneway=yes` 107 830, `oneway=-1` 20, `oneway=no` 20 036, absent 2 144 361,
//! plus `junction=roundabout`, which is one-way by definition and does not say so.
//! Resolved at BUILD time into an `Int8` column (`0` both, `1` forward, `-1` backward) so
//! a router never parses a tag — korp's `parse_tags` is 55.9 % of all allocations on a
//! tile read and a router touches every edge it settles.
//!
//! # One writer
//!
//! Both tables are produced inside [`crate::network::extract_networks`], from the rows
//! that pass is already holding, and written through [`crate::spatial::pack_batches`] with
//! a [`crate::network::NetworkRecipe`] in the footer — same layout, same recipe probe,
//! same manifest as the networks themselves (LAW 5). There is no second extractor and no
//! second read of `ways.parquet`.
#![allow(clippy::float_arithmetic)]
use std::collections::HashMap;
use std::path::Path;
use std::sync::Arc;
use arrow::array::{
Array, ArrayRef, BinaryArray, Float64Array, Int8Array, Int32Array, Int64Array, Int64Builder,
StringArray, StringBuilder,
};
use arrow::datatypes::{DataType, Field, Schema};
use arrow::record_batch::RecordBatch;
use parquet::arrow::arrow_reader::ParquetRecordBatchReaderBuilder;
use crate::metadata::{self, GeoMeta};
use crate::network::tag_value;
/// File stem of the edge table.
pub const GRAPH_EDGES: &str = "graph_edges";
/// File stem of the node table.
pub const GRAPH_NODES: &str = "graph_nodes";
/// **Node classes that are forced into the graph even at degree 1.**
///
/// A `railway=level_crossing` is the ONE place the road network and the rail network meet
/// topologically, so an edge must end there whether or not the count says "junction" —
/// otherwise a crossing whose rail way happens to be clipped out of the region extract
/// silently becomes a shape point and the joint disappears. MEASURED 2026-08-03: 8 168 of
/// 9 148 level crossings (89.3 %) are on both a road and a rail; the forcing is what keeps
/// the other 10.7 % addressable instead of invisible.
///
/// Deliberately NOT every rail node: `signal` (18 820) and `milestone` (16 168) sit along
/// a track without joining anything, and splitting an edge at each of them buys nothing.
pub const JOINT_CLASSES: &[&str] = &["level_crossing", "crossing", "railway_crossing"];
/// **The networks the graph is cut from.**
///
/// `trails` is deliberately out: a trail is a tag overlay on ways that are already in
/// `roads` (`highway=path` with `sac_scale`), so graphing it too would emit the SAME way
/// twice — two rows with the same derived edge id and every shared node counted twice.
/// The trail attribute belongs on the road edge, not on a second edge.
pub const GRAPHED_NETWORKS: &[&str] = &["roads", "rails"];
/// The network whose rows supply node classes and node tags to the graph.
pub const GRAPH_NODE_SOURCE: &str = "rail_nodes";
/// Edge ids are **derived, not counted**: `way_id * SEGMENTS_PER_WAY + seq`. A counter
/// would renumber the whole table whenever an upstream row moved; this way an edge id
/// names its way (`id / SEGMENTS_PER_WAY`) and is stable across rebuilds. OSM caps a way
/// at 2 000 nodes ⇒ at most 1 999 segments, so 4 096 has 2× headroom, and the largest OSM
/// way id (~1.4e9) × 4 096 ≈ 5.7e12 is nowhere near `i64::MAX`.
pub const SEGMENTS_PER_WAY: i64 = 4_096;
// ── the columns ─────────────────────────────────────────────────────────────────
/// **The edge table's columns**, the ONE place they are declared (LAW 5) — the recipe
/// derives itself from this list, so a column added here moves the recipe token with no
/// edit anywhere else.
pub fn edge_fields() -> Vec<Field> {
vec![
// `way_id * SEGMENTS_PER_WAY + seq`.
Field::new("id", DataType::Int64, false),
Field::new("network", DataType::Utf8, false),
Field::new("class", DataType::Utf8, false),
Field::new("way_id", DataType::Int64, false),
Field::new("from_node", DataType::Int64, false),
Field::new("to_node", DataType::Int64, false),
// 0 = both ways, 1 = from→to only, -1 = to→from only. Resolved at build time.
Field::new("oneway", DataType::Int8, false),
// Great-circle length along the sliced geometry, metres. A router needs a cost,
// and computing it from the WKB at query time means re-parsing every edge it
// settles.
Field::new("length_m", DataType::Float64, false),
// km/h — the way's own `maxspeed` where it parses, else the class default from
// the ONE [`SPEED_TABLE`] (lane `nvdb`, 2026-09-02). Resolved at BUILD time for
// the same reason `oneway` is: a router touches every edge it settles and must
// not parse a tag to price it.
Field::new("speed_kmh", DataType::Float64, false),
// "maxspeed" | "class" — where `speed_kmh` came from, so coverage is a column
// read, not a re-parse of 2.3 M tag JSONs.
Field::new("speed_source", DataType::Utf8, false),
crate::shared::schema::geometry_field(),
]
}
/// **The node table's columns.** `edges` is the adjacency list itself — the answer to
/// "which segments meet here" as ONE row read, rather than a scan-and-group over the edge
/// table.
pub fn node_fields() -> Vec<Field> {
vec![
// The OSM node id, kept so the join back to `rail_nodes` (and to OSM itself) is an
// exact i64 and not a float-coordinate guess.
Field::new("id", DataType::Int64, false),
// "road" | "rail" | "both". "both" IS the level-crossing set, by construction.
Field::new("kind", DataType::Utf8, false),
// `edges.len()`, broken out so `degree >= 3` prunes on a column statistic without
// decoding the list.
Field::new("degree", DataType::Int32, false),
// The `railway=*` value of this node, where `rail_nodes` had one.
Field::new("rail_class", DataType::Utf8, true),
// The rail node's own tags, so `crossing:barrier` is askable from the graph alone.
Field::new("tags", DataType::Utf8, true),
Field::new(
"edges",
DataType::List(Arc::new(Field::new("item", DataType::Int64, true))),
false,
),
crate::shared::schema::geometry_field(),
]
}
fn schema_of(fields: Vec<Field>, geom: &str) -> Arc<Schema> {
let mut meta = HashMap::new();
meta.insert(
String::from(metadata::GEO_KEY),
GeoMeta::new(&[geom]).to_json(),
);
Arc::new(Schema::new_with_metadata(fields, meta))
}
/// Arrow schema of the edge table.
pub fn edge_schema() -> Arc<Schema> {
schema_of(edge_fields(), "LineString")
}
/// Arrow schema of the node table.
pub fn node_schema() -> Arc<Schema> {
schema_of(node_fields(), "Point")
}
/// The canonical spelling of how the node set was chosen, for the recipe token. Changing
/// [`JOINT_CLASSES`] or the junction rule re-cuts every graph, because a graph built under
/// a different rule is different DATA at the same schema.
pub fn junction_rule() -> String {
format!("shared>=2|endpoint|joint∈[{}]", JOINT_CLASSES.join("|"))
}
// ── the input ───────────────────────────────────────────────────────────────────
/// One way handed to the builder — exactly the columns a network row already holds, so
/// nothing is read twice.
#[derive(Clone, Copy, Debug)]
pub struct WayIn<'a> {
pub id: i64,
pub network: &'a str,
pub class: &'a str,
pub tags: &'a str,
pub geometry: Option<&'a [u8]>,
pub node_refs: &'a [i64],
}
/// One tagged node handed to the builder (the `rail_nodes` layer).
#[derive(Clone, Copy, Debug)]
pub struct NodeIn<'a> {
pub id: i64,
pub class: &'a str,
pub tags: &'a str,
}
// ── what came out ───────────────────────────────────────────────────────────────
/// Everything a graph build measured. Reported, never inferred.
#[derive(Clone, Debug, Default)]
pub struct GraphStats {
pub ways: usize,
pub node_refs: usize,
/// Distinct node ids the ways touch — the set the junction rule shrinks.
pub distinct_nodes: usize,
/// Nodes referenced by two or more ways (counting a node twice in ONE way, which is a
/// way touching itself, as shared — that is a real topological joint).
pub shared_nodes: usize,
pub endpoint_nodes: usize,
/// [`JOINT_CLASSES`] nodes admitted that the count alone would have dropped.
pub forced_joints: usize,
pub graph_nodes: usize,
pub graph_edges: usize,
/// Graph nodes with both a road edge and a rail edge — the cross-network joints.
pub joints: usize,
/// Ways whose geometry did not have one point per `node_ref`, emitted as ONE
/// whole-way edge instead of being sliced. Counted because a silent fallback is
/// indistinguishable from a slicer that never ran.
pub whole_way_fallback: usize,
pub oneway_forward: usize,
pub oneway_backward: usize,
/// Edges whose `speed_kmh` came from a tagged `maxspeed` (the rest drive the class
/// default). Counted so coverage is REPORTED off the build, never inferred.
pub speed_tagged_edges: usize,
/// Metres of ROAD edges with a tagged `maxspeed`, and total road metres — the
/// km-weighted coverage ratio, which is the honest one (a tagged motorway is worth
/// more route-minutes than an untagged forest track).
pub speed_tagged_road_m: f64,
pub road_m: f64,
/// `class` → edge count.
pub edge_classes: Vec<(String, usize)>,
/// `kind` → node count.
pub node_kinds: Vec<(String, usize)>,
}
/// The built graph, as batches ready for [`crate::spatial::pack_batches`].
pub struct GraphBuild {
pub edges: Vec<RecordBatch>,
pub nodes: Vec<RecordBatch>,
pub stats: GraphStats,
}
// ── WKB ─────────────────────────────────────────────────────────────────────────
/// **The node-by-node point sequence of a way's WKB**, in either byte order.
///
/// A `LineString` is the obvious case. A **single-ring `Polygon` is the other one, and
/// leaving it out was a real defect**: a way that closes on itself — a roundabout, a car
/// park loop, a turning circle — is written as a Polygon by [`crate::geometry`], and its
/// ring is exactly the way's `node_refs` in order. MEASURED on the sweden extract
/// 2026-08-04: handling only LineString left **7 483 road/rail ways unsliceable (0.33 %)**,
/// each collapsing to a single self-loop edge `X → X` that no router can enter or leave —
/// and a roundabout is precisely where a router has decisions to make.
///
/// `None` for Multi\* and everything else: there the one-point-per-`node_ref`
/// correspondence does not hold, so the caller falls back rather than slicing nonsense.
///
/// Exported as [`wkb_line_points`] for consumers (korp's road-graph answers) that hold
/// an edge row's WKB and want the vertex run without a second WKB decoder.
fn line_points(w: &[u8]) -> Option<Vec<(f64, f64)>> {
if w.len() < 9 {
return None;
}
let le = w[0] == 1;
let rd_u32 = |b: &[u8]| -> u32 {
let a = [b[0], b[1], b[2], b[3]];
if le {
u32::from_le_bytes(a)
} else {
u32::from_be_bytes(a)
}
};
let rd_f64 = |b: &[u8]| -> f64 {
let mut a = [0u8; 8];
a.copy_from_slice(&b[..8]);
if le {
f64::from_le_bytes(a)
} else {
f64::from_be_bytes(a)
}
};
// Where the point count sits: straight after the type for a LineString, after the
// ring count for a Polygon (and only a ONE-ring polygon can be one closed way).
let at = match rd_u32(&w[1..5]) % 1000 {
2 => 5usize,
3 => {
if w.len() < 13 || rd_u32(&w[5..9]) != 1 {
return None;
}
9
}
_ => return None,
};
let n = rd_u32(&w[at..at + 4]) as usize;
let head = at + 4;
if w.len() < head + n * 16 {
return None;
}
let mut out = Vec::with_capacity(n);
for i in 0..n {
let o = head + i * 16;
out.push((rd_f64(&w[o..o + 8]), rd_f64(&w[o + 8..o + 16])));
}
Some(out)
}
/// The public face of [`line_points`] — the vertex run of a `LineString` (or one-ring
/// `Polygon`) WKB in either byte order, `None` for anything else.
#[must_use]
pub fn wkb_line_points(w: &[u8]) -> Option<Vec<(f64, f64)>> {
line_points(w)
}
/// A little-endian WKB `LineString` over `pts`.
fn wkb_line(pts: &[(f64, f64)]) -> Vec<u8> {
let mut v = Vec::with_capacity(9 + pts.len() * 16);
v.push(1u8);
v.extend_from_slice(&2u32.to_le_bytes());
v.extend_from_slice(&(pts.len() as u32).to_le_bytes());
for (x, y) in pts {
v.extend_from_slice(&x.to_le_bytes());
v.extend_from_slice(&y.to_le_bytes());
}
v
}
/// A little-endian WKB `Point`.
fn wkb_point((x, y): (f64, f64)) -> Vec<u8> {
let mut v = Vec::with_capacity(21);
v.push(1u8);
v.extend_from_slice(&1u32.to_le_bytes());
v.extend_from_slice(&x.to_le_bytes());
v.extend_from_slice(&y.to_le_bytes());
v
}
/// Great-circle distance in metres. Mean Earth radius; a router comparing road lengths
/// does not need the ellipsoid, and the error (≤0.3 %) is far below OSM's own geometry
/// error.
pub fn haversine_m((x1, y1): (f64, f64), (x2, y2): (f64, f64)) -> f64 {
const R: f64 = 6_371_008.8;
let (p1, p2) = (y1.to_radians(), y2.to_radians());
let dp = p2 - p1;
let dl = (x2 - x1).to_radians();
let a = (dp / 2.0).sin().powi(2) + p1.cos() * p2.cos() * (dl / 2.0).sin().powi(2);
2.0 * R * a.sqrt().clamp(0.0, 1.0).asin()
}
fn line_len_m(pts: &[(f64, f64)]) -> f64 {
pts.windows(2).map(|w| haversine_m(w[0], w[1])).sum()
}
// ── direction ───────────────────────────────────────────────────────────────────
/// The `oneway` value of a way, as the `Int8` the edge column carries.
///
/// `junction=roundabout|circular` is implicitly one-way and almost never carries
/// `oneway=yes`; a graph that reads only the `oneway` tag lets a router drive the wrong
/// way round every roundabout in the country.
pub fn oneway_of(tags: &str) -> i8 {
match tag_value(tags, "oneway").as_deref() {
Some("yes" | "true" | "1") => return 1,
Some("-1" | "reverse") => return -1,
Some("no" | "false" | "0") => return 0,
_ => {}
}
match tag_value(tags, "junction").as_deref() {
Some("roundabout" | "circular") => 1,
_ => 0,
}
}
// ── speed ───────────────────────────────────────────────────────────────────────
/// **The class → km/h table — the ONE place a default speed is written (LAW 5).**
///
/// Moved here from korp's `roadgraph.rs` (lane `nvdb`, 2026-09-02) so the CUT — which
/// stamps `speed_kmh` into the edge table — and every ROUTER pricing arcs share one
/// source. Values are Swedish-plausible class defaults, not measured truth; a way's own
/// `maxspeed` tag beats them ([`edge_speed_kmh`]). MEASURED on the Sweden cut
/// 2026-09-02: 90.2 % of arterial km (motorway/trunk/primary/secondary/tertiary + links)
/// carry a tagged `maxspeed`, so on the roads that decide a route the default is the
/// exception, not the rule.
pub const SPEED_TABLE: &[(&str, f64)] = &[
("motorway", 110.0),
("motorway_link", 80.0),
("trunk", 100.0),
("trunk_link", 70.0),
("primary", 80.0),
("primary_link", 60.0),
("secondary", 70.0),
("secondary_link", 50.0),
("tertiary", 60.0),
("tertiary_link", 50.0),
("unclassified", 50.0),
("residential", 40.0),
("living_street", 20.0),
("service", 20.0),
("track", 20.0),
("road", 50.0),
("pedestrian", 5.0),
("path", 5.0),
("footway", 5.0),
("cycleway", 15.0),
("steps", 3.0),
("bridleway", 10.0),
("rail", 120.0),
("narrow_gauge", 60.0),
("light_rail", 60.0),
("subway", 50.0),
("tram", 30.0),
];
/// A class the table does not name drives at this — stated, never silently zero.
pub const DEFAULT_SPEED_KMH: f64 = 40.0;
/// The default speed of a `class`, km/h.
#[must_use]
pub fn class_speed_kmh(class: &str) -> f64 {
SPEED_TABLE
.iter()
.find(|(c, _)| *c == class)
.map_or(DEFAULT_SPEED_KMH, |(_, v)| *v)
}
/// `speed_source` value: the speed came from the way's own `maxspeed` tag.
pub const SPEED_SOURCE_MAXSPEED: &str = "maxspeed";
/// `speed_source` value: the speed is the class default from [`SPEED_TABLE`].
pub const SPEED_SOURCE_CLASS: &str = "class";
/// **The `maxspeed` tag as km/h**, or `None` when absent or unparseable.
///
/// Handles the forms that exist in the wild: a bare number (km/h — the OSM default
/// unit and the only unit Sweden tags), `N mph`, and `walk` (≈7 km/h). Zone spellings
/// (`SE:urban`), multi-values (`70;50`) and other text are `None` — the class default
/// answers, and `speed_source` says so. Refusing to guess IS the honesty: a parser
/// that read `70;50` as 7050 would poison every route through that street.
#[must_use]
pub fn maxspeed_kmh(tags: &str) -> Option<f64> {
let v = tag_value(tags, "maxspeed")?;
let v = v.trim();
if v.eq_ignore_ascii_case("walk") {
return Some(7.0);
}
let (txt, factor) = match v.strip_suffix("mph") {
Some(rest) => (rest.trim_end(), 1.609_344),
None => (v, 1.0),
};
let n: f64 = txt.parse().ok()?;
let kmh = n * factor;
(kmh > 0.0 && kmh <= 250.0).then_some(kmh)
}
/// **The speed an edge drives at and where it came from** — a parseable `maxspeed`
/// beats the class default. Returns `(km/h, from_maxspeed)`.
#[must_use]
pub fn edge_speed_kmh(tags: &str, class: &str) -> (f64, bool) {
match maxspeed_kmh(tags) {
Some(v) => (v, true),
None => (class_speed_kmh(class), false),
}
}
// ── the build ───────────────────────────────────────────────────────────────────
/// One edge, before it becomes Arrow.
struct Edge {
id: i64,
network: u32,
class: u32,
way_id: i64,
from: i64,
to: i64,
oneway: i8,
length_m: f64,
speed_kmh: f64,
speed_tagged: bool,
geom: Vec<u8>,
}
/// What one chunk of ways produced.
struct Cut {
edges: Vec<Edge>,
/// `(node id, lon, lat)` for every graph node this chunk touched. Deduped later.
coords: Vec<(i64, f64, f64)>,
fallback: usize,
}
/// **Build the graph from the network rows.**
///
/// Three passes, all over data already in memory:
/// 1. flatten every `node_refs` and sort it (gatling — LAW 3), to find the nodes that two
/// or more ways touch. The sort is over the UNION of the networks, which is what makes
/// a level crossing a junction at all.
/// 2. slice each way at its graph nodes, in parallel over chunks, emitting edges and the
/// coordinates of the nodes they end at.
/// 3. fold the edges into per-node adjacency lists, single-threaded and in edge order, so
/// the result is deterministic and needs no lock.
pub fn build_graph(ways: &[WayIn<'_>], nodes: &[NodeIn<'_>]) -> anyhow::Result<GraphBuild> {
let mut st = GraphStats {
ways: ways.len(),
..GraphStats::default()
};
// ── 1. the junction set ──────────────────────────────────────────────────
let total_refs: usize = ways.iter().map(|w| w.node_refs.len()).sum();
st.node_refs = total_refs;
let mut flat: Vec<i64> = Vec::with_capacity(total_refs);
for w in ways {
flat.extend_from_slice(w.node_refs);
}
gatling::gatling_sort::gatling_sort_unstable(&mut flat);
let mut cut: Vec<i64> = Vec::new();
{
let mut i = 0usize;
while i < flat.len() {
let v = flat[i];
let mut j = i + 1;
while j < flat.len() && flat[j] == v {
j += 1;
}
st.distinct_nodes += 1;
if j - i >= 2 {
st.shared_nodes += 1;
cut.push(v);
}
i = j;
}
}
let mut ends: Vec<i64> = Vec::with_capacity(ways.len() * 2);
for w in ways {
if let (Some(a), Some(b)) = (w.node_refs.first(), w.node_refs.last()) {
ends.push(*a);
ends.push(*b);
}
}
ends.sort_unstable();
ends.dedup();
st.endpoint_nodes = ends.len();
// The forced joints: a JOINT_CLASSES node the ways actually touch. `flat` is sorted,
// so membership is a binary search and no second hash set is built.
let mut forced: Vec<i64> = Vec::new();
for n in nodes {
if JOINT_CLASSES.contains(&n.class) && flat.binary_search(&n.id).is_ok() {
forced.push(n.id);
}
}
drop(flat);
// How many of the forced joints the count rule alone would have MISSED — the number
// that says whether forcing does anything at all. `cut` is still exactly the shared
// set here and `ends` is sorted, so this is two binary searches and no third copy.
forced.sort_unstable();
forced.dedup();
st.forced_joints = forced
.iter()
.filter(|id| cut.binary_search(id).is_err() && ends.binary_search(id).is_err())
.count();
cut.extend_from_slice(&ends);
cut.extend_from_slice(&forced);
gatling::gatling_sort::gatling_sort_unstable(&mut cut);
cut.dedup();
st.graph_nodes = cut.len();
drop(ends);
let cut = cut; // frozen: every lookup below is a binary search on this
// ── 2. slice the ways ────────────────────────────────────────────────────
// The class/network strings are interned so an edge carries a u32, not a String per
// row: 4.6 M rows × two Strings is 4.6 M allocations for ~60 distinct values.
let mut networks: Vec<String> = Vec::new();
let mut classes: Vec<String> = Vec::new();
let mut net_ix: HashMap<&str, u32> = HashMap::new();
let mut cls_ix: HashMap<&str, u32> = HashMap::new();
for w in ways {
if !net_ix.contains_key(w.network) {
net_ix.insert(w.network, networks.len() as u32);
networks.push(String::from(w.network));
}
if !cls_ix.contains_key(w.class) {
cls_ix.insert(w.class, classes.len() as u32);
classes.push(String::from(w.class));
}
}
const CHUNK: usize = 16_384;
let chunks: Vec<&[WayIn<'_>]> = ways.chunks(CHUNK).collect();
let cuts: Vec<Cut> = gatling::gatling_forkjoin::gatling_map_balanced(
&chunks,
0,
1,
|c: &&[WayIn<'_>]| c.iter().map(|w| w.node_refs.len() as u64).sum(),
|_i, c: &&[WayIn<'_>]| cut_chunk(c, &cut, &net_ix, &cls_ix),
);
let mut edges: Vec<Edge> = Vec::with_capacity(cuts.iter().map(|c| c.edges.len()).sum());
let mut coords: Vec<(i64, f64, f64)> = Vec::new();
for c in cuts {
st.whole_way_fallback += c.fallback;
edges.extend(c.edges);
coords.extend(c.coords);
}
st.graph_edges = edges.len();
let road_net_ix = net_ix.get("roads").copied();
for e in &edges {
match e.oneway {
1 => st.oneway_forward += 1,
-1 => st.oneway_backward += 1,
_ => {}
}
if e.speed_tagged {
st.speed_tagged_edges += 1;
}
if Some(e.network) == road_net_ix {
st.road_m += e.length_m;
if e.speed_tagged {
st.speed_tagged_road_m += e.length_m;
}
}
}
// ── 3. adjacency ─────────────────────────────────────────────────────────
// Serial, in edge order, so the lists are deterministic and no lock is needed.
let pos = |id: i64| cut.binary_search(&id).ok();
let n = cut.len();
let mut adj: Vec<Vec<i64>> = vec![Vec::new(); n];
// bit 0 = touched by a road edge, bit 1 = touched by a rail edge
let mut touch: Vec<u8> = vec![0u8; n];
let road_ix = net_ix.get("roads").copied();
let rail_ix = net_ix.get("rails").copied();
for e in &edges {
let bit = if Some(e.network) == road_ix {
1u8
} else if Some(e.network) == rail_ix {
2u8
} else {
4u8
};
for id in [e.from, e.to] {
if let Some(p) = pos(id) {
adj[p].push(e.id);
touch[p] |= bit;
}
}
if e.from == e.to {
// A closed loop meets itself once, not twice — the push above already ran
// twice, so drop the duplicate rather than reporting degree 2 for one edge.
if let Some(p) = pos(e.from) {
adj[p].pop();
}
}
}
let mut xy: Vec<Option<(f64, f64)>> = vec![None; n];
for (id, x, y) in coords {
if let Some(p) = pos(id).filter(|&p| xy[p].is_none()) {
xy[p] = Some((x, y));
}
}
let mut rail: HashMap<i64, (&str, &str)> = HashMap::with_capacity(nodes.len());
for nd in nodes {
rail.entry(nd.id).or_insert((nd.class, nd.tags));
}
st.joints = touch.iter().filter(|t| **t & 3 == 3).count();
// ── the batches ──────────────────────────────────────────────────────────
let (edge_batches, edge_hist) = edge_batches(&edges, &networks, &classes)?;
st.edge_classes = hist_vec(edge_hist);
let (node_batches, kind_hist) = node_batches(&cut, &adj, &touch, &xy, &rail)?;
st.node_kinds = hist_vec(kind_hist);
Ok(GraphBuild {
edges: edge_batches,
nodes: node_batches,
stats: st,
})
}
/// Slice one chunk of ways at the graph nodes in `cut`.
fn cut_chunk(
ways: &[WayIn<'_>],
cut: &[i64],
net_ix: &HashMap<&str, u32>,
cls_ix: &HashMap<&str, u32>,
) -> Cut {
let mut out = Cut {
edges: Vec::new(),
coords: Vec::new(),
fallback: 0,
};
for w in ways {
if w.node_refs.len() < 2 {
continue;
}
let network = net_ix[w.network];
let class = cls_ix[w.class];
let oneway = oneway_of(w.tags);
let (speed_kmh, speed_tagged) = edge_speed_kmh(w.tags, w.class);
let pts = w.geometry.and_then(line_points);
let sliceable = pts.as_ref().is_some_and(|p| p.len() == w.node_refs.len());
if !sliceable {
// One whole-way edge, still topologically right — first ref to last ref —
// just not split. Counted.
out.fallback += 1;
let geom = w.geometry.map(<[u8]>::to_vec).unwrap_or_default();
let length_m = pts.as_deref().map_or(0.0, line_len_m);
out.edges.push(Edge {
id: w.id.saturating_mul(SEGMENTS_PER_WAY),
network,
class,
way_id: w.id,
from: w.node_refs[0],
to: w.node_refs[w.node_refs.len() - 1],
oneway,
length_m,
speed_kmh,
speed_tagged,
geom,
});
continue;
}
let pts = pts.expect("sliceable implies Some");
// Cut indices: always the two ends, plus every interior ref that is a graph node.
let mut at: Vec<usize> = Vec::new();
at.push(0);
for (i, r) in w
.node_refs
.iter()
.enumerate()
.skip(1)
.take(w.node_refs.len() - 2)
{
if cut.binary_search(r).is_ok() {
at.push(i);
}
}
at.push(w.node_refs.len() - 1);
for (seq, pair) in at.windows(2).enumerate() {
let (a, b) = (pair[0], pair[1]);
let span = &pts[a..=b];
let seq = i64::try_from(seq).unwrap_or(0).min(SEGMENTS_PER_WAY - 1);
out.edges.push(Edge {
id: w.id.saturating_mul(SEGMENTS_PER_WAY).saturating_add(seq),
network,
class,
way_id: w.id,
from: w.node_refs[a],
to: w.node_refs[b],
oneway,
length_m: line_len_m(span),
speed_kmh,
speed_tagged,
geom: wkb_line(span),
});
}
for i in at {
out.coords.push((w.node_refs[i], pts[i].0, pts[i].1));
}
}
out
}
fn hist_vec(m: HashMap<String, usize>) -> Vec<(String, usize)> {
let mut v: Vec<(String, usize)> = m.into_iter().collect();
v.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
v
}
const BATCH: usize = 65_536;
fn edge_batches(
edges: &[Edge],
networks: &[String],
classes: &[String],
) -> anyhow::Result<(Vec<RecordBatch>, HashMap<String, usize>)> {
let schema = edge_schema();
let mut hist: HashMap<String, usize> = HashMap::new();
let mut out = Vec::with_capacity(edges.len().div_ceil(BATCH).max(1));
for chunk in edges.chunks(BATCH) {
let ids = Int64Array::from_iter_values(chunk.iter().map(|e| e.id));
let net = StringArray::from_iter_values(
chunk.iter().map(|e| networks[e.network as usize].as_str()),
);
let cls = StringArray::from_iter_values(chunk.iter().map(|e| {
let c = classes[e.class as usize].as_str();
*hist.entry(String::from(c)).or_insert(0) += 1;
c
}));
let wid = Int64Array::from_iter_values(chunk.iter().map(|e| e.way_id));
let fr = Int64Array::from_iter_values(chunk.iter().map(|e| e.from));
let to = Int64Array::from_iter_values(chunk.iter().map(|e| e.to));
let ow = Int8Array::from_iter_values(chunk.iter().map(|e| e.oneway));
let ln = Float64Array::from_iter_values(chunk.iter().map(|e| e.length_m));
let sp = Float64Array::from_iter_values(chunk.iter().map(|e| e.speed_kmh));
let ss = StringArray::from_iter_values(chunk.iter().map(|e| {
if e.speed_tagged {
SPEED_SOURCE_MAXSPEED
} else {
SPEED_SOURCE_CLASS
}
}));
let gm = BinaryArray::from_opt_vec(
chunk
.iter()
.map(|e| {
if e.geom.is_empty() {
None
} else {
Some(e.geom.as_slice())
}
})
.collect(),
);
let cols: Vec<ArrayRef> = vec![
Arc::new(ids),
Arc::new(net),
Arc::new(cls),
Arc::new(wid),
Arc::new(fr),
Arc::new(to),
Arc::new(ow),
Arc::new(ln),
Arc::new(sp),
Arc::new(ss),
Arc::new(gm),
];
out.push(RecordBatch::try_new(schema.clone(), cols)?);
}
if out.is_empty() {
out.push(RecordBatch::new_empty(schema));
}
Ok((out, hist))
}
fn node_batches(
cut: &[i64],
adj: &[Vec<i64>],
touch: &[u8],
xy: &[Option<(f64, f64)>],
rail: &HashMap<i64, (&str, &str)>,
) -> anyhow::Result<(Vec<RecordBatch>, HashMap<String, usize>)> {
let schema = node_schema();
let mut hist: HashMap<String, usize> = HashMap::new();
let mut out = Vec::with_capacity(cut.len().div_ceil(BATCH).max(1));
let mut at = 0usize;
while at < cut.len() {
let end = (at + BATCH).min(cut.len());
let ids = Int64Array::from_iter_values(cut[at..end].iter().copied());
let kinds = StringArray::from_iter_values(touch[at..end].iter().map(|t| {
let k = match t & 3 {
3 => "both",
2 => "rail",
1 => "road",
_ => "other",
};
*hist.entry(String::from(k)).or_insert(0) += 1;
k
}));
let deg = Int32Array::from_iter_values(
adj[at..end]
.iter()
.map(|a| i32::try_from(a.len()).unwrap_or(i32::MAX)),
);
let mut rc = StringBuilder::new();
let mut tg = StringBuilder::new();
for id in &cut[at..end] {
match rail.get(id) {
Some((c, t)) => {
rc.append_value(c);
tg.append_value(t);
}
None => {
rc.append_null();
tg.append_null();
}
}
}
let mut lb = arrow::array::ListBuilder::new(Int64Builder::new());
for a in &adj[at..end] {
for e in a {
lb.values().append_value(*e);
}
lb.append(true);
}
let gm = BinaryArray::from_opt_vec(
xy[at..end]
.iter()
.map(|p| p.map(wkb_point))
.collect::<Vec<_>>()
.iter()
.map(|o| o.as_deref())
.collect(),
);
let cols: Vec<ArrayRef> = vec![
Arc::new(ids),
Arc::new(kinds),
Arc::new(deg),
Arc::new(rc.finish()),
Arc::new(tg.finish()),
Arc::new(lb.finish()),
Arc::new(gm),
];
out.push(RecordBatch::try_new(schema.clone(), cols)?);
at = end;
}
if out.is_empty() {
out.push(RecordBatch::new_empty(schema));
}
Ok((out, hist))
}
// ── reading the graph back ──────────────────────────────────────────────────────
/// **One directed arc.** (`NetArc`, not `Arc` — `std::sync::Arc` owns that name here.)
///
/// `net` is the load-bearing field and it was added after a real wrong answer: with the
/// road and rail networks joined into ONE graph — which is the point — a Dijkstra that
/// walked every arc could enter the track at one level crossing and leave it at the next,
/// and report the result as a road distance. The joint must be walkable when the question
/// is about the joint and refused when the question is "how far by road".
#[derive(Clone, Copy, Debug)]
pub struct NetArc {
pub to: u32,
pub len_m: f64,
pub edge: i64,
/// [`NET_ROAD`] | [`NET_RAIL`] | [`NET_OTHER`].
pub net: u8,
/// Index into [`Graph::classes`] — the edge's `class` column, interned per load.
/// Added 2026-09-01 (additive): a router that prices arcs by CLASS SPEED (korp's
/// road-graph questions — isochrone minutes, route minutes) needs the class ON the
/// arc; re-reading a 319 MB edge table per question to learn it would be the
/// tag-parse mistake one representation over.
pub cls: u16,
/// The edge's `speed_kmh` column, rounded to whole km/h (lane `nvdb`, 2026-09-02).
/// A `u8` on purpose: real speeds are 3–130 km/h and the arc must stay 24 bytes —
/// an `f32` here pads the struct to 32 and costs ~150 MB across Sweden's forward +
/// reverse CSRs for precision no signpost has. On an old cut without the column
/// the loader prices the class default from [`SPEED_TABLE`], and
/// [`Graph::speed_from_column`] says which happened.
pub speed_kmh: u8,
}
impl NetArc {
/// The arc's speed in m/s, never zero (a zero would make a cost infinite and a
/// Dijkstra heap NaN-adjacent; 1 km/h is the honest floor for "we know nothing").
#[must_use]
pub fn speed_ms(&self) -> f64 {
f64::from(self.speed_kmh.max(1)) / 3.6
}
}
/// Arc is on a `roads` edge.
pub const NET_ROAD: u8 = 1;
/// Arc is on a `rails` edge.
pub const NET_RAIL: u8 = 2;
/// Arc is on an edge from neither (a network added to [`GRAPHED_NETWORKS`] later).
pub const NET_OTHER: u8 = 4;
fn net_bit(name: &str) -> u8 {
match name {
"roads" => NET_ROAD,
"rails" => NET_RAIL,
_ => NET_OTHER,
}
}
/// **The graph, loaded into the CSR a router walks.**
///
/// Built from the two parquet tables and nothing else — the point of the tables is that
/// this load is the whole of "make it routable".
pub struct Graph {
/// Graph node ids, ascending (the table is Hilbert-sorted, so this is re-sorted on
/// load and every array below is in THIS order).
pub node_id: Vec<i64>,
pub node_kind: Vec<u8>,
pub node_xy: Vec<(f64, f64)>,
pub rail_class: Vec<Option<String>>,
pub node_tags: Vec<Option<String>>,
/// CSR: neighbours of node `i` are `csr[off[i]..off[i + 1]]`.
pub off: Vec<u32>,
pub csr: Vec<NetArc>,
pub edges: usize,
/// The distinct `class` values of the edge table, in first-seen order —
/// [`NetArc::cls`] indexes this. ~60 strings for the whole of Sweden, so a
/// per-arc `u16` instead of a per-arc `String` (the same interning the builder
/// itself does).
pub classes: Vec<String>,
/// `true` when the edge table carried a `speed_kmh` column and the arcs price by
/// it; `false` on an old cut, where every arc got its class default from
/// [`SPEED_TABLE`] instead — the TYPED fallback a consumer reports, never guesses.
pub speed_from_column: bool,
}
impl Graph {
/// Index of `id`, or `None`.
pub fn index_of(&self, id: i64) -> Option<usize> {
self.node_id.binary_search(&id).ok()
}
/// Load `graph_nodes.parquet` + `graph_edges.parquet` from a networks directory.
///
/// Edges are inserted **respecting `oneway`**: `0` both directions, `1` from→to only,
/// `-1` to→from only. A loader that ignored the column would answer routing questions
/// about a road network that does not exist.
pub fn load(dir: &Path) -> anyhow::Result<Self> {
let np = dir.join(format!("{GRAPH_NODES}.parquet"));
let ep = dir.join(format!("{GRAPH_EDGES}.parquet"));
anyhow::ensure!(
np.is_file(),
"no {np:?} — build it with `osm-katana networks`"
);
anyhow::ensure!(
ep.is_file(),
"no {ep:?} — build it with `osm-katana networks`"
);
// nodes
/// `(id, kind bits, (lon, lat), rail_class, tags)` — one node table row.
type NodeRow = (i64, u8, (f64, f64), Option<String>, Option<String>);
let mut rows: Vec<NodeRow> = Vec::new();
let f = std::fs::File::open(&np)?;
for b in ParquetRecordBatchReaderBuilder::try_new(f)?.build()? {
let b = b?;
let id = arr::<Int64Array>(&b, "id")?;
let kind = arr::<StringArray>(&b, "kind")?;
let rc = arr::<StringArray>(&b, "rail_class")?;
let tg = arr::<StringArray>(&b, "tags")?;
let gm = arr::<BinaryArray>(&b, "geometry")?;
for i in 0..b.num_rows() {
let k = match kind.value(i) {
"both" => 3u8,
"rail" => 2,
"road" => 1,
_ => 0,
};
let xy = if gm.is_null(i) {
(f64::NAN, f64::NAN)
} else {
let w = gm.value(i);
if w.len() >= 21 {
let mut a = [0u8; 8];
a.copy_from_slice(&w[5..13]);
let x = f64::from_le_bytes(a);
a.copy_from_slice(&w[13..21]);
(x, f64::from_le_bytes(a))
} else {
(f64::NAN, f64::NAN)
}
};
rows.push((
id.value(i),
k,
xy,
(!rc.is_null(i)).then(|| String::from(rc.value(i))),
(!tg.is_null(i)).then(|| String::from(tg.value(i))),
));
}
}
rows.sort_by_key(|r| r.0);
let n = rows.len();
let mut g = Graph {
node_id: Vec::with_capacity(n),
node_kind: Vec::with_capacity(n),
node_xy: Vec::with_capacity(n),
rail_class: Vec::with_capacity(n),
node_tags: Vec::with_capacity(n),
off: Vec::new(),
csr: Vec::new(),
edges: 0,
classes: Vec::new(),
speed_from_column: false,
};
for (id, k, xy, rc, tg) in rows {
g.node_id.push(id);
g.node_kind.push(k);
g.node_xy.push(xy);
g.rail_class.push(rc);
g.node_tags.push(tg);
}
// edges → directed arc list
let mut arcs: Vec<(u32, NetArc)> = Vec::new();
let mut cls_ix: HashMap<String, u16> = HashMap::new();
let f = std::fs::File::open(&ep)?;
let builder = ParquetRecordBatchReaderBuilder::try_new(f)?;
// An old cut has no `speed_kmh` column. That is a TYPED fallback, not an error:
// every arc prices its class default from [`SPEED_TABLE`], and the flag lets a
// consumer say which of the two speeds it is quoting.
g.speed_from_column = builder.schema().field_with_name("speed_kmh").is_ok();
for b in builder.build()? {
let b = b?;
let id = arr::<Int64Array>(&b, "id")?;
let fr = arr::<Int64Array>(&b, "from_node")?;
let to = arr::<Int64Array>(&b, "to_node")?;
let ow = arr::<Int8Array>(&b, "oneway")?;
let ln = arr::<Float64Array>(&b, "length_m")?;
let nw = arr::<StringArray>(&b, "network")?;
let cl = arr::<StringArray>(&b, "class")?;
let sp = b
.column_by_name("speed_kmh")
.and_then(|c| c.as_any().downcast_ref::<Float64Array>());
for i in 0..b.num_rows() {
let (Some(a), Some(z)) = (g.index_of(fr.value(i)), g.index_of(to.value(i))) else {
continue;
};
g.edges += 1;
let (a, z) = (a as u32, z as u32);
let (l, e) = (ln.value(i), id.value(i));
let net = net_bit(nw.value(i));
let cls = match cls_ix.get(cl.value(i)) {
Some(ix) => *ix,
None => {
let ix = u16::try_from(g.classes.len()).unwrap_or(u16::MAX);
cls_ix.insert(String::from(cl.value(i)), ix);
g.classes.push(String::from(cl.value(i)));
ix
}
};
let kmh = match sp {
Some(a) => a.value(i),
None => class_speed_kmh(cl.value(i)),
};
let speed_kmh = kmh.round().clamp(1.0, 254.0) as u8;
let arc = |to: u32| NetArc {
to,
len_m: l,
edge: e,
net,
cls,
speed_kmh,
};
match ow.value(i) {
1 => arcs.push((a, arc(z))),
-1 => arcs.push((z, arc(a))),
_ => {
arcs.push((a, arc(z)));
arcs.push((z, arc(a)));
}
}
}
}
arcs.sort_unstable_by_key(|a| a.0);
g.off = vec![0u32; n + 1];
for a in &arcs {
g.off[a.0 as usize + 1] += 1;
}
for i in 0..n {
g.off[i + 1] += g.off[i];
}
g.csr = arcs.into_iter().map(|(_, a)| a).collect();
Ok(g)
}
/// Neighbours of node index `i`.
pub fn neighbours(&self, i: usize) -> &[NetArc] {
&self.csr[self.off[i] as usize..self.off[i + 1] as usize]
}
/// Nearest graph node to `(lon, lat)` as the crow flies, restricted to nodes that
/// have at least one outgoing arc (an isolated node is not a place to start routing
/// from).
pub fn nearest_node(&self, lon: f64, lat: f64, nets: u8) -> Option<usize> {
(0..self.node_id.len())
.filter(|&i| self.neighbours(i).iter().any(|a| a.net & nets != 0))
.filter(|&i| self.node_xy[i].0.is_finite())
.min_by(|&a, &b| {
let d = |i: usize| haversine_m((lon, lat), self.node_xy[i]);
d(a).total_cmp(&d(b))
})
}
/// **Dijkstra from `start` until `stop` says yes.** Returns the settled node, its
/// network distance in metres, and how many nodes were settled getting there.
pub fn nearest_matching(
&self,
start: usize,
nets: u8,
stop: impl Fn(usize) -> bool,
) -> Option<(usize, f64, usize)> {
use std::cmp::Reverse;
use std::collections::BinaryHeap;
let n = self.node_id.len();
let mut dist = vec![f64::INFINITY; n];
let mut heap: BinaryHeap<Reverse<(ordered::F, u32)>> = BinaryHeap::new();
dist[start] = 0.0;
heap.push(Reverse((ordered::F(0.0), start as u32)));
let mut settled = 0usize;
while let Some(Reverse((ordered::F(d), u))) = heap.pop() {
let u = u as usize;
if d > dist[u] {
continue;
}
settled += 1;
if stop(u) {
return Some((u, d, settled));
}
for a in self.neighbours(u) {
if a.net & nets == 0 {
continue;
}
let nd = d + a.len_m;
if nd < dist[a.to as usize] {
dist[a.to as usize] = nd;
heap.push(Reverse((ordered::F(nd), a.to)));
}
}
}
None
}
}
/// A total order on `f64` for the priority queue. `f64` is not `Ord`, and `partial_cmp`
/// on a NaN cost silently corrupts a heap; `total_cmp` panics on nothing and orders NaN
/// last, so a bad length degrades to "explored last" rather than to a wrong answer.
mod ordered {
#[derive(Clone, Copy, PartialEq)]
pub struct F(pub f64);
impl Eq for F {}
impl PartialOrd for F {
fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(o))
}
}
impl Ord for F {
fn cmp(&self, o: &Self) -> std::cmp::Ordering {
self.0.total_cmp(&o.0)
}
}
}
fn arr<'a, T: 'static>(b: &'a RecordBatch, name: &str) -> anyhow::Result<&'a T> {
b.column_by_name(name)
.and_then(|c| c.as_any().downcast_ref::<T>())
.ok_or_else(|| anyhow::anyhow!("graph table column `{name}` missing or wrong type"))
}
// ── the questions the graph exists to answer ────────────────────────────────────
/// **Is this crossing actively protected?** A barrier, a light, a bell or a human.
///
/// `crossing:saltire` is deliberately NOT protection: a St Andrew's cross is a passive
/// sign, not something that stops you when a train is coming.
pub fn is_guarded(tags: &str) -> bool {
let yes = |k: &str| matches!(tag_value(tags, k).as_deref(), Some("yes" | "true" | "1"));
if let Some("yes" | "full" | "half" | "double_half" | "gate") =
tag_value(tags, "crossing:barrier").as_deref()
{
return true;
}
yes("crossing:light")
|| yes("crossing:bell")
|| yes("crossing:on_demand")
|| yes("supervised")
|| matches!(
tag_value(tags, "crossing").as_deref(),
Some("traffic_signals")
)
}
/// One unguarded level crossing, with what the ADJACENCY says meets there.
#[derive(Clone, Debug)]
pub struct Unguarded {
pub node: i64,
pub lon: f64,
pub lat: f64,
pub road_edges: usize,
pub rail_edges: usize,
/// The road classes that meet at this node — the thing only the graph knows.
pub road_classes: Vec<String>,
}
/// **Every level crossing that is a real joint between the two networks and carries no
/// barrier, light, bell or supervision.**
///
/// Not a tag scan: a node is only reported if the graph says both a road edge and a rail
/// edge end there (`kind = "both"`), and the road classes come from the incident edges.
pub fn unguarded_crossings(
g: &Graph,
edge_class: &HashMap<i64, (String, String)>,
) -> Vec<Unguarded> {
let mut out = Vec::new();
for i in 0..g.node_id.len() {
if g.node_kind[i] != 3 {
continue;
}
if g.rail_class[i].as_deref() != Some("level_crossing") {
continue;
}
let tags = g.node_tags[i].as_deref().unwrap_or("");
if is_guarded(tags) {
continue;
}
let mut road = 0usize;
let mut rail = 0usize;
let mut cls: Vec<String> = Vec::new();
for a in g.neighbours(i) {
if let Some((net, c)) = edge_class.get(&a.edge) {
if net == "roads" {
road += 1;
if !cls.contains(c) {
cls.push(c.clone());
}
} else if net == "rails" {
rail += 1;
}
}
}
cls.sort();
out.push(Unguarded {
node: g.node_id[i],
lon: g.node_xy[i].0,
lat: g.node_xy[i].1,
road_edges: road,
rail_edges: rail,
road_classes: cls,
});
}
out
}
/// `edge id → (network, class)`, read off the edge table. Needed to say WHAT meets at a
/// node; the adjacency list gives the edge ids.
pub fn edge_classes(dir: &Path) -> anyhow::Result<HashMap<i64, (String, String)>> {
let p = dir.join(format!("{GRAPH_EDGES}.parquet"));
let f = std::fs::File::open(&p)?;
let mut m = HashMap::new();
for b in ParquetRecordBatchReaderBuilder::try_new(f)?.build()? {
let b = b?;
let id = arr::<Int64Array>(&b, "id")?;
let net = arr::<StringArray>(&b, "network")?;
let cls = arr::<StringArray>(&b, "class")?;
for i in 0..b.num_rows() {
m.insert(
id.value(i),
(String::from(net.value(i)), String::from(cls.value(i))),
);
}
}
Ok(m)
}
#[cfg(test)]
mod tests {
use super::*;
use arrow::array::ListArray;
/// A tiny hand-built network: one road of 5 nodes, one rail of 3, meeting at node 30
/// which is tagged `level_crossing`. Node 12 is a T junction with a side road.
///
/// ```text
/// road A: 10 - 11 - 12 - 30 - 13 (12 is also on road B, 30 is the crossing)
/// road B: 12 - 20
/// rail : 40 - 30 - 41
/// ```
fn fixture() -> (
Vec<(
i64,
&'static str,
&'static str,
&'static str,
Vec<i64>,
Vec<(f64, f64)>,
)>,
Vec<(i64, &'static str, &'static str)>,
) {
let ways = vec![
(
1i64,
"roads",
"primary",
r#"{"highway":"primary"}"#,
vec![10i64, 11, 12, 30, 13],
vec![
(17.0, 59.0),
(17.1, 59.0),
(17.2, 59.0),
(17.3, 59.0),
(17.4, 59.0),
],
),
(
2,
"roads",
"residential",
r#"{"highway":"residential","oneway":"yes"}"#,
vec![12, 20],
vec![(17.2, 59.0), (17.2, 59.1)],
),
(
3,
"rails",
"rail",
r#"{"railway":"rail"}"#,
vec![40, 30, 41],
vec![(17.3, 58.9), (17.3, 59.0), (17.3, 59.1)],
),
];
let nodes = vec![
(30i64, "level_crossing", r#"{"railway":"level_crossing"}"#),
(41, "signal", r#"{"railway":"signal"}"#),
];
(ways, nodes)
}
fn build_fixture(
ways: &[(
i64,
&'static str,
&'static str,
&'static str,
Vec<i64>,
Vec<(f64, f64)>,
)],
nodes: &[(i64, &'static str, &'static str)],
) -> (Vec<Vec<u8>>, GraphBuild) {
let geoms: Vec<Vec<u8>> = ways.iter().map(|w| wkb_line(&w.5)).collect();
let wi: Vec<WayIn<'_>> = ways
.iter()
.zip(&geoms)
.map(|(w, g)| WayIn {
id: w.0,
network: w.1,
class: w.2,
tags: w.3,
geometry: Some(g.as_slice()),
node_refs: &w.4,
})
.collect();
let ni: Vec<NodeIn<'_>> = nodes
.iter()
.map(|n| NodeIn {
id: n.0,
class: n.1,
tags: n.2,
})
.collect();
let b = build_graph(&wi, &ni).unwrap();
(geoms, b)
}
/// ★ **RED-when-broken: the junction set must be the SHARED nodes, not every node.**
///
/// A builder that admitted every `node_ref` would produce 8 graph nodes here instead
/// of 6, and every shape point would be a routing decision. Both arms are asserted —
/// the nodes that must be in AND the shape points that must be out — so "admit
/// everything" and "admit nothing" both go red.
#[test]
fn shape_points_are_not_graph_nodes_but_junctions_endpoints_and_crossings_are() {
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
let mut ids: Vec<i64> = Vec::new();
for batch in &b.nodes {
let a = arr::<Int64Array>(batch, "id").unwrap();
ids.extend((0..batch.num_rows()).map(|i| a.value(i)));
}
ids.sort_unstable();
assert_eq!(
ids,
vec![10, 12, 13, 20, 30, 40, 41],
"graph nodes must be endpoints (10,13,20,40,41), the T junction (12) and the \
level crossing (30) — node 11 is a shape point on ONE way and must not be here"
);
assert!(
!ids.contains(&11),
"node 11 is a bend in one road, not a decision"
);
assert_eq!(
b.stats.distinct_nodes, 8,
"8 distinct refs across the three ways"
);
assert_eq!(b.stats.graph_nodes, 7);
}
/// ★ **RED-when-broken: a way is CUT at its interior junctions.**
///
/// Road 1 runs 10-11-12-30-13 and must become three edges (10→12, 12→30, 30→13), not
/// one. A builder that emitted whole ways passes every "the table has rows" test and
/// cannot route.
#[test]
fn a_way_is_split_at_every_interior_junction_and_the_pieces_join_up() {
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
let mut got: Vec<(i64, i64, i64)> = Vec::new();
for batch in &b.edges {
let w = arr::<Int64Array>(batch, "way_id").unwrap();
let f = arr::<Int64Array>(batch, "from_node").unwrap();
let t = arr::<Int64Array>(batch, "to_node").unwrap();
got.extend((0..batch.num_rows()).map(|i| (w.value(i), f.value(i), t.value(i))));
}
got.sort_unstable();
assert_eq!(
got,
vec![
(1, 10, 12),
(1, 12, 30),
(1, 30, 13),
(2, 12, 20),
(3, 30, 41),
(3, 40, 30),
],
"way 1 must be cut at the junction (12) and at the crossing (30); way 3 must \
be cut at the crossing"
);
assert_eq!(
b.stats.whole_way_fallback, 0,
"every fixture way is sliceable"
);
}
/// ★ **RED-when-broken: the geometry SLICE must be the piece, not the whole way.**
///
/// The obvious defect — carry the way's geometry onto every one of its edges — leaves
/// the table valid, drawable and completely wrong for routing: every segment would
/// claim the whole way's length. Asserted on the coordinates and on the length.
#[test]
fn each_edge_carries_only_its_own_span_of_the_line() {
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
let mut by_edge: HashMap<(i64, i64), (Vec<(f64, f64)>, f64)> = HashMap::new();
for batch in &b.edges {
let f = arr::<Int64Array>(batch, "from_node").unwrap();
let t = arr::<Int64Array>(batch, "to_node").unwrap();
let g = arr::<BinaryArray>(batch, "geometry").unwrap();
let l = arr::<Float64Array>(batch, "length_m").unwrap();
for i in 0..batch.num_rows() {
by_edge.insert(
(f.value(i), t.value(i)),
(line_points(g.value(i)).unwrap(), l.value(i)),
);
}
}
let (pts, len) = &by_edge[&(10, 12)];
assert_eq!(
pts,
&vec![(17.0, 59.0), (17.1, 59.0), (17.2, 59.0)],
"edge 10→12 is the FIRST THREE points of way 1, not all five"
);
let (pts2, len2) = &by_edge[&(12, 30)];
assert_eq!(pts2, &vec![(17.2, 59.0), (17.3, 59.0)]);
assert!(
(*len - 2.0 * *len2).abs() < 1.0,
"10→12 spans two 0.1° hops and 12→30 one, so it must be twice as long: \
{len} vs {len2}"
);
// and the whole way's length must NOT be what any single edge reports
let whole: f64 = by_edge.values().filter(|_| true).map(|(_, l)| *l).sum();
assert!(
*len < whole,
"an edge that carried the whole way would equal the sum: {len} vs {whole}"
);
}
/// ★ **RED-when-broken: `oneway` reaches the column, and a roundabout is one-way
/// without saying so.** An `oneway` column that is always 0 is present, valid and a
/// lie about every one-way street in the country.
#[test]
fn oneway_is_resolved_at_build_time_including_the_roundabout_that_never_says_so() {
assert_eq!(oneway_of(r#"{"highway":"primary"}"#), 0);
assert_eq!(oneway_of(r#"{"oneway":"yes"}"#), 1);
assert_eq!(oneway_of(r#"{"oneway":"-1"}"#), -1);
assert_eq!(oneway_of(r#"{"oneway":"no"}"#), 0);
assert_eq!(
oneway_of(r#"{"highway":"primary","junction":"roundabout"}"#),
1,
"a roundabout is one-way by definition and almost never carries oneway=yes"
);
assert_eq!(
oneway_of(r#"{"oneway":"no","junction":"roundabout"}"#),
0,
"an explicit oneway=no must beat the roundabout inference, not be overridden"
);
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
assert_eq!(b.stats.oneway_forward, 1, "only way 2 is oneway=yes");
assert_eq!(b.stats.oneway_backward, 0);
}
/// ★ **RED-when-broken: the two networks are ONE graph, joined at the level
/// crossing.** This is the whole claim. Node 30 must carry road edges AND rail edges,
/// and a walk that starts on the road must be able to reach a rail node.
#[test]
fn the_road_graph_and_the_rail_graph_meet_at_the_level_crossing() {
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
assert_eq!(
b.stats.joints, 1,
"exactly one node has both a road and a rail edge"
);
let mut kind: HashMap<i64, String> = HashMap::new();
let mut adj: HashMap<i64, Vec<i64>> = HashMap::new();
for batch in &b.nodes {
let id = arr::<Int64Array>(batch, "id").unwrap();
let k = arr::<StringArray>(batch, "kind").unwrap();
let e = batch
.column_by_name("edges")
.unwrap()
.as_any()
.downcast_ref::<ListArray>()
.unwrap();
for i in 0..batch.num_rows() {
kind.insert(id.value(i), String::from(k.value(i)));
adj.insert(
id.value(i),
e.value(i)
.as_any()
.downcast_ref::<Int64Array>()
.unwrap()
.iter()
.flatten()
.collect(),
);
}
}
assert_eq!(kind[&30], "both", "node 30 is the joint");
assert_eq!(kind[&12], "road", "the T junction is road only");
assert_eq!(kind[&40], "rail", "a rail endpoint is rail only");
assert_eq!(
adj[&30].len(),
4,
"two road edges and two rail edges meet at the crossing: {:?}",
adj[&30]
);
// THE NEGATIVE ARM: node 11 has no adjacency because it is not a node at all.
assert!(!adj.contains_key(&11));
// and the T junction has exactly the three edges it should
assert_eq!(adj[&12].len(), 3, "10→12, 12→30, 12→20");
}
/// An edge id names its way, so a table can be joined back without a side lookup.
#[test]
fn an_edge_id_names_the_way_it_came_from() {
let (ways, nodes) = fixture();
let (_g, b) = build_fixture(&ways, &nodes);
for batch in &b.edges {
let id = arr::<Int64Array>(batch, "id").unwrap();
let w = arr::<Int64Array>(batch, "way_id").unwrap();
for i in 0..batch.num_rows() {
assert_eq!(
id.value(i) / SEGMENTS_PER_WAY,
w.value(i),
"edge id must divide back to its way id"
);
}
}
}
/// ★ **RED-when-broken: a way whose geometry does not match its refs falls back to
/// ONE edge and is COUNTED.** Slicing it by index would cut it at the wrong places
/// and nothing in the output would say so.
#[test]
fn a_way_whose_geometry_disagrees_with_its_refs_is_counted_not_sliced_wrong() {
let geom = wkb_line(&[(17.0, 59.0), (17.4, 59.0)]); // 2 points
let refs = vec![10i64, 11, 12, 13]; // 4 refs
let w = WayIn {
id: 7,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary"}"#,
geometry: Some(&geom),
node_refs: &refs,
};
let b = build_graph(&[w], &[]).unwrap();
assert_eq!(
b.stats.whole_way_fallback, 1,
"the mismatch must be COUNTED"
);
assert_eq!(
b.stats.graph_edges, 1,
"one whole-way edge, not three wrong ones"
);
let f = arr::<Int64Array>(&b.edges[0], "from_node").unwrap();
let t = arr::<Int64Array>(&b.edges[0], "to_node").unwrap();
assert_eq!(
(f.value(0), t.value(0)),
(10, 13),
"still first ref to last ref"
);
}
/// Write `built` to `dir` as the two graph tables, so [`Graph::load`] can be asserted
/// against a real file rather than against the in-memory structs it never sees.
fn write_tables(dir: &Path, b: &GraphBuild) {
std::fs::create_dir_all(dir).unwrap();
for (name, schema, batches) in [
(GRAPH_EDGES, edge_schema(), &b.edges),
(GRAPH_NODES, node_schema(), &b.nodes),
] {
let f = std::fs::File::create(dir.join(format!("{name}.parquet"))).unwrap();
let mut w = parquet::arrow::ArrowWriter::try_new(f, schema, None).unwrap();
for batch in batches {
w.write(batch).unwrap();
}
w.close().unwrap();
}
}
/// ★ **RED-when-broken: the loaded graph is DIRECTED — a one-way edge is one arc, not
/// two — and the router therefore refuses to drive the wrong way.**
///
/// This is the guard the whole routing answer rests on. A loader that ignored the
/// `oneway` column produces a graph that is bigger, faster to reach anything in, and
/// wrong about every one-way street in the country; nothing in the output would say
/// so, because the shorter answer looks like a better answer. Both directions are
/// asserted, so "always one arc" fails too.
#[test]
fn a_one_way_edge_is_one_arc_and_the_route_refuses_to_go_back_up_it() {
let tmp = tempfile::tempdir().unwrap();
// 10 →(two-way)→ 11 →(ONE-WAY)→ 12. Going 10→12 is 2 hops; 12→10 must be
// impossible, because the only link back is the one-way stretch.
let g1 = wkb_line(&[(17.0, 59.0), (17.01, 59.0)]);
let g2 = wkb_line(&[(17.01, 59.0), (17.02, 59.0)]);
let r1 = vec![10i64, 11];
let r2 = vec![11i64, 12];
let ways = vec![
WayIn {
id: 1,
network: "roads",
class: "residential",
tags: r#"{"highway":"residential"}"#,
geometry: Some(&g1),
node_refs: &r1,
},
WayIn {
id: 2,
network: "roads",
class: "residential",
tags: r#"{"highway":"residential","oneway":"yes"}"#,
geometry: Some(&g2),
node_refs: &r2,
},
];
let b = build_graph(&ways, &[]).unwrap();
write_tables(tmp.path(), &b);
let g = Graph::load(tmp.path()).unwrap();
assert_eq!(g.edges, 2);
assert_eq!(
g.csr.len(),
3,
"the two-way edge is two arcs and the one-way edge is ONE — a loader that \
ignored `oneway` would build 4"
);
let (a, b_, c) = (
g.index_of(10).unwrap(),
g.index_of(11).unwrap(),
g.index_of(12).unwrap(),
);
// forwards: reachable
let hit = g
.nearest_matching(a, NET_ROAD, |i| i == c)
.expect("10 → 12 must be routable");
assert_eq!(hit.0, c);
assert!(hit.1 > 1_000.0, "two ~600 m hops, got {} m", hit.1);
// backwards: NOT reachable, and 11 is not reachable from 12 either
assert!(
g.nearest_matching(c, NET_ROAD, |i| i == a).is_none(),
"12 → 10 must be impossible: the only way back is up a one-way street"
);
assert!(g.nearest_matching(c, NET_ROAD, |i| i == b_).is_none());
// and the two-way half really is two-way, so the test is not passing by paralysis
assert!(
g.nearest_matching(b_, NET_ROAD, |i| i == a).is_some(),
"11 → 10 is two-way"
);
}
/// ★ **RED-when-broken: a ROAD distance may not be shortened by driving on the
/// railway.**
///
/// This one is the reason the arcs carry their network at all, and it was a real wrong
/// answer before it was a test. Joining the road and rail networks into one graph is
/// the whole point — and it means an unrestricted Dijkstra can enter the track at one
/// level crossing and leave it at the next. The shortcut makes every answer *smaller*,
/// and a smaller distance looks like a better one, so nothing downstream would flag it.
///
/// Both arms are asserted: with rail allowed the shortcut MUST be taken (or the
/// fixture proves nothing), and with roads only it must not be.
#[test]
fn a_road_route_may_not_take_the_shortcut_along_the_railway() {
// 10 —road— 30 ==rail== 31 —road— 11 (≈ 180 m through the track)
// 10 ————— 40 —— 41 ————— 11 (≈ 22 km round by road)
let g_a = wkb_line(&[(17.000, 59.0), (17.001, 59.0)]);
let g_r = wkb_line(&[(17.001, 59.0), (17.002, 59.0)]);
let g_b = wkb_line(&[(17.002, 59.0), (17.003, 59.0)]);
let g_d = wkb_line(&[
(17.000, 59.0),
(17.000, 59.1),
(17.003, 59.1),
(17.003, 59.0),
]);
let (ra, rr, rb, rd) = (
vec![10i64, 30],
vec![30i64, 31],
vec![31i64, 11],
vec![10i64, 40, 41, 11],
);
let ways = vec![
WayIn {
id: 1,
network: "roads",
class: "residential",
tags: r#"{"highway":"residential"}"#,
geometry: Some(&g_a),
node_refs: &ra,
},
WayIn {
id: 2,
network: "rails",
class: "rail",
tags: r#"{"railway":"rail"}"#,
geometry: Some(&g_r),
node_refs: &rr,
},
WayIn {
id: 3,
network: "roads",
class: "residential",
tags: r#"{"highway":"residential"}"#,
geometry: Some(&g_b),
node_refs: &rb,
},
WayIn {
id: 4,
network: "roads",
class: "residential",
tags: r#"{"highway":"residential"}"#,
geometry: Some(&g_d),
node_refs: &rd,
},
];
let tmp = tempfile::tempdir().unwrap();
let b = build_graph(&ways, &[]).unwrap();
write_tables(tmp.path(), &b);
let g = Graph::load(tmp.path()).unwrap();
let (a, z) = (g.index_of(10).unwrap(), g.index_of(11).unwrap());
let by_road = g
.nearest_matching(a, NET_ROAD, |i| i == z)
.expect("the detour exists");
let by_both = g
.nearest_matching(a, NET_ROAD | NET_RAIL, |i| i == z)
.expect("through the track");
assert!(
by_both.1 < 500.0,
"with rail allowed the shortcut must be taken, or this fixture proves nothing: \
{} m",
by_both.1
);
assert!(
by_road.1 > 20_000.0,
"by ROAD the only way from 10 to 11 is the 22 km detour — {} m says the router \
drove on the railway",
by_road.1
);
}
/// ★ **RED-when-broken: a CLOSED way — a roundabout — is sliced, not collapsed into
/// one self-loop.**
///
/// A way that closes on itself is written as a `Polygon`, and a slicer that only
/// understands `LineString` emits a single edge `X → X` for it: valid, drawable, and
/// impossible to enter or leave. On the real extract that was **7 483 ways**, most of
/// them roundabouts, which is exactly where a router has decisions to make.
#[test]
fn a_roundabout_is_a_ring_of_edges_not_one_self_loop() {
// A 4-node ring closed back on its first node, written the way `geometry.rs`
// writes a closed way: a one-ring Polygon.
let ring: [(f64, f64); 5] = [
(17.0, 59.0),
(17.01, 59.0),
(17.01, 59.01),
(17.0, 59.01),
(17.0, 59.0),
];
let mut poly = vec![1u8];
poly.extend_from_slice(&3u32.to_le_bytes()); // Polygon
poly.extend_from_slice(&1u32.to_le_bytes()); // one ring
poly.extend_from_slice(&(ring.len() as u32).to_le_bytes());
for (x, y) in ring {
poly.extend_from_slice(&x.to_le_bytes());
poly.extend_from_slice(&y.to_le_bytes());
}
let rrefs = vec![50i64, 51, 52, 53, 50];
// Two side roads join the ring at nodes 51 and 53, so it must break into pieces.
let spur_a = wkb_line(&[(17.01, 59.0), (17.05, 59.0)]);
let spur_b = wkb_line(&[(17.0, 59.01), (16.95, 59.01)]);
let ra = vec![51i64, 60];
let rb = vec![53i64, 61];
let ways = vec![
WayIn {
id: 100,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary","junction":"roundabout"}"#,
geometry: Some(&poly),
node_refs: &rrefs,
},
WayIn {
id: 101,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary"}"#,
geometry: Some(&spur_a),
node_refs: &ra,
},
WayIn {
id: 102,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary"}"#,
geometry: Some(&spur_b),
node_refs: &rb,
},
];
let b = build_graph(&ways, &[]).unwrap();
assert_eq!(
b.stats.whole_way_fallback, 0,
"a one-ring Polygon IS the way's node sequence and must be sliceable"
);
let mut ring_edges: Vec<(i64, i64, i8)> = Vec::new();
for batch in &b.edges {
let w = arr::<Int64Array>(batch, "way_id").unwrap();
let f = arr::<Int64Array>(batch, "from_node").unwrap();
let t = arr::<Int64Array>(batch, "to_node").unwrap();
let o = arr::<Int8Array>(batch, "oneway").unwrap();
for i in 0..batch.num_rows() {
if w.value(i) == 100 {
ring_edges.push((f.value(i), t.value(i), o.value(i)));
}
}
}
assert_eq!(
ring_edges,
vec![(50, 51, 1), (51, 53, 1), (53, 50, 1)],
"the ring must break at the two spur junctions — one self-loop 50→50 would be \
a roundabout no router can enter"
);
}
/// ★ **RED-when-broken: an unguarded crossing is told apart from a guarded one.**
/// A predicate that always said "unguarded" would produce a headline number with no
/// meaning, so both arms are asserted, including the passive saltire that is NOT
/// protection.
#[test]
fn guarded_and_unguarded_crossings_are_told_apart() {
assert!(is_guarded(
r#"{"railway":"level_crossing","crossing:barrier":"full"}"#
));
assert!(is_guarded(
r#"{"railway":"level_crossing","crossing:barrier":"half"}"#
));
assert!(is_guarded(
r#"{"railway":"level_crossing","crossing:light":"yes"}"#
));
assert!(is_guarded(
r#"{"railway":"level_crossing","crossing:bell":"yes"}"#
));
assert!(is_guarded(
r#"{"railway":"level_crossing","supervised":"yes"}"#
));
assert!(!is_guarded(r#"{"railway":"level_crossing"}"#));
assert!(
!is_guarded(r#"{"railway":"level_crossing","crossing:saltire":"yes"}"#),
"a St Andrew's cross is a sign, not a barrier — counting it as protection \
would hide the crossings this question exists to find"
);
assert!(
!is_guarded(r#"{"railway":"level_crossing","crossing:barrier":"no"}"#),
"an explicit `no` is the CLEAREST unguarded case and must not read as guarded \
just because the key is present"
);
}
/// ★ **RED-when-broken: a tagged `maxspeed` beats the ONE class table, and garbage
/// falls back instead of poisoning the column.** A parser that ignored the tag
/// would price every street at its class default and the column would still be
/// full, valid and wrong — which is why both arms are asserted.
#[test]
fn a_tagged_maxspeed_beats_the_class_default_and_garbage_falls_back() {
assert_eq!(maxspeed_kmh(r#"{"maxspeed":"70"}"#), Some(70.0));
assert_eq!(
maxspeed_kmh(r#"{"maxspeed":"30 mph"}"#).map(f64::round),
Some(48.0),
"mph converts, not passes through"
);
assert_eq!(maxspeed_kmh(r#"{"maxspeed":"walk"}"#), Some(7.0));
assert_eq!(
maxspeed_kmh(r#"{"maxspeed":"SE:urban"}"#),
None,
"a zone spelling is not a number — refusing to guess is the honesty"
);
assert_eq!(maxspeed_kmh(r#"{"maxspeed":"70;50"}"#), None);
assert_eq!(maxspeed_kmh(r#"{"maxspeed":"0"}"#), None, "zero is not a speed");
assert_eq!(maxspeed_kmh(r#"{"highway":"primary"}"#), None);
assert_eq!(edge_speed_kmh(r#"{"maxspeed":"110"}"#, "residential"), (110.0, true));
assert_eq!(
edge_speed_kmh(r#"{"highway":"motorway"}"#, "motorway"),
(110.0, false),
"no tag: the class default from the ONE table"
);
assert_eq!(
edge_speed_kmh("{}", "hovercraftway"),
(DEFAULT_SPEED_KMH, false),
"an unknown class drives the stated default, never silently zero"
);
}
/// ★ **RED-when-broken: the speed reaches the COLUMN with its source named, and the
/// build MEASURES coverage.** The tagged street must carry ITS speed and the
/// untagged one its class default — a builder that stamped the default everywhere
/// passes every "the column exists" probe.
#[test]
fn speed_reaches_the_column_from_maxspeed_else_the_class_table() {
let g1 = wkb_line(&[(17.0, 59.0), (17.1, 59.0)]);
let g2 = wkb_line(&[(17.1, 59.0), (17.2, 59.0)]);
let r1 = vec![10i64, 11];
let r2 = vec![11i64, 12];
let ways = vec![
WayIn {
id: 1,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary","maxspeed":"70"}"#,
geometry: Some(&g1),
node_refs: &r1,
},
WayIn {
id: 2,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary"}"#,
geometry: Some(&g2),
node_refs: &r2,
},
];
let b = build_graph(&ways, &[]).unwrap();
let mut got: HashMap<i64, (f64, String)> = HashMap::new();
for batch in &b.edges {
let w = arr::<Int64Array>(batch, "way_id").unwrap();
let sp = arr::<Float64Array>(batch, "speed_kmh").unwrap();
let ss = arr::<StringArray>(batch, "speed_source").unwrap();
for i in 0..batch.num_rows() {
got.insert(w.value(i), (sp.value(i), String::from(ss.value(i))));
}
}
assert_eq!(got[&1], (70.0, String::from(SPEED_SOURCE_MAXSPEED)));
assert_eq!(
got[&2],
(class_speed_kmh("primary"), String::from(SPEED_SOURCE_CLASS)),
"the untagged way drives the class default and SAYS so"
);
assert_eq!(b.stats.speed_tagged_edges, 1);
assert!(b.stats.road_m > 10_000.0, "two ~5.7 km ways: {}", b.stats.road_m);
let ratio = b.stats.speed_tagged_road_m / b.stats.road_m;
assert!(
(ratio - 0.5).abs() < 0.01,
"one of two equal-length ways is tagged — km coverage must be 50 %: {ratio}"
);
}
/// ★ **RED-when-broken: the loaded arc carries its speed, and an OLD cut without
/// the column prices the class default — a typed fallback, not a crash and not a
/// lie.** Both arms asserted: the new cut's arc must carry the TAGGED speed (a
/// loader that recomputed the class default would read 80 here, not 70), and the
/// old cut must load with `speed_from_column == false`.
#[test]
fn the_loaded_arc_carries_its_speed_and_an_old_cut_prices_the_class_default() {
let geom = wkb_line(&[(17.0, 59.0), (17.1, 59.0)]);
let refs = vec![10i64, 11];
let ways = vec![WayIn {
id: 1,
network: "roads",
class: "primary",
tags: r#"{"highway":"primary","maxspeed":"70"}"#,
geometry: Some(&geom),
node_refs: &refs,
}];
let b = build_graph(&ways, &[]).unwrap();
// The NEW cut: the arc prices the tagged 70, not primary's class default 80.
let tmp = tempfile::tempdir().unwrap();
write_tables(tmp.path(), &b);
let g = Graph::load(tmp.path()).unwrap();
assert!(g.speed_from_column, "the new cut carries the column");
let arc = g.csr.first().expect("one edge, at least one arc");
assert_eq!(arc.speed_kmh, 70, "the TAGGED speed rides the arc");
assert!((arc.speed_ms() - 70.0 / 3.6).abs() < 1e-9);
// The OLD cut: same batches with the two speed columns projected OUT.
let full = edge_schema();
let keep: Vec<usize> = full
.fields()
.iter()
.enumerate()
.filter(|(_, f)| f.name() != "speed_kmh" && f.name() != "speed_source")
.map(|(i, _)| i)
.collect();
let old_schema = Arc::new(Schema::new(
keep.iter()
.map(|&i| full.field(i).clone())
.collect::<Vec<Field>>(),
));
let tmp2 = tempfile::tempdir().unwrap();
let f = std::fs::File::create(tmp2.path().join("graph_edges.parquet")).unwrap();
let mut w = parquet::arrow::ArrowWriter::try_new(f, old_schema, None).unwrap();
for batch in &b.edges {
w.write(&batch.project(&keep).unwrap()).unwrap();
}
w.close().unwrap();
let f = std::fs::File::create(tmp2.path().join("graph_nodes.parquet")).unwrap();
let mut w = parquet::arrow::ArrowWriter::try_new(f, node_schema(), None).unwrap();
for batch in &b.nodes {
w.write(batch).unwrap();
}
w.close().unwrap();
let g = Graph::load(tmp2.path()).unwrap();
assert!(!g.speed_from_column, "an old cut says it has no column");
let arc = g.csr.first().expect("still loads");
assert_eq!(
arc.speed_kmh,
class_speed_kmh("primary").round() as u8,
"without the column the class default prices the arc — never zero, never 70"
);
}
}