Architecture

Crate hierarchy

Calculon is a Cargo workspace with six crates and a strict dependency hierarchy:

graph TD
    A[calculon-core] --> B[calculon-tiles]
    B --> C[calculon-costing]
    C --> D[calculon-route]
    C --> E[calculon-matrix]
    D --> F[calculon]
    E --> F

Graph tiles

Calculon reads Valhalla's binary graph tile format. Tiles are organized in a 3-level hierarchy:

GraphId

Every node, edge, and tile is addressed by a GraphId — a single u64 that packs:

• Level (3 bits) — hierarchy level 0-2
• Tile ID (22 bits) — tile index at that level
• ID (21 bits) — node or edge index within the tile

Binary tile parsing

Tile parsing uses unsafe for zero-copy pointer access. Every unsafe block is bounds-checked at the header level and documented. Tiles are memory-mapped (mmap) for fast loading and shared across threads.

Tile cache

GraphReader maintains an LRU cache of loaded tiles. The cache size is configurable via --cache-size (default: 200). Cache hits are lock-free reads; misses acquire a write lock to load from disk.

Bidirectional A*

The routing algorithm is a bidirectional A* search that expands from both origin and destination simultaneously.

flowchart LR
    O((Origin)) -->|Forward search| M{Meeting point}
    D((Destination)) -->|Reverse search| M
    M --> P[Path]

Two-pass strategy

1. First pass — default hierarchy limits (expand local streets briefly, then climb to highways)
2. Second pass — relaxed limits if no path found (handles cases where the optimal path stays on local roads)

Hierarchy expansion

The search uses hierarchy limits to prune the search space:

• Upward transitions are always allowed but increment a counter per source level
• Downward transitions are blocked once stop_expanding(dist) returns true
• Node-level pruning checks stop_expanding before expanding any edges at a node

Default limits for bidirectional search:

Connection and recosting

The search maintains up to 50 candidate connection points (where forward and reverse searches overlap), and tries the top 8 when building the final path. Each candidate is recosted by walking the full predecessor chain and recomputing accurate transition costs — this handles inaccuracies in the heuristic connection cost formula.

The termination condition uses a threshold delta of 420 seconds: once both searches have exceeded this threshold beyond the best known connection cost, the search stops.

DoubleBucketQueue

The priority queue for A* is a bucket-sorted structure optimized for routing workloads:

• Low-level buckets cover a contiguous cost range with O(1) insert
• Overflow bucket catches labels with cost beyond the current range
• Precomputed inv = 1.0 / bucket_size for fast index calculation
• Amortized O(1) pop (scans forward to next non-empty bucket)
• decrease() support for updating labels in-place

This is significantly faster than a binary heap for the narrow cost ranges typical in routing.

EdgeLabel

Each expanded edge in the search tree is stored as an EdgeLabel:

• Predecessor index (for path reconstruction)
• Cost and sort cost (cost + A* heuristic)
• Path distance (meters from origin)
• Edge attributes: shortcut, dest_only, toll, not_thru, deadend, internal
• Opposing edge indices (opp_index for traversal, opp_local_idx for per-pair data)
• Name consistency byte (corrected from end-node perspective)

Route reconstruction

After the search completes, form_path():

1. Walks the predecessor chain from the connection point backward to origin (forward tree)
2. Walks the predecessor chain from the connection point backward to destination (reverse tree)
3. Reconstructs the edge sequence with cumulative costs
4. Decodes edge shapes from tiles, trims first/last edges by snap fraction
5. Applies Douglas-Peucker simplification (unless generalize: 0)

CostMatrix

The matrix algorithm is a multi-origin, multi-destination expansion that uses the same graph infrastructure but with a different search strategy.

Search strategy

• Expands from all sources simultaneously (forward) and all targets simultaneously (reverse)
• Each source/target gets its own DoubleBucketQueue and edge label storage
• A ReachedMap tracks which sources/targets have reached each edge
• Checks for connections whenever forward and reverse searches meet at the same node
• Maximum iteration limit: 2,000,000

Shortcut edges

At level 1, the matrix uses shortcut edges — pre-computed edges that compress sequences of level-2 edges into a single traversal. When shortcuts are active:

• Regular (non-shortcut) edges at the same level are skipped to avoid expanding both
• This approximates Valhalla's superseded() mechanism
• Shortcut activation is controlled by stop_expanding() — requires both up_transition_count > max AND distance > expand_within_dist

Verbose mode

When verbose: true, extract_paths() walks the label predecessor chains for each found cell and reconstructs the edge sequence — the same paths the matrix search actually used, encoded as polyline6 shapes.

Costing

The DynamicCost trait defines the interface for cost models. Each model computes:

• Edge cost — time and cost to traverse an edge, based on speed, road class, surface, access
• Transition cost — cost at a node between two edges, based on turn type, stop impact, signals, name consistency
• Allowed — access and turn restriction filtering

Cost models use pre-computed lookup tables for O(1) factor lookups (speed, density, turn cost, highway/toll factors). See Costing Model for details.

HTTP server

The server crate uses Axum with:

• spawn_blocking for all CPU-bound routing/matrix work
• Shared state via Arc (GraphReader, costing defaults)
• Valhalla-compatible JSON request/response models
• Two-pass routing — first attempt with default hierarchy limits, second with relaxed limits if no path found
• Maneuver building that groups edges into turn-by-turn instructions
• Localized narrative via rust-i18n with 34 language files in locales/

See Narrative & i18n for details on maneuver types and supported languages.