Trees

Discussions about Trees combinatorial classes

Reorganization

We need to cleanup our combinatorial classes for trees to clearly separate the implementation of the tree data structures and of he various methods that are available depending on the specific cases (binary, complete, ...). The current organization essentially has the required functionalities, but causes problems with inheritance (typically, labelledBinaryTrees can't inherit simultaneously from binaryTrees and labelledTrees). It also lacks systematic naming conventions.

Here is a proposition:

domain combinat::trees (rootedTrees? treesRooted? trees::rooted?)

Implementation of the ordered rooted tree data structure

TODO

• mapLabels maps a function on all labels of a tree (to be extracted and sent by FrédéricChapoton from its shift methods) could be generalized to all our labelled combinatorial classes
• mapLeaves maps a function on all labels of the leaves

domain combinat::binaryTrees (trees::binary?)

Implementation of the ordered binary tree data structure. Inherits from combinat::trees, with small changes to the convert methods and friends to guarantee that the structure invariants are respected.

TODO: Define options Left and Right for binary trees walks

domain combinat::freeTrees (treesFree? trees::free?)

Implementation of unrooted trees (or free trees in Knuth terminology)

TODO

• labelled Trees & Prufer correspondance (in progress, NicolasThiéry)

Note that we may think of variants on those basic implementations. For example, the computations in certain tree algebras require to very often ask for the size of a tree. To make this a constant time operation, we could store recursively at each node the size of the corresponding subtree.

category Cat::TreesClass? (DONE)

Specialization of Cat::DecomposableClass for combinatorial classes with a Tree-type specification. Most of the tree domains, including those above inherits from it. It provides the combinatorial class functions that can be implemented via decomposable techniques: list, count, random, ...

category Cat::(Ordered)Trees (Cat::Trees::Ordered?) (if needed)

May become useful to factorized code and standardize the interfaces if we come up some day with some other implementations of ordered trees (that's coming!)

category Cat::BinaryTrees? (Cat::Trees::Binary?)

Methods that are specific to binary trees, independently on the underlying implementation.

category Cat::LabelledTrees? (Cat::Trees::Labelled?) (if needed)

Methods that are specific to labelled trees, independently on the underlying implementation.

category Cat::Trees::LabelledOnLeaves??

Trees, counted by number n of leaves, which are labelled by a permutation of n. Can have other labels on internal nodes.

Operations

• grafting at a label (which includes shifting of the bigger labels)
• multigrafting(t, t1,t2,t3) graft simultaneously t1 on leaf 1, t2 on leaf 2, ...
• power(t,s) : multigraft(t, s,s,s,s,s)

category Cat::ReducedTrees? (Cat::Trees::Reduced?)

Methods that are specific to reduced trees (no node of arity 1)

...

domain combinat::treesGeneric (trees::generic?) (DONE)

Parametrized domain for building all kinds of trees. Essentially a wrapper around Cat::TreesClass?, which inherits from combinat::trees, combinat::binaryTree or combinat::freeTrees

domain combinat::labelledTrees, labelledBinaryTrees

Specialization of combinat::treesGeneric for the most often used cases. Not necessarily required, apart for backward compatibility.

Note that we do not have separate implementation domains for labelled trees. This is for the following reasons:

• there are too many variations of labelled trees (labels on internal nodes, on leaves, on both)
• our data structure can handle all of them rather seamlessly, except for the dummy label trick
• most methods don't care if the tree is labelled or not, and when they do, they usually can deal with it on a node basis during the recursion. So, there is no need to have 4 distinct implementations depending on where the labels are.

Issues:

• Systematic naming scheme: treesBinary, binaryTrees, or trees::binary?
• Do we want to type differently all kinds of trees? Or should we have just three true domains (rooted trees, binary trees, free trees), all the other being facade domains?
• Does this organization resolve all the known and foreseeable needs?

• How should one store a leaf t of a binary tree? Right now, this is as a node having two empty childs. That is we store a binary tree as it's corresponding complete binary tree for the usual bijection. This is easier to describe in the specification, and this ensures that we can always do op(t,1) or op(t,2). However, it makes it difficult to detect when a node is a leave, and this wastes some memory. It also makes binary trees more different from usual trees, and in particular complete binary trees. Typically, trees::print does not deal very well with those empty childs.

  Another approach would be to tweak combinat::binaryTrees::convert to remove the two empty childs. This does not require to change the specification. Furthermore, we could tweak op/subsop and friends to work properly (return zero, add two childs on the fly, ...). Should we do it?