graph_paths/
graph_paths.rs

1//! Shortest paths and reachability as matrix powers over a semiring.
2//!
3//! Run with `cargo run --release --example graph_paths`.
4
5use systile::prelude::*;
6
7fn main() {
8    // A small weighted DAG-ish graph.
9    //   0 →1(4) →3(1)
10    //   0 →2(1) →3(5)
11    //   2 →1(2)
12    let mut g = TensorGraph::new(4);
13    g.add_edge(0, 1, 4.0);
14    g.add_edge(0, 2, 1.0);
15    g.add_edge(2, 1, 2.0);
16    g.add_edge(1, 3, 1.0);
17    g.add_edge(2, 3, 5.0);
18
19    println!("{g:?}\n");
20
21    println!("all-pairs shortest paths (tropical matrix powers):");
22    for u in 0..g.nodes() {
23        for v in 0..g.nodes() {
24            match g.distance(u, v) {
25                Some(d) => print!("  {u}->{v}:{d:>3}"),
26                None => print!("  {u}->{v}:  ∞"),
27            }
28        }
29        println!();
30    }
31
32    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
33    println!(
34        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
35        g.distance(0, 3)
36    );
37    assert_eq!(g.distance(0, 3), Some(4.0));
38
39    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
40    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
41    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
42}
graph_paths/graph_paths.rs

graph_paths/
graph_paths.rs
