Graphy

Build a routing graph from raw OpenStreetMap data, implement the shortest-path algorithms yourself, and watch them run on a real city.

That's Rīga International Airport to a clinic across the river: 10.15 km over 134 hops. The dots are the search itself — every vertex Dijkstra had to settle to be sure, blue where it started and red at the frontier. It settled 20,224 of 69,865 vertices to answer one query, because Dijkstra has no idea where the target is. Making that number collapse is the whole project.

One hard rule: no OSMnx, no NetworkX, no graphlib, nothing that hands you a ready graph or a ready shortest path. Those are exactly the parts worth writing. Use them as a correctness oracle if you like.

./graphy setup     # .venv + numpy, scipy, pytest, osmium
./graphy graph     # download OSM data, build riga.bin (~2 min, 133 MB once)
./graphy app       # build and launch the macOS app

Then load riga.bin, type two places into A and B, and hit Run.

./graphy test                      Python + Swift tests
./graphy bench                     compare the Swift algorithms on a real graph
./graphy run <file> [s t metric]   run one solution
./graphy check <file> --pairs 20   verify a solution against the reference
./graphy langs                     which toolchains you have

Needs macOS 13+ and Swift 5.9 for the app. The pipeline is Python and runs anywhere.

pipeline/ (Python, run rarely)  ──graph.bin──▶  GraphyCore (pure Swift)  ──SearchResult──▶  mac/App (SwiftUI + MapKit)

GraphyCore never imports AppKit or MapKit, so swift test exercises every algorithm headlessly without launching a window — a far tighter loop than building the app.

graph.bin is the contract between them: a 48-byte header then flat, 4-byte-aligned, little-endian arrays. It was designed so a browser could build typed-array views onto it with zero copying, and that same property is why any language can read it directly. runners/PROTOCOL.md has the layout.

Riga, car profile, generous bbox:

BFS and Dijkstra are implemented. BidirectionalDijkstra, AStar, ALT and ContractionHierarchies are stubs, each with a doc comment describing the specific thing that goes wrong in that algorithm — the bidirectional stopping condition, A*'s admissibility divisor on the time metric, ALT's landmark selection, CH's node ordering and unpacking.

In Swift, fill in search in mac/Sources/GraphyCore/Algorithms.swift, set isImplemented = true, and run:

cd mac && swift test --filter ConformanceTests/testAStar
swift run -c release GraphyBench ../riga.bin

In any other language, use the editor pane in the app. Pick a language, write a search, hit ⌘R, and your frontier animates on the map beside your code. Templates ship for C, C++, Pascal, Java, Scala, Python and JavaScript — each a complete graph.bin reader plus a plain Dijkstra, so they run before you change a line. Your program reads the graph file directly and prints four lines back; see runners/PROTOCOL.md.

Either way it's checked against Dijkstra automatically, on cost and on whether the path is a real walk that sums to the cost you reported. Costs, not paths — ties are everywhere in a road network and two correct algorithms legitimately return different equal-cost routes.

This matters more than it sounds. A deliberately broken A* written while testing the harness settled 23× fewer vertices than Dijkstra — and was wrong. Speed with a wrong answer looks exactly like success.

The editor compiles and runs whatever you type, as you, with no sandbox. That's fine for code you wrote on your own machine. Do not paste in code you don't trust, and don't expose this to anyone else without confining it first.

pipeline/     OSM → graph.bin: way splitting, oneway rules, speeds, SCC, CSR
mac/
  Sources/GraphyCore/   graph reader, CSR, heap, the algorithm ladder
  Sources/GraphyBench/  correctness + settled-count comparison on a real graph
  App/                  SwiftUI + MapKit, frontier animation, code editor
  Tests/                ConformanceTests is the suite an implementation must pass
runners/      PROTOCOL.md, run.sh, check.py, templates/ for each language
DESIGN.md     the spec and the reasoning — read this first

python -m pipeline build data/riga.json -o riga.bin
python -m pipeline build data/latvia-latest.osm.pbf -o riga.bin --bbox riga
python -m pipeline build data/riga.json -o riga-foot.bin --profile foot
python -m pipeline verify riga.bin --route

--bbox takes the presets riga / riga-central, or raw minlat,minlon,maxlat,maxlon. Profiles are car, foot, bike.

verify runs the structural invariants, checks strong connectivity by forward and backward BFS, and does a corner-to-corner Dijkstra. Everything should pass on a healthy build; if one fails, the bug is in the pipeline and not in whatever you're writing on top of it.

Two data sources. ./pipeline/fetch.sh overpass is small and dependency-free but hits a volunteer-run server that is often too busy — it answers "server too busy" with HTTP 200 and an HTML body, so the script checks it actually got JSON. ./pipeline/fetch.sh geofabrik downloads the whole country as .osm.pbf (~133 MB) and is far more reliable; clip it with --bbox.

Tests run against pipeline/tests/fixtures/tiny.osm, a hand-built 24-node file covering junction detection, oneway=-1, implicit roundabout direction, access=private, footway filtering, self-loops, duplicate arcs, maxspeed parsing, and a detached component that largest-SCC has to prune. osmium is required to run them — the fixture is .osm XML, and everything that isn't Overpass JSON goes through osmium.

Graph-shaped test data with no download:

python -m pipeline.tests.make_synthetic --blocks 200 -o /tmp/syn.json
python -m pipeline build /tmp/syn.json -o /tmp/syn.bin

DESIGN.md is the spec: the OSM reduction, the on-wire format, the algorithm ladder from BFS to Contraction Hierarchies, and a collected list of the traps — ways aren't edges, largest-SCC is mandatory, oneway=-1 exists, A* on the time metric must divide by the graph's max speed, and the bidirectional stopping condition is topF + topB ≥ μ rather than "the frontiers touched".