catlog/dbl/discrete/
model_morphism.rs

1//! Morphisms between models of a discrete double theory.
2
3use std::collections::HashSet;
4use std::rc::Rc;
5
6use nonempty::NonEmpty;
7
8use crate::dbl::{model::*, model_morphism::*};
9use crate::one::graph_algorithms::{bounded_simple_paths, simple_paths, spec_order};
10use crate::one::*;
11use crate::validate::{self, Validate};
12use crate::zero::{HashColumn, Mapping, MutMapping, QualifiedName};
13
14/// A mapping between models of a discrete double theory.
15///
16/// Because a discrete double theory has only trivial operations, the naturality
17/// axioms for a model morphism are also trivial.
18#[derive(Clone, Debug, Default, PartialEq, Eq)]
19pub struct DiscreteDblModelMapping(pub DiscreteDblModelMappingData);
20
21type DiscreteDblModelMappingData = FpFunctorData<
22    HashColumn<QualifiedName, QualifiedName>,
23    HashColumn<QualifiedName, QualifiedPath>,
24>;
25
26impl DiscreteDblModelMapping {
27    /// Constructs a model mapping from a pair of hash maps.
28    pub fn new(
29        ob_pairs: impl IntoIterator<Item = (QualifiedName, QualifiedName)>,
30        mor_pairs: impl IntoIterator<Item = (QualifiedName, QualifiedPath)>,
31    ) -> Self {
32        Self(FpFunctorData::new(
33            ob_pairs.into_iter().collect(),
34            mor_pairs.into_iter().collect(),
35        ))
36    }
37
38    /// Assigns an object generator, returning the previous assignment.
39    pub fn assign_ob(&mut self, x: QualifiedName, y: QualifiedName) -> Option<QualifiedName> {
40        self.0.ob_generator_map.set(x, y)
41    }
42
43    /// Assigns a morphism generator, returning the previous assignment.
44    pub fn assign_mor(&mut self, e: QualifiedName, n: QualifiedPath) -> Option<QualifiedPath> {
45        self.0.mor_generator_map.set(e, n)
46    }
47
48    /// Unassigns an object generator, returning the previous assignment.
49    pub fn unassign_ob(&mut self, x: &QualifiedName) -> Option<QualifiedName> {
50        self.0.ob_generator_map.unset(x)
51    }
52
53    /// Unassigns a morphism generator, returning the previous assignment.
54    pub fn unassign_mor(&mut self, e: &QualifiedName) -> Option<QualifiedPath> {
55        self.0.mor_generator_map.unset(e)
56    }
57
58    /// Interprets the data as a functor into the given model.
59    pub fn functor_into<'a>(
60        &'a self,
61        cod: &'a DiscreteDblModel,
62    ) -> FpFunctor<'a, DiscreteDblModelMappingData, QualifiedFpCategory> {
63        self.0.functor_into(&cod.category)
64    }
65
66    /// Finder of morphisms between two models of a discrete double theory.
67    pub fn morphisms<'a>(
68        dom: &'a DiscreteDblModel,
69        cod: &'a DiscreteDblModel,
70    ) -> DiscreteDblModelMorphismFinder<'a> {
71        DiscreteDblModelMorphismFinder::new(dom, cod)
72    }
73}
74
75/// A functor between models of a double theory.
76///
77/// This struct borrows its data to perform validation. The domain and codomain are
78/// assumed to be valid models of double theories. If that is in question, the
79/// models should be validated *before* validating this object.
80pub struct DblModelMorphism<'a, Map, Dom, Cod>(pub &'a Map, pub &'a Dom, pub &'a Cod);
81
82/// A morphism between models of a discrete double theory.
83pub type DiscreteDblModelMorphism<'a> =
84    DblModelMorphism<'a, DiscreteDblModelMapping, DiscreteDblModel, DiscreteDblModel>;
85
86impl<'a> DiscreteDblModelMorphism<'a> {
87    /// Iterates over failures of the mapping to be a model morphism.
88    pub fn iter_invalid(
89        &self,
90    ) -> impl Iterator<Item = InvalidDblModelMorphism<QualifiedName, QualifiedName>> + 'a + use<'a>
91    {
92        let DblModelMorphism(DiscreteDblModelMapping(mapping), dom, cod) = *self;
93        let category_errors: Vec<_> = mapping
94            .functor_into(&cod.category)
95            .iter_invalid_on(&dom.category)
96            .map(|err| match err {
97                InvalidFpFunctor::ObGen(x) => InvalidDblModelMorphism::Ob(x),
98                InvalidFpFunctor::MorGen(m) => InvalidDblModelMorphism::Mor(m),
99                InvalidFpFunctor::Dom(m) => InvalidDblModelMorphism::Dom(m),
100                InvalidFpFunctor::Cod(m) => InvalidDblModelMorphism::Cod(m),
101                InvalidFpFunctor::Eq(id) => InvalidDblModelMorphism::Eq(id),
102            })
103            .collect();
104        let ob_type_errors = dom.ob_generators().filter_map(|x| {
105            if let Some(y) = mapping.ob_generator_map.get(&x)
106                && cod.has_ob(y)
107                && dom.ob_type(&x) != cod.ob_type(y)
108            {
109                Some(InvalidDblModelMorphism::ObType(x))
110            } else {
111                None
112            }
113        });
114        let th_cat = cod.theory();
115        let mor_type_errors = dom.mor_generators().filter_map(move |f| {
116            if let Some(g) = mapping.mor_generator_map.get(&f)
117                && cod.has_mor(g)
118                && !th_cat.0.morphisms_are_equal(dom.mor_generator_type(&f), cod.mor_type(g))
119            {
120                Some(InvalidDblModelMorphism::MorType(f))
121            } else {
122                None
123            }
124        });
125        category_errors.into_iter().chain(ob_type_errors).chain(mor_type_errors)
126    }
127
128    /// Are morphism generators sent to simple composites of morphisms in the
129    /// codomain?
130    fn is_simple(&self) -> bool {
131        let DblModelMorphism(DiscreteDblModelMapping(mapping), dom, _) = *self;
132        dom.mor_generators()
133            .all(|e| mapping.apply_edge(e).map(|p| p.is_simple()).unwrap_or(true))
134    }
135
136    /// Is the model morphism injective on objects?
137    pub fn is_injective_objects(&self) -> bool {
138        let DblModelMorphism(DiscreteDblModelMapping(mapping), dom, _) = *self;
139        let mut seen_obs: HashSet<_> = HashSet::new();
140        for x in dom.ob_generators() {
141            if let Some(f_x) = mapping.apply_vertex(x) {
142                if seen_obs.contains(&f_x) {
143                    return false; // not monic
144                } else {
145                    seen_obs.insert(f_x);
146                }
147            }
148        }
149        true
150    }
151
152    /// Is the model morphism faithful?
153    ///
154    /// This check is a nontrivial computation since we cannot enumerate all of the
155    /// morphisms of the domain category. We simplify the problem by only allowing
156    /// free models. Furthermore, we restrict the mapping to send generating
157    /// morphisms in the domain to simple paths in the codomain. If any of these
158    /// assumptions are violated, the function will panic.
159    pub fn is_free_simple_faithful(&self) -> bool {
160        let DblModelMorphism(DiscreteDblModelMapping(mapping), dom, cod) = *self;
161
162        assert!(dom.is_free(), "Domain model should be free");
163        assert!(cod.is_free(), "Codomain model should be free");
164        assert!(self.is_simple(), "Morphism assignments should be simple");
165
166        let functor = mapping.functor_into(&cod.category);
167        for x in dom.ob_generators() {
168            for y in dom.ob_generators() {
169                let mut seen: HashSet<_> = HashSet::new();
170                for path in simple_paths(dom.generating_graph(), &x, &y) {
171                    if let Some(f_path) = functor.apply_mor(path) {
172                        if seen.contains(&f_path) {
173                            return false; // not faithful
174                        } else {
175                            seen.insert(f_path);
176                        }
177                    }
178                }
179            }
180        }
181        true
182    }
183
184    /// Is the model morphism a monomorphism?
185    ///
186    /// A monomorphism in Cat is an injective on objects and faithful functor. Thus,
187    /// we check injectivity on objects and faithfulness. Note that the latter check
188    /// is subject to the same limitations as
189    /// [`is_free_simple_faithful`](DblModelMorphism::is_free_simple_faithful).
190    pub fn is_free_simple_monic(&self) -> bool {
191        self.is_injective_objects() && self.is_free_simple_faithful()
192    }
193}
194
195impl Validate for DiscreteDblModelMorphism<'_> {
196    type ValidationError = InvalidDblModelMorphism<QualifiedName, QualifiedName>;
197
198    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
199        validate::wrap_errors(self.iter_invalid())
200    }
201}
202
203/// Finds morphisms between two models of a discrete double theory.
204///
205/// Morphisms are found using backtracking search. In general, there can be
206/// infinitely many morphisms between two models, so not all of them can be
207/// reported. The search is restricted to morphisms that send each basic morphism in
208/// the domain to a [simple path](crate::one::graph_algorithms::simple_paths) of
209/// basic morphisms in the codomain.
210pub struct DiscreteDblModelMorphismFinder<'a> {
211    dom: &'a DiscreteDblModel,
212    cod: &'a DiscreteDblModel,
213    map: DiscreteDblModelMapping,
214    results: Vec<DiscreteDblModelMapping>,
215    var_order: Vec<GraphElem<QualifiedName, QualifiedName>>,
216    max_path_len: Option<usize>,
217    injective_ob: bool,
218    faithful: bool,
219    ob_init: HashColumn<QualifiedName, QualifiedName>,
220    mor_init: HashColumn<QualifiedName, QualifiedPath>,
221    ob_inv: HashColumn<QualifiedName, QualifiedName>,
222}
223
224impl<'a> DiscreteDblModelMorphismFinder<'a> {
225    fn new(dom: &'a DiscreteDblModel, cod: &'a DiscreteDblModel) -> Self {
226        assert!(
227            Rc::ptr_eq(&dom.theory(), &cod.theory()),
228            "Domain and codomain model should have the same theory"
229        );
230        assert!(dom.is_free(), "Domain model should be free");
231
232        // Order the variables of the CSP, which are the elements of the domain
233        // graph. Prefer vertices with high degree since they are more
234        // constrained. This is a version of the well known "most constrained
235        // variable" heuristic in CSP.
236        let dom_graph = dom.generating_graph();
237        let mut vertices: Vec<_> = dom_graph.vertices().collect();
238        vertices.sort_by_key(|v| std::cmp::Reverse(dom_graph.degree(v)));
239        let var_order = spec_order(dom_graph, vertices.into_iter());
240
241        Self {
242            dom,
243            cod,
244            map: Default::default(),
245            results: Default::default(),
246            var_order,
247            max_path_len: None,
248            injective_ob: false,
249            faithful: false,
250            ob_init: Default::default(),
251            mor_init: Default::default(),
252            ob_inv: Default::default(),
253        }
254    }
255
256    /// Restrict the maximum length of the image of a generator.
257    pub fn max_path_len(&mut self, n: usize) -> &mut Self {
258        self.max_path_len = Some(n);
259        self
260    }
261
262    /// Restrict the search to monomorphisms between models.
263    pub fn monic(&mut self) -> &mut Self {
264        self.injective_ob = true;
265        self.faithful = true;
266        self
267    }
268
269    /// Restrict the search to model morphisms that are injective on objects.
270    pub fn injective_ob(&mut self) -> &mut Self {
271        self.injective_ob = true;
272        self
273    }
274
275    /// Restrict the search to model morphisms that are faithful.
276    ///
277    /// A faithful morphism is an injective map on morphisms when restricted to any
278    /// domain/codomain pair of objects in the domain.
279    ///
280    /// In future work, this will be efficiently checked for early search tree
281    /// pruning; however, this is currently enforced by filtering with
282    /// [is_free_simple_faithful](DiscreteDblModelMorphism::is_free_simple_faithful).
283    pub fn faithful(&mut self) -> &mut Self {
284        self.faithful = true;
285        self
286    }
287
288    /// Require morphisms to send object `ob` in domain to `val` in codomain.
289    pub fn initialize_ob(&mut self, ob: QualifiedName, val: QualifiedName) -> &mut Self {
290        self.ob_init.set(ob, val);
291        self
292    }
293
294    /// Require morphisms to send morphism `m` in domain to `val` in codomain.
295    pub fn initialize_mor(&mut self, m: QualifiedName, val: QualifiedPath) -> &mut Self {
296        self.mor_init.set(m, val);
297        self
298    }
299
300    /// Finds all morphisms.
301    pub fn find_all(&mut self) -> Vec<DiscreteDblModelMapping> {
302        self.search(0);
303        std::mem::take(&mut self.results)
304    }
305
306    fn search(&mut self, depth: usize) {
307        if depth >= self.var_order.len() {
308            if !self.faithful
309                || DblModelMorphism(&self.map, self.dom, self.cod).is_free_simple_faithful()
310            {
311                self.results.push(self.map.clone());
312            }
313            return;
314        }
315        let var = &self.var_order[depth];
316        match var.clone() {
317            GraphElem::Vertex(x) => {
318                if let Some(y) = self.ob_init.apply_to_ref(&x) {
319                    let can_assign = self.assign_ob(x.clone(), y.clone());
320                    if can_assign {
321                        self.search(depth + 1);
322                        self.unassign_ob(x, y)
323                    }
324                } else {
325                    for y in self.cod.ob_generators_with_type(&self.dom.ob_type(&x)) {
326                        let can_assign = self.assign_ob(x.clone(), y.clone());
327                        if can_assign {
328                            self.search(depth + 1);
329                            self.unassign_ob(x.clone(), y)
330                        }
331                    }
332                }
333            }
334            GraphElem::Edge(m) => {
335                if let Some(path) = self.mor_init.apply_to_ref(&m) {
336                    self.map.assign_mor(m, path);
337                    self.search(depth + 1);
338                } else {
339                    let functor = self.map.0.functor_into(&self.cod.category);
340                    let mor_type = self.dom.mor_generator_type(&m);
341                    let w = functor
342                        .apply_ob(self.dom.mor_generator_dom(&m))
343                        .expect("Domain should already be assigned");
344                    let z = functor
345                        .apply_ob(self.dom.mor_generator_cod(&m))
346                        .expect("Codomain should already be assigned");
347
348                    let cod_graph = self.cod.generating_graph();
349                    let th_cat = &self.cod.theory().0;
350                    for path in bounded_simple_paths(cod_graph, &w, &z, self.max_path_len) {
351                        if th_cat.morphisms_are_equal(self.cod.mor_type(&path), mor_type.clone())
352                            && !(self.faithful && path.is_empty())
353                        {
354                            self.map.assign_mor(m.clone(), path);
355                            self.search(depth + 1);
356                        }
357                    }
358                }
359            }
360        }
361    }
362
363    /// Attempt an object assignment, returning true iff successful.
364    fn assign_ob(&mut self, x: QualifiedName, y: QualifiedName) -> bool {
365        if self.injective_ob && self.ob_inv.get(&y).is_some_and(|y_inv| *y_inv != x) {
366            return false;
367        }
368        self.map.assign_ob(x.clone(), y.clone());
369        self.ob_inv.set(y, x);
370        true
371    }
372
373    /// Undo an object assignment.
374    fn unassign_ob(&mut self, _: QualifiedName, y: QualifiedName) {
375        self.ob_inv.unset(&y);
376    }
377}
378
379#[cfg(test)]
380mod tests {
381    use super::*;
382    use crate::stdlib::*;
383    use crate::validate::Validate;
384    use crate::{one::Path, zero::name};
385
386    #[test]
387    fn find_positive_loops() {
388        let th = Rc::new(th_signed_category());
389        let positive_loop = positive_loop(th.clone());
390        let pos = positive_loop.mor_generators().next().unwrap().into();
391
392        let maps = DiscreteDblModelMapping::morphisms(&positive_loop, &positive_loop).find_all();
393        assert_eq!(maps.len(), 2);
394        let mors: Vec<_> = maps
395            .into_iter()
396            .map(|map| map.functor_into(&positive_loop).mor_map().apply_to_ref(&pos))
397            .collect();
398        assert!(mors.iter().any(|mor| matches!(mor, Some(Path::Id(_)))));
399        assert!(mors.iter().any(|mor| matches!(mor, Some(Path::Seq(_)))));
400
401        let maps = DiscreteDblModelMapping::morphisms(&positive_loop, &positive_loop)
402            .monic()
403            .find_all();
404        assert_eq!(maps.len(), 1);
405        assert!(matches!(
406            maps[0].functor_into(&positive_loop).apply_mor(pos),
407            Some(Path::Seq(_))
408        ));
409    }
410
411    /// The [simple path](crate::one::graph_algorithms::simple_paths) should
412    /// give identical results to hom search from a walking morphism (assuming
413    /// all the object/morphism types are the same).
414    #[test]
415    fn find_simple_paths() {
416        let th = Rc::new(th_signed_category());
417
418        let mut walking = DiscreteDblModel::new(th.clone());
419        walking.add_ob(name("A"), name("Object"));
420        walking.add_ob(name("B"), name("Object"));
421        walking.add_mor(name("f"), name("A"), name("B"), Path::Id(name("Object")));
422
423        //     y         Graph with lots of cyclic paths.
424        //   ↗  ↘
425        // ↻x ⇆ z
426        let mut model = DiscreteDblModel::new(th);
427        model.add_ob(name("X"), name("Object"));
428        model.add_ob(name("Y"), name("Object"));
429        model.add_ob(name("Z"), name("Object"));
430        model.add_mor(name("xy"), name("X"), name("Y"), Path::Id(name("Object")));
431        model.add_mor(name("yz"), name("Y"), name("Z"), Path::Id(name("Object")));
432        model.add_mor(name("zx"), name("Z"), name("X"), Path::Id(name("Object")));
433        model.add_mor(name("xz"), name("X"), name("Z"), Path::Id(name("Object")));
434        model.add_mor(name("xx"), name("X"), name("X"), Path::Id(name("Object")));
435
436        for i in model.ob_generators() {
437            for j in model.ob_generators() {
438                let maps: HashSet<_> = DiscreteDblModelMapping::morphisms(&walking, &model)
439                    .initialize_ob(name("A"), i.clone())
440                    .initialize_ob(name("B"), j.clone())
441                    .find_all()
442                    .into_iter()
443                    .map(|map| map.functor_into(&model).apply_mor_generator(name("f")).unwrap())
444                    .collect();
445                let spaths: HashSet<_> = simple_paths(model.generating_graph(), &i, &j).collect();
446                assert_eq!(maps, spaths);
447            }
448        }
449    }
450
451    #[test]
452    fn find_negative_loops() {
453        let th = Rc::new(th_signed_category());
454        let negative_loop = negative_loop(th.clone());
455        let base_pt = negative_loop.ob_generators().next().unwrap();
456
457        let negative_feedback = negative_feedback(th);
458        let maps = DiscreteDblModelMapping::morphisms(&negative_loop, &negative_feedback)
459            .max_path_len(2)
460            .find_all();
461        assert_eq!(maps.len(), 2);
462        let obs: Vec<_> = maps
463            .iter()
464            .map(|map| map.functor_into(&negative_feedback).apply_ob(base_pt.clone()))
465            .collect();
466        assert!(obs.contains(&Some(name("x"))));
467        assert!(obs.contains(&Some(name("y"))));
468
469        let maps = DiscreteDblModelMapping::morphisms(&negative_loop, &negative_feedback)
470            .max_path_len(1)
471            .find_all();
472        assert!(maps.is_empty());
473    }
474
475    #[test]
476    fn validate_model_morphism() {
477        let theory = Rc::new(th_signed_category());
478        let negloop = negative_loop(theory.clone());
479        let posfeed = positive_feedback(theory.clone());
480
481        let f = DiscreteDblModelMapping::new(
482            [(name("x"), name("x"))],
483            [(name(""), Path::Id(name("negative")))],
484        );
485        let dmm = DblModelMorphism(&f, &negloop, &negloop);
486        assert!(dmm.validate().is_err());
487
488        // A bad map from h to itself that is wrong for the ob (it is in the map
489        // but sent to something that doesn't exist) and for the hom generator
490        // (not in the map)
491        let f = DiscreteDblModelMapping::new(
492            [(name("x"), name("y"))],
493            [(name("y"), Path::Id(name("y")))],
494        );
495        let dmm = DblModelMorphism(&f, &negloop, &negloop);
496        let errs: Vec<_> = dmm.validate().unwrap_err().into();
497        assert!(
498            errs == vec![
499                InvalidDblModelMorphism::Ob(name("x")),
500                InvalidDblModelMorphism::Mor(name("loop")),
501            ]
502        );
503
504        // A bad map that doesn't preserve dom
505        let f = DiscreteDblModelMapping::new(
506            [(name("x"), name("x"))],
507            [(name("loop"), Path::single(name("positive1")))],
508        );
509        let dmm = DblModelMorphism(&f, &negloop, &posfeed);
510        let errs: Vec<_> = dmm.validate().unwrap_err().into();
511        assert!(
512            errs == vec![
513                InvalidDblModelMorphism::Cod(name("loop")),
514                InvalidDblModelMorphism::MorType(name("loop")),
515            ]
516        );
517
518        // A bad map that doesn't preserve codom
519        let f = DiscreteDblModelMapping::new(
520            [(name("x"), name("x"))],
521            [(name("loop"), Path::single(name("positive2")))],
522        );
523        let dmm = DblModelMorphism(&f, &negloop, &posfeed);
524        let errs: Vec<_> = dmm.validate().unwrap_err().into();
525        assert!(
526            errs == vec![
527                InvalidDblModelMorphism::Dom(name("loop")),
528                InvalidDblModelMorphism::MorType(name("loop")),
529            ]
530        );
531    }
532
533    #[test]
534    fn validate_is_free_simple_monic() {
535        let theory = Rc::new(th_signed_category());
536        let negloop = positive_loop(theory.clone());
537
538        // Identity map
539        let f = DiscreteDblModelMapping::new(
540            [(name("x"), name("x"))],
541            [(name("loop"), Path::single(name("loop")))],
542        );
543        let dmm = DblModelMorphism(&f, &negloop, &negloop);
544        assert!(dmm.validate().is_ok());
545        assert!(dmm.is_free_simple_monic());
546
547        // Send generator to identity
548        let f = DiscreteDblModelMapping::new(
549            [(name("x"), name("x"))],
550            [(name("loop"), Path::Id(name("x")))],
551        );
552        let dmm = DblModelMorphism(&f, &negloop, &negloop);
553        assert!(dmm.validate().is_ok());
554        assert!(!dmm.is_free_simple_monic());
555    }
556
557    #[test]
558    fn monic_constraint() {
559        // The number of endomonomorphisms of a set |N| is N!.
560        let theory = Rc::new(th_signed_category());
561        let mut model = DiscreteDblModel::new(theory.clone());
562        for id in ["Q", "X", "Y", "Z"] {
563            model.add_ob(name(id), name("Object"));
564        }
565        let mors = DiscreteDblModelMapping::morphisms(&model, &model).monic().find_all();
566        assert_eq!(mors.into_iter().len(), 4 * 3 * 2);
567
568        // Hom from noncommuting triangle into a pair of triangles, only one one
569        // of which commutes. There is only one morphism that is faithful.
570        let mut freetri = DiscreteDblModel::new(theory.clone());
571        for id in ["X", "Y", "Z"] {
572            freetri.add_ob(name(id), name("Object"));
573        }
574        freetri.add_mor(name("f"), name("X"), name("Y"), Path::Id(name("Object")));
575        freetri.add_mor(name("g"), name("Y"), name("Z"), Path::Id(name("Object")));
576        freetri.add_mor(name("h"), name("X"), name("Z"), Path::Id(name("Object")));
577
578        let mut quad = DiscreteDblModel::new(theory);
579        for id in ["Q", "X", "Y", "Z"] {
580            quad.add_ob(name(id), name("Object"));
581        }
582        quad.add_mor(name("f"), name("X"), name("Y"), Path::Id(name("Object")));
583        quad.add_mor(name("g"), name("Y"), name("Z"), Path::Id(name("Object")));
584        quad.add_mor(name("i"), name("Y"), name("Q"), Path::Id(name("Object")));
585        quad.add_mor(name("j"), name("X"), name("Q"), Path::Id(name("Object")));
586        let mors = DiscreteDblModelMapping::morphisms(&freetri, &quad).faithful().find_all();
587        assert_eq!(mors.into_iter().len(), 1);
588    }
589}
catlog/dbl/discrete/model_morphism.rs

catlog/dbl/discrete/
model_morphism.rs
