grid/
grid.rs

1//! A 3 x 3 street grid with one slow diagonal: shortest path, alternatives,
2//! and the Pareto front of (distance, penalty) paths.
3//!
4//! Run with `cargo run --example grid`.
5
6use osmnxr_core::graph::Graph;
7use osmnxr_core::routing::{csp_lagrangian, k_shortest_paths, pareto_paths, shortest_path_route};
8
9fn main() {
10    // Nodes 0..9 laid out as
11    //   0 - 1 - 2
12    //   |   |   |
13    //   3 - 4 - 5
14    //   |   |   |
15    //   6 - 7 - 8
16    // Every street is two-way, so it is two directed edges.
17    let mut from = Vec::new();
18    let mut to = Vec::new();
19    let mut length = Vec::new();
20    let mut penalty = Vec::new();
21    let mut street = |a: usize, b: usize, len: f64, pen: f64| {
22        for (u, v) in [(a, b), (b, a)] {
23            from.push(u);
24            to.push(v);
25            length.push(len);
26            penalty.push(pen);
27        }
28    };
29    for row in 0..3 {
30        for col in 0..3 {
31            let n = row * 3 + col;
32            if col < 2 {
33                street(n, n + 1, 100.0, 1.0);
34            }
35            if row < 2 {
36                street(n, n + 3, 100.0, 1.0);
37            }
38        }
39    }
40    // A shortcut across the middle: shorter, but it carries a heavy penalty
41    // (say, a steep hill or a toll).
42    street(0, 4, 120.0, 10.0);
43    street(4, 8, 120.0, 10.0);
44
45    let g = Graph::from_edges(&from, &to, &length, 9);
46
47    let (path, _slots, cost) = shortest_path_route(&g, 0, 8).unwrap();
48    println!("shortest by length: {path:?}  {cost} m");
49
50    let routes = k_shortest_paths(&g, &from, &to, &length, 0, 8, 3);
51    for (i, r) in routes.iter().enumerate() {
52        println!("alternative {}: {:?}  {} m", i + 1, r.path, r.cost);
53    }
54
55    println!("\nPareto front of (length, penalty):");
56    let front = pareto_paths(
57        &from,
58        &to,
59        &length,
60        &penalty,
61        9,
62        0,
63        8,
64        f64::INFINITY,
65        usize::MAX,
66    );
67    for r in &front {
68        println!("  {:?}  {} m  penalty {}", r.path, r.cost, r.resource);
69    }
70
71    let budget = 5.0;
72    let best = csp_lagrangian(&from, &to, &length, &penalty, 9, 0, 8, budget, 50).unwrap();
73    println!(
74        "\ncheapest path with penalty <= {budget}: {:?}  {} m  (lower bound {}, {} Dijkstra runs)",
75        best.path, best.cost, best.lower_bound, best.iterations
76    );
77}
grid/grid.rs

grid/
grid.rs
