use std::collections::{HashMap, VecDeque};
use std::fmt;
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::ar::TauError;
use crate::basic::{
BasicDecomposition, BasicError, PairFingerprint, ProjectiveSupport, SupportPairIsoOutcome,
SupportPairIsoWitness, pair_iso,
};
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::indecomposable_iso;
use crate::module::{Module, direct_sum};
use crate::mutation::{FacWitness, Mutation, MutationError, SlotOutcome, mutate_at_with_cache};
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,
},
}
impl fmt::Display for GraphError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Basic(error) => write!(f, "basic layer: {error}"),
Self::SupportTau(error) => write!(f, "support tau-tilting layer: {error}"),
Self::Mutation(error) => write!(f, "mutation layer: {error}"),
Self::Defect { reason } => write!(f, "internal cross-check failed: {reason}"),
}
}
}
impl std::error::Error for GraphError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::Basic(error) => Some(error),
Self::SupportTau(error) => Some(error),
Self::Mutation(error) => Some(error),
Self::Defect { .. } => None,
}
}
}
impl From<BasicError> for GraphError {
fn from(error: BasicError) -> GraphError {
GraphError::Basic(error)
}
}
impl From<SupportTauError> for GraphError {
fn from(error: SupportTauError) -> GraphError {
GraphError::SupportTau(error)
}
}
impl From<MutationError> for GraphError {
fn from(error: MutationError) -> GraphError {
GraphError::Mutation(error)
}
}
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,
}
impl fmt::Display for GraphLimit {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Vertices => f.write_str("max_vertices"),
Self::DirectedMutations => f.write_str("max_directed_mutations"),
Self::WorkUnits => f.write_str("max_work_units"),
Self::MatrixEntries => f.write_str("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 {
#[inline]
pub fn vertices_found(&self) -> usize {
self.vertices_found
}
#[inline]
pub fn verified_slots(&self) -> usize {
self.verified_slots
}
#[inline]
pub fn new_vertices(&self) -> usize {
self.new_vertices
}
#[inline]
pub fn repeated_endpoints(&self) -> usize {
self.repeated_endpoints
}
#[inline]
pub fn frontier(&self) -> usize {
self.frontier
}
#[inline]
pub fn vertex(&self) -> usize {
self.vertex
}
#[inline]
pub fn slot(&self) -> Option<usize> {
self.slot
}
#[inline]
pub fn open_slots(&self) -> usize {
self.open_slots
}
#[inline]
pub fn work_units(&self) -> u64 {
self.work_units
}
#[inline]
pub fn limit(&self) -> GraphLimit {
self.limit
}
}
impl fmt::Display for GraphBudgetDiagnostics {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{} ran out at vertex {} slot {:?}: {} vertices, {} slots decided, {} open, \
frontier {}, {} work units",
self.limit,
self.vertex,
self.slot,
self.vertices_found,
self.verified_slots,
self.open_slots,
self.frontier,
self.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 {
#[inline]
pub fn vertex(&self) -> usize {
self.vertex
}
#[inline]
pub fn slot(&self) -> Option<usize> {
self.slot
}
#[inline]
pub fn reason(&self) -> &str {
&self.reason
}
#[inline]
pub fn vertices_found(&self) -> usize {
self.vertices_found
}
#[inline]
pub fn work_units(&self) -> u64 {
self.work_units
}
}
impl fmt::Display for CertificationBlocker {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"certification blocked at vertex {} slot {:?}: {}",
self.vertex, self.slot, self.reason
)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum IncompleteReason {
BudgetExhausted(GraphBudgetDiagnostics),
CertificationBlocked(CertificationBlocker),
}
impl fmt::Display for IncompleteReason {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::BudgetExhausted(diagnostics) => write!(f, "{diagnostics}"),
Self::CertificationBlocked(blocker) => write!(f, "{blocker}"),
}
}
}
#[derive(Debug)]
pub enum SlotRecord {
LeftMutation {
mutation: usize,
},
NoLeftMutation(FacWitness),
}
impl SlotRecord {
#[inline]
pub fn mutation(&self) -> Option<usize> {
match self {
Self::LeftMutation { mutation } => Some(*mutation),
Self::NoLeftMutation(_) => None,
}
}
#[inline]
pub fn fac_witness(&self) -> Option<&FacWitness> {
match self {
Self::NoLeftMutation(witness) => Some(witness),
Self::LeftMutation { .. } => None,
}
}
}
#[derive(Debug)]
pub struct GraphVertex {
pair: SupportTauTiltingPair,
slots: Vec<SlotRecord>,
}
impl GraphVertex {
#[inline]
pub fn pair(&self) -> &SupportTauTiltingPair {
&self.pair
}
#[inline]
pub fn slots(&self) -> &[SlotRecord] {
&self.slots
}
}
#[derive(Debug)]
pub struct VerifiedMutation {
source: usize,
slot: usize,
target: usize,
mutation: Mutation,
endpoint: SupportPairIsoWitness,
}
impl VerifiedMutation {
#[inline]
pub fn source(&self) -> usize {
self.source
}
#[inline]
pub fn slot(&self) -> usize {
self.slot
}
#[inline]
pub fn target(&self) -> usize {
self.target
}
#[inline]
pub fn mutation(&self) -> &Mutation {
&self.mutation
}
#[inline]
pub fn endpoint(&self) -> &SupportPairIsoWitness {
&self.endpoint
}
}
fn reachable_from_root(vertex_count: usize, edges: &[(usize, usize)]) -> usize {
if vertex_count == 0 {
return 0;
}
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);
}
}
let mut seen = vec![false; vertex_count];
seen[0] = true;
let mut queue = VecDeque::from([0usize]);
let mut count = 1;
while let Some(v) = queue.pop_front() {
for &w in &out[v] {
if !seen[w] {
seen[w] = true;
count += 1;
queue.push_back(w);
}
}
}
count
}
#[derive(Debug)]
pub struct ClosureWitness {
algebra: Arc<Algebra>,
vertices: Vec<GraphVertex>,
mutations: Vec<VerifiedMutation>,
}
impl ClosureWitness {
#[inline]
pub fn algebra(&self) -> &Arc<Algebra> {
&self.algebra
}
#[inline]
pub fn vertices(&self) -> &[GraphVertex] {
&self.vertices
}
#[inline]
pub fn mutations(&self) -> &[VerifiedMutation] {
&self.mutations
}
fn vertices_certified(&self) -> bool {
self.vertices.iter().all(|v| {
Arc::ptr_eq(v.pair.module().module().algebra(), &self.algebra) && v.pair.verify()
})
}
fn pairwise_distinct(&self) -> bool {
let mut fingerprints = Vec::with_capacity(self.vertices.len());
for v in &self.vertices {
match PairFingerprint::new(v.pair.module(), &v.pair.projective()) {
Ok(fingerprint) => fingerprints.push(fingerprint),
Err(_) => return false,
}
}
for (i, left) in self.vertices.iter().enumerate() {
for (j, right) in self.vertices.iter().enumerate().skip(i + 1) {
if fingerprints[i] != fingerprints[j] {
continue;
}
match pair_iso(
left.pair.module(),
&left.pair.projective(),
right.pair.module(),
&right.pair.projective(),
) {
Ok(SupportPairIsoOutcome::NotIsomorphic(_)) => {}
_ => return false,
}
}
}
true
}
fn root_is_regular(&self) -> bool {
let Some(root) = self.vertices.first() else {
return false;
};
let Ok((module, support)) = regular_parts(&self.algebra) else {
return false;
};
matches!(
pair_iso(
&module,
&support,
root.pair.module(),
&root.pair.projective()
),
Ok(SupportPairIsoOutcome::Isomorphic(_))
)
}
fn slots_resolved(&self) -> bool {
let mut referenced = vec![false; self.mutations.len()];
for (v, vertex) in self.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 Some(edge) = self.mutations.get(*mutation) else {
return false;
};
if referenced[*mutation] {
return false;
}
referenced[*mutation] = true;
if edge.source != v || edge.slot != slot {
return false;
}
if edge.target >= self.vertices.len() {
return false;
}
if edge.mutation.slot() != slot || !edge.mutation.verify() {
return false;
}
if !edge
.mutation
.witness()
.source_module()
.ptr_eq(vertex.pair.module().module())
|| edge.mutation.witness().source_projective()
!= vertex.pair.projective().vertices()
{
return false;
}
}
SlotRecord::NoLeftMutation(witness) => {
if !witness.verify() {
return false;
}
let summands = vertex.pair.module().summands();
let Some(x) = summands.get(slot) else {
return false;
};
if !witness.summand().ptr_eq(x.module()) {
return false;
}
let kept = summands
.iter()
.enumerate()
.filter(|(i, _)| *i != slot)
.map(|(_, other)| other.module());
let stored = witness.summands();
if stored.len() + 1 != summands.len() {
return false;
}
if !kept.zip(stored).all(|(a, b)| a.ptr_eq(b)) {
return false;
}
}
}
}
}
referenced.iter().all(|used| *used)
}
fn endpoints_bound(&self) -> bool {
for edge in &self.mutations {
let Some(vertex) = self.vertices.get(edge.target) else {
return false;
};
let built = edge.mutation.target();
if built.projective().vertices() != vertex.pair.projective().vertices() {
return false;
}
let from = built.module().summands();
let to = vertex.pair.module().summands();
let bijection = edge.endpoint.bijection();
if bijection.len() != from.len() || from.len() != to.len() {
return false;
}
if !edge.endpoint.verify() {
return false;
}
for (i, &j) in bijection.iter().enumerate() {
let (Some(source), Some(target)) = (from.get(i), to.get(j)) else {
return false;
};
let forward = &edge.endpoint.forward()[i];
let backward = &edge.endpoint.backward()[i];
if !forward.source().ptr_eq(source.module())
|| !forward.target().ptr_eq(target.module())
|| !backward.source().ptr_eq(target.module())
|| !backward.target().ptr_eq(source.module())
{
return false;
}
}
}
true
}
fn connected(&self) -> bool {
let edges: Vec<(usize, usize)> = self
.mutations
.iter()
.map(|edge| (edge.source, edge.target))
.collect();
reachable_from_root(self.vertices.len(), &edges) == 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 {
if edge.target >= incoming.len() {
return false;
}
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;
if incoming[v] != fac + vertex.pair.projective().len() {
return false;
}
if outgoing + incoming[v] != n {
return false;
}
}
true
}
pub fn verify(&self) -> bool {
self.vertices_certified()
&& self.pairwise_distinct()
&& self.root_is_regular()
&& self.slots_resolved()
&& self.endpoints_bound()
&& self.connected()
&& self.n_regular()
}
}
#[derive(Debug)]
pub struct ClosedSupportTauTiltingGraph {
witness: ClosureWitness,
work_units: u64,
}
impl ClosedSupportTauTiltingGraph {
#[inline]
pub fn algebra(&self) -> &Arc<Algebra> {
self.witness.algebra()
}
pub fn pairs(&self) -> impl ExactSizeIterator<Item = &SupportTauTiltingPair> {
self.witness.vertices().iter().map(GraphVertex::pair)
}
#[inline]
pub fn vertices(&self) -> &[GraphVertex] {
self.witness.vertices()
}
#[inline]
pub fn mutations(&self) -> &[VerifiedMutation] {
self.witness.mutations()
}
#[inline]
pub fn len(&self) -> usize {
self.witness.vertices().len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.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
}
#[inline]
pub fn witness(&self) -> &ClosureWitness {
&self.witness
}
#[inline]
pub fn work_units(&self) -> u64 {
self.work_units
}
pub fn verify(&self) -> bool {
self.witness.verify()
}
}
#[derive(Debug)]
pub struct IncompleteSupportTauTiltingGraph {
algebra: Arc<Algebra>,
vertices: Vec<GraphVertex>,
mutations: Vec<VerifiedMutation>,
reason: IncompleteReason,
work_units: u64,
}
impl IncompleteSupportTauTiltingGraph {
#[inline]
pub fn algebra(&self) -> &Arc<Algebra> {
&self.algebra
}
#[inline]
pub fn vertices_found(&self) -> &[GraphVertex] {
&self.vertices
}
#[inline]
pub fn verified_mutations(&self) -> &[VerifiedMutation] {
&self.mutations
}
#[inline]
pub fn reason(&self) -> &IncompleteReason {
&self.reason
}
#[inline]
pub fn work_units(&self) -> u64 {
self.work_units
}
pub fn verify_parts(&self) -> bool {
self.vertices.iter().all(|v| {
Arc::ptr_eq(v.pair.module().module().algebra(), &self.algebra) && v.pair.verify()
}) && self
.mutations
.iter()
.all(|edge| edge.mutation.verify() && edge.endpoint.verify())
}
}
#[derive(Debug)]
pub enum SupportTauTiltingGraphOutcome {
Closed(ClosedSupportTauTiltingGraph),
Incomplete(IncompleteSupportTauTiltingGraph),
}
impl SupportTauTiltingGraphOutcome {
#[inline]
pub fn is_closed(&self) -> bool {
matches!(self, Self::Closed(_))
}
#[inline]
pub fn closed(&self) -> Option<&ClosedSupportTauTiltingGraph> {
match self {
Self::Closed(graph) => Some(graph),
Self::Incomplete(_) => None,
}
}
#[inline]
pub fn incomplete(&self) -> Option<&IncompleteSupportTauTiltingGraph> {
match self {
Self::Closed(_) => None,
Self::Incomplete(graph) => Some(graph),
}
}
#[inline]
pub fn into_closed(self) -> Option<ClosedSupportTauTiltingGraph> {
match self {
Self::Closed(graph) => Some(graph),
Self::Incomplete(_) => None,
}
}
}
fn regular_parts(
algebra: &Arc<Algebra>,
) -> Result<(BasicDecomposition, ProjectiveSupport), BasicError> {
let parts: Vec<Module> = (0..algebra.quiver().num_vertices())
.map(|v| Module::projective(algebra, v))
.collect();
let refs: Vec<&Module> = parts.iter().collect();
let module = if refs.is_empty() {
Module::zero(algebra)
} else {
direct_sum(&refs).0
};
Ok((
BasicDecomposition::new(&module)?,
ProjectiveSupport::new(algebra, &[])?,
))
}
#[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)
}
fn over_work_budget(&self) -> Option<Stop> {
if self.ledger.units > self.limits.max_work_units {
Some(Stop::Budget(GraphLimit::WorkUnits))
} else {
None
}
}
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;
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 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), graph.len());
let cut: Vec<(usize, usize)> = all
.iter()
.copied()
.filter(|(source, _)| *source != 0)
.collect();
assert!(reachable_from_root(graph.len(), &cut) < graph.len());
assert_eq!(reachable_from_root(graph.len(), &[]), 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));
}
}
}