#8703: Combinatorial Rooted Ordered and Binary Trees
-----------------------------------------------------+----------------------
Reporter: hivert | Owner: hivert
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-5.7
Component: combinatorics | Resolution:
Keywords: trees, Cernay2012 | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Florent Hivert, Frédéric Chapoton | Merged in:
Dependencies: #8702 | Stopgaps:
-----------------------------------------------------+----------------------
Comment (by hivert):
Hi,
Thanks for all these comments. Before replying point by point, let me
mention
that there is a lot of work done around the trees and that several patch
are
waiting between this one. So we don't need to write everything in this
patch
and we hope to have it in Sage soon.
Replying to [comment:28 darij]:
> This is mostly way over my head, but I'm adding myself to cc because I'm
highly interested in what comes out of this.
>
> A bug: The as_digraph method yields not what it should yield when some
labels are equal. Example:
> I suggest rewriting as_digraph from scratch, no longer using the labels
as unique identifiers for nodes; independently, I think there should be
more doctests checking what happens to trees with equal labels.
When I wrote this function I plan to use it only for graph with distinct
label. I'm not sure what we want when there are repeated label. This must
be
discussed. The particular case of None is by chance handled by the graph
but
I'm not sure we should rely on it. In the mean time, I'd like to document
that
the function currently only work for graph with disctinct label and open a
new
ticket for more general cases. What do you think ?
> - I would add "BinaryTree([])" and "BinaryTree(None)"
> to the examples in te docstring of the BinaryTree class. Also, in the
> "INPUT" section, maybe add that [] is the same as [None, None]? I must
say
> the "INPUT" part of the docstring for BinaryTree doesn't exactly explain
to
> me how exactly the "children" argument is getting parsed; I am used to
> constructors for trees being free (in the sense of, no two different
inputs
> lead to the same tree), so I wouldn't say this is very intuitive. It's
> "explained" in the __init__ sourcecode, but that's uncommented and I
have no
> idea what it does :(
The idea is that to allows for short input, None can be omitted where
there is
no ambiguity. Please, feel free to suggest a patch for doc improvements.
> Might also want to point out that these binary trees are planar aka what
you
> call ordered, i. e., the order of the children on each node matters.
When you see tree from the graph point of view, all trees are of course
planar
(IE: can be embedded in the plane without crossing). So I rather call them
ordered trees. From this point of view, the proper name is plane tree (See
eg
http://en.wikipedia.org/wiki/Tree_%28graph_theory%29#Plane_Tree). Note
that
they freely mix plane and ordered there. I feel (and I wasn't alone when
discussed on Sage-combinat-devel) that OrderedBinaryTree is too long.
> - In the "show" method of BinaryTree, can the tree_orientation be passed
as
> a keyword? I know a lot of people who don't draw trees upside down...
Unless a quick fix is proposed, I'd rather leave it for a forthcomming
patch.
> - I don't understand from the docstrings what "make_node" and
"make_leaf"
> do... Just replace the tree by a node resp. leaf? If so, what's the
> advantage over just redefining the tree?
Some times it could be useful for algorithmic reason to modify a tree in
place
without allocating a new object.
> - ordered_tree.py: Isn't this kind of "ordered trees" usually called
planar trees? (Not like I want anything renamed. But it might be good to
point out in the docstring that these ordered trees are not, e. g.,
Foissy's ordered trees.)
See my former comment on planar being improper.
> - This appears weird to me: "The actual canonical labelling is currently
> unspecified." Isn't it just the left-to-right labelling, or are you
saying
> that we shouldn't count on it staying that way?
Yes it is for ordered trees, but it is defined in an abtract class and
soon
after this patch there is another one for rooted unordered tree. Then
left-to-right labelling doesn't mean anything. There is also another
forthcoming patch where you can specify which order you want. I don't want
to
choose the default now.
> Suggestions (I can figure myself working on them as well):
> Do we have a checker function that looks if a given labelled binary tree
is
> a binary search tree? A decreasing tree? The RSK-like algorithms from
> http://arxiv.org/abs/math/0401089 ? An binary_search_tree and an
> increasing_tree method for arbitrary words, not just permutations? (The
"gen
> = self[::-1]" trick won't work here anymore, though.) Oh, well, and
forests,
> of course, even if they can be internally the same as trees with one
more
> vertex...
There is also several other patch done around those question. In the
Sage-combinat queue there are implementation of the Loday-Ronco algebra,
the
dendriform, prelie operads and more. As I said, this is just the beginning
:-).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8703#comment:30>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
