#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 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:
{{{
sage: Q = LBT([LBT([],label=2),LBT([],label=4)],label=2)
sage: Q.as_digraph()
Digraph on 2 vertices
sage: Q
2[2[., .], 4[., .]]
}}}
While small examples suggest that this doesn't happen with "None" labels,
this isn't actually the case (even though they somehow magically become
nonnegative integers):
{{{
sage: Z = LabelledOrderedTree([[],[[[],[]], []]])
sage: Z
None[None[], None[None[None[], None[]], None[]]]
sage: Z.as_digraph()
Digraph on 5 vertices
}}}
I suggest rewriting as_digraph from scratch; independently, I think there
should be more doctests checking what happens to trees with equal labels.
Some docstring gripes:
- 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 :(
Might also want to point out that these binary trees are planar, i. e.,
the order of the children on each node matters.
- 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...
- 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?
- Docstring for "to_dyck_word": replace "where `T(l)` and `T(r)` are the
trees" by "where `T(l)` and `T(r)` are the Dyck words".
- The docstring for "canopee" has a grammar error ("`1` is a left leaf"
should be "`1` if the leaf is a left leaf").
- 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.)
- Couple of typos in the docstring for OrderedTree: "a constructed" and
"the the order".
- 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?
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...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8703#comment:28>
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.
