use std::collections::{HashMap, HashSet};
use std::fmt;
#[derive(Debug, Clone, PartialEq, Eq)]
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)]
pub struct SheafVertexStalk { pub id: String, pub dimension: usize }
#[derive(Debug, Clone, PartialEq, Eq)]
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)]
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)]
pub struct CellularSheafCover {
pub name: String,
pub vertices: Vec<SheafVertexStalk>,
pub edges: Vec<SheafEdgeRestriction>,
pub triangles: Vec<SheafTriangleRestriction>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
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()
}
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())) }
}
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
}
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
}
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 })
}
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())
}
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())
}
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())));
}
}