catlog/dbl/
tree.rs

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

catlog/dbl/
tree.rs
