use std::collections::{BTreeMap, BTreeSet};
use std::sync::Arc;
use super::classes_tests::relabel;
use super::presentation_tests::bound;
use super::*;
use crate::algebra::Algebra;
use crate::field::PrimeField;
fn f2() -> PrimeField {
PrimeField::new(2).unwrap()
}
fn invariant(algebra: &Arc<Algebra>) -> GentleDerivedInvariant {
GentlePresentation::new(algebra)
.unwrap()
.complete_invariant()
}
pub(super) fn aps_first() -> Arc<Algebra> {
bound(3, &[(0, 1), (0, 1), (1, 2), (1, 2)], &[(0, 2), (1, 3)])
}
pub(super) fn aps_second() -> Arc<Algebra> {
bound(
3,
&[(0, 1), (1, 2), (2, 0), (2, 0)],
&[(2, 0), (0, 1), (1, 3)],
)
}
#[test]
fn the_first_aps_pair_is_separated_by_the_gcd() {
let first = invariant(&aps_first());
let second = invariant(&aps_second());
assert_eq!(first.aag_function(), second.aag_function());
assert_eq!(first.aag_function().pairs(), [(2, 4)]);
assert_eq!(first.winding_class(), WindingClass::Gcd(0));
assert_eq!(second.winding_class(), WindingClass::Gcd(2));
assert_eq!(first.to_string(), "[(2, 4)], genus 1, gcd 0");
assert_eq!(second.to_string(), "[(2, 4)], genus 1, gcd 2");
}
#[test]
fn the_second_aps_pair_shares_the_invariant() {
let first = bound(
6,
&[
(4, 0),
(1, 4),
(5, 1),
(5, 3),
(3, 2),
(4, 3),
(2, 4),
(1, 0),
(0, 1),
],
&[(6, 5), (4, 6), (5, 4), (1, 0), (0, 8), (8, 7), (2, 1)],
);
let second = bound(
6,
&[
(0, 5),
(1, 0),
(4, 1),
(4, 3),
(1, 2),
(3, 5),
(2, 3),
(5, 2),
(0, 4),
],
&[(5, 7), (7, 6), (3, 5), (8, 2), (1, 8), (2, 1)],
);
let value = invariant(&first);
assert_eq!(value, invariant(&second));
assert_eq!(value.genus(), 1);
assert_eq!(value.winding_class(), WindingClass::Gcd(1));
let windings: BTreeSet<i64> = value
.aag_function()
.pairs()
.iter()
.map(|&(n, m)| n as i64 - m as i64)
.collect();
assert_eq!(windings, BTreeSet::from([-3, 0]));
}
#[test]
fn the_lekili_polishchuk_koszul_dual_has_gcd_zero() {
let dual = bound(
6,
&[
(0, 1),
(1, 2),
(0, 4),
(4, 2),
(3, 4),
(4, 5),
(3, 1),
(1, 5),
],
&[(0, 1), (2, 3), (4, 5), (6, 7)],
);
let value = invariant(&dual);
assert_eq!(value.aag_function().pairs(), [(2, 4), (2, 4)]);
assert_eq!(value.winding_class(), WindingClass::Gcd(0));
}
#[test]
fn genus_zero_reduces_to_the_aag_function() {
for vertices in 1..=4 {
for key in connected_gentle_keys(vertices) {
let presentation = GentlePresentation::new(&key.algebra(f2()).unwrap()).unwrap();
let value = presentation.complete_invariant();
assert_eq!(&presentation.aag_function(), value.aag_function());
assert_eq!(value.genus(), presentation.genus());
let planar = value.winding_class() == WindingClass::Planar;
assert_eq!(planar, value.genus() == 0, "{value}");
}
}
}
#[test]
fn relabeling_keeps_the_invariant() {
let mut state = 0x2545_f491_4f6c_dd1du64;
for key in connected_gentle_keys(4) {
let value = invariant(&key.algebra(f2()).unwrap());
if value.genus() == 0 {
continue;
}
for _ in 0..2 {
assert_eq!(invariant(&relabel(&key, &mut state)), value, "{key:?}");
}
}
}
#[test]
fn the_invariant_splits_seven_aag_groups_at_four_vertices() {
let mut groups: BTreeMap<AagFunction, BTreeSet<GentleDerivedInvariant>> = BTreeMap::new();
let mut classes: BTreeMap<String, usize> = BTreeMap::new();
let keys = connected_gentle_keys(4);
for key in &keys {
let value = invariant(&key.algebra(f2()).unwrap());
let name = value.winding_class().to_string();
let kind = name.split(' ').next().unwrap().to_string();
*classes.entry(kind).or_default() += 1;
let group = groups.entry(value.aag_function().clone()).or_default();
group.insert(value);
}
let split: Vec<usize> = groups
.values()
.map(BTreeSet::len)
.filter(|&len| len > 1)
.collect();
let total: usize = groups.values().map(BTreeSet::len).sum();
assert_eq!(keys.len(), 894);
assert_eq!(groups.len(), 91);
assert_eq!(split, [3, 2, 2, 2, 2, 3, 4]);
assert_eq!(total, 102);
let expected = [("gcd", 385), ("odd", 21), ("planar", 488)];
let expected: BTreeMap<String, usize> = expected
.iter()
.map(|&(kind, count)| (kind.to_string(), count))
.collect();
assert_eq!(classes, expected);
}
fn majority_arf(presentation: &GentlePresentation) -> u8 {
let graph = presentation.ribbon_graph();
let cycles = graph.fundamental_cycles();
let values: Vec<bool> = cycles
.iter()
.map(|cycle| (graph.winding(cycle) / 2 + 1) % 2 != 0)
.collect();
let pairing = graph.pairing(&cycles);
let size = cycles.len();
let mut ones = 0usize;
for mask in 0u64..1 << size {
let bit = |i: usize| mask >> i & 1 == 1;
let mut value = false;
for i in (0..size).filter(|&i| bit(i)) {
value ^= values[i];
for j in (i + 1..size).filter(|&j| bit(j)) {
value ^= pairing[i][j] % 2 != 0;
}
}
ones += usize::from(value);
}
u8::from(2 * ones > 1 << size)
}
#[test]
fn the_arf_invariant_is_the_majority_value_at_five_vertices() {
let mut seen: BTreeMap<String, usize> = BTreeMap::new();
for key in connected_gentle_keys(5) {
let presentation = GentlePresentation::new(&key.algebra(f2()).unwrap()).unwrap();
let value = presentation.complete_invariant();
if value.genus() < 2 {
continue;
}
if let WindingClass::Arf(arf) = value.winding_class() {
assert_eq!(arf, majority_arf(&presentation), "{key:?}");
assert_eq!(value.aag_function().pairs(), [(2, 8)]);
}
*seen.entry(value.winding_class().to_string()).or_default() += 1;
}
let expected = [("arf 0", 14), ("arf 1", 9), ("odd", 1213)];
let expected: BTreeMap<String, usize> = expected
.iter()
.map(|&(class, count)| (class.to_string(), count))
.collect();
assert_eq!(seen, expected);
}
#[test]
fn winding_classes_print_their_value() {
let printed: Vec<String> = [
WindingClass::Planar,
WindingClass::Gcd(3),
WindingClass::Odd,
WindingClass::Even,
WindingClass::Arf(1),
]
.iter()
.map(ToString::to_string)
.collect();
assert_eq!(printed, ["planar", "gcd 3", "odd", "even", "arf 1"]);
}