Skip to main content

Crate vulture

Crate vulture 

Source
Expand description

An implementation of RAPTOR (Delling, Pajor, Werneck): given a public transit network, find all Pareto-optimal journeys between two stops, trading fewer transfers against earlier arrival.

§Quick start

The gtfs adapter implements Timetable over a parsed GTFS feed.

use gtfs_structures::Gtfs;
use jiff::civil::date;
use vulture::{SecondOfDay, Timetable};
use vulture::gtfs::GtfsTimetable;

let gtfs = Gtfs::new("path/to/gtfs.zip")?;
// Pin the timetable to one service date; inactive trips are filtered out.
let tt = GtfsTimetable::new(&gtfs, date(2026, 5, 4))?;

// The algorithm takes dense u32 indices, not GTFS string IDs – resolve first.
let start = tt.stop_idx("dilshad_garden").expect("unknown stop");
let target = tt.stop_idx("vishwavidyalaya").expect("unknown stop");

let journeys = tt
    .query()
    .from(start)
    .to(target)
    .max_transfers(10)
    .depart_at(SecondOfDay::hms(9, 0, 0))
    .run();

for j in &journeys {
    println!("{} trip(s), arrives {}", j.plan.len(), j.arrival());
}

§Concepts

RAPTOR proceeds in rounds. Round k holds the earliest known arrival time at every stop reachable using at most k trips. Each round scans the routes through stops improved in the previous round and then relaxes walking footpaths to a fixed point. The output is a Pareto front: one Journey per trip count between zero and max_transfers, with strictly earlier arrivals as trip count rises.

The default routing is single-criterion: minimise arrival time, one journey per trip count. The criterion is abstracted by the Label trait; the default ArrivalTime carries a SecondOfDay. Multi-criterion routing plugs in via Timetable::query_with_label with one of the labels impls or a custom Label.

§Common patterns

§Custom backends

Implement the Timetable trait directly for non-GTFS data. Identifiers are dense u32 newtypes (StopIdx, RouteIdx, TripIdx); the adapter interns external IDs at construction. The trait carries one mandatory soundness contract, no-overtaking within a route, documented on Timetable. Footpaths returned by Timetable::get_footpaths_from are direct walks only; the algorithm chains them within a round, so transitive closure is not required. Adapters whose relation is closed can opt into single-pass relaxation via Timetable::footpaths_are_transitively_closed.

manual::SimpleTimetable is a hand-rolled in-memory adapter for tests and small fixtures.

Issue-by-issue audit against the paper: docs/soundness.md.

§Errors

Four patterns, picked per call:

§Cargo features

Modules§

ffi
Concrete-typed entry points for FFI bindings (PyO3, wasm-bindgen, and similar) that can’t easily monomorphise the generic Query<'tt, T, L, M> builder across the language boundary.
gtfs
Timetable implementation backed by a GTFS feed.
labels
Canned Label implementations.
manual
In-memory Timetable adapter you build by hand with .route(...) / .footpath(...) calls. Useful when your data isn’t from a parsed GTFS feed – for tests, custom data sources, and toy examples. Hand-rolled in-memory Timetable for tests, fixtures, and small synthetic networks.

Structs§

ArrivalTime
Single-criterion label = arrival time at a stop. Default L throughout the algorithm. Constructing from a SecondOfDay is direct; extracting back is arrival().
Duration
A length of time, in seconds. Distinct from SecondOfDay (a point in time) so the algorithm signatures can express which kind they expect: a walk-time offset, a transfer time, and a dwell time are all Duration; an arrival time and a departure time are both SecondOfDay.
Endpoints
A bag of (stop, walk-time-offset) pairs used as the origin or target of a query.
Journey
A journey found by the RAPTOR algorithm.
NeedsDeparture
Marker type: a Query that hasn’t yet had a departure configured. .run() is not callable in this state; call Query::depart_at (single departure) or Query::depart_in_window (range query) first.
PooledCache
Scoped handle from RaptorCachePool::checkout. Owns a RaptorCache for its lifetime and returns it to the pool on drop. Derefs to RaptorCache; pass &mut pooled_cache where &mut RaptorCache is wanted.
Query
Builder for a RAPTOR query. Constructed via Timetable::query.
RangeDeparture
Marker type: a range-query Query over a window of departure times. The supplied iterator is collected eagerly at builder time and normalised to a descending, deduplicated Vec<SecondOfDay> (the order rRAPTOR scans them in). .run() returns Vec<RangeJourney<L>>.
RangeJourney
One entry in a range-query profile: a departure time paired with the Journey it produces. Returned by Query::run / Query::run_with_cache on builders configured with Query::depart_in_window.
RaptorCache
Reusable scratch buffers for Query::run_with_cache.
RaptorCachePool
A Sync pool of RaptorCaches sized for one timetable. Each worker calls checkout() for the duration of one query.
RouteIdx
Dense index of a route within a Timetable. Indices are in 0..tt.n_routes().
SecondOfDay
A point in time, in seconds since midnight on the timetable’s service date. Wraps a u32 – the day is 86,400 seconds; u32 covers feed quirks like trips encoded past 24h with room to spare.
SingleDeparture
Marker type: a single-departure Query. .run() returns Vec<Journey<L>>.
StopIdx
Dense index of a stop within a Timetable. Indices are in 0..tt.n_stops().
TimedLeg
One transit leg of a Journey with reconstructed timing. Produced by Journey::with_timing.
Transfers
User-facing transfer cap. The algorithm explores rounds 0 through transfers inclusive, so Transfers(10) lets a journey involve up to 10 boardings. u8 is plenty – practical journey queries cap at single digits.
TripContext
Per-trip context passed to Label::extend_by_trip. Single-criterion labels read only arrival; multi-criterion impls (fare-aware, route-preference, transfer-penalty) draw on the remaining fields.
TripIdx
Dense index of a trip within a Timetable. Indices are in 0..n_trips.

Enums§

ParseSecondOfDayError
Errors produced when parsing a string into a SecondOfDay via FromStr.
TimingError
Failure modes for Journey::with_timing.
TryFromSignedDurationError
Errors produced when narrowing a jiff::SignedDuration into a vulture Duration.

Traits§

IntoEndpoints
Convert any of the natural query-endpoint inputs into an Endpoints value the algorithm can consume.
Label
A label attached to a (round, stop) cell during the RAPTOR scan.
Timetable
Models a route-based transit network for the RAPTOR algorithm.