logicaffeine_proof/
cubical.rs1use crate::progress_complex::gf2_rank_wide;
15use std::collections::{BTreeSet, HashMap};
16
17#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
20pub struct Cube {
21 pub corner: Vec<usize>,
22 pub dirs: Vec<usize>,
23}
24
25impl Cube {
26 pub fn dim(&self) -> usize {
27 self.dirs.len()
28 }
29
30 pub fn boundary(&self) -> Vec<Cube> {
33 let mut faces = Vec::with_capacity(2 * self.dirs.len());
34 for (idx, &a) in self.dirs.iter().enumerate() {
35 let mut sub = self.dirs.clone();
36 sub.remove(idx);
37 faces.push(Cube {
38 corner: self.corner.clone(),
39 dirs: sub.clone(),
40 });
41 let mut up = self.corner.clone();
42 up[a] += 1;
43 faces.push(Cube {
44 corner: up,
45 dirs: sub,
46 });
47 }
48 faces
49 }
50}
51
52pub struct CubicalComplex {
54 cells: Vec<BTreeSet<Cube>>,
55 dim: usize,
56}
57
58impl CubicalComplex {
59 pub fn from_top_cells(top: Vec<Cube>) -> Self {
61 let dim = top.iter().map(Cube::dim).max().unwrap_or(0);
62 let mut cells: Vec<BTreeSet<Cube>> = vec![BTreeSet::new(); dim + 1];
63 for c in top {
64 let d = c.dim();
65 cells[d].insert(c);
66 }
67 for k in (1..=dim).rev() {
68 let current: Vec<Cube> = cells[k].iter().cloned().collect();
69 for c in current {
70 for f in c.boundary() {
71 cells[f.dim()].insert(f);
72 }
73 }
74 }
75 CubicalComplex { cells, dim }
76 }
77
78 pub fn progress(lengths: &[usize], forbidden: &[Vec<usize>]) -> Self {
81 let d = lengths.len();
82 let forbidden: BTreeSet<Vec<usize>> = forbidden.iter().cloned().collect();
83 let mut top = Vec::new();
84 let mut idx = vec![0usize; d];
85 loop {
86 if !forbidden.contains(&idx) {
87 top.push(Cube {
88 corner: idx.clone(),
89 dirs: (0..d).collect(),
90 });
91 }
92 let mut a = 0;
93 while a < d {
94 idx[a] += 1;
95 if idx[a] < lengths[a] {
96 break;
97 }
98 idx[a] = 0;
99 a += 1;
100 }
101 if a == d {
102 break;
103 }
104 }
105 CubicalComplex::from_top_cells(top)
106 }
107
108 pub fn dim(&self) -> usize {
109 self.dim
110 }
111
112 pub fn num_cells(&self, k: usize) -> usize {
113 self.cells.get(k).map_or(0, BTreeSet::len)
114 }
115
116 fn boundary_rank(&self, k: usize) -> usize {
118 if k == 0 || k > self.dim {
119 return 0;
120 }
121 let lower: Vec<Cube> = self.cells[k - 1].iter().cloned().collect();
122 let ncols = lower.len();
123 if ncols == 0 {
124 return 0;
125 }
126 let lidx: HashMap<Cube, usize> =
127 lower.into_iter().enumerate().map(|(i, c)| (c, i)).collect();
128 let rows: Vec<Vec<u64>> = self.cells[k]
129 .iter()
130 .map(|c| {
131 let mut row = vec![0u64; ncols.div_ceil(64)];
132 for f in c.boundary() {
133 let idx = lidx[&f];
134 row[idx / 64] ^= 1u64 << (idx % 64);
135 }
136 row
137 })
138 .collect();
139 gf2_rank_wide(rows, ncols)
140 }
141
142 pub fn betti(&self) -> Vec<usize> {
144 let mut ranks = vec![0usize; self.dim + 2];
145 for k in 1..=self.dim {
146 ranks[k] = self.boundary_rank(k);
147 }
148 (0..=self.dim)
149 .map(|k| self.cells[k].len() - ranks[k] - ranks[k + 1])
150 .collect()
151 }
152
153 pub fn euler(&self) -> i64 {
155 (0..=self.dim)
156 .map(|k| {
157 let c = self.cells[k].len() as i64;
158 if k % 2 == 0 {
159 c
160 } else {
161 -c
162 }
163 })
164 .sum()
165 }
166}
167
168#[cfg(test)]
169#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/cubical/tests.rs"]
170mod tests;