use std::collections::{BTreeMap, BTreeSet};
use std::sync::Arc;
use super::invariant_tests::{aps_first, aps_second};
use super::presentation_tests::bound;
use super::*;
use crate::algebra::Algebra;
use crate::control::ComputationControl;
use crate::equivalence_discovery::{DiscoveryLimits, discover_equivalences};
use crate::equivalence_edge::{DerivedEquivalenceEdge, DerivedEquivalenceEdgeOutcome};
use crate::field::PrimeField;
use crate::target::TargetLimits;
fn small_limits() -> DiscoveryLimits {
DiscoveryLimits {
max_vertices: 8,
max_directed_mutations: 32,
max_total_terms: 256,
max_matrix_entries: 16_384,
..DiscoveryLimits::default()
}
}
fn gentle_targets_agree(algebra: &Arc<Algebra>) -> (usize, BTreeSet<GentleKey>) {
let expected = GentlePresentation::new(algebra)
.unwrap()
.complete_invariant();
let graph = discover_equivalences(algebra, small_limits(), &ComputationControl::new()).unwrap();
let mut accepted = BTreeSet::new();
for (index, vertex) in graph.vertices().iter().enumerate() {
let outcome = DerivedEquivalenceEdge::recover(
vertex
.to_tilting()
.expect("a tilting walk stores tilting vertices"),
&TargetLimits::default(),
)
.unwrap();
let DerivedEquivalenceEdgeOutcome::Certified(edge) = outcome else {
panic!("target recovery was cut at vertex {index}");
};
if let Ok(target) = GentlePresentation::new(edge.target()) {
assert_eq!(
target.complete_invariant(),
expected,
"a derived equivalent target differs at vertex {index}"
);
accepted.insert(target.key());
}
}
(graph.vertices().len(), accepted)
}
#[test]
fn recovered_gentle_targets_share_the_complete_invariant() {
let field = PrimeField::new(3).unwrap();
let cases = [
("Kronecker", crate::algebra::kronecker(2, field), 8, 1),
("A_3 with a source", bound(3, &[(1, 0), (1, 2)], &[]), 8, 4),
(
"affine A_{1,2}",
bound(3, &[(0, 1), (0, 2), (2, 1)], &[]),
8,
3,
),
("A_3", crate::algebra::linear_an(3, field), 8, 4),
(
"A_3/(ab)",
crate::algebra::an_with_relations(3, &[(0, 2)], field).unwrap(),
8,
4,
),
("k[x]/(x^2)", bound(1, &[(0, 0)], &[(0, 0)]), 8, 1),
(
"2-cycle with one relation",
bound(2, &[(0, 1), (1, 0)], &[(0, 1)]),
8,
1,
),
(
"genus 1",
bound(2, &[(0, 1), (1, 0), (0, 1)], &[(2, 1), (1, 0)]),
8,
1,
),
("APS Λ_1, gcd 0", aps_first(), 8, 1),
("APS Λ_2, gcd 2", aps_second(), 7, 1),
];
for (name, algebra, targets, classes) in &cases {
let (recovered, accepted) = gentle_targets_agree(algebra);
assert_eq!(recovered, *targets, "{name}: recovered targets");
assert!(
accepted.len() >= *classes,
"{name}: {} classes",
accepted.len()
);
}
}
fn discovery_components(
vertices: u32,
keep: impl Fn(&GentleDerivedInvariant) -> bool,
) -> (usize, Vec<String>) {
let field = PrimeField::new(2).unwrap();
let mut root: BTreeMap<GentleKey, GentleKey> = BTreeMap::new();
let mut classes: BTreeMap<GentleDerivedInvariant, Vec<GentleKey>> = BTreeMap::new();
for key in connected_gentle_keys(vertices) {
let algebra = key.algebra(field).unwrap();
let value = GentlePresentation::new(&algebra)
.unwrap()
.complete_invariant();
if !keep(&value) {
continue;
}
for target in gentle_targets_agree(&algebra).1 {
let (left, right) = (find(&mut root, &key), find(&mut root, &target));
root.insert(left, right);
}
classes.entry(value).or_default().push(key);
}
let split = classes
.iter()
.filter_map(|(value, keys)| {
let roots: BTreeSet<GentleKey> = keys.iter().map(|key| find(&mut root, key)).collect();
(roots.len() > 1).then(|| format!("{value}: {}", roots.len()))
})
.collect();
(classes.len(), split)
}
fn find(root: &mut BTreeMap<GentleKey, GentleKey>, key: &GentleKey) -> GentleKey {
let mut current = key.clone();
while let Some(next) = root.get(¤t).filter(|next| **next != current) {
current = next.clone();
}
root.insert(key.clone(), current.clone());
current
}
#[test]
#[ignore]
fn discovery_components_refine_the_invariant_at_four_vertices() {
let (classes, split) = discovery_components(4, |value| value.genus() >= 1);
assert_eq!(classes, 35);
assert_eq!(
split,
[
"[(1, 1), (1, 5)], genus 1, gcd 1: 2",
"[(1, 7)], genus 2, odd: 2"
]
);
}
#[test]
#[ignore]
fn discovery_keeps_the_arf_invariant_at_five_vertices() {
let arf =
|value: &GentleDerivedInvariant| matches!(value.winding_class(), WindingClass::Arf(_));
let (classes, split) = discovery_components(5, arf);
assert_eq!(classes, 2);
assert_eq!(
split,
["[(2, 8)], genus 2, arf 0: 3", "[(2, 8)], genus 2, arf 1: 3"]
);
}