auslander 0.9.0

Computational representation theory of finite-dimensional bound quiver algebras
Documentation
use crate::algebra::{Algebra, BasisIdx};

use super::super::limits::{BarInput, HochschildError};

pub(crate) fn tuple_starts(algebra: &Algebra, degree: usize) -> Vec<Vec<usize>> {
    let vertices = algebra.quiver().num_vertices() as usize;
    let mut starts = vec![vec![1; vertices]];
    for _ in 0..degree {
        let previous = starts.last().expect("degree zero starts exist");
        let next = (0..vertices)
            .map(|source| {
                algebra.paths_from(source as u32)[1..]
                    .iter()
                    .try_fold(0usize, |total, &word| {
                        total.checked_add(previous[algebra.basis()[word].target() as usize])
                    })
                    .expect("a completed tuple count fits usize")
            })
            .collect();
        starts.push(next);
    }
    starts
}

fn select_word(
    algebra: &Algebra,
    candidates: impl Iterator<Item = BasisIdx>,
    remaining: &[usize],
    rank: &mut usize,
) -> Option<BasisIdx> {
    for word in candidates {
        let block = remaining[algebra.basis()[word].target() as usize];
        if *rank < block {
            return Some(word);
        }
        *rank -= block;
    }
    None
}

pub(crate) fn decode_tuple(
    algebra: &Algebra,
    degree: usize,
    tuple_rank: usize,
    starts: &[Vec<usize>],
    tuple: &mut Vec<BasisIdx>,
) {
    let first_word = algebra.quiver().num_vertices() as usize;
    tuple.clear();
    let mut suffix_rank = tuple_rank;
    for position in 0..degree {
        let remaining = &starts[degree - position - 1];
        let word = if let Some(&previous) = tuple.last() {
            let source = algebra.basis()[previous].target();
            select_word(
                algebra,
                algebra.paths_from(source)[1..].iter().copied(),
                remaining,
                &mut suffix_rank,
            )
        } else {
            select_word(
                algebra,
                first_word..algebra.dim(),
                remaining,
                &mut suffix_rank,
            )
        };
        tuple.push(word.expect("a measured tuple rank decodes"));
    }
}

pub(crate) fn walk_tuples<E>(
    algebra: &Algebra,
    degree: usize,
    tuples: usize,
    starts: &[Vec<usize>],
    mut callback: impl FnMut(usize, &[BasisIdx], u32, u32) -> Result<(), E>,
) -> Result<(), E> {
    let vertices = algebra.quiver().num_vertices();
    if degree == 0 {
        for vertex in 0..vertices {
            callback(vertex as usize, &[], vertex, vertex)?;
        }
        return Ok(());
    }
    let mut tuple: Vec<BasisIdx> = Vec::with_capacity(degree);
    for tuple_rank in 0..tuples {
        decode_tuple(algebra, degree, tuple_rank, starts, &mut tuple);
        let first = &algebra.basis()[tuple[0]];
        let last = &algebra.basis()[*tuple.last().expect("positive-degree tuple")];
        callback(tuple_rank, &tuple, first.source(), last.target())?;
    }
    Ok(())
}

fn vertex_rank(algebra: &Algebra, vertex: u32) -> Result<usize, HochschildError> {
    if vertex >= algebra.quiver().num_vertices() {
        Err(HochschildError::VertexOutOfRange {
            vertex,
            num_vertices: algebra.quiver().num_vertices(),
        })
    } else {
        Ok(vertex as usize)
    }
}

fn validate_tuple(algebra: &Algebra, words: &[BasisIdx]) -> Result<(), HochschildError> {
    let vertices = algebra.quiver().num_vertices() as usize;
    words.iter().enumerate().try_for_each(|(position, &word)| {
        if word >= algebra.dim() {
            return Err(HochschildError::BasisOutOfRange {
                position,
                index: word,
            });
        }
        if word < vertices {
            return Err(HochschildError::TrivialInput { position });
        }
        if position > 0
            && algebra.basis()[words[position - 1]].target() != algebra.basis()[word].source()
        {
            return Err(HochschildError::NonComposableInput {
                position: position - 1,
            });
        }
        Ok(())
    })
}

fn tuple_rank(
    algebra: &Algebra,
    degree: usize,
    words: &[BasisIdx],
) -> Result<usize, HochschildError> {
    if words.len() != degree {
        return Err(HochschildError::WrongInputDegree {
            expected: degree,
            got: words.len(),
        });
    }
    validate_tuple(algebra, words)?;
    let starts = tuple_starts(algebra, degree);
    let tuples = starts[degree]
        .iter()
        .try_fold(0usize, |total, &count| total.checked_add(count))
        .expect("a completed tuple count fits usize");
    let mut tuple = Vec::with_capacity(degree);
    let rank = (0..tuples)
        .find(|&rank| {
            decode_tuple(algebra, degree, rank, &starts, &mut tuple);
            tuple.as_slice() == words
        })
        .expect("a validated tuple occurs in the streamed basis");
    Ok(rank)
}

pub(crate) fn input_rank(
    algebra: &Algebra,
    degree: usize,
    input: &BarInput,
) -> Result<usize, HochschildError> {
    match (degree, input) {
        (0, BarInput::Vertex(vertex)) => vertex_rank(algebra, *vertex),
        (0, BarInput::Tuple(words)) => Err(HochschildError::WrongInputDegree {
            expected: 0,
            got: words.len(),
        }),
        (_, BarInput::Vertex(_)) => Err(HochschildError::WrongInputDegree {
            expected: degree,
            got: 0,
        }),
        (_, BarInput::Tuple(words)) => tuple_rank(algebra, degree, words),
    }
}