Skip to content

v3.1.0

Latest

Choose a tag to compare

@trasch trasch released this 05 Nov 20:25
8e52051

Added

  • Multi-level Dijkstra routing (#413, #414) — graph.multiLevelIndex(levels:baseRows:baseColumns:) builds a reusable hierarchy of nested grid cells with sparse boundary overlays, and Graph.MultiLevelIndex.shortestPath(from:to:) answers repeated point-to-point queries with a level-aware bidirectional search. Works for directed and undirected graphs and every projection; queries with blockedNodes or edgeFilter fall back to plain Dijkstra. graph.shortestPathViaMultiLevel(from:to:) is a one-shot convenience.

    if let index = graph.multiLevelIndex(levels: 3, baseRows: 32, baseColumns: 32) {
        let path = index.shortestPath(from: start, to: end)
    }
  • New DocC guide: Graph routing algorithms and tuning — explains how the graph, direct searches, contraction, routing indexes, landmark routing and MLD fit together, with guidance on mode-specific graphs, constraints, custom costs and tuning parameters.

  • Real-world routing coverage and benchmarks — MLD is cross-checked against Dijkstra on Munich and Paris fixtures, including cycling-filtered Munich, and the benchmark suite reports index build and query times for Allgäu, Munich (undirected and directed) and Paris.