Struct TensorGraph 

pub struct TensorGraph { /* private fields */ }

A directed, weighted graph backed by a dense adjacency lattice.

Implementations

impl TensorGraph

pub fn new(n: usize) -> Self

Create an n-node graph with no edges.

Examples found in repository

examples/graph_paths.rs (line 12)

fn main() {
    // A small weighted DAG-ish graph.
    //   0 →1(4) →3(1)
    //   0 →2(1) →3(5)
    //   2 →1(2)
    let mut g = TensorGraph::new(4);
    g.add_edge(0, 1, 4.0);
    g.add_edge(0, 2, 1.0);
    g.add_edge(2, 1, 2.0);
    g.add_edge(1, 3, 1.0);
    g.add_edge(2, 3, 5.0);

    println!("{g:?}\n");

    println!("all-pairs shortest paths (tropical matrix powers):");
    for u in 0..g.nodes() {
        for v in 0..g.nodes() {
            match g.distance(u, v) {
                Some(d) => print!("  {u}->{v}:{d:>3}"),
                None => print!("  {u}->{v}:  ∞"),
            }
        }
        println!();
    }

    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
    println!(
        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
        g.distance(0, 3)
    );
    assert_eq!(g.distance(0, 3), Some(4.0));

    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
}

pub fn nodes(&self) -> usize

Number of nodes.

Examples found in repository

examples/graph_paths.rs (line 22)

fn main() {
    // A small weighted DAG-ish graph.
    //   0 →1(4) →3(1)
    //   0 →2(1) →3(5)
    //   2 →1(2)
    let mut g = TensorGraph::new(4);
    g.add_edge(0, 1, 4.0);
    g.add_edge(0, 2, 1.0);
    g.add_edge(2, 1, 2.0);
    g.add_edge(1, 3, 1.0);
    g.add_edge(2, 3, 5.0);

    println!("{g:?}\n");

    println!("all-pairs shortest paths (tropical matrix powers):");
    for u in 0..g.nodes() {
        for v in 0..g.nodes() {
            match g.distance(u, v) {
                Some(d) => print!("  {u}->{v}:{d:>3}"),
                None => print!("  {u}->{v}:  ∞"),
            }
        }
        println!();
    }

    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
    println!(
        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
        g.distance(0, 3)
    );
    assert_eq!(g.distance(0, 3), Some(4.0));

    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
}

pub fn edge_count(&self) -> usize

Number of edges added.

pub fn add_edge(&mut self, u: usize, v: usize, weight: f32)

Add a weighted directed edge u → v.

Examples found in repository

examples/graph_paths.rs (line 13)

fn main() {
    // A small weighted DAG-ish graph.
    //   0 →1(4) →3(1)
    //   0 →2(1) →3(5)
    //   2 →1(2)
    let mut g = TensorGraph::new(4);
    g.add_edge(0, 1, 4.0);
    g.add_edge(0, 2, 1.0);
    g.add_edge(2, 1, 2.0);
    g.add_edge(1, 3, 1.0);
    g.add_edge(2, 3, 5.0);

    println!("{g:?}\n");

    println!("all-pairs shortest paths (tropical matrix powers):");
    for u in 0..g.nodes() {
        for v in 0..g.nodes() {
            match g.distance(u, v) {
                Some(d) => print!("  {u}->{v}:{d:>3}"),
                None => print!("  {u}->{v}:  ∞"),
            }
        }
        println!();
    }

    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
    println!(
        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
        g.distance(0, 3)
    );
    assert_eq!(g.distance(0, 3), Some(4.0));

    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
}

pub fn add_edge_unweighted(&mut self, u: usize, v: usize)

Add an unweighted directed edge u → v (weight 1).

pub fn reachability(&self) -> PaddedTileLattice<f32>

The reflexive-transitive closure: reachable[u][v] is 1 iff v is reachable from u. Computed as boolean matrix powers.

pub fn reachable(&self, u: usize, v: usize) -> bool

True if v is reachable from u (including u == v).

Examples found in repository

examples/graph_paths.rs (line 39)

fn main() {
    // A small weighted DAG-ish graph.
    //   0 →1(4) →3(1)
    //   0 →2(1) →3(5)
    //   2 →1(2)
    let mut g = TensorGraph::new(4);
    g.add_edge(0, 1, 4.0);
    g.add_edge(0, 2, 1.0);
    g.add_edge(2, 1, 2.0);
    g.add_edge(1, 3, 1.0);
    g.add_edge(2, 3, 5.0);

    println!("{g:?}\n");

    println!("all-pairs shortest paths (tropical matrix powers):");
    for u in 0..g.nodes() {
        for v in 0..g.nodes() {
            match g.distance(u, v) {
                Some(d) => print!("  {u}->{v}:{d:>3}"),
                None => print!("  {u}->{v}:  ∞"),
            }
        }
        println!();
    }

    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
    println!(
        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
        g.distance(0, 3)
    );
    assert_eq!(g.distance(0, 3), Some(4.0));

    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
}

pub fn shortest_paths(&self) -> PaddedTileLattice<f32>

All-pairs shortest path distances, computed as tropical matrix powers. Unreachable pairs hold +∞.

pub fn distance(&self, u: usize, v: usize) -> Option<f32>

The shortest-path distance from u to v, or None if unreachable.

Examples found in repository

examples/graph_paths.rs (line 24)

fn main() {
    // A small weighted DAG-ish graph.
    //   0 →1(4) →3(1)
    //   0 →2(1) →3(5)
    //   2 →1(2)
    let mut g = TensorGraph::new(4);
    g.add_edge(0, 1, 4.0);
    g.add_edge(0, 2, 1.0);
    g.add_edge(2, 1, 2.0);
    g.add_edge(1, 3, 1.0);
    g.add_edge(2, 3, 5.0);

    println!("{g:?}\n");

    println!("all-pairs shortest paths (tropical matrix powers):");
    for u in 0..g.nodes() {
        for v in 0..g.nodes() {
            match g.distance(u, v) {
                Some(d) => print!("  {u}->{v}:{d:>3}"),
                None => print!("  {u}->{v}:  ∞"),
            }
        }
        println!();
    }

    // Best route 0 -> 3 is 0->2->1->3 = 1 + 2 + 1 = 4, beating 0->1->3 = 5.
    println!(
        "\nshortest 0 -> 3 = {:?}  (via 0->2->1->3)",
        g.distance(0, 3)
    );
    assert_eq!(g.distance(0, 3), Some(4.0));

    println!("reachable 0 -> 3? {}", g.reachable(0, 3));
    println!("reachable 3 -> 0? {}", g.reachable(3, 0));
    println!("\n✓ traversal computed as a handful of dense matmuls, no queue, no branches.");
}

pub fn walk_counts(&self, k: usize) -> PaddedTileLattice<f32>

The number of distinct walks of exactly k edges from u to v, as the k-th ordinary matrix power of the adjacency.

Trait Implementations

impl Clone for TensorGraph

fn clone(&self) -> TensorGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TensorGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.