catlog_wasm/
model_morphism.rs

1use std::hash::Hash;
2
3use serde::{Deserialize, Serialize};
4use tsify_next::Tsify;
5use uuid::Uuid;
6
7use catlog::dbl::{model, model_morphism};
8use catlog::one::{FgCategory, fin_category::UstrFinCategory};
9
10use super::model::DblModel;
11
12pub(crate) type DiscreteDblModelMapping = model_morphism::DiscreteDblModelMapping<Uuid, Uuid>;
13
14/// Options for motif finder.
15#[derive(Debug, Deserialize, Serialize, Tsify)]
16#[tsify(into_wasm_abi, from_wasm_abi, missing_as_null)]
17pub struct MotifsOptions {
18    #[serde(rename = "maxPathLength")]
19    max_path_len: Option<usize>,
20}
21
22/// Find motifs in a model of a discrete double theory.
23pub fn motifs<Id>(
24    motif: &model::DiscreteDblModel<Id, UstrFinCategory>,
25    model: &DblModel,
26    options: MotifsOptions,
27) -> Result<Vec<DblModel>, String>
28where
29    Id: Clone + Eq + Hash,
30{
31    let model: &model::DiscreteDblModel<_, _> = (&model.0)
32        .try_into()
33        .map_err(|_| "Motif finding expects a discrete double model")?;
34
35    let mut finder = model_morphism::DiscreteDblModelMapping::morphisms(motif, model);
36    if let Some(n) = options.max_path_len {
37        finder.max_path_len(n);
38    }
39    let mut images: Vec<_> = finder
40        .monic()
41        .find_all()
42        .into_iter()
43        .map(|mapping| mapping.syntactic_image(model))
44        .collect();
45
46    // Order motifs from small to large.
47    images.sort_by_key(|im| (im.ob_generators().count(), im.mor_generators().count()));
48
49    // Remove duplicates: different morphisms can have the same image.
50    retain_unique(&mut images);
51
52    Ok(images.into_iter().map(|im| DblModel(im.into())).collect())
53}
54
55/** Remove duplicate elements from a vector.
56
57This is the naive quadratic algorithm that only uses equality tests.
58 */
59fn retain_unique<T>(vec: &mut Vec<T>)
60where
61    T: Eq,
62{
63    let mut i = 0;
64    while i < vec.len() {
65        if (0..i).any(|j| vec[j] == vec[i]) {
66            vec.remove(i);
67        } else {
68            i += 1;
69        }
70    }
71}
catlog_wasm/model_morphism.rs

catlog_wasm/
model_morphism.rs
