# Gravel — Product Requirements Document

**Version 2.1 | Last updated: April 2026**

## Executive Summary

Gravel is a C++ library with first-class Python bindings that quantifies how vulnerable road networks are to edge failures. It combines contraction-hierarchy routing with replacement-path fragility analysis to produce composite isolation scores for geographic regions, supporting disaster preparedness research, infrastructure planning, and transportation equity analysis.

## Problem Statement

Traditional routing libraries answer "what is the shortest path?" Gravel answers a harder question: **"how does that path degrade when edges fail?"** This matters because:

- Disaster response plans assume road networks remain functional; they rarely do
- Rural and mountain communities depend on single critical routes that have no viable detours
- Emergency services need to know where redundancy is genuinely absent versus merely reduced
- FEMA disaster declarations intersect with network topology in ways that aren't visible from map inspection alone

Gravel produces quantitative fragility scores that make these vulnerabilities comparable across counties, states, and regions.

## Users and Use Cases

### Primary users
- **Disaster sociology researchers** — studying how infrastructure failure correlates with FEMA disaster outcomes
- **Transportation planners** — identifying critical links that warrant redundancy investment
- **Emergency management** — pre-positioning resources where isolation risk is highest
- **Civil engineers** — bridge and road criticality analysis beyond traditional ADT-based methods

### Primary use cases

1. **Rank regions by vulnerability** — produce a fragility score for every county in a state/nation and rank them
2. **Scenario analysis** — given a hazard footprint (flood, wildfire, landslide), measure its impact on connectivity
3. **Progressive failure simulation** — degrade edges one at a time, plot the resulting isolation curve
4. **Inter-regional connectivity** — quantify how dependent one county is on another's roads
5. **Directional analysis** — reveal asymmetric vulnerability (e.g., a coastal town's evacuation routes north are fine but east is fragile)

## Architecture Overview

### Sub-library structure

Gravel v2.1 organizes code into six sub-libraries with a strict dependency DAG:

```
gravel-core      → (nothing)
gravel-ch        → gravel-core
gravel-simplify  → gravel-core, gravel-ch
gravel-fragility → gravel-core, gravel-ch, gravel-simplify
gravel-geo       → gravel-core, gravel-simplify
gravel-us        → gravel-geo
```

External dependencies are isolated:

| Dependency | Confined to | Optional |
|-----------|-------------|----------|
| libosmium | gravel-geo | Yes (GRAVEL_USE_OSMIUM) |
| Eigen + Spectra | gravel-fragility | No (always built) |
| nlohmann/json | gravel-geo, gravel-fragility | No |
| Apache Arrow | gravel-fragility (output) | Yes (GRAVEL_USE_ARROW) |

Consumers link only what they need. A tool that only does routing (no fragility) doesn't pull in Eigen/Spectra.

### Core data model

- **`ArrayGraph`** — structure-of-arrays CSR representation for cache efficiency
- **`ContractionResult`** — compiled contraction hierarchy for O(log n) shortest-path queries
- **`RegionAssignment`** — per-node region index (e.g., which county each node belongs to)
- **`IncrementalSSSP`** — reverse-incremental shortest-path engine for edge-removal analysis

### Analysis pipeline

```
OSM PBF ──▶ ArrayGraph ──▶ CH ──┬──▶ route queries (milliseconds)
                                │
                                ├──▶ location_fragility  (2s on 200K nodes)
                                │
                                ├──▶ county_fragility    (composite index)
                                │
                                └──▶ scenario_fragility  (hazard footprint)

County boundaries ──▶ RegionAssignment ──┬──▶ border_edges
                                         │
                                         ├──▶ boundary_nodes (protection)
                                         │
                                         └──▶ coarsen_graph (meta-graph)
```

## Functional Requirements

### FR-1: Graph Loading
- **FR-1.1** Load OSM PBF files with speed profiles (`load_osm_graph`)
- **FR-1.2** Load CSV edge lists with optional coordinates
- **FR-1.3** Build graphs from programmatic edge lists
- **FR-1.4** Serialize/deserialize graphs to binary format

### FR-2: Routing
- **FR-2.1** Shortest-path queries via contraction hierarchy (`CHQuery`)
- **FR-2.2** Bidirectional Dijkstra for verification
- **FR-2.3** Distance matrices with OpenMP parallelization
- **FR-2.4** Blocked-edge queries (`BlockedCHQuery`) for scenario analysis

### FR-3: Fragility Analysis
- **FR-3.1** Per-edge replacement-path ratios (`route_fragility`)
- **FR-3.2** Location-based isolation risk (`location_fragility`) with Monte Carlo/Greedy strategies
- **FR-3.3** County-level composite index (`county_fragility_index`)
- **FR-3.4** Scenario analysis with hazard footprints (`scenario_fragility`)
- **FR-3.5** Progressive elimination with degradation curves (`progressive_fragility`)
- **FR-3.6** Ensemble and uncertainty quantification

### FR-4: Geographic Analysis
- **FR-4.1** Point-in-polygon node assignment (`assign_nodes_to_regions`)
- **FR-4.2** GeoJSON boundary loading with coordinate swap
- **FR-4.3** Border edge summarization (`summarize_border_edges`)
- **FR-4.4** Graph coarsening (`coarsen_graph`)
- **FR-4.5** Boundary-aware simplification (preserves inter-regional nodes)
- **FR-4.6** Binary serialization of region assignments

### FR-5: US-Specific Support
- **FR-5.1** TIGER/Line loaders for counties, states, CBSAs, places, urban areas
- **FR-5.2** FIPS crosswalk (county→state, county→CBSA)
- **FR-5.3** Typed wrappers (`CountyAssignment`, `CBSAAssignment`)

### FR-6: Python Bindings
- **FR-6.1** Full API exposure via pybind11
- **FR-6.2** NumPy-compatible construction (edge lists as arrays)
- **FR-6.3** Optional OSM loading (graceful degradation if not built)

## Non-Functional Requirements

### Performance

| Target | Scale | Measured |
|--------|-------|----------|
| CH build | 200K nodes | 0.7s (M1 Mac, release) |
| Location fragility | 200K nodes, MC=20 | 2.1s |
| County fragility | 200K nodes, 20 OD pairs | 0.7s |
| National pipeline | 3,221 US counties | 3.1 hours |

### Quality
- **200+ unit tests** via Catch2 (C++) — every public function covered
- **Real-world validation** — Swain County OSM data as regression test
- **Spectral validation** — CH results cross-checked against Dijkstra
- **No memory leaks** — verified with ASan builds

### Portability
- Linux (x86_64, aarch64), macOS (x86_64, arm64), Windows (x86_64)
- C++20 compiler required
- Python 3.10+ for bindings
- CMake 3.20+

### Documentation
- Every public function has a Doxygen-style comment
- `REFERENCE.md` — complete API reference (1-for-1 with headers)
- PRD (this document) — architecture and requirements
- `examples/` — runnable tutorials in Python and C++
- Sphinx-generated API docs on GitHub Pages

## Key Design Decisions

### DD-1: Reverse-incremental SSSP over forward approach
For edge-removal analysis, we block all candidate edges first, run one blocked Dijkstra, then incrementally restore edges with bounded propagation. This is counterintuitive (most tools remove edges one at a time) but gives tight bounds and enables early termination.

### DD-2: Simplify before analyze
Degree-2 contraction reduces 200K-node county graphs to ~14K nodes with zero loss of shortest-path information. All analysis runs on the simplified graph; results map back to original node IDs via stored mapping.

### DD-3: Sample-based scoring
Location fragility scores use 200 target nodes (not all nodes) for distance inflation measurement. This caps per-trial cost at O(k) where k is sample count, independent of graph size. Accuracy is validated against full-node scoring on test graphs.

### DD-4: Composite score formula
```
isolation_risk = 0.5 * disconnected_fraction
               + 0.3 * normalized_distance_inflation
               + 0.2 * coverage_gap
```
Weights chosen empirically to rank Swain County and Bryson City as intuitively "more fragile" than Asheville. Formula is a single source of truth in `composite_formula.h`.

### DD-5: Graph coarsening for inter-county
For inter-county analysis, we coarsen the graph (one node per county) rather than running pairwise analysis on the full graph. This reduces a national matrix from O(3200²) expensive queries to O(3200) coarsening + O(adjacent pairs) cheap queries on a tiny graph.

## Version History

### v2.1 (April 2026) — Current
- **Major rewrite** of `location_fragility` using Dijkstra + IncrementalSSSP (~400x speedup)
- Sub-library architecture (6 CMake targets with enforced dependency DAG)
- New infrastructure: `EdgeSampler`, `IncrementalSSSP`, `RegionAssignment`, boundary-aware simplification
- New features: border edge summarization, graph coarsening, FIPS crosswalk, scenario fragility fast path
- Python API cleanup, region serialization, TIGER loaders
- National US county fragility pipeline (3,221 counties in ~3 hours)

### v2.0
- Progressive elimination fragility with Monte Carlo / Greedy strategies
- `AnalysisContext` performance cache
- Scenario fragility (hazard footprint intersection)
- Edge confidence scoring
- Tiled fragility analysis

### v1.0
- Initial release: routing, CH, route fragility, county fragility index

## Future Work

### Short term
- Inter-county fragility matrix for all US counties
- Choropleth visualization tooling
- CBSA / state-level aggregation helpers

### Medium term
- Temporal fragility (how networks degrade over construction schedules)
- Multi-modal integration (transit + walking)
- Stochastic edge failure modeling (probabilistic closure risk)

### Long term
- International road network support (non-TIGER boundaries)
- Real-time integration with traffic incident data
- ML-assisted edge importance ranking

## Non-Goals

- Gravel is not a turn-by-turn navigation library. Use OSRM or GraphHopper for that.
- Gravel is not a transit planner. Use OpenTripPlanner for GTFS/multi-modal.
- Gravel does not handle dynamic graphs. All CH operations assume a static edge set.