32_graph_path_counting/
32_graph_path_counting.rs

1//! # Example: Graph Path Counting
2//!
3//! Run: cargo run --example 32_graph_path_counting
4//!
5//! ## Problem
6//! Count the number of *walks* of a given length between nodes of a directed
7//! graph.
8//!
9//! ## Math idea
10//! If `A` is the adjacency matrix of a graph (`A[i, j] = 1` when there is an edge
11//! `i -> j`), then
12//! ```text
13//! (A^k)[i, j] = number of walks of length k from node i to node j.
14//! ```
15//! A *walk* may repeat nodes and edges; it is not the same as a *simple path*,
16//! which may not.
17//!
18//! ## Tensor representation
19//! The adjacency matrix is a 2-D `Tensor` of shape `[n, n]`. Each extra power is
20//! one `Tensor::matmul`; entries are read with `Tensor::get`.
21//!
22//! ## What this demonstrates
23//! - representing a graph as an adjacency `Tensor`;
24//! - matrix powers via repeated `Tensor::matmul`;
25//! - interpreting the entries of `A^k`.
26//!
27//! ## Expected output
28//! ```text
29//! A^2:
30//!   [0, 0, 1, 2]
31//!   [0, 0, 0, 1]
32//!   [0, 0, 0, 0]
33//!   [0, 0, 0, 0]
34//! A^3:
35//!   [0, 0, 0, 1]
36//!   [0, 0, 0, 0]
37//!   [0, 0, 0, 0]
38//!   [0, 0, 0, 0]
39//! walks of length 2 from 0 to 3 = 2
40//! walks of length 3 from 0 to 3 = 1
41//! Graph path counting: OK
42//! ```
43
44use matten::Tensor;
45
46/// Returns `a` raised to the `k`-th matrix power via repeated `matmul`.
47///
48/// `a` must be a square 2-D tensor and `k >= 1`.
49fn matrix_power(a: &Tensor, k: u32) -> Tensor {
50    let mut acc = a.clone();
51    for _ in 1..k {
52        acc = acc.matmul(a);
53    }
54    acc
55}
56
57/// Pretty-print a small integer-valued matrix.
58fn print_matrix(label: &str, m: &Tensor) {
59    let (rows, cols) = (m.shape()[0], m.shape()[1]);
60    println!("{label}:");
61    for i in 0..rows {
62        let row: Vec<String> = (0..cols)
63            .map(|j| format!("{:.0}", m.get(&[i, j]).expect("index in bounds")))
64            .collect();
65        println!("  [{}]", row.join(", "));
66    }
67}
68
69fn main() {
70    // Directed graph on 4 nodes:
71    //   0 -> 1, 0 -> 2, 1 -> 2, 1 -> 3, 2 -> 3
72    //
73    //        to: 0  1  2  3
74    //   from 0 [ 0  1  1  0 ]
75    //        1 [ 0  0  1  1 ]
76    //        2 [ 0  0  0  1 ]
77    //        3 [ 0  0  0  0 ]
78    let a = Tensor::new(
79        vec![
80            0.0, 1.0, 1.0, 0.0, //
81            0.0, 0.0, 1.0, 1.0, //
82            0.0, 0.0, 0.0, 1.0, //
83            0.0, 0.0, 0.0, 0.0, //
84        ],
85        &[4, 4],
86    );
87
88    let a2 = matrix_power(&a, 2);
89    let a3 = matrix_power(&a, 3);
90
91    print_matrix("A^2", &a2);
92    print_matrix("A^3", &a3);
93
94    // From node 0 to node 3: two length-2 walks (0->1->3, 0->2->3)
95    // and one length-3 walk (0->1->2->3).
96    let walks2 = a2.get(&[0, 3]).expect("index in bounds");
97    let walks3 = a3.get(&[0, 3]).expect("index in bounds");
98    println!("walks of length 2 from 0 to 3 = {walks2:.0}");
99    println!("walks of length 3 from 0 to 3 = {walks3:.0}");
100
101    assert_eq!(walks2, 2.0);
102    assert_eq!(walks3, 1.0);
103    println!("Graph path counting: OK");
104}
32_graph_path_counting/32_graph_path_counting.rs

32_graph_path_counting/
32_graph_path_counting.rs
