catlog/dbl/
computad.rs

1//! Computads for virtual double categories.
2
3use std::hash::{BuildHasher, Hash};
4
5use derivative::Derivative;
6use derive_more::Constructor;
7
8use super::graph::{InvalidVDblGraph, VDblGraph};
9use crate::one::{Graph, Path, ReflexiveGraph, ShortPath};
10use crate::zero::*;
11
12/** Top-dimensional data of an augmented virtual double computad.
13
14Intended for use with [`AVDCComputad`].
15 */
16#[derive(Debug, Derivative)]
17#[derivative(Default(bound = "S: Default"))]
18pub struct AVDCComputadTop<Ob, Arr, Pro, Sq, S> {
19    squares: HashFinSet<Sq, S>,
20    dom: HashColumn<Sq, Path<Ob, Pro>, S>,
21    cod: HashColumn<Sq, ShortPath<Ob, Pro>, S>,
22    src: HashColumn<Sq, Arr, S>,
23    tgt: HashColumn<Sq, Arr, S>,
24}
25
26impl<Ob, Arr, Pro, Sq, S> AVDCComputadTop<Ob, Arr, Pro, Sq, S>
27where
28    Ob: Eq + Clone,
29    Arr: Eq + Clone,
30    Pro: Eq + Clone,
31    Sq: Eq + Clone + Hash,
32    S: BuildHasher,
33{
34    /// Adds a square to the double computad.
35    pub fn add_square(
36        &mut self,
37        sq: Sq,
38        dom: Path<Ob, Pro>,
39        cod: ShortPath<Ob, Pro>,
40        src: Arr,
41        tgt: Arr,
42    ) -> bool {
43        self.dom.set(sq.clone(), dom);
44        self.cod.set(sq.clone(), cod);
45        self.src.set(sq.clone(), src);
46        self.tgt.set(sq.clone(), tgt);
47        self.squares.insert(sq)
48    }
49}
50
51/** An augmented virtual double computad.
52
53The set of objects and the graphs of arrows and proarrows are assumed already
54constructed, possibly from other generating data, while the top-dimensional
55generating data is provided directly.
56
57We say "augmented" because the generating squares have co-arity zero or one,
58like the cells in an *augmented VDC* ([Koudenburg
592020](crate::refs::AugmentedVDCs)), though we use such computads to generate
60*unital* VDCs.
61 */
62#[derive(Constructor)]
63pub struct AVDCComputad<'a, Ob, Arr, Pro, ObSet, ArrGraph, ProGraph, Sq, S> {
64    objects: &'a ObSet,
65    arrows: &'a ArrGraph,
66    proarrows: &'a ProGraph,
67    computad: &'a AVDCComputadTop<Ob, Arr, Pro, Sq, S>,
68}
69
70impl<'a, Ob, Arr, Pro, ObSet, ArrGraph, ProGraph, Sq, S> VDblGraph
71    for AVDCComputad<'a, Ob, Arr, Pro, ObSet, ArrGraph, ProGraph, Sq, S>
72where
73    Ob: Eq + Clone,
74    Arr: Eq + Clone,
75    Pro: Eq + Clone,
76    Sq: Eq + Clone + Hash,
77    ObSet: Set<Elem = Ob>,
78    ArrGraph: Graph<V = Ob, E = Arr>,
79    ProGraph: ReflexiveGraph<V = Ob, E = Pro>,
80    S: BuildHasher,
81{
82    type V = Ob;
83    type E = Arr;
84    type ProE = Pro;
85    type Sq = Sq;
86
87    fn has_vertex(&self, v: &Self::V) -> bool {
88        self.objects.contains(v)
89    }
90    fn has_edge(&self, e: &Self::E) -> bool {
91        self.arrows.has_edge(e)
92    }
93    fn has_proedge(&self, p: &Self::ProE) -> bool {
94        self.proarrows.has_edge(p)
95    }
96    fn has_square(&self, sq: &Self::Sq) -> bool {
97        self.computad.squares.contains(sq)
98    }
99    fn dom(&self, e: &Self::E) -> Self::V {
100        self.arrows.src(e)
101    }
102    fn cod(&self, e: &Self::E) -> Self::V {
103        self.arrows.tgt(e)
104    }
105    fn src(&self, p: &Self::ProE) -> Self::V {
106        self.proarrows.src(p)
107    }
108    fn tgt(&self, p: &Self::ProE) -> Self::V {
109        self.proarrows.tgt(p)
110    }
111    fn square_dom(&self, sq: &Self::Sq) -> Path<Self::V, Self::ProE> {
112        self.computad.dom.apply_to_ref(sq).expect("Domain of square should be defined")
113    }
114    fn square_cod(&self, sq: &Self::Sq) -> Self::ProE {
115        self.computad
116            .cod
117            .apply_to_ref(sq)
118            .expect("Codomain of square should be defined")
119            .as_edge(self.proarrows)
120    }
121    fn square_src(&self, sq: &Self::Sq) -> Self::E {
122        self.computad.src.apply_to_ref(sq).expect("Source of square should be defined")
123    }
124    fn square_tgt(&self, sq: &Self::Sq) -> Self::E {
125        self.computad.tgt.apply_to_ref(sq).expect("Target of square should be defined")
126    }
127    fn arity(&self, sq: &Self::Sq) -> usize {
128        self.computad.dom.get(sq).expect("Domain of square should be defined").len()
129    }
130}
131
132impl<'a, Ob, Arr, Pro, ObSet, ArrGraph, ProGraph, Sq, S>
133    AVDCComputad<'a, Ob, Arr, Pro, ObSet, ArrGraph, ProGraph, Sq, S>
134where
135    Ob: Eq + Clone,
136    Arr: Eq + Clone,
137    Pro: Eq + Clone,
138    Sq: Eq + Clone + Hash,
139    ArrGraph: Graph<V = Ob, E = Arr>,
140    ProGraph: Graph<V = Ob, E = Pro>,
141    S: BuildHasher,
142{
143    /** Iterates over failures to be a valid virtual double graph.
144
145    Note that this method *assumes* that the graphs of objects and (pro)arrows
146    are already valid. If that is in question, validate them first.
147     */
148    pub fn iter_invalid<E, ProE>(&self) -> impl Iterator<Item = InvalidVDblGraph<E, ProE, Sq>> {
149        let cptd = self.computad;
150        cptd.squares.iter().flat_map(|sq| {
151            let (dom, cod) = (cptd.dom.get(&sq), cptd.cod.get(&sq));
152            let (src, tgt) = (cptd.src.get(&sq), cptd.tgt.get(&sq));
153            let mut errs = Vec::new();
154            if !dom.is_some_and(|path| path.contained_in(self.proarrows)) {
155                errs.push(InvalidVDblGraph::SquareDom(sq.clone()));
156            }
157            if !cod.is_some_and(|path| path.contained_in(self.proarrows)) {
158                errs.push(InvalidVDblGraph::SquareCod(sq.clone()));
159            }
160            if !src.is_some_and(|f| self.arrows.has_edge(f)) {
161                errs.push(InvalidVDblGraph::SquareSrc(sq.clone()));
162            }
163            if !tgt.is_some_and(|g| self.arrows.has_edge(g)) {
164                errs.push(InvalidVDblGraph::SquareTgt(sq.clone()));
165            }
166            if errs.is_empty() {
167                let (m, n, f, g) = (dom.unwrap(), cod.unwrap(), src.unwrap(), tgt.unwrap());
168                if !(m.src(self.proarrows) == self.arrows.src(f)
169                    && m.tgt(self.proarrows) == self.arrows.src(g)
170                    && n.src(self.proarrows) == self.arrows.tgt(f)
171                    && n.tgt(self.proarrows) == self.arrows.tgt(g))
172                {
173                    errs.push(InvalidVDblGraph::NotSquare(sq));
174                }
175            }
176            errs.into_iter()
177        })
178    }
179}
catlog/dbl/computad.rs

catlog/dbl/
computad.rs
