use std::fmt;
use crate::field::{Fp, PrimeField};
use crate::order::word_cmp;
use crate::quiver::{ArrowId, PathWord, Quiver, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RelationError {
Empty,
ZeroCoefficient { index: usize },
NonCanonicalCoefficient { index: usize },
DuplicateWord { index: usize },
InvalidWord { index: usize, error: QuiverError },
WordTooShort { index: usize, len: usize },
MixedSource { index: usize },
MixedTarget { index: usize },
}
impl fmt::Display for RelationError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Empty => f.write_str("relation needs at least one term"),
Self::ZeroCoefficient { index } => {
write!(f, "term {index} has coefficient zero")
}
Self::NonCanonicalCoefficient { index } => write!(
f,
"term {index} has a coefficient outside 0..p; it was made for another field"
),
Self::DuplicateWord { index } => {
write!(f, "term {index} repeats the word of an earlier term")
}
Self::InvalidWord { index, error } => {
write!(f, "term {index} is not a path: {error}")
}
Self::WordTooShort { index, len } => write!(
f,
"term {index} has length {len}; admissibility needs length >= 2"
),
Self::MixedSource { index } => {
write!(f, "term {index} starts at a different vertex than term 0")
}
Self::MixedTarget { index } => {
write!(f, "term {index} ends at a different vertex than term 0")
}
}
}
}
impl std::error::Error for RelationError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::InvalidWord { error, .. } => Some(error),
_ => None,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Relation {
terms: Vec<(Fp, PathWord)>,
}
impl Relation {
pub fn new(
quiver: &Quiver,
field: PrimeField,
terms: Vec<(Fp, Vec<ArrowId>)>,
) -> Result<Relation, RelationError> {
if terms.is_empty() {
return Err(RelationError::Empty);
}
let mut checked: Vec<(Fp, PathWord)> = Vec::with_capacity(terms.len());
let mut seen = std::collections::BTreeSet::new();
for (index, (coeff, arrows)) in terms.into_iter().enumerate() {
if coeff.is_zero() {
return Err(RelationError::ZeroCoefficient { index });
}
if coeff.raw() >= field.modulus() {
return Err(RelationError::NonCanonicalCoefficient { index });
}
if arrows.len() < 2 {
return Err(RelationError::WordTooShort {
index,
len: arrows.len(),
});
}
let word = PathWord::from_arrows(quiver, &arrows)
.map_err(|error| RelationError::InvalidWord { index, error })?;
if let Some((_, first)) = checked.first() {
if word.source() != first.source() {
return Err(RelationError::MixedSource { index });
}
if word.target() != first.target() {
return Err(RelationError::MixedTarget { index });
}
}
if !seen.insert(arrows) {
return Err(RelationError::DuplicateWord { index });
}
checked.push((coeff, word));
}
checked.sort_by(|(_, a), (_, b)| word_cmp(b.arrows(), a.arrows()));
Ok(Relation { terms: checked })
}
#[inline]
pub fn terms(&self) -> &[(Fp, PathWord)] {
&self.terms
}
#[inline]
pub fn leading(&self) -> (&Fp, &PathWord) {
let (coeff, word) = &self.terms[0];
(coeff, word)
}
#[inline]
pub fn source(&self) -> u32 {
self.terms[0].1.source()
}
#[inline]
pub fn target(&self) -> u32 {
self.terms[0].1.target()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Presentation {
quiver: Quiver,
field: PrimeField,
relations: Vec<Relation>,
}
impl Presentation {
pub fn new(
quiver: Quiver,
field: PrimeField,
relations: Vec<Relation>,
) -> Result<Presentation, RelationError> {
for relation in &relations {
for (index, (coeff, word)) in relation.terms.iter().enumerate() {
if coeff.is_zero() {
return Err(RelationError::ZeroCoefficient { index });
}
if coeff.raw() >= field.modulus() {
return Err(RelationError::NonCanonicalCoefficient { index });
}
word.validate_in(&quiver)
.map_err(|error| RelationError::InvalidWord { index, error })?;
}
}
Ok(Presentation {
quiver,
field,
relations,
})
}
#[inline]
pub fn quiver(&self) -> &Quiver {
&self.quiver
}
#[inline]
pub fn field(&self) -> PrimeField {
self.field
}
#[inline]
pub fn relations(&self) -> &[Relation] {
&self.relations
}
}
#[cfg(test)]
mod tests {
use super::*;
fn commutative_square() -> Quiver {
Quiver::new(4, &[(0, 1), (1, 3), (0, 2), (2, 3)]).unwrap()
}
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn ids(raw: &[u32]) -> Vec<ArrowId> {
raw.iter().copied().map(ArrowId).collect()
}
#[test]
fn terms_sort_strictly_descending() {
let q = commutative_square();
let f = f5();
let r = Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.elem(-1), ids(&[2, 3]))],
)
.unwrap();
assert_eq!(r.terms().len(), 2);
assert_eq!(r.terms()[0].1.arrows(), ids(&[2, 3]).as_slice());
assert_eq!(r.terms()[1].1.arrows(), ids(&[0, 1]).as_slice());
let (lead_coeff, lead_word) = r.leading();
assert_eq!(*lead_coeff, f.elem(-1));
assert_eq!(lead_word.arrows(), ids(&[2, 3]).as_slice());
assert_eq!((r.source(), r.target()), (0, 3));
}
#[test]
fn empty_relation_rejected() {
assert_eq!(
Relation::new(&commutative_square(), f5(), Vec::new()),
Err(RelationError::Empty)
);
}
#[test]
fn zero_coefficient_rejected() {
let q = commutative_square();
let f = f5();
assert_eq!(
Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.zero(), ids(&[2, 3]))]
),
Err(RelationError::ZeroCoefficient { index: 1 })
);
}
#[test]
fn non_canonical_coefficient_rejected() {
let q = commutative_square();
let foreign = PrimeField::new(7).unwrap().elem(6);
assert_eq!(
Relation::new(&q, f5(), vec![(foreign, ids(&[0, 1]))]),
Err(RelationError::NonCanonicalCoefficient { index: 0 })
);
}
#[test]
fn duplicate_word_rejected() {
let q = commutative_square();
let f = f5();
assert_eq!(
Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.elem(2), ids(&[0, 1]))]
),
Err(RelationError::DuplicateWord { index: 1 })
);
}
#[test]
fn non_composable_word_rejected() {
let q = commutative_square();
let f = f5();
assert_eq!(
Relation::new(&q, f, vec![(f.elem(1), ids(&[0, 3]))]),
Err(RelationError::InvalidWord {
index: 0,
error: QuiverError::NotComposable { position: 0 },
})
);
}
#[test]
fn short_words_rejected() {
let q = commutative_square();
let f = f5();
assert_eq!(
Relation::new(&q, f, vec![(f.elem(1), ids(&[0]))]),
Err(RelationError::WordTooShort { index: 0, len: 1 })
);
assert_eq!(
Relation::new(&q, f, vec![(f.elem(1), Vec::new())]),
Err(RelationError::WordTooShort { index: 0, len: 0 })
);
}
#[test]
fn mixed_source_rejected() {
let q = Quiver::new(4, &[(0, 1), (1, 3), (2, 1), (1, 3)]).unwrap();
let f = f5();
assert_eq!(
Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.elem(1), ids(&[2, 3]))]
),
Err(RelationError::MixedSource { index: 1 })
);
}
#[test]
fn mixed_target_rejected() {
let q = Quiver::new(4, &[(0, 1), (1, 3), (0, 1), (1, 2)]).unwrap();
let f = f5();
assert_eq!(
Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.elem(1), ids(&[2, 3]))]
),
Err(RelationError::MixedTarget { index: 1 })
);
}
#[test]
fn presentation_accepts_its_own_relations() {
let q = commutative_square();
let f = f5();
let r = Relation::new(
&q,
f,
vec![(f.elem(1), ids(&[0, 1])), (f.elem(-1), ids(&[2, 3]))],
)
.unwrap();
let p = Presentation::new(q.clone(), f, vec![r.clone()]).unwrap();
assert_eq!(p.quiver(), &q);
assert_eq!(p.field(), f);
assert_eq!(p.relations(), &[r]);
}
#[test]
fn presentation_rejects_relations_over_another_quiver() {
let f = f5();
let other = Quiver::new(3, &[(0, 1), (1, 2)]).unwrap();
let r = Relation::new(&other, f, vec![(f.elem(1), ids(&[0, 1]))]).unwrap();
assert!(matches!(
Presentation::new(commutative_square(), f, vec![r]),
Err(RelationError::InvalidWord { index: 0, .. })
));
}
#[test]
fn presentation_rejects_relations_over_another_field() {
let q = commutative_square();
let f7 = PrimeField::new(7).unwrap();
let r = Relation::new(&q, f7, vec![(f7.elem(6), ids(&[0, 1]))]).unwrap();
assert_eq!(
Presentation::new(q, f5(), vec![r]),
Err(RelationError::NonCanonicalCoefficient { index: 0 })
);
}
}