catlog/dbl/
tree.rs

1//! Double trees: pasting diagrams in virtual double categories.
2//!
3//! A *double tree* (nonstandard term) is the data structure for a [pasting
4//! diagram](https://ncatlab.org/nlab/show/pasting+diagram) in a virtual double
5//! category. To be more precise, a double tree is ([up to
6//! isomorphism](DblTree::is_isomorphic_to)) a normal form for a general composition
7//! of cells in a VDC. That is, every sequence of composing cells and forming
8//! identity cells can be represented as a double tree, and, moreover, any two
9//! sequences equivalent under the associativity and unitality axioms of a VDC are
10//! represented by the same double tree.
11//!
12//! Yet another way to say this is that double trees are the cells of [free
13//! VDCs](super::category::FreeVDblCategory), generalizing how trees are the
14//! morphisms of free multicategories. Turning this around, we use our data
15//! structure for trees, specifically [open trees](crate::one::tree), to implement
16//! double trees. A double tree is thus implemented as an open tree whose types are
17//! proarrows and operations are cells, subject to additional typing constraints on
18//! the sources and targets.
19//!
20//! The only hitch in this plan is that composition in a VDC includes the degenerate
21//! case of composing a cell with a zero-length path of cells, which is just a
22//! single arrow. To accomodate nullary cell composition, the [nodes](DblNode) in a
23//! double tree contain either cells *or* arrows. This complicates the code in a few
24//! places, since it is now possible for a nullary operation (cell) to have a child
25//! node, and it gives the data structure something of the spirit of *augmented*
26//! virtual double categories ([Koudenburg 2020](crate::refs::AugmentedVDCs)).
27//! Double trees are *not* however data structures for pasting diagrams in augmented
28//! VDCs, which would introduce further complications.
29
30use derive_more::From;
31use ego_tree::NodeRef;
32use itertools::{EitherOrBoth::Both, Itertools, zip_eq};
33
34use super::graph::VDblGraph;
35use crate::one::{path::Path, tree::*, tree_algorithms::*};
36
37/// A node in a [double tree](DblTree).
38///
39/// More precisely, this is the type of *values* carried by nodes in a double tree.
40#[derive(Clone, Debug, PartialEq, Eq)]
41pub enum DblNode<E, Sq> {
42    /// A generic cell, given by a square in a virtual double graph.
43    Cell(Sq),
44
45    /// An edge on the boundary of the double tree.
46    ///
47    /// In a well-formed double tree, each spine node must be a child of a nullary
48    /// cell or of another spine node. Spines represent the operation of
49    /// precomposing a nullary cell with an arrow to obtain another nullary cell, a
50    /// degenerate case of composition in a virtual double category.
51    Spine(E),
52}
53
54impl<E, Sq> DblNode<E, Sq> {
55    /// Domain of node in the given virtual double graph.
56    ///
57    /// Returns a path of arbitrary length.
58    pub fn dom<V, ProE>(
59        &self,
60        graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>,
61    ) -> Path<V, ProE> {
62        match self {
63            DblNode::Cell(sq) => graph.square_dom(sq),
64            DblNode::Spine(e) => Path::empty(graph.dom(e)),
65        }
66    }
67
68    /// Codomain of node in the given virtual double graph.
69    ///
70    /// Returns a path of length at most one.
71    pub fn cod<V, ProE>(
72        &self,
73        graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>,
74    ) -> Path<V, ProE> {
75        match self {
76            DblNode::Cell(sq) => graph.square_cod(sq).into(),
77            DblNode::Spine(e) => Path::empty(graph.cod(e)),
78        }
79    }
80
81    /// Source of node in the given virtual double graph.
82    pub fn src(&self, graph: &impl VDblGraph<E = E, Sq = Sq>) -> E
83    where
84        E: Clone,
85    {
86        match self {
87            DblNode::Cell(sq) => graph.square_src(sq),
88            DblNode::Spine(e) => e.clone(),
89        }
90    }
91
92    /// Target of node in the given virtual double graph.
93    pub fn tgt(&self, graph: &impl VDblGraph<E = E, Sq = Sq>) -> E
94    where
95        E: Clone,
96    {
97        match self {
98            DblNode::Cell(sq) => graph.square_tgt(sq),
99            DblNode::Spine(e) => e.clone(),
100        }
101    }
102
103    /// Arity of node in the given virtual double graph.
104    pub fn arity(&self, graph: &impl VDblGraph<E = E, Sq = Sq>) -> usize {
105        match self {
106            DblNode::Cell(sq) => graph.arity(sq),
107            DblNode::Spine(_) => 0,
108        }
109    }
110
111    /// Is the node contained in the given virtual double graph?
112    pub fn contained_in(&self, graph: &impl VDblGraph<E = E, Sq = Sq>) -> bool {
113        match self {
114            DblNode::Cell(sq) => graph.has_square(sq),
115            DblNode::Spine(e) => graph.has_edge(e),
116        }
117    }
118}
119
120/// A double tree, or pasting diagram in a virtual double category.
121///
122/// The underlying data structure of a double tree is a [open tree](OpenTree) whose
123/// [nodes](DblNode) represent cells (or occasionally arrows) in the pasting
124/// diagram. Not just any tree constitutes a valid pasting. The domains/codomains
125/// and sources/targets of the cells must compatible, and [spines](DblNode::Spine)
126/// can only appear in certain configurations.
127#[derive(Clone, Debug, From, PartialEq, Eq)]
128pub struct DblTree<E, ProE, Sq>(pub OpenTree<ProE, DblNode<E, Sq>>);
129
130impl<E, ProE, Sq> DblTree<E, ProE, Sq> {
131    /// Constructs the empty or identity double tree.
132    pub fn empty(p: ProE) -> Self {
133        OpenTree::empty(p).into()
134    }
135
136    /// Constructs a double tree with a single square from a virtual double graph.
137    pub fn single(sq: Sq, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> Self {
138        let n = graph.arity(&sq);
139        OpenTree::single(DblNode::Cell(sq), n).into()
140    }
141
142    /// Constructs a double tree of height two.
143    pub fn two_level(
144        squares: impl IntoIterator<Item = Sq>,
145        base: Sq,
146        graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>,
147    ) -> Self {
148        let subtrees = squares.into_iter().map(|sq| {
149            let n = graph.arity(&sq);
150            OpenTree::single(DblNode::Cell(sq), n)
151        });
152        OpenTree::graft(subtrees, DblNode::Cell(base)).into()
153    }
154
155    /// Domain of the tree in the given virtual double graph.
156    pub fn dom<V>(
157        &self,
158        graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>,
159    ) -> Path<V, ProE>
160    where
161        ProE: Clone,
162    {
163        // Helper function to perform the recursion.
164        fn dom_at<V, E, ProE, Sq>(
165            node: NodeRef<'_, Option<DblNode<E, Sq>>>,
166            graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>,
167        ) -> Path<V, ProE> {
168            let path = node.get_value().unwrap().dom(graph);
169            if node.children().all(|node| node.is_boundary()) {
170                // In particular, handle special case that the node has no children.
171                return path;
172            }
173            if path.is_empty() && node.has_children() {
174                // Handle special case of nullary cells with spines.
175                let child = node.children().exactly_one().ok().expect("Invalid nullary composite");
176                return dom_at(child, graph);
177            }
178            // At this point, the path length must equal the number of children.
179            let paths = zip_eq(node.children(), path)
180                .map(|(child, proedge)| {
181                    if child.is_boundary() {
182                        Path::single(proedge)
183                    } else {
184                        dom_at(child, graph)
185                    }
186                })
187                .collect_vec();
188            Path::collect(paths).unwrap().flatten()
189        }
190
191        match &self.0 {
192            OpenTree::Id(p) => p.clone().into(),
193            OpenTree::Comp(tree) => dom_at(tree.root(), graph),
194        }
195    }
196
197    /// Codomain of the tree in the given virtual double graph.
198    pub fn cod(&self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> ProE
199    where
200        ProE: Clone,
201    {
202        match &self.0 {
203            OpenTree::Id(p) => p.clone(),
204            OpenTree::Comp(tree) => tree
205                .root()
206                .get_value()
207                .expect("Root of a double tree should not be null")
208                .cod(graph)
209                .only()
210                .expect("Root of a double tree should not be a spine"),
211        }
212    }
213
214    /// Source of the tree in the given virtual double graph.
215    pub fn src<V>(&self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>) -> Path<V, E>
216    where
217        E: Clone,
218    {
219        match &self.0 {
220            OpenTree::Id(p) => Path::empty(graph.src(p)),
221            OpenTree::Comp(tree) => {
222                let mut edges = tree
223                    .root()
224                    .left_boundary()
225                    .filter_map(|node| node.get_value().map(|dn| dn.src(graph)))
226                    .collect_vec();
227                edges.reverse();
228                Path::from_vec(edges).unwrap()
229            }
230        }
231    }
232
233    /// Target of the tree in the given virtual double graph.
234    pub fn tgt<V>(&self, graph: &impl VDblGraph<V = V, E = E, ProE = ProE, Sq = Sq>) -> Path<V, E>
235    where
236        E: Clone,
237    {
238        match &self.0 {
239            OpenTree::Id(p) => Path::empty(graph.tgt(p)),
240            OpenTree::Comp(tree) => {
241                let mut edges = tree
242                    .root()
243                    .right_boundary()
244                    .filter_map(|node| node.get_value().map(|dn| dn.tgt(graph)))
245                    .collect_vec();
246                edges.reverse();
247                Path::from_vec(edges).unwrap()
248            }
249        }
250    }
251
252    /// Arity of the cell specified by the double tree.
253    ///
254    /// Note that this arity can differ from the [arity](OpenTree::arity) of the
255    /// underlying open tree due to the possibility of spines.
256    pub fn arity(&self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> usize {
257        match &self.0 {
258            OpenTree::Id(_) => 1,
259            OpenTree::Comp(tree) => tree
260                .root()
261                .boundary()
262                .filter(|node| node.parent_value().unwrap().arity(graph) != 0)
263                .count(),
264        }
265    }
266
267    /// Extracts the unique node in a tree of size 1.
268    ///
269    /// This method is a one-sided inverse to [`DblTree::single`].
270    pub fn only(self) -> Option<Sq> {
271        self.0.only().and_then(|node| {
272            match node {
273                DblNode::Cell(sq) => Some(sq),
274                // This case will never occur in a well-formed double tree.
275                DblNode::Spine(_) => None,
276            }
277        })
278    }
279
280    /// Is the double tree contained in the given virtual double graph?
281    ///
282    /// This includes checking whether the double tree is well-typed, i.e., that the
283    /// domains and codomains, and sources and targets, of the cells are compatible.
284    pub fn contained_in(&self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> bool
285    where
286        E: Eq + Clone,
287        ProE: Eq + Clone,
288    {
289        let tree = match &self.0 {
290            OpenTree::Id(p) => return graph.has_proedge(p),
291            OpenTree::Comp(tree) => tree,
292        };
293        let root = tree.root();
294        let mut traverse = root.bfs();
295        while let Some(node) = traverse.next() {
296            let Some(dn) = node.value() else {
297                continue;
298            };
299            // The cell itself is contained in the graph.
300            if !dn.contained_in(graph) {
301                return false;
302            }
303            // Source and target edges are compatible.
304            if !traverse
305                .peek_at_same_level()
306                .is_none_or(|next| Some(dn.tgt(graph)) == next.get_value().map(|dn| dn.src(graph)))
307            {
308                return false;
309            }
310
311            // Domain and codomain pro-edges are compatible.
312            let path = dn.dom(graph);
313            if path.is_empty() && node.has_children() {
314                // Handle special cae of nullary cells with spines.
315                if node
316                    .children()
317                    .exactly_one()
318                    .ok()
319                    .is_none_or(|child| child.get_value().is_some_and(|dn| dn.cod(graph) != path))
320                {
321                    return false;
322                }
323                continue;
324            }
325            // At this point, the path length must equal the number of children.
326            for pair in node.children().zip_longest(path) {
327                let Both(child, proedge) = pair else {
328                    return false;
329                };
330                if child.get_value().is_some_and(|cn| cn.cod(graph) != Path::single(proedge)) {
331                    return false;
332                }
333            }
334        }
335        true
336    }
337
338    /// Is the double tree isomorphic to another?
339    ///
340    /// This method simply checks whether the underlying open trees are
341    /// [isomorphic](OpenTree::is_isomorphic_to).
342    pub fn is_isomorphic_to(&self, other: &Self) -> bool
343    where
344        E: Eq,
345        ProE: Eq,
346        Sq: Eq,
347    {
348        self.0.is_isomorphic_to(&other.0)
349    }
350
351    /// Maps over the edges and squares of the tree.
352    pub fn map<CodE, CodSq>(
353        self,
354        mut fn_e: impl FnMut(E) -> CodE,
355        mut fn_sq: impl FnMut(Sq) -> CodSq,
356    ) -> DblTree<CodE, ProE, CodSq> {
357        self.0
358            .map(|dn| match dn {
359                DblNode::Cell(sq) => DblNode::Cell(fn_sq(sq)),
360                DblNode::Spine(e) => DblNode::Spine(fn_e(e)),
361            })
362            .into()
363    }
364}
365
366impl<V, E, ProE, Sq> DblTree<Path<V, E>, ProE, DblTree<E, ProE, Sq>> {
367    /// Flattens a double tree of double trees into a single double tree.
368    pub fn flatten(self) -> DblTree<E, ProE, Sq> {
369        let tree = self.0.map(|dn| match dn {
370            DblNode::Cell(tree) => tree.0,
371            DblNode::Spine(path) => OpenTree::linear(path.into_iter().map(DblNode::Spine))
372                .expect("Spine should be a non-empty path"),
373        });
374        tree.flatten().into()
375    }
376}
377
378impl<Arr, ProE, Sq> DblTree<Arr, ProE, DblTree<Arr, ProE, Sq>> {
379    /// Flattens a double tree of double trees into a single double tree.
380    pub fn flatten(self) -> DblTree<Arr, ProE, Sq> {
381        let tree = self.0.map(|dn| match dn {
382            DblNode::Cell(tree) => tree.0,
383            DblNode::Spine(f) => OpenTree::single(DblNode::Spine(f), 1),
384        });
385        tree.flatten().into()
386    }
387}
388
389#[cfg(test)]
390mod tests {
391    use ego_tree::tree;
392    use nonempty::nonempty;
393
394    use super::super::category::{WalkingBimodule as Bimod, WalkingFunctor as Funct, *};
395    use super::*;
396
397    #[test]
398    fn tree_dom_cod() {
399        let bimod = Bimod::Main();
400        let graph = UnderlyingDblGraph(Bimod::Main());
401        let path = Path::Seq(nonempty![Bimod::Pro::Left, Bimod::Pro::Middle, Bimod::Pro::Right]);
402        let mid = bimod.composite_ext(path).unwrap();
403        let tree = DblTree::two_level(
404            vec![bimod.id_cell(Bimod::Pro::Left), mid.clone(), bimod.id_cell(Bimod::Pro::Right)],
405            mid.clone(),
406            &graph,
407        );
408        let tree_alt = tree!(
409            Some(mid.clone()) => {
410                Some(bimod.id_cell(Bimod::Pro::Left)) => { None },
411                Some(mid.clone()) => { None, None, None },
412                Some(bimod.id_cell(Bimod::Pro::Right)) => { None }
413            }
414        );
415        let tree_alt = DblTree(OpenTree::from(tree_alt).map(DblNode::Cell));
416        assert_eq!(tree, tree_alt);
417        assert!(tree.contained_in(&graph));
418
419        assert_eq!(tree.arity(&graph), 5);
420        assert_eq!(
421            tree.dom(&graph),
422            Path::Seq(nonempty![
423                Bimod::Pro::Left,
424                Bimod::Pro::Left,
425                Bimod::Pro::Middle,
426                Bimod::Pro::Right,
427                Bimod::Pro::Right
428            ])
429        );
430        assert_eq!(tree.cod(&graph), Bimod::Pro::Middle);
431
432        // Trees with incompatible (co)domains.
433        let tree = tree!(
434            Some(mid.clone()) => {
435                Some(bimod.id_cell(Bimod::Pro::Left)) => { None },
436                Some(mid.clone()) => { None, None, None }
437            }
438        );
439        assert!(!DblTree(OpenTree::from(tree).map(DblNode::Cell)).contained_in(&graph));
440        let tree = tree!(
441            Some(mid.clone()) => {
442                Some(bimod.id_cell(Bimod::Pro::Right)) => { None },
443                Some(mid.clone()) => { None, None, None },
444                Some(bimod.id_cell(Bimod::Pro::Left)) => { None }
445            }
446        );
447        assert!(!DblTree(OpenTree::from(tree).map(DblNode::Cell)).contained_in(&graph));
448    }
449
450    #[test]
451    fn tree_src_tgt() {
452        let funct = Funct::Main();
453        let graph = UnderlyingDblGraph(Funct::Main());
454        let f = Funct::Arr::Arrow;
455        let unit1 = funct.unit_ext(Funct::Ob::One).unwrap();
456        let tree =
457            DblTree(OpenTree::linear(vec![DblNode::Spine(f), DblNode::Cell(unit1)]).unwrap());
458        let tree_alt = DblTree(
459            tree!(
460                Some(DblNode::Cell(unit1)) => { Some(DblNode::Spine(f)) => { None } }
461            )
462            .into(),
463        );
464        assert_eq!(tree, tree_alt);
465        assert!(tree.contained_in(&graph));
466
467        assert_eq!(tree.src(&graph), Path::pair(f, Funct::Arr::One));
468        assert_eq!(tree.tgt(&graph), Path::pair(f, Funct::Arr::One));
469        assert!(tree.dom(&graph).is_empty());
470
471        // Trees with incompatible sources and targets.
472        let comp = funct.composite2_ext(Funct::Ob::One, Funct::Ob::One).unwrap();
473        let tree = DblTree(
474            tree!(
475                Some(DblNode::Cell(comp)) => {
476                    Some(DblNode::Cell(unit1)) => {
477                        Some(DblNode::Spine(Funct::Arr::One)) => { None }
478                    },
479                    Some(DblNode::Cell(unit1)) => {
480                        Some(DblNode::Spine(f)) => { None }
481                    },
482                }
483            )
484            .into(),
485        );
486        assert!(!tree.contained_in(&graph));
487    }
488
489    #[test]
490    fn flatten_tree() {
491        let bimod = Bimod::Main();
492        let graph = UnderlyingDblGraph(Bimod::Main());
493        let path = Path::Seq(nonempty![Bimod::Pro::Left, Bimod::Pro::Middle, Bimod::Pro::Right]);
494        let unitl = bimod.unit_ext(Bimod::Ob::Left).unwrap();
495        let unitr = bimod.unit_ext(Bimod::Ob::Right).unwrap();
496        let mid = bimod.composite_ext(path).unwrap();
497        let tree = tree!(
498            Some(mid.clone()) => {
499                Some(bimod.id_cell(Bimod::Pro::Left)) => {
500                    Some(unitl.clone())
501                },
502                Some(mid) => {
503                    Some(unitl),
504                    Some(bimod.id_cell(Bimod::Pro::Middle)) => { None },
505                    Some(unitr.clone())
506                },
507                Some(bimod.id_cell(Bimod::Pro::Right)) => {
508                    Some(unitr),
509                }
510            }
511        );
512        let tree = DblTree(OpenTree::from(tree).map(DblNode::Cell));
513        assert_eq!(tree.dom(&graph), Path::single(Bimod::Pro::Middle));
514        assert_eq!(tree.cod(&graph), Bimod::Pro::Middle);
515
516        // Degenerate case: the outer tree is a singleton.
517        let outer: DblTree<Path<Bimod::Ob, Bimod::Ob>, _, _> =
518            OpenTree::single(DblNode::Cell(tree.clone()), tree.arity(&graph)).into();
519        assert_eq!(outer.flatten(), tree);
520
521        // Degenerate case: all inner trees are singletons.
522        let outer: DblTree<Path<Bimod::Ob, Bimod::Ob>, _, _> =
523            tree.clone().map(Path::single, |dn| DblTree::single(dn, &graph));
524        let result = outer.flatten();
525        assert!(result.is_isomorphic_to(&tree));
526    }
527}
catlog/dbl/tree.rs

catlog/dbl/
tree.rs
