use std::sync::Arc;
use crate::algebra::Algebra;
use crate::arquiver::{CatalogProvenance, IndecomposableCatalog};
use crate::basic::{
BasicDecomposition, PairFingerprint, ProjectiveSupport, SupportPairIsoOutcome, pair_iso,
pairwise_distinct_by,
};
use crate::hom::hom_dim;
use crate::taurigid::TauCache;
use super::errors::SupportTauError;
use super::pair::{SupportTauTiltingClassification, SupportTauTiltingPair};
struct CatalogWalk<'a> {
catalog: &'a IndecomposableCatalog,
algebra: Arc<Algebra>,
vertices: usize,
tau_hom: Vec<Vec<usize>>,
cache: TauCache,
pairs: Vec<SupportTauTiltingPair>,
nodes: usize,
}
impl CatalogWalk<'_> {
fn extends_tau_rigid(&self, chosen: &[usize], i: usize) -> bool {
self.tau_hom[i][i] == 0
&& chosen
.iter()
.all(|&j| self.tau_hom[i][j] == 0 && self.tau_hom[j][i] == 0)
}
fn walk(&mut self, chosen: &mut Vec<usize>, start: usize) -> Result<(), SupportTauError> {
self.emit(chosen)?;
if chosen.len() == self.vertices {
return Ok(());
}
for i in start..self.catalog.len() {
if self.extends_tau_rigid(chosen, i) {
chosen.push(i);
self.nodes += 1;
self.walk(chosen, i + 1)?;
chosen.pop();
}
}
Ok(())
}
fn emit(&mut self, chosen: &[usize]) -> Result<(), SupportTauError> {
let support: Vec<u32> = (0..self.vertices as u32)
.filter(|&v| self.vanishes_at(chosen, v))
.collect();
if support.len() + chosen.len() != self.vertices {
return Ok(());
}
let module = BasicDecomposition::from_catalog(self.catalog, chosen)?;
let indices = chosen.to_vec();
let projective = ProjectiveSupport::new(&self.algebra, &support)?;
let classification = SupportTauTiltingPair::classify_with_cache(
module,
projective,
&indices,
Some(&mut self.cache),
)?;
match classification {
SupportTauTiltingClassification::Pair(pair) => {
self.pairs.push(pair);
Ok(())
}
SupportTauTiltingClassification::Rejected(rejection) => Err(SupportTauError::Defect {
reason: format!(
"the tables admitted the subset {chosen:?} with support {support:?} and the \
certified route rejected it: {rejection}"
),
}),
}
}
fn vanishes_at(&self, chosen: &[usize], vertex: u32) -> bool {
chosen
.iter()
.all(|&i| self.catalog.entries()[i].module().dim_vector()[vertex as usize] == 0)
}
}
pub struct CatalogEnumeration {
algebra: Arc<Algebra>,
provenance: CatalogProvenance,
catalog_len: usize,
pub(super) pairs: Vec<SupportTauTiltingPair>,
nodes_visited: usize,
}
debug_fields!(CatalogEnumeration |this| {
"provenance" => this.provenance;
"catalog_len" => this.catalog_len;
"pairs" => this.pairs.len();
"nodes_visited" => this.nodes_visited;
});
impl CatalogEnumeration {
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub provenance() -> CatalogProvenance = |this| this.provenance;
pub catalog_len() -> usize = |this| this.catalog_len;
pub pairs() -> &[SupportTauTiltingPair] = |this| &this.pairs;
pub len() -> usize = |this| this.pairs.len();
pub is_empty() -> bool = |this| this.pairs.is_empty();
pub nodes_visited() -> usize = |this| this.nodes_visited;
}
pub fn histogram(&self) -> Vec<usize> {
let vertices = self.algebra.quiver().num_vertices() as usize;
let mut out = vec![0; vertices + 1];
for pair in &self.pairs {
out[pair.module().len()] += 1;
}
out
}
pub fn verify(&self) -> bool {
pairwise_distinct_by(
&self.pairs,
|pair| {
(Arc::ptr_eq(pair.module().module().algebra(), &self.algebra) && pair.verify())
.then(|| PairFingerprint::new(pair.module(), &pair.projective()).ok())
.flatten()
},
|left, right| {
matches!(
pair_iso(
left.module(),
&left.projective(),
right.module(),
&right.projective(),
),
Ok(SupportPairIsoOutcome::NotIsomorphic(_))
)
},
)
}
}
pub fn enumerate_over_catalog(
catalog: &IndecomposableCatalog,
) -> Result<CatalogEnumeration, SupportTauError> {
let algebra = catalog.algebra().clone();
let vertices = algebra.quiver().num_vertices() as usize;
let mut cache = TauCache::new();
let mut translates = Vec::with_capacity(catalog.len());
for entry in catalog.entries() {
translates.push(cache.tau_of(entry.module())?.clone());
}
let mut tau_hom = vec![vec![0usize; catalog.len()]; catalog.len()];
for (i, x) in catalog.entries().iter().enumerate() {
for (j, translate) in translates.iter().enumerate() {
if !translate.is_zero() {
tau_hom[i][j] = hom_dim(x.module(), translate)?;
}
}
}
let mut walk = CatalogWalk {
catalog,
algebra: algebra.clone(),
vertices,
tau_hom,
cache,
pairs: Vec::new(),
nodes: 1,
};
walk.walk(&mut Vec::with_capacity(vertices), 0)?;
Ok(CatalogEnumeration {
algebra,
provenance: catalog.provenance(),
catalog_len: catalog.len(),
pairs: walk.pairs,
nodes_visited: walk.nodes,
})
}
pub fn enumerate_over_algebra(
algebra: &Arc<Algebra>,
) -> Result<CatalogEnumeration, SupportTauError> {
let catalog = IndecomposableCatalog::complete(algebra)?;
enumerate_over_catalog(&catalog)
}