solverforge-maps

Generic map and routing utilities for Vehicle Routing Problems (VRP) and similar optimization problems.

Features

OSM Road Network: Download and cache OpenStreetMap road data via Overpass API
K-D Tree Spatial Indexing: Nearest-node and nearest-segment snapping on the road network
Shortest Path Routing: Dijkstra-style shortest paths for time and distance objectives
Travel Time Matrix: Compute all-pairs travel times with parallel computation
Route Geometry: Node-snapped and edge-snapped route geometries with Douglas-Peucker simplification
Polyline Encoding: Google Polyline Algorithm for efficient route transmission
Input Validation: Fail-fast coordinate and bounding box validation
Cache Management: In-memory and file-based caching with inspection and eviction
Graph Analysis: Connectivity analysis for debugging routing failures
Zero-Erasure Design: No Arc, no Box<dyn>, concrete types throughout

Installation

[dependencies]
solverforge-maps = "2.1"
tokio = { version = "1", features = ["full"] }

Quick Start

use solverforge_maps::{BoundingBox, Coord, NetworkConfig, RoadNetwork, RoutingResult};

#[tokio::main]
async fn main() -> RoutingResult<()> {
    let locations = vec![
        Coord::try_new(39.95, -75.16)?,
        Coord::try_new(39.96, -75.17)?,
    ];

    let bbox = BoundingBox::from_coords(&locations).expand_for_routing(&locations);
    let config = NetworkConfig::default();

    let network = RoadNetwork::load_or_fetch(&bbox, &config, None).await?;
    let matrix = network.compute_matrix(&locations, None).await;
    let route = network.route(locations[0], locations[1])?; // snaps both points to nearest nodes

    println!("Matrix size: {}", matrix.size());
    println!("Route duration: {} seconds", route.duration_seconds);
    Ok(())
}

API Reference

Coord

Geographic coordinate with latitude and longitude. Validates input on construction.

use solverforge_maps::{Coord, CoordError};

// Use try_new for external or user-provided input
let coord = Coord::try_new(39.95, -75.16)?;

// Fallible construction
let coord: Result<Coord, CoordError> = Coord::try_new(91.0, -75.16);
assert!(matches!(coord, Err(CoordError::LatOutOfRange { .. })));

// Coord::new is still fine for trusted literals that are guaranteed valid
let trusted_coord = Coord::new(39.95, -75.16);

// Distance calculation
let other = Coord::try_new(39.96, -75.17)?;
let distance_meters = coord.distance_to(other);

// Tuple conversion
let from_tuple: Result<Coord, CoordError> = (39.95, -75.16).try_into();
let to_tuple: (f64, f64) = coord.into();

CoordError

pub enum CoordError {
    LatOutOfRange { value: f64 },   // lat < -90 or > 90
    LngOutOfRange { value: f64 },   // lng < -180 or > 180
    LatNaN,
    LngNaN,
    LatInfinite { value: f64 },
    LngInfinite { value: f64 },
}

BoundingBox

Rectangular geographic region. Validates that min < max on construction.

use solverforge_maps::{BoundingBox, BBoxError, Coord};

// Use try_new when bounds come from external input
let bbox = BoundingBox::try_new(39.9, -75.2, 40.0, -75.1)?;

// Fallible construction
let bbox: Result<BoundingBox, BBoxError> = BoundingBox::try_new(40.0, -75.2, 39.9, -75.1);
assert!(matches!(bbox, Err(BBoxError::MinLatGreaterThanMax { .. })));

// From coordinates
let locations = vec![
    Coord::try_new(39.95, -75.16)?,
    Coord::try_new(39.96, -75.17)?,
];
let bbox = BoundingBox::from_coords(&locations);

// Expansion methods
let expanded = bbox.expand(0.1);                      // Expand by ratio
let expanded = bbox.expand_meters(1000.0);            // Expand by meters
let expanded = bbox.expand_for_routing(&locations);   // Smart expansion (1.4x detour factor)

// Queries
let center: Coord = bbox.center();
let contains: bool = bbox.contains(Coord::try_new(39.95, -75.15)?);

BoundingBox::new remains appropriate when the bounds are compile-time literals or otherwise already validated before construction.

BBoxError

pub enum BBoxError {
    MinLatGreaterThanMax { min: f64, max: f64 },
    MinLngGreaterThanMax { min: f64, max: f64 },
    LatOutOfRange { value: f64 },
    LngOutOfRange { value: f64 },
    NaN { field: &'static str },
    Infinite { field: &'static str, value: f64 },
}

NetworkConfig

Configuration for network loading and routing.

use solverforge_maps::{NetworkConfig, SpeedProfile};
use std::time::Duration;

// Defaults
let config = NetworkConfig::default();

// Builder pattern
let config = NetworkConfig::new()
    .overpass_url("https://overpass-api.de/api/interpreter")
    .cache_dir("/tmp/osm_cache")
    .connect_timeout(Duration::from_secs(30))
    .read_timeout(Duration::from_secs(120))
    .speed_profile(SpeedProfile::default());

SpeedProfile

Speed profiles for different road types.

use solverforge_maps::SpeedProfile;

let profile = SpeedProfile::default();

// Get speed in meters per second (maxspeed tag, highway type)
let speed_mps = profile.speed_mps(None, "motorway");       // ~27.78 m/s (100 km/h default)
let speed_mps = profile.speed_mps(Some("50"), "motorway"); // ~13.89 m/s (50 km/h from tag)

Highway Type	Default Speed
motorway	100 km/h
trunk	80 km/h
primary	60 km/h
secondary	50 km/h
tertiary	40 km/h
residential	30 km/h
unclassified	30 km/h
service	20 km/h
living_street	10 km/h

RoadNetwork

Core routing engine built from OSM data.

Loading a Network

use solverforge_maps::{BoundingBox, NetworkConfig, RoadNetwork, NetworkRef};

let bbox = BoundingBox::try_new(39.9, -75.2, 40.0, -75.1)?;
let config = NetworkConfig::default();

// Load from cache or fetch from API (returns cached reference)
let network: NetworkRef = RoadNetwork::load_or_fetch(&bbox, &config, None).await?;

// Always fetch fresh (bypasses cache)
let network: RoadNetwork = RoadNetwork::fetch(&bbox, &config, None).await?;

NetworkRef is a zero-cost guard that provides access to the cached RoadNetwork. It implements Deref<Target = RoadNetwork> so all methods are available directly.

Routing

route and route_with snap both endpoints to the nearest graph nodes before searching. They currently call the shared astar implementation with a zero heuristic, so the public search behavior is equivalent to Dijkstra's algorithm. If you need geometry that starts and ends on the containing road segments rather than at snapped nodes, use snap_to_edge with route_edge_snapped.

use solverforge_maps::{Coord, Objective, RouteResult, RoutingError};

let from = Coord::try_new(39.95, -75.16)?;
let to = Coord::try_new(39.96, -75.17)?;

// Route by minimum travel time (default). Endpoints are snapped to nearest nodes.
let route: Result<RouteResult, RoutingError> = network.route(from, to);

// Route with specific objective. Public search still uses a zero heuristic today.
let route = network.route_with(from, to, Objective::Time)?;     // Minimize time
let route = network.route_with(from, to, Objective::Distance)?; // Minimize distance

// Access route data
println!("Duration: {} seconds", route.duration_seconds);
println!("Distance: {:.0} meters", route.distance_meters);
println!("Geometry: {} points", route.geometry.len());

// Simplify geometry for transmission (Douglas-Peucker algorithm)
let simplified = route.simplify(10.0);  // tolerance in meters

Edge-Snapped Routing

Use edge snapping when you want the returned geometry to begin and end on the nearest road segments instead of the nearest graph nodes.

use solverforge_maps::{Coord, RouteResult, RoutingError};

let from = Coord::try_new(39.95, -75.16)?;
let to = Coord::try_new(39.96, -75.17)?;

let from_edge = network.snap_to_edge(from)?;
let to_edge = network.snap_to_edge(to)?;
let route: Result<RouteResult, RoutingError> = network.route_edge_snapped(&from_edge, &to_edge);

Coordinate Snapping

use solverforge_maps::{Coord, SnappedCoord, RoutingError};

let coord = Coord::try_new(39.95, -75.16)?;

// Simple snap (returns None if network is empty)
let node = network.snap_to_road(coord);

// Detailed snap with distance information
let snapped: Result<SnappedCoord, RoutingError> = network.snap_to_road_detailed(coord);

if let Ok(snap) = snapped {
    println!("Original: {:?}", snap.original);
    println!("Snapped: {:?}", snap.snapped);
    println!("Snap distance: {:.1} meters", snap.snap_distance_m);
}

// Route between pre-snapped node locations (more efficient for repeated routing)
let from_snap = network.snap_to_road_detailed(from)?;
let to_snap = network.snap_to_road_detailed(to)?;
let route = network.route_snapped(&from_snap, &to_snap)?;

Network Statistics

let nodes: usize = network.node_count();
let edges: usize = network.edge_count();

// Connectivity analysis (useful for debugging routing failures)
let components: usize = network.strongly_connected_components();
let largest_fraction: f64 = network.largest_component_fraction();
let is_connected: bool = network.is_strongly_connected();

println!("Network has {} SCCs", components);
println!("Largest component contains {:.1}% of nodes", largest_fraction * 100.0);

TravelTimeMatrix

Travel time matrix with metadata and analysis methods.

use solverforge_maps::{Coord, TravelTimeMatrix, UNREACHABLE};

let locations = vec![
    Coord::try_new(39.95, -75.16)?,
    Coord::try_new(39.96, -75.17)?,
    Coord::try_new(39.94, -75.15)?,
];

// Compute matrix (async, parallel via rayon internally)
let matrix: TravelTimeMatrix = network.compute_matrix(&locations, None).await;

// Access travel times
let time: Option<i64> = matrix.get(0, 1);           // From location 0 to 1
let row: Option<&[i64]> = matrix.row(0);            // All times from location 0
let reachable: bool = matrix.is_reachable(0, 1);    // Check if pair is reachable

// Matrix metadata
let size: usize = matrix.size();                     // Number of locations
let locations: &[SnappedCoord] = matrix.locations(); // Snapped coordinates

// Statistics (excluding diagonal and unreachable pairs)
let min: Option<i64> = matrix.min();
let max: Option<i64> = matrix.max();
let mean: Option<f64> = matrix.mean();

// Reachability analysis
let ratio: f64 = matrix.reachability_ratio();                 // Fraction reachable
let unreachable: Vec<(usize, usize)> = matrix.unreachable_pairs();

// Raw data access
let data: &[i64] = matrix.as_slice();  // Row-major flat array

The constant UNREACHABLE (i64::MAX) indicates pairs with no path.

Route Geometries

Compute geometries for all location pairs.

use solverforge_maps::Coord;
use std::collections::HashMap;

let locations = vec![
    Coord::new(39.95, -75.16),
    Coord::new(39.96, -75.17),
];

// Async computation
let geometries: HashMap<(usize, usize), Vec<Coord>> =
    network.compute_geometries(&locations, None).await;

// Access specific route geometry
if let Some(route_geom) = geometries.get(&(0, 1)) {
    println!("Route 0->1 has {} points", route_geom.len());
}

Cache Management

Inspect and manage the network cache.

use solverforge_maps::{RoadNetwork, CacheStats, BoundingBox};

// Get cache statistics
let stats: CacheStats = RoadNetwork::cache_stats().await;
println!("Cached networks: {}", stats.networks_cached);
println!("Total nodes: {}", stats.total_nodes);
println!("Total edges: {}", stats.total_edges);
println!("Memory: {} bytes", stats.memory_bytes);
println!("Load requests: {}", stats.load_requests);
println!("Memory hits: {}", stats.memory_hits);
println!("Disk hits: {}", stats.disk_hits);
println!("Network fetches: {}", stats.network_fetches);
println!("In-flight waits: {}", stats.in_flight_waits);

// List cached regions
let regions: Vec<BoundingBox> = RoadNetwork::cached_regions().await;

// Evict specific region
let bbox = BoundingBox::new(39.9, -75.2, 40.0, -75.1);
let evicted: bool = RoadNetwork::evict(&bbox).await;

// Clear entire cache
RoadNetwork::clear_cache().await;

CacheStats reports outcome-based cache metrics for load_or_fetch requests. The old aggregate hits / misses counters are intentionally not exposed because they did not distinguish memory, disk, network, or contention outcomes accurately. in_flight_waits is additive contention metadata, so a request that waits and then returns from the in-memory cache counts as both a memory hit and an in-flight wait.

Progress Reporting

Stream progress updates during long operations.

use solverforge_maps::{BoundingBox, NetworkConfig, RoadNetwork, RoutingProgress};
use tokio::sync::mpsc;

let (tx, mut rx) = mpsc::channel::<RoutingProgress>(100);

tokio::spawn(async move {
    while let Some(progress) = rx.recv().await {
        match progress {
            RoutingProgress::CheckingCache { percent } => {
                println!("[{:3}%] Checking cache...", percent);
            }
            RoutingProgress::DownloadingNetwork { percent, bytes } => {
                println!("[{:3}%] Downloading... {} bytes", percent, bytes);
            }
            RoutingProgress::BuildingGraph { percent } => {
                println!("[{:3}%] Building graph...", percent);
            }
            RoutingProgress::ComputingMatrix { percent, row, total } => {
                println!("[{:3}%] Computing matrix row {}/{}", percent, row, total);
            }
            RoutingProgress::Complete => {
                println!("[100%] Done");
            }
            _ => {}
        }
    }
});

let network = RoadNetwork::load_or_fetch(&bbox, &config, Some(&tx)).await?;
let matrix = network.compute_matrix(&locations, Some(&tx)).await;

RoutingProgress Variants

Variant	Description
`CheckingCache { percent }`	Checking in-memory and file caches
`DownloadingNetwork { percent, bytes }`	Downloading from Overpass API
`ParsingOsm { percent, nodes, edges }`	Parsing OSM JSON response
`BuildingGraph { percent }`	Building routing graph
`ComputingMatrix { percent, row, total }`	Computing travel time matrix
`ComputingGeometries { percent, pair, total }`	Computing route geometries
`Complete`	Operation finished

Polyline Encoding

Encode/decode route geometries using Google Polyline Algorithm.

use solverforge_maps::{encode_polyline, decode_polyline, Coord};

let coords = vec![
    Coord::new(38.5, -120.2),
    Coord::new(40.7, -120.95),
    Coord::new(43.252, -126.453),
];

let encoded: String = encode_polyline(&coords);
let decoded: Vec<Coord> = decode_polyline(&encoded);

Haversine Distance

Calculate great-circle distance between two coordinates.

use solverforge_maps::{haversine_distance, Coord};

let a = Coord::new(39.9526, -75.1635);
let b = Coord::new(39.9496, -75.1503);

let distance_meters = haversine_distance(a, b);

// Or use the method on Coord
let distance_meters = a.distance_to(b);

Error Handling

use solverforge_maps::{RoutingError, RoutingResult};

fn example() -> RoutingResult<()> {
    Ok(())
}

match network.route(from, to) {
    Ok(route) => { /* use route */ }
    Err(RoutingError::SnapFailed { coord, nearest_distance_m }) => {
        eprintln!("Could not snap {:?} to road network", coord);
        if let Some(dist) = nearest_distance_m {
            eprintln!("Nearest node was {} meters away", dist);
        }
    }
    Err(RoutingError::NoPath { from, to }) => {
        eprintln!("No path exists from {:?} to {:?}", from, to);
    }
    Err(RoutingError::InvalidCoordinate { error }) => {
        eprintln!("Invalid coordinate: {}", error);
    }
    Err(RoutingError::Network(msg)) => {
        eprintln!("Network error: {}", msg);
    }
    Err(RoutingError::Parse(msg)) => {
        eprintln!("Parse error: {}", msg);
    }
    Err(RoutingError::Io(e)) => {
        eprintln!("I/O error: {}", e);
    }
    Err(RoutingError::Cancelled) => {
        eprintln!("Operation cancelled");
    }
}

Types Summary

Structs

Type	Description
`Coord`	Geographic coordinate (lat, lng)
`BoundingBox`	Rectangular geographic region
`NetworkConfig`	Configuration for network loading
`SpeedProfile`	Road type speed mapping
`RoadNetwork`	Core routing graph
`NetworkRef`	Zero-cost reference to cached network
`RouteResult`	Single route with geometry
`SnappedCoord`	Coordinate snapped to road network
`TravelTimeMatrix`	N x N travel time matrix
`CacheStats`	Cache statistics and metrics
`EncodedSegment`	Pre-encoded route segment

Enums

Type	Description
`CoordError`	Coordinate validation errors
`BBoxError`	Bounding box validation errors
`RoutingError`	Routing operation errors
`RoutingProgress`	Progress reporting events
`Objective`	Routing objective (Time, Distance)

Constants

Constant	Value	Description
`UNREACHABLE`	`i64::MAX`	Sentinel for unreachable pairs

Caching

Three-tier caching for performance:

In-Memory Cache: Instant lookup for repeated requests
File Cache: Persists to cache_dir (default .osm_cache/)
Overpass API: Downloads fresh data on cache miss

# Clear file cache
rm -rf .osm_cache/

// Or programmatically
RoadNetwork::clear_cache().await;

Testing

Hermetic tests run by default:

cargo test

Live external-service integration tests are enabled explicitly for local runs:

make test-live

make test and make pre-release include the live suite locally. GitHub CI does not set SOLVERFORGE_RUN_LIVE_TESTS=1, so workflow runs stay self-contained and skip external-service checks by policy.

For manual network visualization against live Overpass data, run:

cargo run --example live_network_visualization

License

Apache-2.0

Name		Name	Last commit message	Last commit date
Latest commit History 62 Commits
.github		.github
examples		examples
src		src
tests		tests
.gitignore		.gitignore
.pre-commit-config.yaml		.pre-commit-config.yaml
CHANGELOG.md		CHANGELOG.md
Cargo.lock		Cargo.lock
Cargo.toml		Cargo.toml
LICENSE		LICENSE
Makefile		Makefile
README.md		README.md

Uh oh!

Folders and files

Latest commit

History

Repository files navigation

solverforge-maps

Features

Installation

Quick Start

API Reference

Coord

CoordError

BoundingBox

BBoxError

NetworkConfig

SpeedProfile

RoadNetwork

Loading a Network

Routing

Edge-Snapped Routing

Coordinate Snapping

Network Statistics

TravelTimeMatrix

Route Geometries

Cache Management

Progress Reporting

RoutingProgress Variants

Polyline Encoding

Haversine Distance

Error Handling

Types Summary

Structs

Enums

Constants

Caching

Testing

License

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases 4

Sponsor this project

Uh oh!

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

Packages