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    /** Is the double tree contained in the given virtual double graph?
275
276    This includes checking whether the double tree is well-typed, i.e., that the
277    domains and codomains, and sources and targets, of the cells are compatible.
278     */
279    pub fn contained_in(&self, graph: &impl VDblGraph<E = E, ProE = ProE, Sq = Sq>) -> bool
280    where
281        E: Eq + Clone,
282        ProE: Eq + Clone,
283    {
284        let tree = match &self.0 {
285            OpenTree::Id(p) => return graph.has_proedge(p),
286            OpenTree::Comp(tree) => tree,
287        };
288        let root = tree.root();
289        let mut traverse = root.bfs();
290        while let Some(node) = traverse.next() {
291            let Some(dn) = node.value() else {
292                continue;
293            };
294            // The cell itself is contained in the graph.
295            if !dn.contained_in(graph) {
296                return false;
297            }
298            // Source and target edges are compatible.
299            if !traverse
300                .peek_at_same_level()
301                .is_none_or(|next| Some(dn.tgt(graph)) == next.get_value().map(|dn| dn.src(graph)))
302            {
303                return false;
304            }
305
306            // Domain and codomain pro-edges are compatible.
307            let path = dn.dom(graph);
308            if path.is_empty() && node.has_children() {
309                // Handle special cae of nullary cells with spines.
310                if node
311                    .children()
312                    .exactly_one()
313                    .ok()
314                    .is_none_or(|child| child.get_value().is_some_and(|dn| dn.cod(graph) != path))
315                {
316                    return false;
317                }
318                continue;
319            }
320            // At this point, the path length must equal the number of children.
321            for pair in node.children().zip_longest(path) {
322                let Both(child, proedge) = pair else {
323                    return false;
324                };
325                if child.get_value().is_some_and(|cn| cn.cod(graph) != Path::single(proedge)) {
326                    return false;
327                }
328            }
329        }
330        true
331    }
332
333    /** Is the double tree isomorphic to another?
334
335    This method simply checks whether the underlying open trees are
336    [isomorphic](OpenTree::is_isomorphic_to).
337     */
338    pub fn is_isomorphic_to(&self, other: &Self) -> bool
339    where
340        E: Eq,
341        ProE: Eq,
342        Sq: Eq,
343    {
344        self.0.is_isomorphic_to(&other.0)
345    }
346
347    /// Maps over the edges and squares of the tree.
348    pub fn map<CodE, CodSq>(
349        self,
350        mut fn_e: impl FnMut(E) -> CodE,
351        mut fn_sq: impl FnMut(Sq) -> CodSq,
352    ) -> DblTree<CodE, ProE, CodSq> {
353        self.0
354            .map(|dn| match dn {
355                DblNode::Cell(sq) => DblNode::Cell(fn_sq(sq)),
356                DblNode::Spine(e) => DblNode::Spine(fn_e(e)),
357            })
358            .into()
359    }
360}
361
362impl<V, E, ProE, Sq> DblTree<Path<V, E>, ProE, DblTree<E, ProE, Sq>> {
363    /// Flattens a double tree of double trees into a single double tree.
364    pub fn flatten(self) -> DblTree<E, ProE, Sq> {
365        let tree = self.0.map(|dn| match dn {
366            DblNode::Cell(tree) => tree.0,
367            DblNode::Spine(path) => OpenTree::linear(path.into_iter().map(DblNode::Spine))
368                .expect("Spine should be a non-empty path"),
369        });
370        tree.flatten().into()
371    }
372}
373
374impl<Arr, ProE, Sq> DblTree<Arr, ProE, DblTree<Arr, ProE, Sq>> {
375    /// Flattens a double tree of double trees into a single double tree.
376    pub fn flatten(self) -> DblTree<Arr, ProE, Sq> {
377        let tree = self.0.map(|dn| match dn {
378            DblNode::Cell(tree) => tree.0,
379            DblNode::Spine(f) => OpenTree::single(DblNode::Spine(f), 1),
380        });
381        tree.flatten().into()
382    }
383}
384
385#[cfg(test)]
386mod tests {
387    use ego_tree::tree;
388    use nonempty::nonempty;
389
390    use super::super::category::{WalkingBimodule as Bimod, WalkingFunctor as Funct, *};
391    use super::*;
392
393    #[test]
394    fn tree_dom_cod() {
395        let bimod = Bimod::Main();
396        let graph = UnderlyingDblGraph(Bimod::Main());
397        let path = Path::Seq(nonempty![Bimod::Pro::Left, Bimod::Pro::Middle, Bimod::Pro::Right]);
398        let mid = bimod.composite_ext(path).unwrap();
399        let tree = DblTree::two_level(
400            vec![bimod.id_cell(Bimod::Pro::Left), mid.clone(), bimod.id_cell(Bimod::Pro::Right)],
401            mid.clone(),
402            &graph,
403        );
404        let tree_alt = tree!(
405            Some(mid.clone()) => {
406                Some(bimod.id_cell(Bimod::Pro::Left)) => { None },
407                Some(mid.clone()) => { None, None, None },
408                Some(bimod.id_cell(Bimod::Pro::Right)) => { None }
409            }
410        );
411        let tree_alt = DblTree(OpenTree::from(tree_alt).map(DblNode::Cell));
412        assert_eq!(tree, tree_alt);
413        assert!(tree.contained_in(&graph));
414
415        assert_eq!(tree.arity(&graph), 5);
416        assert_eq!(
417            tree.dom(&graph),
418            Path::Seq(nonempty![
419                Bimod::Pro::Left,
420                Bimod::Pro::Left,
421                Bimod::Pro::Middle,
422                Bimod::Pro::Right,
423                Bimod::Pro::Right
424            ])
425        );
426        assert_eq!(tree.cod(&graph), Bimod::Pro::Middle);
427
428        // Trees with incompatible (co)domains.
429        let tree = tree!(
430            Some(mid.clone()) => {
431                Some(bimod.id_cell(Bimod::Pro::Left)) => { None },
432                Some(mid.clone()) => { None, None, None }
433            }
434        );
435        assert!(!DblTree(OpenTree::from(tree).map(DblNode::Cell)).contained_in(&graph));
436        let tree = tree!(
437            Some(mid.clone()) => {
438                Some(bimod.id_cell(Bimod::Pro::Right)) => { None },
439                Some(mid.clone()) => { None, None, None },
440                Some(bimod.id_cell(Bimod::Pro::Left)) => { None }
441            }
442        );
443        assert!(!DblTree(OpenTree::from(tree).map(DblNode::Cell)).contained_in(&graph));
444    }
445
446    #[test]
447    fn tree_src_tgt() {
448        let funct = Funct::Main();
449        let graph = UnderlyingDblGraph(Funct::Main());
450        let f = Funct::Arr::Arrow;
451        let unit1 = funct.unit_ext(Funct::Ob::One).unwrap();
452        let tree =
453            DblTree(OpenTree::linear(vec![DblNode::Spine(f), DblNode::Cell(unit1)]).unwrap());
454        let tree_alt = DblTree(
455            tree!(
456                Some(DblNode::Cell(unit1)) => { Some(DblNode::Spine(f)) => { None } }
457            )
458            .into(),
459        );
460        assert_eq!(tree, tree_alt);
461        assert!(tree.contained_in(&graph));
462
463        assert_eq!(tree.src(&graph), Path::pair(f, Funct::Arr::One));
464        assert_eq!(tree.tgt(&graph), Path::pair(f, Funct::Arr::One));
465        assert!(tree.dom(&graph).is_empty());
466
467        // Trees with incompatible sources and targets.
468        let comp = funct.composite2_ext(Funct::Ob::One, Funct::Ob::One).unwrap();
469        let tree = DblTree(
470            tree!(
471                Some(DblNode::Cell(comp)) => {
472                    Some(DblNode::Cell(unit1)) => {
473                        Some(DblNode::Spine(Funct::Arr::One)) => { None }
474                    },
475                    Some(DblNode::Cell(unit1)) => {
476                        Some(DblNode::Spine(f)) => { None }
477                    },
478                }
479            )
480            .into(),
481        );
482        assert!(!tree.contained_in(&graph));
483    }
484
485    #[test]
486    fn flatten_tree() {
487        let bimod = Bimod::Main();
488        let graph = UnderlyingDblGraph(Bimod::Main());
489        let path = Path::Seq(nonempty![Bimod::Pro::Left, Bimod::Pro::Middle, Bimod::Pro::Right]);
490        let unitl = bimod.unit_ext(Bimod::Ob::Left).unwrap();
491        let unitr = bimod.unit_ext(Bimod::Ob::Right).unwrap();
492        let mid = bimod.composite_ext(path).unwrap();
493        let tree = tree!(
494            Some(mid.clone()) => {
495                Some(bimod.id_cell(Bimod::Pro::Left)) => {
496                    Some(unitl.clone())
497                },
498                Some(mid) => {
499                    Some(unitl),
500                    Some(bimod.id_cell(Bimod::Pro::Middle)) => { None },
501                    Some(unitr.clone())
502                },
503                Some(bimod.id_cell(Bimod::Pro::Right)) => {
504                    Some(unitr),
505                }
506            }
507        );
508        let tree = DblTree(OpenTree::from(tree).map(DblNode::Cell));
509        assert_eq!(tree.dom(&graph), Path::single(Bimod::Pro::Middle));
510        assert_eq!(tree.cod(&graph), Bimod::Pro::Middle);
511
512        // Degenerate case: the outer tree is a singleton.
513        let outer: DblTree<Path<Bimod::Ob, Bimod::Ob>, _, _> =
514            OpenTree::single(DblNode::Cell(tree.clone()), tree.arity(&graph)).into();
515        assert_eq!(outer.flatten(), tree);
516
517        // Degenerate case: all inner trees are singletons.
518        let outer: DblTree<Path<Bimod::Ob, Bimod::Ob>, _, _> =
519            tree.clone().map(Path::single, |dn| DblTree::single(dn, &graph));
520        let result = outer.flatten();
521        assert!(result.is_isomorphic_to(&tree));
522    }
523}
catlog/dbl/tree.rs

catlog/dbl/
tree.rs
