vulture 0.24.0

Rust implementation of RAPTOR (Round-bAsed Public Transit Routing)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Reusing scratch allocations across queries with [`RaptorCache`]
//! ([`RaptorCachePool`] is the `Sync` variant for thread pools).
//!
//! Server use-case: a single timetable is loaded once and many
//! queries hit it over the lifetime of the process. Each query
//! needs scratch buffers (label bags, marked-stop bitsets, route
//! queue, boarding tree). Allocating those fresh for every query is
//! wasted work; allocating one [`RaptorCache`] and finishing each
//! chain with `.run_with_cache(&mut cache)` reuses them.
//!
//! This example issues 50 queries with both shapes:
//!
//! - one-shot `.run()` (allocates internally, drops afterwards),
//! - `.run_with_cache(&mut cache)` (cache outlives the call).
//!
//! It asserts that the journeys returned are identical between
//! the two modes — the cache is purely an allocation-amortisation
//! detail, not a behaviour-changing feature. Run with
//! `cargo run --release --example cache_reuse`.

use vulture::manual::SimpleTimetable;
use vulture::{Duration, Journey, RaptorCache, SecondOfDay, Timetable};

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum S {
    A,
    B,
    C,
}

fn main() {
    let tt = SimpleTimetable::new()
        .route(
            "R_AB",
            &[S::A, S::B],
            &[(
                "T_AB",
                &[
                    (SecondOfDay(0), SecondOfDay(0)),
                    (SecondOfDay(60), SecondOfDay(60)),
                ],
            )],
        )
        .route(
            "R_BC",
            &[S::B, S::C],
            &[(
                "T_BC",
                &[
                    (SecondOfDay(120), SecondOfDay(120)),
                    (SecondOfDay(180), SecondOfDay(180)),
                ],
            )],
        );

    let a = tt.stop_idx_of(&S::A);
    let c = tt.stop_idx_of(&S::C);

    // Allocate a single cache sized for this timetable. Reuse it
    // across every query in this thread.
    let mut cache: RaptorCache<vulture::ArrivalTime> = RaptorCache::for_timetable(&tt);

    let n = 50usize;
    let mut one_shot_results: Vec<Vec<Journey<vulture::ArrivalTime>>> = Vec::with_capacity(n);
    let mut cached_results: Vec<Vec<Journey<vulture::ArrivalTime>>> = Vec::with_capacity(n);

    for _ in 0..n {
        // One-shot: allocates scratch internally, drops on return.
        let one_shot = tt
            .query()
            .from(&[(a, Duration::ZERO)])
            .to(&[(c, Duration::ZERO)])
            .max_transfers(2)
            .depart_at(SecondOfDay(0))
            .run();
        one_shot_results.push(one_shot);

        // Cached: scratch lives in `cache` across iterations.
        let cached = tt
            .query()
            .from(&[(a, Duration::ZERO)])
            .to(&[(c, Duration::ZERO)])
            .max_transfers(2)
            .depart_at(SecondOfDay(0))
            .run_with_cache(&mut cache);
        cached_results.push(cached);
    }

    println!(
        "Ran {} A→C queries, one-shot vs. cached: result-set sizes match = {}",
        n,
        one_shot_results
            .iter()
            .zip(cached_results.iter())
            .all(|(o, c)| o.len() == c.len()),
    );
    if let Some(first) = one_shot_results.first().and_then(|v| v.first()) {
        println!(
            "  example journey: A → C, arrives {}, plan {} legs",
            first.label.0,
            first.plan.len(),
        );
    }

    // Behaviour must be identical: the cache amortises allocation,
    // it doesn't change what the algorithm computes.
    assert_eq!(one_shot_results.len(), cached_results.len());
    for (one, cached) in one_shot_results.iter().zip(cached_results.iter()) {
        assert_eq!(one.len(), cached.len());
        for (a_j, b_j) in one.iter().zip(cached.iter()) {
            assert_eq!(a_j.origin, b_j.origin);
            assert_eq!(a_j.target, b_j.target);
            assert_eq!(a_j.label, b_j.label);
            assert_eq!(a_j.plan, b_j.plan);
        }
    }

    // Sanity-check the journey itself: A → C requires boarding R_AB
    // (A→B), then transferring to R_BC (B→C), arriving at 180.
    let final_journey = one_shot_results
        .last()
        .and_then(|v| v.first())
        .expect("expected at least one A→C journey");
    assert_eq!(final_journey.label.0.0, 180);
    assert_eq!(final_journey.plan.len(), 2);
}