clm-kernel 0.0.15

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Cellular sheaf coboundary operators, exact cohomology dimensions, and Dirichlet energy over integer stalks.

use std::collections::{HashMap, HashSet};
use std::fmt;

#[derive(Debug, Clone, PartialEq, Eq)]
/// Domain error returned when validating a cellular sheaf cover or applying a coboundary operator.
pub enum SheafCoboundaryError {
    InvalidVertex(String),
    InvalidEdge(String),
    InvalidTriangle(String),
    NonCommutingRestrictions(String),
    CochainLengthMismatch { expected: usize, actual: usize },
}

impl fmt::Display for SheafCoboundaryError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidVertex(id) => write!(f, "invalid vertex stalk '{id}'"),
            Self::InvalidEdge(id) => write!(f, "invalid edge restriction '{id}'"),
            Self::InvalidTriangle(id) => write!(f, "invalid 2-simplex restriction '{id}'"),
            Self::NonCommutingRestrictions(id) => write!(f, "non-commuting restrictions on '{id}'"),
            Self::CochainLengthMismatch { expected, actual } => write!(f, "expected length {expected}, got {actual}"),
        }
    }
}

impl std::error::Error for SheafCoboundaryError {}

#[derive(Debug, Clone, PartialEq, Eq)]
/// Zero-cell vertex stalk specification on a Cech nerve cover.
pub struct SheafVertexStalk { pub id: String, pub dimension: usize }

#[derive(Debug, Clone, PartialEq, Eq)]
/// Oriented one-cell edge restriction maps between source and target vertex stalks.
pub struct SheafEdgeRestriction {
    pub id: String, pub source: String, pub target: String, pub dimension: usize,
    pub source_map: Vec<Vec<i64>>, pub target_map: Vec<Vec<i64>>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
/// Two-simplex face restriction maps connecting three boundary edges into a triangle stalk.
pub struct SheafTriangleRestriction {
    pub id: String, pub vertices: [String; 3], pub dimension: usize,
    pub edge_ab: String, pub edge_bc: String, pub edge_ac: String,
    pub map_ab: Vec<Vec<i64>>, pub map_bc: Vec<Vec<i64>>, pub map_ac: Vec<Vec<i64>>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
/// Cellular sheaf specification on the Cech nerve 2-skeleton (C0, C1, C2).
pub struct CellularSheafCover {
    pub name: String,
    pub vertices: Vec<SheafVertexStalk>,
    pub edges: Vec<SheafEdgeRestriction>,
    pub triangles: Vec<SheafTriangleRestriction>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
/// Exact cochain dimensions, coboundary ranks, and cellular sheaf cohomology dimensions.
pub struct SheafCohomologyDimensions {
    pub dim_c0: usize, pub dim_c1: usize, pub dim_c2: usize,
    pub rank_delta0: usize, pub rank_delta1: usize, pub dim_ker_delta1: usize,
    pub dim_h0: usize, pub dim_h1: usize,
}

fn check_shape(mat: &[Vec<i64>], rows: usize, cols: usize) -> bool {
    mat.len() == rows && mat.iter().all(|r| r.len() == cols)
}

fn mat_mul(a: &[Vec<i64>], b: &[Vec<i64>]) -> Vec<Vec<i128>> {
    let cols = b.first().map_or(0, Vec::len);
    (0..a.len()).map(|i| (0..cols).map(|j| (0..b.len()).map(|k| i128::from(a[i][k]) * i128::from(b[k][j])).sum()).collect()).collect()
}

/// Assemble the integer Cech 0-coboundary matrix delta0 : C0 -> C1.
pub fn build_coboundary_0_matrix(cover: &CellularSheafCover) -> Result<Vec<Vec<i64>>, SheafCoboundaryError> {
    let (mut v_meta, mut dim_c0) = (HashMap::with_capacity(cover.vertices.len()), 0usize);
    for v in &cover.vertices {
        if v_meta.insert(v.id.as_str(), (dim_c0, v.dimension)).is_some() {
            return Err(SheafCoboundaryError::InvalidVertex(v.id.clone()));
        }
        dim_c0 += v.dimension;
    }
    let (mut seen, mut rows) = (HashSet::with_capacity(cover.edges.len()), Vec::new());
    for e in &cover.edges {
        let Some(&(so, sd)) = v_meta.get(e.source.as_str()) else { return Err(SheafCoboundaryError::InvalidEdge(e.id.clone())); };
        let Some(&(to, td)) = v_meta.get(e.target.as_str()) else { return Err(SheafCoboundaryError::InvalidEdge(e.id.clone())); };
        if !seen.insert(e.id.as_str()) || !check_shape(&e.source_map, e.dimension, sd) || !check_shape(&e.target_map, e.dimension, td) {
            return Err(SheafCoboundaryError::InvalidEdge(e.id.clone()));
        }
        for r in 0..e.dimension {
            let mut row = vec![0i64; dim_c0];
            for c in 0..sd { row[so + c] += e.source_map[r][c]; }
            for c in 0..td { row[to + c] -= e.target_map[r][c]; }
            rows.push(row);
        }
    }
    Ok(rows)
}

type EdgeInc<'a> = (usize, usize, i64, &'a [Vec<i64>], &'a [Vec<i64>]);

fn resolve_inc<'a>(e_meta: &'a HashMap<&'a str, (usize, &'a SheafEdgeRestriction)>, eid: &str, a: &str, b: &str, tid: &str) -> Result<EdgeInc<'a>, SheafCoboundaryError> {
    let &(off, ed) = e_meta.get(eid).ok_or_else(|| SheafCoboundaryError::InvalidTriangle(tid.to_string()))?;
    if ed.source == a && ed.target == b { Ok((off, ed.dimension, 1, &ed.source_map, &ed.target_map)) }
    else if ed.source == b && ed.target == a { Ok((off, ed.dimension, -1, &ed.target_map, &ed.source_map)) }
    else { Err(SheafCoboundaryError::InvalidTriangle(tid.to_string())) }
}

/// Assemble the integer Cech 1-coboundary matrix delta1 : C1 -> C2 and verify commuting face maps.
pub fn build_coboundary_1_matrix(cover: &CellularSheafCover) -> Result<Vec<Vec<i64>>, SheafCoboundaryError> {
    build_coboundary_0_matrix(cover)?;
    let (mut e_meta, mut dim_c1, mut rows) = (HashMap::with_capacity(cover.edges.len()), 0usize, Vec::new());
    for e in &cover.edges { e_meta.insert(e.id.as_str(), (dim_c1, e)); dim_c1 += e.dimension; }
    for tri in &cover.triangles {
        let [u, v, w] = &tri.vertices;
        if u == v || v == w || u == w { return Err(SheafCoboundaryError::InvalidTriangle(tri.id.clone())); }
        let (ab, bc, ac) = (resolve_inc(&e_meta, &tri.edge_ab, u, v, &tri.id)?, resolve_inc(&e_meta, &tri.edge_bc, v, w, &tri.id)?, resolve_inc(&e_meta, &tri.edge_ac, u, w, &tri.id)?);
        if !check_shape(&tri.map_ab, tri.dimension, ab.1) || !check_shape(&tri.map_bc, tri.dimension, bc.1) || !check_shape(&tri.map_ac, tri.dimension, ac.1) {
            return Err(SheafCoboundaryError::InvalidTriangle(tri.id.clone()));
        }
        if mat_mul(&tri.map_ab, ab.3) != mat_mul(&tri.map_ac, ac.3) || mat_mul(&tri.map_ab, ab.4) != mat_mul(&tri.map_bc, bc.3) || mat_mul(&tri.map_bc, bc.4) != mat_mul(&tri.map_ac, ac.4) {
            return Err(SheafCoboundaryError::NonCommutingRestrictions(tri.id.clone()));
        }
        for r in 0..tri.dimension {
            let mut row = vec![0i64; dim_c1];
            for (off, dim, sgn, fmap) in [(ab.0, ab.1, ab.2, &tri.map_ab), (bc.0, bc.1, bc.2, &tri.map_bc), (ac.0, ac.1, -ac.2, &tri.map_ac)] {
                for c in 0..dim { row[off + c] += sgn * fmap[r][c]; }
            }
            rows.push(row);
        }
    }
    Ok(rows)
}

fn gcd_i128(mut a: i128, mut b: i128) -> i128 {
    a = a.abs(); b = b.abs();
    while b != 0 { let t = a % b; a = b; b = t; }
    a
}

/// Compute exact rational rank of an integer matrix via GCD-reduced i128 Gaussian elimination.
pub fn compute_exact_rational_rank(matrix: &[Vec<i64>]) -> usize {
    let (rows, cols) = (matrix.len(), matrix.first().map_or(0, Vec::len));
    let mut work: Vec<Vec<i128>> = matrix.iter().map(|r| r.iter().map(|&v| i128::from(v)).collect()).collect();
    let mut rank = 0usize;
    for col in 0..cols {
        if rank == rows { break; }
        let Some(piv) = (rank..rows).find(|&r| work[r][col] != 0) else { continue; };
        work.swap(rank, piv);
        let piv_row = work[rank].clone();
        let pv = piv_row[col];
        for (r, row) in work.iter_mut().enumerate() {
            if r != rank && row[col] != 0 {
                let fac = row[col];
                for c in col..cols { row[c] = row[c] * pv - fac * piv_row[c]; }
                let g = row.iter().fold(0i128, |acc, &x| gcd_i128(acc, x));
                if g > 1 { for x in row.iter_mut() { *x /= g; } }
            }
        }
        rank += 1;
    }
    rank
}

/// Compute exact cellular sheaf cohomology dimensions (dim H0, dim H1) on a 2-skeleton cover.
pub fn compute_sheaf_cohomology_dims(cover: &CellularSheafCover) -> Result<SheafCohomologyDimensions, SheafCoboundaryError> {
    let (d0, d1) = (build_coboundary_0_matrix(cover)?, build_coboundary_1_matrix(cover)?);
    let (dim_c0, dim_c1, dim_c2) = (cover.vertices.iter().map(|v| v.dimension).sum(), cover.edges.iter().map(|e| e.dimension).sum(), cover.triangles.iter().map(|t| t.dimension).sum());
    let (r0, r1) = (compute_exact_rational_rank(&d0), compute_exact_rational_rank(&d1));
    Ok(SheafCohomologyDimensions { dim_c0, dim_c1, dim_c2, rank_delta0: r0, rank_delta1: r1, dim_ker_delta1: dim_c1 - r1, dim_h0: dim_c0 - r0, dim_h1: (dim_c1 - r1) - r0 })
}

/// Apply Cech 0-coboundary operator delta0 : C0 -> C1 to an integer vector-clock 0-cochain.
pub fn compute_coboundary_0(cover: &CellularSheafCover, cochain0: &[i64]) -> Result<Vec<i64>, SheafCoboundaryError> {
    let expected: usize = cover.vertices.iter().map(|v| v.dimension).sum();
    if cochain0.len() != expected { return Err(SheafCoboundaryError::CochainLengthMismatch { expected, actual: cochain0.len() }); }
    Ok(build_coboundary_0_matrix(cover)?.into_iter().map(|row| row.into_iter().zip(cochain0).map(|(a, &x)| a * x).sum()).collect())
}

/// Apply Cech 1-coboundary operator delta1 : C1 -> C2 to an integer 1-cochain.
pub fn compute_coboundary_1(cover: &CellularSheafCover, cochain1: &[i64]) -> Result<Vec<i64>, SheafCoboundaryError> {
    let expected: usize = cover.edges.iter().map(|e| e.dimension).sum();
    if cochain1.len() != expected { return Err(SheafCoboundaryError::CochainLengthMismatch { expected, actual: cochain1.len() }); }
    Ok(build_coboundary_1_matrix(cover)?.into_iter().map(|row| row.into_iter().zip(cochain1).map(|(a, &z)| a * z).sum()).collect())
}

/// Compute non-negative Hodge Sheaf Laplacian Dirichlet energy ||delta0 x||_2^2 over integer stalks.
pub fn compute_sheaf_laplacian_energy(cover: &CellularSheafCover, cochain0: &[i64]) -> Result<i128, SheafCoboundaryError> {
    Ok(compute_coboundary_0(cover, cochain0)?.into_iter().map(|v| i128::from(v) * i128::from(v)).sum())
}

#[cfg(test)]
mod tests {
    use super::*;

    fn v(id: &str, dimension: usize) -> SheafVertexStalk { SheafVertexStalk { id: id.into(), dimension } }
    fn e(id: &str, s: &str, t: &str, d: usize, sm: Vec<Vec<i64>>, tm: Vec<Vec<i64>>) -> SheafEdgeRestriction {
        SheafEdgeRestriction { id: id.into(), source: s.into(), target: t.into(), dimension: d, source_map: sm, target_map: tm }
    }
    fn tri(id: &str, vs: [&str; 3], d: usize, ab: &str, bc: &str, ac: &str, m: Vec<Vec<i64>>) -> SheafTriangleRestriction {
        SheafTriangleRestriction { id: id.into(), vertices: vs.map(Into::into), dimension: d, edge_ab: ab.into(), edge_bc: bc.into(), edge_ac: ac.into(), map_ab: m.clone(), map_bc: m.clone(), map_ac: m }
    }

    #[test]
    fn test_sheaf_polyglot_parity_corpus() {
        let (id2, sw2, u1) = (|| vec![vec![1, 0], vec![0, 1]], || vec![vec![0, 1], vec![1, 0]], || vec![vec![1]]);
        let tree_surj = CellularSheafCover { name: "tree_surjective_vector_clock".into(), vertices: vec![v("v0", 2), v("v1", 2), v("v2", 2)], edges: vec![e("e01", "v0", "v1", 2, id2(), id2()), e("e12", "v1", "v2", 2, id2(), id2())], triangles: vec![] };
        let ds = compute_sheaf_cohomology_dims(&tree_surj).unwrap();
        assert_eq!((ds.dim_h0, ds.dim_h1), (2, 0));
        assert_eq!(compute_sheaf_laplacian_energy(&tree_surj, &[4, -1, 4, -1, 4, -1]).unwrap(), 0);
        assert_eq!(compute_coboundary_0(&tree_surj, &[3, 1, 0, -2, -1, 4]).unwrap(), vec![3, 3, 1, -6]);
        assert_eq!(compute_sheaf_laplacian_energy(&tree_surj, &[3, 1, 0, -2, -1, 4]).unwrap(), 55);
        let proj = || vec![vec![1], vec![0]];
        let tree_drop = CellularSheafCover { name: "tree_rank_drop_obstruction".into(), vertices: vec![v("v0", 1), v("v1", 1), v("v2", 1)], edges: vec![e("e01", "v0", "v1", 2, proj(), proj()), e("e12", "v1", "v2", 2, proj(), proj())], triangles: vec![] };
        let dd = compute_sheaf_cohomology_dims(&tree_drop).unwrap();
        assert_eq!((dd.dim_h0, dd.dim_h1), (1, 2));
        assert_eq!(compute_coboundary_0(&tree_drop, &[4, 1, -2]).unwrap(), vec![3, 0, 3, 0]);
        assert_eq!(compute_sheaf_laplacian_energy(&tree_drop, &[4, 1, -2]).unwrap(), 18);
        let ring3 = CellularSheafCover { name: "unfilled_3_ring_cycle".into(), vertices: vec![v("u0", 1), v("u1", 1), v("u2", 1)], edges: vec![e("e01", "u0", "u1", 1, u1(), u1()), e("e12", "u1", "u2", 1, u1(), u1()), e("e20", "u2", "u0", 1, u1(), u1())], triangles: vec![] };
        let dr = compute_sheaf_cohomology_dims(&ring3).unwrap();
        assert_eq!((dr.dim_h0, dr.dim_h1), (1, 1));
        assert_eq!(compute_coboundary_0(&ring3, &[3, 1, 0]).unwrap(), vec![2, 1, -3]);
        assert_eq!(compute_sheaf_laplacian_energy(&ring3, &[3, 1, 0]).unwrap(), 14);
        assert_eq!(compute_sheaf_laplacian_energy(&ring3, &[4, 4, 4]).unwrap(), 0);
        let filled = CellularSheafCover { name: "filled_2_simplex_triangle".into(), vertices: vec![v("u0", 1), v("u1", 1), v("u2", 1)], edges: vec![e("e01", "u0", "u1", 1, u1(), u1()), e("e12", "u1", "u2", 1, u1(), u1()), e("e02", "u0", "u2", 1, u1(), u1())], triangles: vec![tri("t012", ["u0", "u1", "u2"], 1, "e01", "e12", "e02", u1())] };
        let df = compute_sheaf_cohomology_dims(&filled).unwrap();
        assert_eq!((df.dim_h0, df.dim_h1), (1, 0));
        let c0f = compute_coboundary_0(&filled, &[2, -1, 5]).unwrap();
        assert_eq!(c0f, vec![3, -6, -3]);
        assert_eq!(compute_coboundary_1(&filled, &c0f).unwrap(), vec![0]);
        assert_eq!(compute_coboundary_1(&filled, &[1, 1, 1]).unwrap(), vec![1]);
        assert_eq!(compute_sheaf_laplacian_energy(&filled, &[2, -1, 5]).unwrap(), 54);
        let twisted = CellularSheafCover { name: "vector_clock_twisted_2_simplex".into(), vertices: vec![v("p0", 2), v("p1", 2), v("p2", 2)], edges: vec![e("e01", "p0", "p1", 2, id2(), sw2()), e("e12", "p1", "p2", 2, sw2(), id2()), e("e20", "p2", "p0", 2, id2(), id2())], triangles: vec![tri("tri_p012", ["p0", "p1", "p2"], 2, "e01", "e12", "e20", id2())] };
        let dt = compute_sheaf_cohomology_dims(&twisted).unwrap();
        assert_eq!((dt.dim_h0, dt.dim_h1), (2, 0));
        let c0t = compute_coboundary_0(&twisted, &[5, -3, 2, 7, -4, 1]).unwrap();
        assert_eq!(c0t, vec![-2, -5, 11, 1, -9, 4]);
        assert_eq!(compute_coboundary_1(&twisted, &c0t).unwrap(), vec![0, 0]);
        assert_eq!(compute_sheaf_laplacian_energy(&twisted, &[5, -3, 2, 7, -4, 1]).unwrap(), 248);
        let mut broken = filled.clone();
        broken.triangles[0].map_ac = vec![vec![2]];
        assert_eq!(compute_sheaf_cohomology_dims(&broken), Err(SheafCoboundaryError::NonCommutingRestrictions("t012".into())));
    }
}