Published · v2.2.2

Gravel

Network graph fragility analysis. Given a graph and a notion of "failure," Gravel quantifies how badly connectivity degrades — which edges are load-bearing, which regions become isolated, and where redundancy is genuinely absent versus merely reduced. Ships with first-class OpenStreetMap support for road networks; the analysis engine itself works on any directed weighted graph.

Apache 2.0 C++20 Python 3.10+ Linux · macOS · Windows

View on GitHub

The question routing libraries don't ask

Traditional routing answers what is the shortest path? Gravel answers a harder one: how does that path degrade when edges fail?

Why it matters

Critical-infrastructure plans assume networks stay functional under stress. They rarely do. Constrained geographies — mountain passes, coastal corridors, single-substation towns — depend on a handful of edges with no viable detours.

What Gravel produces

Quantitative fragility scores that make vulnerabilities comparable across regions and domains — so "where is redundancy genuinely absent?" becomes a ranked list, not a hunch or a tabletop guess.

Built for roads. Works on any network.

Gravel's analysis operates on a generic ArrayGraph — nodes, directed weighted edges, optional coordinates. The road-specific parts (OSM PBF loading, TIGER/Census boundaries, speed profiles) live in the gravel-geo and gravel-us sub-libraries. Everything else — contraction hierarchies, replacement-path analysis, isolation scoring, scenario fragility — doesn't care what your edges represent.

Built-in

Road networks

OpenStreetMap PBF loader with configurable speed profiles. TIGER/Line loaders for US counties, states, CBSAs. Emergency routing, evacuation planning, bridge criticality, rural-access equity.

Bring your own

Electrical grids

Substations and generators as nodes; transmission lines as weighted edges (impedance, capacity). Identify single-substation dependencies, model cascade-failure propagation, rank blackout exposure by region.

Bring your own

Telecom networks

Routers, switches, and towers as nodes; fiber runs and microwave links as edges (bandwidth, latency). Quantify fiber-cut impact, find routing-diversity gaps, pre-position redundancy where it matters.

Bring your own

Water, gas, rail, custom

Any graph with nodes, weighted edges, and a notion of flow works. Load from CSV edge lists, a NumPy array, or programmatic builders — no OSM dependency required, no geography assumed.

Why this matters for disaster & national security planning

The networks a country depends on — power, communications, water, transport — share the same underlying math. An edge fails; some set of downstream nodes becomes harder or impossible to reach. Gravel lets you score that failure quantitatively across domains using one toolkit, so comparative risk analysis stops being apples-to-oranges.

Installation

conda — recommended

conda install -c conda-forge gravel-fragility

pip — source build

pip install gravel-fragility

From source

git clone https://github.com/rhoekstr/gravel.git
cd gravel
cmake -B build -DGRAVEL_BUILD_PYTHON=ON -DGRAVEL_USE_OSMIUM=ON
cmake --build build -j

OSM loading requires libosmium — install separately via brew install libosmium on macOS or apt install libosmium2-dev on Debian/Ubuntu. If you're bringing your own graph and don't need OSM, skip it entirely: the core and fragility libraries have no geographic dependencies.

Quick start

Two examples — a synthetic graph (no geography), then a real OSM county.

Synthetic graph — any network

import gravel

# Build a 20×20 grid graph — 400 nodes, no geography
graph = gravel.make_grid_graph(20, 20)

# Contraction hierarchy: one-time cost, then O(log n) queries
ch = gravel.build_ch(graph)
query = gravel.CHQuery(ch)

# Shortest path from corner to corner
result = query.route(source=0, target=399)
print(f"distance: {result.distance:.2f}, "
      f"path: {len(result.path)} nodes")

Location fragility — real OSM data

import gravel

graph = gravel.load_osm_graph("county.osm.pbf",
                              gravel.SpeedProfile.car())
ch = gravel.build_ch(graph)

cfg = gravel.LocationFragilityConfig()
cfg.center = gravel.Coord(35.43, -83.45)   # Bryson City, NC
cfg.radius_meters = 30_000                 # 30km
cfg.monte_carlo_runs = 20

result = gravel.location_fragility(graph, ch, cfg)
print(f"isolation risk:        {result.isolation_risk:.3f}")
print(f"reachable nodes:       {result.reachable_nodes}")
print(f"directional coverage:  {result.directional_coverage:.2f}")

Measured performance

Apple M-series laptop, release build. Real OSM data at two scales.

Swain Co. NC (200K nodes) and Buncombe Co. NC (593K nodes), real OSM data.
Operation	Swain · 200K nodes	Buncombe · 593K nodes
OSM PBF load	0.36 s	0.99 s
CH build	0.85 s	3.92 s
CH distance query	3.8 µs	8.8 µs
CH route (with path unpacking)	82.7 µs	144.8 µs
Distance matrix cell (OpenMP)	5.5 µs	6.3 µs
Route fragility (per path edge)	~60 ms	~124 ms
Location fragility (MC=20)	2.1 s	~8 s

National per-county 3.1 h Isolation fragility for all 3,221 US counties, end to end.

Inter-county ~22 h 8,547 adjacent county pairs including 1,082 cross-state pairs via osmium merge.

v2.1 → v2.2 speedup ~400× Location fragility rewrite: Dijkstra + IncrementalSSSP on a simplified subgraph.

What the national run found

Running per-county isolation fragility across all 3,221 US counties produced ranked results. Mean risk per state, April 2026 run.

Most vulnerable states

New Hampshire 0.638

Maine 0.571

Rhode Island 0.570

Connecticut 0.563

Most resilient states

Kansas 0.146

Nebraska 0.162

Iowa 0.163

North Dakota 0.165

What the ranking tells you

The Great Plains grid-states score lowest — flat terrain and rectangular road networks yield extensive redundancy. Mountain and coastal states score highest — constrained geography forces traffic through single-path corridors. These are the sort of patterns fragility analysis surfaces cleanly: not "this bridge is old" but "these regions have no topological alternative."

Architecture

Six sub-libraries with a strict dependency DAG. Consumers link only what they need — a router-only tool never pulls in Eigen, Spectra, or libosmium.

Library	Purpose	Depends on
`gravel-core`	ArrayGraph, primitives, OpenMP helpers	stdlib
`gravel-ch`	Contraction hierarchy + blocked-edge queries	core
`gravel-simplify`	Degree-2 contraction, bridges, reduced-graph builder	core, ch
`gravel-fragility`	All fragility analysis — Eigen + Spectra	core, ch, simplify
`gravel-geo`	OSM loading, regions, snapping, boundary nodes (libosmium)	core, simplify
`gravel-us`	TIGER/Census loaders, FIPS crosswalk	geo

The key architectural choice

gravel-fragility does not depend on gravel-geo. Road-specific and geography-specific code is isolated to two leaf sub-libraries. The moment you bring your own graph, you drop those dependencies and link against the domain-agnostic core.

Where it earns its keep

Emergency management

Pre-position by isolation risk

Rank every county or district by the fragility of its access routes. Supply depots and response teams go where isolation is most likely, not where a gut call sends them.

Infrastructure planning

Redundancy investment

Identify the edges that matter disproportionately — the bridge or transmission line whose failure disconnects real populations — and prioritize capital projects that buy the most resilience per dollar.

Critical infrastructure

National security assessment

Model cascade failure and single-point-of-failure exposure on power, water, telecom, and transport networks using a consistent toolkit. Comparative risk analysis across domains becomes a numerical exercise.

Transportation equity

Access gaps, quantified

Measure how dependent a community is on a single critical route. Directional analysis reveals asymmetric vulnerabilities — the evacuation-route problems that don't show up on a map.

Documentation & citation

Reference

README · Complete API reference · Full docs · Runnable examples

License

Apache 2.0 — free for commercial, research, and government use. Contributions welcome via GitHub Issues and Pull Requests.

BibTeX

@software{gravel2026,
  author  = {Hoekstra, Robert},
  title   = {Gravel: Network Graph Fragility Analysis},
  year    = {2026},
  url     = {https://github.com/rhoekstr/gravel},
  version = {2.2.0}
}

What Gravel is not

Not turn-by-turn

Not a navigation library. Use OSRM or GraphHopper for directions.

Not transit

Not a multi-modal trip planner. Use OpenTripPlanner for GTFS.

Not dynamic

Contraction hierarchies assume a static edge set. No live traffic, no mutable graphs.