use std::sync::Arc;
use crate::algebra::{Algebra, AlgebraBuildError, monomial_algebra};
use crate::field::PrimeField;
use crate::quiver::ArrowId;
use super::shape::{Kind, Shape, monomial_ideal};
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct GentleKey {
vertices: u32,
arrows: Vec<(u32, u32)>,
relations: Vec<(ArrowId, ArrowId)>,
}
impl GentleKey {
accessor_methods! {
pub vertices() -> u32 = |this| this.vertices;
pub arrows() -> &[(u32, u32)] = |this| &this.arrows;
pub relations() -> &[(ArrowId, ArrowId)] = |this| &this.relations;
}
pub fn algebra(&self, field: PrimeField) -> Result<Arc<Algebra>, AlgebraBuildError> {
let ideal = monomial_ideal(self.vertices, &self.arrows, &self.relations);
monomial_algebra(&ideal, field)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GentleLabeling {
key: GentleKey,
vertex_map: Vec<u32>,
arrow_map: Vec<ArrowId>,
}
impl GentleLabeling {
pub(crate) fn new(shape: &Shape) -> GentleLabeling {
let starts = (0..shape.arrows().len() as u32).map(ArrowId);
starts
.map(|start| relabel(shape, start))
.min_by(|left, right| left.key.cmp(&right.key))
.unwrap_or_else(|| GentleLabeling {
key: GentleKey {
vertices: shape.vertices(),
arrows: Vec::new(),
relations: Vec::new(),
},
vertex_map: (0..shape.vertices()).collect(),
arrow_map: Vec::new(),
})
}
accessor_methods! {
pub key() -> &GentleKey = |this| &this.key;
pub vertex_map() -> &[u32] = |this| &this.vertex_map;
pub arrow_map() -> &[ArrowId] = |this| &this.arrow_map;
}
pub fn into_key(self) -> GentleKey {
self.key
}
}
fn relabel(shape: &Shape, start: ArrowId) -> GentleLabeling {
let order = walk(shape, start);
let mut arrow_map = vec![ArrowId(0); order.len()];
for (label, arrow) in order.iter().enumerate() {
arrow_map[arrow.index()] = ArrowId(label as u32);
}
let vertex_map = vertex_labels(shape, &order);
let arrows = order
.iter()
.map(|&arrow| {
let (source, target) = shape.arrows()[arrow.index()];
(vertex_map[source as usize], vertex_map[target as usize])
})
.collect();
let relations = order
.iter()
.enumerate()
.filter_map(|(label, &arrow)| {
let next = shape.successor(Kind::Forbidden, arrow)?;
Some((ArrowId(label as u32), arrow_map[next.index()]))
})
.collect();
GentleLabeling {
key: GentleKey {
vertices: shape.vertices(),
arrows,
relations,
},
vertex_map,
arrow_map,
}
}
fn walk(shape: &Shape, start: ArrowId) -> Vec<ArrowId> {
let mut seen = vec![false; shape.arrows().len()];
seen[start.index()] = true;
let mut order = vec![start];
let mut position = 0;
while let Some(&arrow) = order.get(position) {
for next in moves(shape, arrow).into_iter().flatten() {
if !seen[next.index()] {
seen[next.index()] = true;
order.push(next);
}
}
position += 1;
}
assert_eq!(
order.len(),
seen.len(),
"the canonical walk missed an arrow of a connected quiver; library bug"
);
order
}
fn moves(shape: &Shape, arrow: ArrowId) -> [Option<ArrowId>; 6] {
[
shape.successor(Kind::Permitted, arrow),
shape.successor(Kind::Forbidden, arrow),
shape.predecessor(Kind::Permitted, arrow),
shape.predecessor(Kind::Forbidden, arrow),
shape.outgoing_sibling(arrow),
shape.incoming_sibling(arrow),
]
}
fn vertex_labels(shape: &Shape, order: &[ArrowId]) -> Vec<u32> {
let mut labels = vec![u32::MAX; shape.vertices() as usize];
let mut next = 0;
for &(source, target) in order.iter().map(|arrow| &shape.arrows()[arrow.index()]) {
for vertex in [source, target] {
if labels[vertex as usize] == u32::MAX {
labels[vertex as usize] = next;
next += 1;
}
}
}
assert_eq!(
next,
shape.vertices(),
"a vertex of a connected quiver has no arrow; library bug"
);
labels
}