open-standards/map/map-rs/crates/map-route/src/isochrone.rs

//! Isochrones — the region reachable from a source within a cost budget.
//!
//! A bounded Dijkstra expansion over the [`RouteGraph`]: accumulate the least
//! cost (travel time or distance) to each node, pruning anything beyond the
//! budget. The result is every reachable node with its cost — the input a client
//! turns into a "what's within 15 minutes" overlay (e.g. by covering the reached
//! coordinates into cells via `map-index`).

use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap};

use serde::{Deserialize, Serialize};

use crate::{Coordinate, RouteGraph};

/// Which edge weight the budget is measured in.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum Metric {
    /// Travel time, seconds (`edge.duration_secs`).
    Duration,
    /// Path length, meters (`edge.distance_m`).
    Distance,
}

/// A node reached within budget, and the least cost to get there.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct Reach {
    pub node: u64,
    pub coord: Coordinate,
    pub cost: f64,
}

/// The reachable set from a source within a budget.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct Isochrone {
    pub source: u64,
    pub metric: Metric,
    pub budget: f64,
    /// Reached nodes, ascending by cost (the source first, at cost 0).
    pub reached: Vec<Reach>,
}

impl Isochrone {
    /// The reachable coordinates (for covering into cells / drawing a hull).
    pub fn coords(&self) -> Vec<Coordinate> {
        self.reached.iter().map(|r| r.coord).collect()
    }
    /// The farthest reached cost (≤ budget), or 0 if only the source is reached.
    pub fn frontier_cost(&self) -> f64 {
        self.reached.last().map(|r| r.cost).unwrap_or(0.0)
    }
}

/// Compute the isochrone from `source` within `budget` of `metric`.
///
/// Returns an empty `reached` (not even the source) if `source` is not in the
/// graph; otherwise the source is always included at cost 0.
pub fn isochrone(graph: &RouteGraph, source: u64, budget: f64, metric: Metric) -> Isochrone {
    let mut out = Isochrone { source, metric, budget, reached: Vec::new() };
    if !graph.nodes.contains_key(&source) || budget < 0.0 {
        return out;
    }

    let weight = |e: &crate::RouteEdge| match metric {
        Metric::Duration => e.duration_secs,
        Metric::Distance => e.distance_m,
    };

    let mut best: BTreeMap<u64, f64> = BTreeMap::new();
    best.insert(source, 0.0);
    // Ordering key: cost scaled to an integer (ms / mm) for a min-heap.
    let mut heap: BinaryHeap<Reverse<(u64, u64)>> = BinaryHeap::new();
    heap.push(Reverse((0, source)));

    while let Some(Reverse((cost_key, u))) = heap.pop() {
        let cost_u = cost_key as f64 / 1000.0;
        if let Some(&b) = best.get(&u) {
            if cost_u > b + 1e-6 {
                continue; // stale heap entry
            }
        }
        if let Some(adj) = graph.adjacency.get(&u) {
            for &edge_idx in adj {
                let edge = &graph.edges[edge_idx];
                let nd = cost_u + weight(edge);
                if nd > budget + 1e-9 {
                    continue; // beyond the budget — prune
                }
                let cur = best.get(&edge.to).copied().unwrap_or(f64::INFINITY);
                if nd < cur {
                    best.insert(edge.to, nd);
                    heap.push(Reverse(((nd * 1000.0) as u64, edge.to)));
                }
            }
        }
    }

    let mut reached: Vec<Reach> = best
        .into_iter()
        .filter_map(|(node, cost)| {
            graph.nodes.get(&node).map(|n| Reach { node, coord: n.coord, cost })
        })
        .collect();
    reached.sort_by(|a, b| a.cost.partial_cmp(&b.cost).unwrap_or(std::cmp::Ordering::Equal));
    out.reached = reached;
    out
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Coordinate, RoadType, RouteEdge, RouteGraph, RouteNode};

    /// A chain 0→1→2→3, each edge 100 m / 60 s.
    fn chain() -> RouteGraph {
        let mut g = RouteGraph::new();
        for id in 0..4 {
            g.add_node(RouteNode { id, coord: Coordinate::new(0.0, id as f64 * 0.001) });
        }
        for from in 0..3u64 {
            g.add_edge(RouteEdge {
                from,
                to: from + 1,
                distance_m: 100.0,
                duration_secs: 60.0,
                road_type: RoadType::Residential,
            });
        }
        g
    }

    #[test]
    fn budget_bounds_the_reachable_set() {
        let g = chain();
        // 130 s budget → source + nodes 1 (60s) + 2 (120s); node 3 (180s) excluded.
        let iso = isochrone(&g, 0, 130.0, Metric::Duration);
        let ids: Vec<u64> = iso.reached.iter().map(|r| r.node).collect();
        assert_eq!(ids, vec![0, 1, 2]);
        assert_eq!(iso.reached[0].cost, 0.0); // source
        assert!((iso.frontier_cost() - 120.0).abs() < 1e-6);
    }

    #[test]
    fn distance_metric_and_full_reach() {
        let g = chain();
        let iso = isochrone(&g, 0, 1000.0, Metric::Distance);
        assert_eq!(iso.reached.len(), 4); // all reachable within 1 km
        assert!((iso.reached[3].cost - 300.0).abs() < 1e-6);
        assert_eq!(iso.coords().len(), 4);
    }

    #[test]
    fn source_only_and_missing_source() {
        let g = chain();
        // Zero budget → just the source.
        let iso = isochrone(&g, 0, 0.0, Metric::Duration);
        assert_eq!(iso.reached.len(), 1);
        assert_eq!(iso.reached[0].node, 0);
        // Missing source → empty.
        assert!(isochrone(&g, 99, 1000.0, Metric::Duration).reached.is_empty());
    }
}