use std::collections::{HashMap, VecDeque};
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::ar::TauError;
use crate::basic::{
BasicDecomposition, BasicError, PairFingerprint, ProjectiveSupport, SupportPairIsoOutcome,
SupportPairIsoWitness, pair_iso, pairwise_distinct_by,
};
use crate::context::VerificationContext;
use crate::dynkin::reachable_count;
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::indecomposable_iso;
use crate::module::{Module, summand_sum};
use crate::mutation::{FacWitness, Mutation, MutationError, SlotOutcome, mutate_at_with_cache};
use crate::profile::{Site, hit};
use crate::supporttau::{SupportTauError, SupportTauTiltingClassification, SupportTauTiltingPair};
use crate::taurigid::{TauCache, TauRigidError};
#[derive(Clone, Debug)]
pub enum GraphError {
Basic(BasicError),
SupportTau(SupportTauError),
Mutation(MutationError),
Defect {
reason: String,
},
}
display_error! { GraphError {
Self::Basic(error) => "basic layer: {error}";
Self::SupportTau(error) => "support tau-tilting layer: {error}";
Self::Mutation(error) => "mutation layer: {error}";
Self::Defect { reason } => "internal cross-check failed: {reason}";
} }
error_source!(GraphError {
Self::Basic(error) => Some(error),
Self::SupportTau(error) => Some(error),
Self::Mutation(error) => Some(error),
Self::Defect { .. } => None,
});
from_variants!(GraphError {
BasicError => Basic,
SupportTauError => SupportTau,
MutationError => Mutation,
});
fn defect(reason: String) -> GraphError {
GraphError::Defect { reason }
}
fn basic_blocker(error: &BasicError) -> Option<String> {
match error {
BasicError::CertificationBlocked { reason } => Some(reason.clone()),
_ => None,
}
}
fn support_blocker(error: &SupportTauError) -> Option<String> {
match error {
SupportTauError::Basic(inner) => basic_blocker(inner),
SupportTauError::TauRigid(TauRigidError::Tau(TauError::AgreementUnknown {
reason,
..
})) => Some(format!("the two tau routes stayed undecided: {reason}")),
_ => None,
}
}
fn mutation_blocker(error: &MutationError) -> Option<String> {
match error {
MutationError::Basic(inner) => basic_blocker(inner),
MutationError::SupportTau(inner) => support_blocker(inner),
MutationError::Indec(IndecError::Undetermined { attempts }) => Some(format!(
"a cokernel summand stayed undetermined after {attempts} split attempts"
)),
_ => None,
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct MutationGraphLimits {
pub max_vertices: usize,
pub max_directed_mutations: usize,
pub max_work_units: u64,
pub max_matrix_entries: usize,
}
impl Default for MutationGraphLimits {
fn default() -> MutationGraphLimits {
MutationGraphLimits {
max_vertices: 10_000,
max_directed_mutations: 100_000,
max_work_units: 50_000_000,
max_matrix_entries: 4_000_000,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GraphLimit {
Vertices,
DirectedMutations,
WorkUnits,
MatrixEntries,
}
display_error! { GraphLimit {
Self::Vertices => "max_vertices";
Self::DirectedMutations => "max_directed_mutations";
Self::WorkUnits => "max_work_units";
Self::MatrixEntries => "max_matrix_entries";
} }
fn scale_of(dims: &[usize]) -> u64 {
let entries: u64 = dims.iter().map(|&d| (d as u64) * (d as u64)).sum();
entries.max(1)
}
const fn hom_units(systems: u64, scale: u64) -> u64 {
systems * scale
}
fn decompose_units(summands: usize, scale: u64) -> u64 {
8 * (summands as u64).pow(3) * scale
}
fn iso_units(summands: usize, scale: u64) -> u64 {
decompose_units(summands, scale) + 16 * scale
}
fn tau_units(summands: usize, scale: u64) -> u64 {
64 * summands as u64 * scale + decompose_units(summands, scale)
}
fn indec_units(scale: u64) -> u64 {
8 * scale
}
fn slot_units(summands: usize, left_mutation: bool, scale: u64) -> u64 {
let mut units = hom_units(1, scale);
if !left_mutation {
return units;
}
let kept = summands - 1;
units += decompose_units(kept, scale) + kept as u64 * indec_units(scale);
units += hom_units((kept * kept) as u64 + 1, scale);
units += decompose_units(1, scale) + indec_units(scale);
units += decompose_units(summands, scale) + summands as u64 * indec_units(scale);
units += hom_units((summands * summands) as u64 + 1, scale);
units + iso_units(summands, scale)
}
fn vertex_units(summands: usize, scale: u64) -> u64 {
decompose_units(summands, scale)
+ summands as u64 * indec_units(scale)
+ hom_units((summands * summands) as u64 + 1, scale)
}
fn fingerprint_units(summands: usize, vertices: usize, scale: u64) -> u64 {
hom_units(2 * (summands * vertices) as u64, scale)
}
fn hom_entries(m: &[usize], n: &[usize]) -> usize {
m.iter().zip(n).map(|(a, b)| a * b).sum()
}
#[derive(Clone, Copy, Debug, Default)]
struct WorkLedger {
units: u64,
}
impl WorkLedger {
fn charge(&mut self, units: u64) {
self.units += units;
}
fn charge_tau_misses(&mut self, misses: u64, scale: u64) {
self.units += misses * tau_units(1, scale);
}
fn would_exceed(&self, extra: u64, limit: u64) -> bool {
self.units + extra > limit
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GraphBudgetDiagnostics {
vertices_found: usize,
verified_slots: usize,
new_vertices: usize,
repeated_endpoints: usize,
frontier: usize,
vertex: usize,
slot: Option<usize>,
open_slots: usize,
work_units: u64,
limit: GraphLimit,
}
impl GraphBudgetDiagnostics {
accessor_methods! {
pub vertices_found() -> usize = |this| this.vertices_found;
pub verified_slots() -> usize = |this| this.verified_slots;
pub new_vertices() -> usize = |this| this.new_vertices;
pub repeated_endpoints() -> usize = |this| this.repeated_endpoints;
pub frontier() -> usize = |this| this.frontier;
pub vertex() -> usize = |this| this.vertex;
pub slot() -> Option<usize> = |this| this.slot;
pub open_slots() -> usize = |this| this.open_slots;
pub work_units() -> u64 = |this| this.work_units;
pub limit() -> GraphLimit = |this| this.limit;
}
}
display_error! { GraphBudgetDiagnostics {
Self { limit, vertex, slot, vertices_found, verified_slots, open_slots, frontier, work_units, .. } => "{} ran out at vertex {} slot {:?}: {} vertices, {} slots decided, {} open, frontier {}, {} work units", limit, vertex, slot, vertices_found, verified_slots, open_slots, frontier, work_units;
} }
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CertificationBlocker {
vertex: usize,
slot: Option<usize>,
reason: String,
vertices_found: usize,
work_units: u64,
}
impl CertificationBlocker {
accessor_methods! {
pub vertex() -> usize = |this| this.vertex;
pub slot() -> Option<usize> = |this| this.slot;
pub reason() -> &str = |this| &this.reason;
pub vertices_found() -> usize = |this| this.vertices_found;
pub work_units() -> u64 = |this| this.work_units;
}
}
display_error! { CertificationBlocker {
Self { vertex, slot, reason, .. } => "certification blocked at vertex {} slot {:?}: {}", vertex, slot, reason;
} }
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum IncompleteReason {
BudgetExhausted(GraphBudgetDiagnostics),
CertificationBlocked(CertificationBlocker),
}
display_error! { IncompleteReason {
Self::BudgetExhausted(diagnostics) => "{diagnostics}";
Self::CertificationBlocked(blocker) => "{blocker}";
} }
#[derive(Debug)]
pub enum SlotRecord {
LeftMutation {
mutation: usize,
},
NoLeftMutation(FacWitness),
}
impl SlotRecord {
optional_accessors! {
pub mutation() -> usize = Self::LeftMutation { mutation } => *mutation;
pub fac_witness() -> &FacWitness = Self::NoLeftMutation(witness) => witness;
}
}
#[derive(Debug)]
pub struct GraphVertex {
pair: SupportTauTiltingPair,
slots: Vec<SlotRecord>,
}
impl GraphVertex {
accessor_methods! {
pub pair() -> &SupportTauTiltingPair = |this| &this.pair;
pub slots() -> &[SlotRecord] = |this| &this.slots;
}
}
#[derive(Debug)]
pub struct VerifiedMutation {
source: usize,
slot: usize,
target: usize,
mutation: Mutation,
endpoint: SupportPairIsoWitness,
}
impl VerifiedMutation {
accessor_methods! {
pub source() -> usize = |this| this.source;
pub slot() -> usize = |this| this.slot;
pub target() -> usize = |this| this.target;
pub mutation() -> &Mutation = |this| &this.mutation;
pub endpoint() -> &SupportPairIsoWitness = |this| &this.endpoint;
}
}
fn reachable_from_root(
vertex_count: usize,
edges: impl IntoIterator<Item = (usize, usize)>,
) -> usize {
let mut out: Vec<Vec<usize>> = vec![Vec::new(); vertex_count];
for (source, target) in edges {
if source < vertex_count && target < vertex_count {
out[source].push(target);
}
}
reachable_count(&out, 0)
}
#[derive(Debug)]
pub struct ClosureWitness {
algebra: Arc<Algebra>,
vertices: Vec<GraphVertex>,
mutations: Vec<VerifiedMutation>,
}
impl ClosureWitness {
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub vertices() -> &[GraphVertex] = |this| &this.vertices;
pub mutations() -> &[VerifiedMutation] = |this| &this.mutations;
}
fn vertices_certified_with_context(&self, context: &VerificationContext) -> bool {
self.vertices.iter().all(|v| {
Arc::ptr_eq(v.pair.module().module().algebra(), &self.algebra)
&& v.pair.verify_with_context(context)
})
}
fn pairwise_distinct_with_context(&self, context: &VerificationContext) -> bool {
pairwise_distinct_by(
&self.vertices,
|vertex| {
PairFingerprint::new_with_context(
vertex.pair.module(),
&vertex.pair.projective(),
context,
)
.ok()
},
|left, right| {
matches!(
context.pair_iso_for(
left.pair.module(),
&left.pair.projective(),
right.pair.module(),
&right.pair.projective(),
),
Ok(outcome)
if matches!(outcome.as_ref(), SupportPairIsoOutcome::NotIsomorphic(_))
)
},
)
}
fn root_is_regular_with_context(&self, context: &VerificationContext) -> bool {
let_or_false!(Some(root) = self.vertices.first());
let_or_false!(Ok((module, support)) = regular_parts_with_context(&self.algebra, context));
matches!(
context.pair_iso_for(
&module,
&support,
root.pair.module(),
&root.pair.projective(),
),
Ok(outcome) if matches!(outcome.as_ref(), SupportPairIsoOutcome::Isomorphic(_))
)
}
fn slots_resolved_with_context(&self, context: &VerificationContext) -> bool {
let mut referenced = vec![false; self.mutations.len()];
for (v, vertex) in self.vertices.iter().enumerate() {
verify_guard!(vertex.slots.len() == vertex.pair.module().len());
for (slot, record) in vertex.slots.iter().enumerate() {
match record {
SlotRecord::LeftMutation { mutation } => {
let_or_false!(Some(edge) = self.mutations.get(*mutation));
verify_guard!(
!referenced[*mutation]
&& edge.source == v
&& edge.slot == slot
&& edge.target < self.vertices.len()
&& edge.mutation.slot() == slot
&& edge.mutation.verify_with_context(context)
);
verify_guard!(
edge.mutation
.witness()
.source_module()
.ptr_eq(vertex.pair.module().module())
&& edge.mutation.witness().source_projective()
== vertex.pair.projective().vertices()
);
referenced[*mutation] = true;
}
SlotRecord::NoLeftMutation(witness) => {
verify_guard!(witness.verify());
let summands = vertex.pair.module().summands();
let_or_false!(Some(x) = summands.get(slot));
verify_guard!(witness.summand().ptr_eq(x.module()));
let kept = summands
.iter()
.enumerate()
.filter(|(i, _)| *i != slot)
.map(|(_, other)| other.module());
let stored = witness.summands();
verify_guard!(
stored.len() + 1 == summands.len()
&& kept.zip(stored).all(|(a, b)| a.ptr_eq(b))
);
}
}
}
}
referenced.iter().all(|used| *used)
}
fn endpoints_bound(&self) -> bool {
for edge in &self.mutations {
let_or_false!(Some(vertex) = self.vertices.get(edge.target));
let built = edge.mutation.target();
verify_guard!(built.projective().vertices() == vertex.pair.projective().vertices());
let from = built.module().summands();
let to = vertex.pair.module().summands();
let bijection = edge.endpoint.bijection();
verify_guard!(bijection.len() == from.len() && from.len() == to.len());
verify_guard!(edge.endpoint.verify());
for (i, &j) in bijection.iter().enumerate() {
let_or_false!((Some(source), Some(target)) = (from.get(i), to.get(j)));
let forward = &edge.endpoint.forward()[i];
let backward = &edge.endpoint.backward()[i];
verify_guard!(
forward.source().ptr_eq(source.module())
&& forward.target().ptr_eq(target.module())
&& backward.source().ptr_eq(target.module())
&& backward.target().ptr_eq(source.module())
);
}
}
true
}
fn connected(&self) -> bool {
reachable_from_root(
self.vertices.len(),
self.mutations.iter().map(|edge| (edge.source, edge.target)),
) == self.vertices.len()
}
fn n_regular(&self) -> bool {
let n = self.algebra.quiver().num_vertices() as usize;
let mut incoming = vec![0usize; self.vertices.len()];
for edge in &self.mutations {
verify_guard!(edge.target < incoming.len());
incoming[edge.target] += 1;
}
for (v, vertex) in self.vertices.iter().enumerate() {
let outgoing = vertex
.slots
.iter()
.filter(|record| record.mutation().is_some())
.count();
let fac = vertex.slots.len() - outgoing;
verify_guard!(incoming[v] == fac + vertex.pair.projective().len());
verify_guard!(outgoing + incoming[v] == n);
}
true
}
verify_methods!(, { hit(Site::ClosureWitnessVerify); },
|self, context| {
self.vertices_certified_with_context(context)
&& self.pairwise_distinct_with_context(context)
&& self.root_is_regular_with_context(context)
&& self.slots_resolved_with_context(context)
&& self.endpoints_bound()
&& self.connected()
&& self.n_regular()
});
}
#[derive(Debug)]
pub struct ClosedSupportTauTiltingGraph {
witness: ClosureWitness,
work_units: u64,
}
impl ClosedSupportTauTiltingGraph {
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| this.witness.algebra();
pub pairs() -> impl ExactSizeIterator<Item = &SupportTauTiltingPair> =
|this| this.witness.vertices().iter().map(GraphVertex::pair);
pub vertices() -> &[GraphVertex] = |this| this.witness.vertices();
pub mutations() -> &[VerifiedMutation] = |this| this.witness.mutations();
pub len() -> usize = |this| this.witness.vertices().len();
pub is_empty() -> bool = |this| this.witness.vertices().is_empty();
}
pub fn histogram(&self) -> Vec<usize> {
let n = self.algebra().quiver().num_vertices() as usize;
let mut out = vec![0; n + 1];
for vertex in self.witness.vertices() {
out[vertex.pair.module().len()] += 1;
}
out
}
accessor_methods! {
pub witness() -> &ClosureWitness = |this| &this.witness;
pub work_units() -> u64 = |this| this.work_units;
pub verify() -> bool = |this| this.witness.verify();
}
}
#[derive(Debug)]
pub struct IncompleteSupportTauTiltingGraph {
algebra: Arc<Algebra>,
vertices: Vec<GraphVertex>,
mutations: Vec<VerifiedMutation>,
reason: IncompleteReason,
work_units: u64,
}
impl IncompleteSupportTauTiltingGraph {
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub vertices_found() -> &[GraphVertex] = |this| &this.vertices;
pub verified_mutations() -> &[VerifiedMutation] = |this| &this.mutations;
pub reason() -> &IncompleteReason = |this| &this.reason;
pub work_units() -> u64 = |this| this.work_units;
pub verify_parts() -> bool = |this| this.vertices.iter().all(|v| {
Arc::ptr_eq(v.pair.module().module().algebra(), &this.algebra) && v.pair.verify()
}) && this
.mutations
.iter()
.all(|edge| edge.mutation.verify() && edge.endpoint.verify());
}
}
#[derive(Debug)]
pub enum SupportTauTiltingGraphOutcome {
Closed(ClosedSupportTauTiltingGraph),
Incomplete(IncompleteSupportTauTiltingGraph),
}
impl SupportTauTiltingGraphOutcome {
binary_outcome_accessors!(
Closed,
Incomplete,
closed -> ClosedSupportTauTiltingGraph = |value| value,
incomplete -> IncompleteSupportTauTiltingGraph = |value| value,
is_closed,
into_closed -> ClosedSupportTauTiltingGraph = |value| value;
flag = "Whether the walk closed.";
positive = "The closed graph, or `None` when the walk stopped short.";
negative = "The partial graph, or `None` when the walk closed.";
into = "The closed graph by value, or `None` when the walk stopped short.";
);
}
fn regular_parts(
algebra: &Arc<Algebra>,
) -> Result<(BasicDecomposition, ProjectiveSupport), BasicError> {
regular_parts_with(algebra, BasicDecomposition::new)
}
fn regular_parts_with(
algebra: &Arc<Algebra>,
basic: impl FnOnce(&Module) -> Result<BasicDecomposition, BasicError>,
) -> Result<(BasicDecomposition, ProjectiveSupport), BasicError> {
let vertices: Vec<u32> = (0..algebra.quiver().num_vertices()).collect();
let module = summand_sum(algebra, &vertices, Module::projective);
Ok((basic(&module)?, ProjectiveSupport::new(algebra, &[])?))
}
fn regular_parts_with_context(
algebra: &Arc<Algebra>,
context: &VerificationContext,
) -> Result<(BasicDecomposition, ProjectiveSupport), BasicError> {
regular_parts_with(algebra, |module| {
BasicDecomposition::new_with_context(module, context)
})
}
#[derive(Default)]
struct SummandRegistry {
entries: Vec<(usize, Module)>,
next: usize,
}
impl SummandRegistry {
fn fresh(&mut self) -> usize {
let index = self.next;
self.next += 1;
index
}
fn lookup(&self, x: &IndecomposableModule, ledger: &mut WorkLedger) -> Option<usize> {
let scale = scale_of(x.module().dim_vector());
for (index, entry) in &self.entries {
if entry.dim_vector() != x.module().dim_vector() {
continue;
}
ledger.charge(iso_units(1, scale));
if indecomposable_iso(x.module(), entry, x.endo()).is_some() {
return Some(*index);
}
}
None
}
fn insert(&mut self, index: usize, x: Module) {
self.entries.push((index, x));
}
}
enum Stop {
Budget(GraphLimit),
Blocked(String),
}
struct Walk<'a> {
algebra: Arc<Algebra>,
limits: &'a MutationGraphLimits,
cache: TauCache,
registry: SummandRegistry,
ledger: WorkLedger,
vertices: Vec<GraphVertex>,
indices: Vec<Vec<usize>>,
fingerprints: Vec<PairFingerprint>,
buckets: HashMap<PairFingerprint, Vec<usize>>,
mutations: Vec<VerifiedMutation>,
queue: VecDeque<usize>,
total_slots: usize,
verified_slots: usize,
new_vertices: usize,
repeated_endpoints: usize,
at_vertex: usize,
at_slot: Option<usize>,
}
impl Walk<'_> {
fn quiver_vertices(&self) -> usize {
self.algebra.quiver().num_vertices() as usize
}
fn charge_tau(&mut self, misses_before: u64, scale: u64) {
let misses = self.cache.misses() - misses_before;
self.ledger.charge_tau_misses(misses, scale);
}
fn resolve_indices(
&mut self,
decomposition: &BasicDecomposition,
preferred: Option<usize>,
) -> Vec<usize> {
let mut preferred = preferred;
let mut out = Vec::with_capacity(decomposition.len());
for x in decomposition.summands() {
if let Some(index) = self.registry.lookup(x, &mut self.ledger) {
out.push(index);
continue;
}
let index = preferred.take().unwrap_or_else(|| self.registry.fresh());
self.registry.insert(index, x.module().clone());
out.push(index);
}
out
}
fn push_vertex(
&mut self,
module: BasicDecomposition,
support: ProjectiveSupport,
preferred: Option<usize>,
) -> Result<Result<usize, Stop>, GraphError> {
let summands = module.len();
let n = self.quiver_vertices();
let scale = scale_of(module.module().dim_vector());
self.ledger.charge(vertex_units(summands, scale));
let indices = self.resolve_indices(&module, preferred);
let misses = self.cache.misses();
let classification = SupportTauTiltingPair::classify_with_cache(
module,
support,
&indices,
Some(&mut self.cache),
);
self.charge_tau(misses, scale);
let classification = match classification {
Ok(classification) => classification,
Err(error) => {
if let Some(reason) = support_blocker(&error) {
return Ok(Err(Stop::Blocked(reason)));
}
return Err(error.into());
}
};
let pair = match classification {
SupportTauTiltingClassification::Pair(pair) => pair,
SupportTauTiltingClassification::Rejected(rejection) => {
return Err(defect(format!(
"a mutation target left condition {} unmet: {rejection}",
rejection.condition()
)));
}
};
self.ledger.charge(fingerprint_units(summands, n, scale));
let fingerprint = PairFingerprint::new(pair.module(), &pair.projective())?;
let index = self.vertices.len();
self.buckets
.entry(fingerprint.clone())
.or_default()
.push(index);
self.fingerprints.push(fingerprint);
self.indices.push(indices);
self.total_slots += summands;
self.vertices.push(GraphVertex {
pair,
slots: Vec::with_capacity(summands),
});
self.queue.push_back(index);
Ok(Ok(index))
}
fn find_vertex(
&mut self,
pair: &SupportTauTiltingPair,
) -> Result<Option<(usize, SupportPairIsoWitness)>, GraphError> {
let summands = pair.module().len();
let scale = scale_of(pair.module().module().dim_vector());
self.ledger
.charge(fingerprint_units(summands, self.quiver_vertices(), scale));
let fingerprint = PairFingerprint::new(pair.module(), &pair.projective())?;
let Some(bucket) = self.buckets.get(&fingerprint) else {
return Ok(None);
};
let bucket = bucket.clone();
for candidate in bucket {
self.ledger.charge(iso_units(summands, scale));
let vertex = &self.vertices[candidate];
match pair_iso(
pair.module(),
&pair.projective(),
vertex.pair.module(),
&vertex.pair.projective(),
)? {
SupportPairIsoOutcome::Isomorphic(witness) => {
return Ok(Some((candidate, witness)));
}
SupportPairIsoOutcome::NotIsomorphic(_) => {}
}
}
Ok(None)
}
fn fac_system_fits(&self, vertex: usize, slot: usize) -> bool {
let summands = self.vertices[vertex].pair.module().summands();
let x = summands[slot].module().dim_vector();
let mut kept = vec![0usize; x.len()];
for (i, other) in summands.iter().enumerate() {
if i == slot {
continue;
}
for (entry, dim) in kept.iter_mut().zip(other.module().dim_vector()) {
*entry += dim;
}
}
hom_entries(&kept, x) <= self.limits.max_matrix_entries
}
fn visit_slot(&mut self, vertex: usize, slot: usize) -> Result<Option<Stop>, GraphError> {
self.at_vertex = vertex;
self.at_slot = Some(slot);
let summands = self.vertices[vertex].pair.module().len();
let scale = scale_of(self.vertices[vertex].pair.module().module().dim_vector());
if !self.fac_system_fits(vertex, slot) {
return Ok(Some(Stop::Budget(GraphLimit::MatrixEntries)));
}
if self.ledger.would_exceed(
slot_units(summands, true, scale),
self.limits.max_work_units,
) {
return Ok(Some(Stop::Budget(GraphLimit::WorkUnits)));
}
let fresh = self.registry.fresh();
let indices = self.indices[vertex].clone();
let misses = self.cache.misses();
let outcome = mutate_at_with_cache(
&self.vertices[vertex].pair,
slot,
&indices,
fresh,
Some(&mut self.cache),
);
self.charge_tau(misses, scale);
let outcome = match outcome {
Ok(outcome) => outcome,
Err(error) => {
if let Some(reason) = mutation_blocker(&error) {
return Ok(Some(Stop::Blocked(reason)));
}
return Err(error.into());
}
};
let mutation = match outcome {
SlotOutcome::NoLeftMutation(witness) => {
self.ledger.charge(slot_units(summands, false, scale));
self.vertices[vertex]
.slots
.push(SlotRecord::NoLeftMutation(witness));
self.verified_slots += 1;
return Ok(None);
}
SlotOutcome::LeftMutation(mutation) => mutation,
};
self.ledger.charge(slot_units(summands, true, scale));
if self.mutations.len() >= self.limits.max_directed_mutations {
return Ok(Some(Stop::Budget(GraphLimit::DirectedMutations)));
}
let (target, endpoint) = match self.find_vertex(mutation.target())? {
Some((index, witness)) => {
self.repeated_endpoints += 1;
(index, witness)
}
None => {
if self.vertices.len() >= self.limits.max_vertices {
return Ok(Some(Stop::Budget(GraphLimit::Vertices)));
}
let module = BasicDecomposition::new(mutation.target().module().module())?;
let support = ProjectiveSupport::new(
&self.algebra,
mutation.target().projective().vertices(),
)?;
let preferred = mutation.witness().replacement().map(|_| fresh);
let index = match self.push_vertex(module, support, preferred)? {
Ok(index) => index,
Err(stop) => return Ok(Some(stop)),
};
self.new_vertices += 1;
self.ledger.charge(iso_units(
mutation.target().module().len(),
scale_of(mutation.target().module().module().dim_vector()),
));
let witness = match pair_iso(
mutation.target().module(),
&mutation.target().projective(),
self.vertices[index].pair.module(),
&self.vertices[index].pair.projective(),
)? {
SupportPairIsoOutcome::Isomorphic(witness) => witness,
SupportPairIsoOutcome::NotIsomorphic(obstruction) => {
return Err(defect(format!(
"the rebuilt vertex is not isomorphic to the mutation target: \
{obstruction:?}"
)));
}
};
(index, witness)
}
};
let edge = self.mutations.len();
self.mutations.push(VerifiedMutation {
source: vertex,
slot,
target,
mutation: *mutation,
endpoint,
});
self.vertices[vertex]
.slots
.push(SlotRecord::LeftMutation { mutation: edge });
self.verified_slots += 1;
Ok(None)
}
accessor_methods! {
over_work_budget() -> Option<Stop> = |this|
(this.ledger.units > this.limits.max_work_units)
.then_some(Stop::Budget(GraphLimit::WorkUnits));
}
fn run(&mut self) -> Result<Option<Stop>, GraphError> {
while let Some(vertex) = self.queue.pop_front() {
let slots = self.vertices[vertex].pair.module().len();
for slot in 0..slots {
if let Some(stop) = self.visit_slot(vertex, slot)? {
return Ok(Some(stop));
}
if let Some(stop) = self.over_work_budget() {
return Ok(Some(stop));
}
}
self.at_slot = None;
}
Ok(self.over_work_budget())
}
fn diagnostics(&self, limit: GraphLimit) -> GraphBudgetDiagnostics {
GraphBudgetDiagnostics {
vertices_found: self.vertices.len(),
verified_slots: self.verified_slots,
new_vertices: self.new_vertices,
repeated_endpoints: self.repeated_endpoints,
frontier: self.queue.len(),
vertex: self.at_vertex,
slot: self.at_slot,
open_slots: self.total_slots - self.verified_slots,
work_units: self.ledger.units,
limit,
}
}
fn blocker(&self, reason: String) -> CertificationBlocker {
CertificationBlocker {
vertex: self.at_vertex,
slot: self.at_slot,
reason,
vertices_found: self.vertices.len(),
work_units: self.ledger.units,
}
}
}
fn close(
algebra: &Arc<Algebra>,
vertices: Vec<GraphVertex>,
mutations: Vec<VerifiedMutation>,
work_units: u64,
) -> Result<ClosedSupportTauTiltingGraph, GraphError> {
let witness = ClosureWitness {
algebra: algebra.clone(),
vertices,
mutations,
};
if !witness.verify() {
return Err(defect(
"the walk drained its frontier and the closure recheck failed".to_string(),
));
}
Ok(ClosedSupportTauTiltingGraph {
witness,
work_units,
})
}
pub fn support_tau_tilting_graph(
algebra: &Arc<Algebra>,
limits: &MutationGraphLimits,
) -> Result<SupportTauTiltingGraphOutcome, GraphError> {
let mut walk = Walk {
algebra: algebra.clone(),
limits,
cache: TauCache::new(),
registry: SummandRegistry::default(),
ledger: WorkLedger::default(),
vertices: Vec::new(),
indices: Vec::new(),
fingerprints: Vec::new(),
buckets: HashMap::new(),
mutations: Vec::new(),
queue: VecDeque::new(),
total_slots: 0,
verified_slots: 0,
new_vertices: 0,
repeated_endpoints: 0,
at_vertex: 0,
at_slot: None,
};
let (module, support) = regular_parts(algebra)?;
let stop = match walk.push_vertex(module, support, None)? {
Ok(_) => walk.run()?,
Err(stop) => Some(stop),
};
let work_units = walk.ledger.units;
let reason = match stop {
None => {
return Ok(SupportTauTiltingGraphOutcome::Closed(close(
algebra,
walk.vertices,
walk.mutations,
work_units,
)?));
}
Some(Stop::Budget(limit)) => IncompleteReason::BudgetExhausted(walk.diagnostics(limit)),
Some(Stop::Blocked(reason)) => IncompleteReason::CertificationBlocked(walk.blocker(reason)),
};
Ok(SupportTauTiltingGraphOutcome::Incomplete(
IncompleteSupportTauTiltingGraph {
algebra: algebra.clone(),
vertices: walk.vertices,
mutations: walk.mutations,
reason,
work_units,
},
))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
kronecker, linear_an, linear_nakayama, radical_square_zero_cycle, truncated_poly,
};
use crate::arquiver::IndecomposableCatalog;
use crate::dynkin::{DynkinType, dynkin_quiver};
use crate::field::PrimeField;
use crate::quiver::Quiver;
use crate::supporttau::enumerate_over_catalog;
impl ClosureWitness {
fn pairwise_distinct(&self) -> bool {
pairwise_distinct(self)
}
fn slots_resolved(&self) -> bool {
slots_resolved(self)
}
fn verify_without_context(&self) -> bool {
hit(Site::ClosureWitnessVerify);
self.vertices.iter().all(|vertex| {
Arc::ptr_eq(vertex.pair.module().module().algebra(), &self.algebra)
&& vertex.pair.verify()
}) && pairwise_distinct(self)
&& root_is_regular(self)
&& slots_resolved(self)
&& self.endpoints_bound()
&& self.connected()
&& self.n_regular()
}
fn fingerprints_without_context(&self) -> Vec<PairFingerprint> {
self.vertices
.iter()
.map(|vertex| {
PairFingerprint::new(vertex.pair.module(), &vertex.pair.projective())
.expect("the graph stores compatible pairs")
})
.collect()
}
fn fingerprints_with_context(&self, context: &VerificationContext) -> Vec<PairFingerprint> {
self.vertices
.iter()
.map(|vertex| {
PairFingerprint::new_with_context(
vertex.pair.module(),
&vertex.pair.projective(),
context,
)
.expect("the graph stores compatible pairs")
})
.collect()
}
}
fn pairwise_distinct(witness: &ClosureWitness) -> bool {
let mut fingerprints = Vec::with_capacity(witness.vertices.len());
for vertex in &witness.vertices {
match PairFingerprint::new(vertex.pair.module(), &vertex.pair.projective()) {
Ok(fingerprint) => fingerprints.push(fingerprint),
Err(_) => return false,
}
}
for (i, left) in witness.vertices.iter().enumerate() {
for (j, right) in witness.vertices.iter().enumerate().skip(i + 1) {
if fingerprints[i] == fingerprints[j]
&& !matches!(
pair_iso(
left.pair.module(),
&left.pair.projective(),
right.pair.module(),
&right.pair.projective(),
),
Ok(SupportPairIsoOutcome::NotIsomorphic(_))
)
{
return false;
}
}
}
true
}
fn root_is_regular(witness: &ClosureWitness) -> bool {
let_or_false!(Some(root) = witness.vertices.first());
let_or_false!(Ok((module, support)) = regular_parts(&witness.algebra));
matches!(
pair_iso(
&module,
&support,
root.pair.module(),
&root.pair.projective(),
),
Ok(SupportPairIsoOutcome::Isomorphic(_))
)
}
fn slots_resolved(witness: &ClosureWitness) -> bool {
let mut referenced = vec![false; witness.mutations.len()];
for (vertex_index, vertex) in witness.vertices.iter().enumerate() {
if vertex.slots.len() != vertex.pair.module().len() {
return false;
}
for (slot, record) in vertex.slots.iter().enumerate() {
match record {
SlotRecord::LeftMutation { mutation } => {
let_or_false!(Some(edge) = witness.mutations.get(*mutation));
if referenced[*mutation]
|| edge.source != vertex_index
|| edge.slot != slot
|| edge.target >= witness.vertices.len()
|| edge.mutation.slot() != slot
|| !edge.mutation.verify()
|| !edge
.mutation
.witness()
.source_module()
.ptr_eq(vertex.pair.module().module())
|| edge.mutation.witness().source_projective()
!= vertex.pair.projective().vertices()
{
return false;
}
referenced[*mutation] = true;
}
SlotRecord::NoLeftMutation(fac) => {
let summands = vertex.pair.module().summands();
let_or_false!(Some(summand) = summands.get(slot));
let kept = summands
.iter()
.enumerate()
.filter(|(index, _)| *index != slot)
.map(|(_, summand)| summand.module());
if !fac.verify()
|| !fac.summand().ptr_eq(summand.module())
|| fac.summands().len() + 1 != summands.len()
|| !kept.zip(fac.summands()).all(|(a, b)| a.ptr_eq(b))
{
return false;
}
}
}
}
}
referenced.iter().all(|used| *used)
}
fn f2() -> PrimeField {
PrimeField::new(2).unwrap()
}
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn fields() -> [PrimeField; 2] {
[f2(), f5()]
}
fn path_algebra(quiver: Quiver, field: PrimeField) -> Arc<Algebra> {
crate::algebra::path_algebra(quiver, field)
.expect("the zero ideal over an acyclic quiver completes")
}
fn semisimple(n: u32, field: PrimeField) -> Arc<Algebra> {
path_algebra(
Quiver::new(n, &[]).expect("no arrow is out of range"),
field,
)
}
fn d4(field: PrimeField) -> Arc<Algebra> {
path_algebra(
dynkin_quiver(DynkinType::D(4)).expect("D_4 has a quiver"),
field,
)
}
fn walk(algebra: &Arc<Algebra>) -> ClosedSupportTauTiltingGraph {
let outcome = support_tau_tilting_graph(algebra, &MutationGraphLimits::default())
.expect("the fixture walks without a defect");
match outcome {
SupportTauTiltingGraphOutcome::Closed(graph) => graph,
SupportTauTiltingGraphOutcome::Incomplete(graph) => {
panic!("the walk stopped short: {}", graph.reason())
}
}
}
fn catalog_fixtures(field: PrimeField) -> Vec<(String, Arc<Algebra>, IndecomposableCatalog)> {
let modulus = field.modulus();
let mut out = Vec::new();
for n in [2u32, 3, 4] {
let algebra = semisimple(n, field);
let catalog =
IndecomposableCatalog::nakayama(&algebra).expect("no arrow means Nakayama");
out.push((
format!("semisimple({n}) over F_{modulus}"),
algebra,
catalog,
));
}
for n in [2usize, 3] {
let algebra = linear_an(n, field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("A_n is Dynkin");
out.push((format!("linear_an({n}) over F_{modulus}"), algebra, catalog));
}
let tp = truncated_poly(3, field).expect("k[x]/(x^3) is admissible");
let catalog = IndecomposableCatalog::nakayama(&tp).expect("one loop is Nakayama");
out.push((format!("truncated_poly(3) over F_{modulus}"), tp, catalog));
let cycle = radical_square_zero_cycle(3, field);
let catalog = IndecomposableCatalog::nakayama(&cycle).expect("a cycle is Nakayama");
out.push((
format!("radical_square_zero_cycle(3) over F_{modulus}"),
cycle,
catalog,
));
let nakayama = linear_nakayama(&[2, 2, 1], field).expect("[2, 2, 1] is a Kupisch series");
let catalog =
IndecomposableCatalog::nakayama(&nakayama).expect("a linear quiver is Nakayama");
out.push((
format!("linear_nakayama([2, 2, 1]) over F_{modulus}"),
nakayama,
catalog,
));
out
}
fn same_pair_set(left: &[&SupportTauTiltingPair], right: &[&SupportTauTiltingPair]) -> bool {
if left.len() != right.len() {
return false;
}
let mut used = vec![false; right.len()];
for a in left {
let mut matched = false;
for (j, b) in right.iter().enumerate() {
if used[j] {
continue;
}
match pair_iso(a.module(), &a.projective(), b.module(), &b.projective())
.expect("both routes build pairs over one algebra")
{
SupportPairIsoOutcome::Isomorphic(witness) => {
assert!(witness.verify(), "the matching isomorphism rechecks");
used[j] = true;
matched = true;
break;
}
SupportPairIsoOutcome::NotIsomorphic(_) => {}
}
}
if !matched {
return false;
}
}
used.iter().all(|hit| *hit)
}
fn render(graph: &ClosedSupportTauTiltingGraph) -> String {
let mut out = String::new();
for (v, vertex) in graph.vertices().iter().enumerate() {
out.push_str(&format!(
"v{v} {:?} p{:?}\n",
vertex.pair().module().dim_vectors(),
vertex.pair().projective().vertices()
));
for (slot, record) in vertex.slots().iter().enumerate() {
match record {
SlotRecord::LeftMutation { mutation } => {
out.push_str(&format!(" s{slot} -> e{mutation}\n"));
}
SlotRecord::NoLeftMutation(witness) => {
out.push_str(&format!(
" s{slot} fac {:?} of {:?} maps {}\n",
witness.summand().dim_vector(),
witness.module().dim_vector(),
witness.maps().len()
));
}
}
}
}
for (e, edge) in graph.mutations().iter().enumerate() {
out.push_str(&format!(
"e{e} {}:{} -> {} shape {:?} exchanged {:?} target {:?} bijection {:?}\n",
edge.source(),
edge.slot(),
edge.target(),
edge.mutation().shape(),
edge.mutation().witness().exchanged().dim_vector(),
edge.mutation().witness().target_module().dim_vector(),
edge.endpoint().bijection()
));
}
out
}
#[test]
fn the_pair_counts_agree_with_three_independent_sources() {
let expected = [4usize, 8, 16, 5, 14, 2, 14, 12];
for field in fields() {
let fixtures = catalog_fixtures(field);
assert_eq!(fixtures.len(), expected.len());
for ((name, algebra, _), count) in fixtures.iter().zip(expected) {
let graph = walk(algebra);
assert_eq!(graph.len(), count, "{name}");
assert_eq!(graph.pairs().len(), count, "{name}");
}
}
}
#[test]
fn the_d4_graph_has_fifty_pairs_and_the_published_histogram() {
for field in fields() {
let graph = walk(&d4(field));
assert_eq!(graph.len(), 50, "over F_{}", field.modulus());
assert_eq!(graph.histogram(), vec![1, 4, 9, 16, 20]);
assert_eq!(graph.mutations().len(), 100);
}
}
#[test]
fn a_d4_f5_closure_context_has_hits_and_misses() {
let _reset_guard = crate::profile::tests::reset_lock();
let graph = walk(&d4(f5()));
let without_fingerprints = graph.witness.fingerprints_without_context();
let primitive_calls = |counts: &[u64]| {
[
Site::HomDim,
Site::Tau,
Site::TauWithOpposite,
Site::EndoNew,
Site::Decompose,
Site::PairIso,
]
.into_iter()
.map(|site| counts[site as usize])
.sum::<u64>()
};
crate::profile::reset();
assert!(graph.witness.verify_without_context());
let without_counts = crate::profile::snapshot();
let without_distinct = crate::profile::distinct_snapshot();
let without_context = primitive_calls(&without_counts);
crate::profile::reset();
let context = VerificationContext::new();
assert!(graph.witness.verify_with_context(&context));
assert_eq!(
without_fingerprints,
graph.witness.fingerprints_with_context(&context)
);
let (hits, misses) = context.memo_stats();
assert!(hits > 0, "the context has no hit");
assert!(misses > 0, "the context has no miss");
let with_counts = crate::profile::snapshot();
let with_distinct = crate::profile::distinct_snapshot();
let with_context = primitive_calls(&with_counts);
if crate::profile::ENABLED {
let sites = [
Site::HomDim,
Site::Tau,
Site::TauWithOpposite,
Site::EndoNew,
Site::Decompose,
Site::PairIso,
];
eprintln!(
"D4/F5 context: memo hits {hits}, misses {misses}; primitive calls {without_context} -> {with_context}; distinct {:?} -> {:?}",
sites
.iter()
.map(|site| without_distinct[*site as usize])
.collect::<Vec<_>>(),
sites
.iter()
.map(|site| with_distinct[*site as usize])
.collect::<Vec<_>>()
);
assert!(
with_context < without_context,
"context made {with_context} primitive calls versus {without_context} uncached"
);
}
}
#[test]
fn the_walk_and_the_catalog_route_list_the_same_pairs() {
for field in fields() {
for (name, algebra, catalog) in catalog_fixtures(field) {
let graph = walk(&algebra);
let enumeration = enumerate_over_catalog(&catalog).expect("the catalog route runs");
let walked: Vec<&SupportTauTiltingPair> = graph.pairs().collect();
let listed: Vec<&SupportTauTiltingPair> = enumeration.pairs().iter().collect();
assert_eq!(walked.len(), listed.len(), "{name}");
assert!(same_pair_set(&walked, &listed), "{name}: walk into catalog");
assert!(same_pair_set(&listed, &walked), "{name}: catalog into walk");
}
}
}
#[test]
fn every_closed_graph_verifies_its_closure_witness() {
for field in fields() {
for (name, algebra, _) in catalog_fixtures(field) {
let graph = walk(&algebra);
assert!(graph.verify(), "{name}");
}
}
}
#[test]
fn a_vertex_budget_equal_to_the_true_count_still_closes() {
let limits = MutationGraphLimits {
max_vertices: 5,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&linear_an(2, f2()), &limits)
.expect("A_2 walks without a defect");
assert!(outcome.is_closed());
assert_eq!(outcome.closed().expect("closed").len(), 5);
let tight = MutationGraphLimits {
max_vertices: 4,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&linear_an(2, f2()), &tight)
.expect("A_2 walks without a defect");
let graph = outcome.incomplete().expect("four vertices are one too few");
match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => {
assert_eq!(diagnostics.limit(), GraphLimit::Vertices);
}
IncompleteReason::CertificationBlocked(blocker) => {
panic!("a vertex budget is no blocked certification: {blocker}")
}
}
}
#[test]
fn the_kronecker_walk_truncates_with_a_typed_budget() {
let limits = MutationGraphLimits {
max_vertices: 16,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&kronecker(2, f2()), &limits)
.expect("the Kronecker walk runs without a defect");
assert!(!outcome.is_closed());
let graph = outcome.incomplete().expect("the walk stopped short");
let diagnostics = match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => diagnostics,
IncompleteReason::CertificationBlocked(blocker) => {
panic!("the Kronecker walk certifies every step it takes: {blocker}")
}
};
assert_eq!(diagnostics.limit(), GraphLimit::Vertices);
assert_eq!(diagnostics.vertices_found(), 16);
assert_eq!(graph.vertices_found().len(), 16);
assert!(diagnostics.open_slots() > 0);
assert!(diagnostics.work_units() > 0);
for vertex in graph.vertices_found() {
assert!(vertex.pair().verify());
assert_eq!(vertex.pair().summand_count(), 2);
}
for vertex in graph.vertices_found() {
for summand in vertex.pair().module().summands() {
let dim = summand.module().dim_vector();
assert!(dim[0] <= dim[1], "a preinjective summand {dim:?} appeared");
}
}
}
#[test]
fn the_work_unit_counts_stay_under_their_ceilings() {
let cases: [(&str, Arc<Algebra>, u64); 4] = [
("A_2", linear_an(2, f2()), 16_384),
("A_3", linear_an(3, f2()), 524_288),
("A_4", linear_an(4, f2()), 8_388_608),
("D_4", d4(f2()), 8_388_608),
];
for (name, algebra, ceiling) in cases {
let graph = walk(&algebra);
assert!(
graph.work_units() <= ceiling,
"{name}: {} units over the ceiling {ceiling}",
graph.work_units()
);
}
assert_eq!(
walk(&linear_an(3, f2())).work_units(),
walk(&linear_an(3, f5())).work_units()
);
}
#[test]
fn the_a2_walk_is_the_pentagon() {
for field in fields() {
let graph = walk(&linear_an(2, field));
assert_eq!(graph.len(), 5);
assert_eq!(graph.mutations().len(), 5);
let mut parts: Vec<(Vec<Vec<usize>>, Vec<u32>)> = graph
.pairs()
.map(|pair| {
(
pair.module().dim_vectors(),
pair.projective().vertices().to_vec(),
)
})
.collect();
parts.sort();
assert_eq!(
parts,
vec![
(vec![], vec![0, 1]),
(vec![vec![0, 1]], vec![0]),
(vec![vec![0, 1], vec![1, 1]], vec![]),
(vec![vec![1, 0]], vec![1]),
(vec![vec![1, 0], vec![1, 1]], vec![]),
]
);
let fac: Vec<&FacWitness> = graph
.vertices()
.iter()
.flat_map(|vertex| vertex.slots())
.filter_map(SlotRecord::fac_witness)
.collect();
assert_eq!(fac.len(), 1);
assert_eq!(fac[0].summand().dim_vector(), [1, 0]);
assert_eq!(fac[0].module().dim_vector(), [1, 1]);
assert_eq!(graph.vertices()[0].slots().len(), 2);
let minima = graph
.vertices()
.iter()
.filter(|vertex| vertex.pair().module().is_empty())
.count();
assert_eq!(minima, 1);
assert!(graph.mutations().iter().all(|edge| edge.target() != 0));
}
}
#[test]
fn two_runs_agree_on_order_and_witnesses() {
for field in fields() {
for algebra in [linear_an(3, field), radical_square_zero_cycle(3, field)] {
let first = walk(&algebra);
let second = walk(&algebra);
assert_eq!(render(&first), render(&second));
assert_eq!(first.work_units(), second.work_units());
}
}
}
#[test]
fn the_gate_refuses_a_witness_that_fails_its_recheck() {
let algebra = linear_an(2, f2());
let graph = walk(&algebra);
let work_units = graph.work_units();
let ClosureWitness {
mut vertices,
mutations,
..
} = graph.witness;
vertices[0].slots.pop();
match close(&algebra, vertices, mutations, work_units) {
Ok(_) => panic!("the gate handed out a graph whose recheck fails"),
Err(GraphError::Defect { reason }) => {
assert!(reason.contains("closure recheck failed"), "{reason}");
}
Err(other) => panic!("a failed recheck is a defect, not {other}"),
}
}
#[test]
fn the_gate_admits_an_intact_witness() {
let algebra = linear_an(2, f2());
let graph = walk(&algebra);
let work_units = graph.work_units();
let ClosureWitness {
vertices,
mutations,
..
} = graph.witness;
let regated = close(&algebra, vertices, mutations, work_units)
.expect("an intact witness passes the gate");
assert_eq!(regated.len(), 5);
assert_eq!(regated.work_units(), work_units);
}
#[test]
fn a_missing_slot_fails_the_closure_witness() {
let mut graph = walk(&linear_an(2, f2()));
assert!(graph.verify());
graph.witness.vertices[0].slots.pop();
assert!(!graph.witness.slots_resolved());
assert!(!graph.verify());
}
#[test]
fn a_duplicated_vertex_fails_the_closure_witness() {
let algebra = linear_an(2, f2());
let mut graph = walk(&algebra);
let (module, support) = regular_parts(&algebra).expect("A_2 has a regular pair");
let indices: Vec<usize> = (0..module.len()).collect();
let pair = SupportTauTiltingPair::classify_with_cache(module, support, &indices, None)
.expect("(A, 0) classifies")
.into_pair()
.expect("(A, 0) is a pair");
graph.witness.vertices.push(GraphVertex {
pair,
slots: Vec::new(),
});
assert!(!graph.witness.pairwise_distinct());
assert!(!graph.verify());
}
#[test]
fn a_retargeted_edge_fails_the_closure_witness() {
let mut graph = walk(&linear_an(3, f2()));
assert!(graph.witness.endpoints_bound());
let target = graph.witness.mutations[0].target;
let other = graph
.witness
.mutations
.iter()
.map(|edge| edge.target)
.find(|candidate| *candidate != target)
.expect("A_3 has more than one mutation target");
graph.witness.mutations[0].target = other;
assert!(!graph.witness.endpoints_bound());
assert!(!graph.verify());
}
#[test]
fn an_endpoint_witness_from_another_edge_fails() {
let mut graph = walk(&linear_an(3, f2()));
let borrowed = graph.witness.mutations[1].endpoint.clone();
graph.witness.mutations[0].endpoint = borrowed;
assert!(!graph.witness.endpoints_bound());
assert!(!graph.verify());
}
#[test]
fn a_broken_edge_list_is_not_connected_from_the_root() {
let graph = walk(&linear_an(3, f2()));
let all: Vec<(usize, usize)> = graph
.mutations()
.iter()
.map(|edge| (edge.source(), edge.target()))
.collect();
assert_eq!(
reachable_from_root(graph.len(), all.iter().copied()),
graph.len()
);
let cut: Vec<(usize, usize)> = all
.iter()
.copied()
.filter(|(source, _)| *source != 0)
.collect();
assert!(reachable_from_root(graph.len(), cut.iter().copied()) < graph.len());
assert_eq!(reachable_from_root(graph.len(), std::iter::empty()), 1);
}
#[test]
fn a_matrix_budget_stops_the_walk_before_allocating() {
let limits = MutationGraphLimits {
max_matrix_entries: 1,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&linear_an(3, f2()), &limits)
.expect("A_3 walks without a defect");
let graph = outcome.incomplete().expect("the budget stops the walk");
match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => {
assert_eq!(diagnostics.limit(), GraphLimit::MatrixEntries);
}
IncompleteReason::CertificationBlocked(blocker) => {
panic!("a matrix budget is no blocked certification: {blocker}")
}
}
}
#[test]
fn a_work_unit_budget_stops_the_walk() {
let limits = MutationGraphLimits {
max_work_units: 1,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&linear_an(3, f2()), &limits)
.expect("A_3 walks without a defect");
let graph = outcome.incomplete().expect("the budget stops the walk");
match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => {
assert_eq!(diagnostics.limit(), GraphLimit::WorkUnits);
assert_eq!(diagnostics.vertices_found(), 1);
assert_eq!(diagnostics.verified_slots(), 0);
}
IncompleteReason::CertificationBlocked(blocker) => {
panic!("a work budget is no blocked certification: {blocker}")
}
}
}
#[test]
fn a_closed_walk_never_charges_more_than_its_budget() {
let algebra = semisimple(1, f2());
let spent = walk(&algebra).work_units();
for max_work_units in 1..spent {
let limits = MutationGraphLimits {
max_work_units,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&algebra, &limits)
.expect("the one-vertex walk runs without a defect");
match outcome {
SupportTauTiltingGraphOutcome::Closed(graph) => panic!(
"a budget of {max_work_units} closed at {} units",
graph.work_units()
),
SupportTauTiltingGraphOutcome::Incomplete(graph) => match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => {
assert_eq!(diagnostics.limit(), GraphLimit::WorkUnits);
}
IncompleteReason::CertificationBlocked(blocker) => {
panic!("a work budget is no blocked certification: {blocker}")
}
},
}
}
let limits = MutationGraphLimits {
max_work_units: spent,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&algebra, &limits)
.expect("the one-vertex walk runs without a defect");
assert_eq!(
outcome
.closed()
.expect("the true count closes")
.work_units(),
spent
);
}
#[test]
fn a_mutation_budget_stops_the_walk() {
let limits = MutationGraphLimits {
max_directed_mutations: 2,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&linear_an(3, f2()), &limits)
.expect("A_3 walks without a defect");
let graph = outcome.incomplete().expect("the budget stops the walk");
assert_eq!(graph.verified_mutations().len(), 2);
match graph.reason() {
IncompleteReason::BudgetExhausted(diagnostics) => {
assert_eq!(diagnostics.limit(), GraphLimit::DirectedMutations);
}
IncompleteReason::CertificationBlocked(blocker) => {
panic!("a mutation budget is no blocked certification: {blocker}")
}
}
}
#[test]
fn blocked_certifications_never_read_as_budget_exhaustion() {
let algebra = linear_an(2, f2());
let blocked = BasicError::CertificationBlocked {
reason: "a summand stayed undetermined after 8 split attempts".to_string(),
};
assert!(basic_blocker(&blocked).is_some());
assert!(mutation_blocker(&MutationError::Basic(blocked.clone())).is_some());
assert!(support_blocker(&SupportTauError::Basic(blocked)).is_some());
assert!(
mutation_blocker(&MutationError::Indec(IndecError::Undetermined {
attempts: 8
}))
.is_some()
);
let undecided = SupportTauError::TauRigid(TauRigidError::Tau(TauError::AgreementUnknown {
nakayama_kernel: Module::zero(&algebra),
transpose_dual: Module::zero(&algebra),
reason: "an undetermined summand".to_string(),
}));
assert!(support_blocker(&undecided).is_some());
assert!(mutation_blocker(&MutationError::SupportTau(undecided)).is_some());
assert!(
mutation_blocker(&MutationError::SlotOutOfRange {
slot: 4,
summands: 2
})
.is_none()
);
assert!(
basic_blocker(&BasicError::NotBasic {
first: 0,
second: 1
})
.is_none()
);
}
#[test]
#[ignore = "exhaustive tier of docs/v0.5-design.md section 11"]
fn the_kronecker_mutations_recheck() {
let limits = MutationGraphLimits {
max_vertices: 16,
..MutationGraphLimits::default()
};
let outcome = support_tau_tilting_graph(&kronecker(2, f2()), &limits)
.expect("the Kronecker walk runs without a defect");
let graph = outcome.incomplete().expect("the walk stopped short");
assert!(graph.verify_parts());
}
#[test]
#[ignore = "exhaustive tier of docs/v0.5-design.md section 11"]
fn the_d4_closure_witness_and_the_catalog_route_agree() {
for field in fields() {
let algebra = d4(field);
let graph = walk(&algebra);
assert!(graph.verify());
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("D_4 is Dynkin");
let enumeration = enumerate_over_catalog(&catalog).expect("the catalog route runs");
let walked: Vec<&SupportTauTiltingPair> = graph.pairs().collect();
let listed: Vec<&SupportTauTiltingPair> = enumeration.pairs().iter().collect();
assert!(same_pair_set(&walked, &listed));
assert!(same_pair_set(&listed, &walked));
}
}
}