trop/tri/kleene.tri

// ---
// tags: trop, trident
// crystal-type: circuit
// crystal-domain: comp
// ---

//  Kleene star (shortest-path closure) for tropical matrices.
//
//  Computes A* = I + A + A^2 + ... + A^(n-1) using the
//  Floyd-Warshall algorithm, which is exactly the Kleene star
//  in the (min, +) semiring. Runs in O(n^3).

module trop.kleene

use trop.element.{INF, Tropical, add, mul, is_inf, from_u32}
use trop.matrix.{MAX_N, TropMatrix, new, get}

/// Compute the Kleene star of a tropical matrix.
///
/// A*[i][j] is the shortest-path distance from i to j
/// in the weighted digraph represented by A.
///
/// Uses Floyd-Warshall: O(n^3) time, O(n^2) space.
pub fn kleene_star(a: TropMatrix) -> TropMatrix {
    let n: U32 = a.n

    // Initialize d = I (min) A: copy A, then merge diagonal with identity.
    let mut d: [U32; 4096] = [INF; 4096]
    for i in 0..64 {
        if i < n {
            for j in 0..64 {
                if j < n {
                    d[i * MAX_N + j] = a.data[i * MAX_N + j]
                }
            }
            // Merge with identity: diagonal entry = min(current, 0)
            let diag: U32 = i * MAX_N + i
            let cur: Tropical = from_u32(d[diag])
            let ident: Tropical = Tropical { val: 0 }
            d[diag] = add(cur, ident).val
        }
    }

    // Floyd-Warshall relaxation
    for k in 0..64 {
        if k < n {
            for i in 0..64 {
                if i < n {
                    let d_ik: Tropical = from_u32(d[i * MAX_N + k])
                    if is_inf(d_ik) == false {
                        for j in 0..64 {
                            if j < n {
                                let d_kj: Tropical = from_u32(d[k * MAX_N + j])
                                let candidate: Tropical = mul(d_ik, d_kj)
                                let idx: U32 = i * MAX_N + j
                                let current: Tropical = from_u32(d[idx])
                                d[idx] = add(current, candidate).val
                            }
                        }
                    }
                }
            }
        }
    }

    let mut result: TropMatrix = new(n)
    result.data = d
    result
}