hyperpaths-rs 0.2.0

Spiess-Florian optimal strategies transit assignment
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

use std::collections::HashMap;
use std::hint::black_box;

use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};

use hyperpaths_rs::testutil::{gen_grid_network, grid_full_od, grid_stops};
use hyperpaths_rs::{Graph, compute_sf, find_optimal_strategy};

fn bench_single_dest(c: &mut Criterion) {
    let sizes = [(8usize, 8usize), (16, 16), (32, 32)];

    let mut fos = c.benchmark_group("find_optimal_strategy");
    for &(rows, cols) in &sizes {
        let (links, nodes, dest, _) = gen_grid_network(rows, cols, 6.0, 3.0);
        let id = BenchmarkId::from_parameter(format!("{}x{}", rows, cols));
        fos.bench_function(id, |b| {
            b.iter(|| black_box(find_optimal_strategy(&links, &nodes, &dest)));
        });
    }
    fos.finish();

    let mut sf = c.benchmark_group("compute_sf");
    for &(rows, cols) in &sizes {
        let (links, nodes, dest, od) = gen_grid_network(rows, cols, 6.0, 3.0);
        let id = BenchmarkId::from_parameter(format!("{}x{}", rows, cols));
        sf.bench_function(id, |b| {
            b.iter(|| black_box(compute_sf(&links, &nodes, &dest, &od)));
        });
    }
    sf.finish();
}

fn bench_full_assignment(c: &mut Criterion) {
    let mut group = c.benchmark_group("full_assignment");
    for &(rows, cols) in &[(8usize, 8usize), (12, 12)] {
        let (links, nodes, _, _) = gen_grid_network(rows, cols, 6.0, 3.0);
        let stops = grid_stops(rows, cols);
        let od = grid_full_od(&stops);
        let size = format!("{}x{}", rows, cols);

        // old: compute_sf per destination, rebuilding the arena each time
        group.bench_function(BenchmarkId::new("compute_sf_per_dest", &size), |b| {
            b.iter(|| {
                for dest in &stops {
                    let mut col: HashMap<String, HashMap<String, f64>> = HashMap::new();
                    for o in &stops {
                        if o != dest {
                            col.insert(o.clone(), HashMap::from([(dest.clone(), 1.0)]));
                        }
                    }
                    black_box(compute_sf(&links, &nodes, dest, &col));
                }
            });
        });

        // new: Graph interned once, Workspace reused via solve_each (warm)
        let g = Graph::new(&links, &nodes);
        let mut w = g.new_workspace();
        group.bench_function(BenchmarkId::new("solve_each", &size), |b| {
            b.iter(|| {
                w.solve_each(&od, |res| {
                    black_box(res.link_vol);
                });
            });
        });
    }
    group.finish();
}

criterion_group!(benches, bench_single_dest, bench_full_assignment);
criterion_main!(benches);