[Sage] #14498: trees and binary trees
Sage
-----------------------------+----------------------------------------------
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.10
Component: combinatorics | Keywords: trees, binary trees, latex
Work issues: | Report Upstream: N/A
Reviewers: | Authors: Jean-Baptiste Priez
Merged in: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------------------
Hi,
I purpose several methods for trees and binary trees:
File : trees_classicals_algorithms_EliX-jbp:
several classical operations on trees and binary trees
- on abstract trees:
* depth pre/post order transversal algorithms
* breadth first order transversal algorithm
- on binary trees:
* infix order transversal algorithm
* canonical permutation associated to the left/right binary search tree
insertion
* left/right rotate (for labelled and unlabelled BT)
File: trees_research_algorithms_EliX-jbp:
several research algorithms on binary trees
- over/under (Loday-Ronco)
- pred/succ in the tamari lattice
- hook length formula
File: trees_latex_output_EliX-jbp:
a method for nice latex output
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
Dependencies: | Stopgaps:
Changes (by elixyre):
* status: new => needs_review
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:1>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
Dependencies: | Stopgaps:
Comment (by chapoton):
Maybe there is a dependency on #8703 ?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:2>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Changes (by elixyre):
* dependencies: => #8703
Comment:
Replying to [comment:2 chapoton]:
> Maybe there is a dependency on #8703 ?
Yes that's true.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:3>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by darij):
A nice step towards the Hopf algebras. Some comments:
@Classical algorithms:
Typo appearing twice: "explorer" (should be "explores"). Also, "An other"
-> "Another".
Not sure, but I also think "transversal" should be "traversal".
The docstrings fail to explain an important point: what exactly
"manipulate" means (and, correspondingly, what the "action" variable is
for). The first time I read them I thought the methods output the list of
nodes in the respective order! The doc for ``in_order_transversal`` should
explain the difference between node_action and leaf_action. By the way,
why do the other methods have only 1 type of action?
The example for ``in_order_transversal`` has two different things called
"b". Not a big issue, of course.
I don't understand what "the canonical permutation associated to the
binary search tree insertion" is supposed to mean; is this a notation from
one of Loday(-Ronco)'s papers?
Copypaste error: the docstring for ``left_rotate`` says "Right". (Both
times.)
@Research algorithms:
Is computing the hook_length_formula by symbolic integration really easier
than just recursively multiplying the hook_length_formulas for the left
and right subtrees and then multiplying by an appropriate binomial
coefficient? I'm not saying it isn't, just asking.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:4>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.10
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Changes (by chapoton):
* status: needs_review => needs_work
Comment:
Some doctests are failing, please correct them.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:5>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by elixyre):
This new patch contains all the modifications.
Replying to [comment:4 darij]:
> Typo appearing twice: "explorer" (should be "explores"). Also, "An
other" -> "Another".
>
> Not sure, but I also think "transversal" should be "traversal".
Typo ok?
> The docstrings fail to explain an important point: what exactly
"manipulate" means (and, correspondingly, what the "action" variable is
for). The first time I read them I thought the methods output the list of
nodes in the respective order! The doc for ``in_order_transversal`` should
explain the difference between node_action and leaf_action. By the way,
why do the other methods have only 1 type of action?
I tried to explain what is "action". But my english is very bad so...
About, ``action`` and ``leaf/node_action``... The distinction between leaf
and node on Abstract Trees class is not clear for me.
> I don't understand what "the canonical permutation associated to the
binary search tree insertion" is supposed to mean; is this a notation from
one of Loday(-Ronco)'s papers?
The term canonical is may be not a good choose, this method is suppose to
compute a representant of the ``sylvester class``...
> Copypaste error: the docstring for ``left_rotate`` says "Right". (Both
times.)
OK
> @Research algorithms:
>
> Is computing the hook_length_formula by symbolic integration really
easier than just recursively multiplying the hook_length_formulas for the
left and right subtrees and then multiplying by an appropriate binomial
coefficient? I'm not saying it isn't, just asking.
I implement the `q_hook_length_formula`.
Replying to [comment:5 chapoton]:
> Some doctests are failing, please correct them.
OK
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:6>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Changes (by elixyre):
* cc: viviane.pons@… (added)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:7>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_review
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Changes (by elixyre):
* status: needs_work => needs_review
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:8>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by VivianePons):
Hi,
I cannot apply your patch, maybe it's conflicting with #14731 and #14784
which have already been positively reviewed are already or will be merged
in sage 5.11. Also, we actually wrote twice the same things, I have two
methods "to_132_avoiding_permutation" and "to_312_avoiding_permutation"
which are somehow similar to your "canonical_permutation". I think we
should keep my name which is clearer. But for these methods, I wrote a
"_postfix_word" method which is similar to your "post_order_traversal"
thing (but I think yours is better and with better documentation). But my
patch has already been merged, so you should write yours on top of mine
and just replace my methods by yours when they're better.
About names, I think "sylvestrohedron_greater" is not a good name, we
should say "Tamari_greater", because it's more commonly used.
Do you want to come to Marne-la-vallee so that we can work on the merge of
your patch with mine? I'll be there Thursday, Friday and Monday. Then
again at the end of July. Please tell me
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:9>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by elixyre):
Hi,
I have removed canonical permutation and add some other classical methods
on trees (is_perfect, complete, ...).
I don't modify your "_postfix_word" with "post_order_traversal" because it
is more specific... in the traversal algorithm we don't care about the
children order.
The "sylvestrohedron" is become "tamari".
Thanks, JB
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:10>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by chapoton):
please write which patches should be applied
* in a comment, for the bot
* in the description, for humans
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:11>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by darij):
Hi Jean-Baptiste, thanks for the changes (but aren't the "An other" and
"explorer" typos still there?).
In the q-hook-length formula, are you sure you want to work in the
symbolic ring? That is, you really want not to do any cancellations? For
example, your doctested example
{{{
sage: BinaryTree([[],[]]).q_hook_length_formula()
(((q + 2)*q + 2)*q + 1)*q/((q + 1)*q + 1)
}}}
simplifies to {{{q^2 + q}}}. I have not done any speed tests, but I would
be surprised if the fraction field of a univariate polynomial ring wasn't
faster than the symbolic ring (also I don't trust the symbolic ring, but
this might be unfounded). Alternatively, you can make a recursive
computation with q-binomial coefficients that never leaves the polynomial
ring; but not sure if this is very efficient (q-binomial coefficient might
be dense).
I think the formula in the docstring of q_hook_length_formula() doesn't
match the algorithm. In the formula, there is a positive power of q in the
denominator (which should give a Laurent polynomial, not a polynomial),
while in the algorithm there is a negative power of q in the denominator
(which gives a polynomial divisible by some power of q in the end). I'm
not sure why the power of q is there at all...
I hate to say I am still confused by the input syntax of trees:
{{{
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).canonical_labelling()
sage: parent(b)
Labelled binary trees
sage: b
3[1[., 2[., .]], 7[5[4[., .], 6[., .]], 8[., .]]]
sage: OrderedTree(b)
[[[], [[], []]], [[[[], []], [[], []]], [[], []]]]
sage: b.node_number()
8
sage: OrderedTree(b).node_number()
17
}}}
Apparently the coercion(!) from b to an ordered tree replaces every leaf
by a node with two children because for some reason leaves of binary trees
are stored as nodes-with-two-children internally. This is all defensible
from some viewpoint, but I want it doced. Once somebody clears this up I
would volunteer to review #14498, but so far I don't want to spread my own
confusion...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:12>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Comment (by elixyre):
Hello,
I added your modifications and I modify *q_hook_length_formula* with ... I
am not sure about what to do with that... could you check it is correct
now.
Replying to [comment:11 chapoton]:
> please write which patches should be applied
>
> * in a comment, for the bot
> * in the description, for humans
For human, apply: trac_14498_algorithms_trees_13_07_15_EliX-jbp.patch
For the bot... I don't know how to do a comment.
Thanks,
Jean-Baptiste
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:13>
Sage
Reporter: elixyre | Owner: sage-combinat
Priority: major | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Old description:
> Hi,
>
> I purpose several methods for trees and binary trees:
>
> File : trees_classicals_algorithms_EliX-jbp:
> several classical operations on trees and binary trees
> - on abstract trees:
> * depth pre/post order transversal algorithms
> * breadth first order transversal algorithm
> - on binary trees:
> * infix order transversal algorithm
> * canonical permutation associated to the left/right binary search
> tree insertion
> * left/right rotate (for labelled and unlabelled BT)
>
> File: trees_research_algorithms_EliX-jbp:
> several research algorithms on binary trees
> - over/under (Loday-Ronco)
> - pred/succ in the tamari lattice
> - hook length formula
>
> File: trees_latex_output_EliX-jbp:
> a method for nice latex output
Hi,
I purpose several methods for trees and binary trees:
File : trees_classicals_algorithms_EliX-jbp:
several classical operations on trees and binary trees
- on abstract trees:
* depth pre/post order transversal algorithms
* breadth first order transversal algorithm
- on binary trees:
* infix order transversal algorithm
* canonical permutation associated to the left/right binary search tree
insertion
* left/right rotate (for labelled and unlabelled BT)
File: trees_research_algorithms_EliX-jbp:
several research algorithms on binary trees
- over/under (Loday-Ronco)
- pred/succ in the tamari lattice
- hook length formula
File: trees_latex_output_EliX-jbp:
a method for nice latex output
* [attachment:trac_14498_algorithms_trees_13_07_15_EliX-jbp.patch]
--
Comment (by chapoton):
well, what you have just written is a '''comment'''. And what I write now
is another one.
for humans, I have added one line in the '''description''' (see top of the
page)
for the bot, you just have to write the following line
apply trac_14498_algorithms_trees_13_07_15_EliX-jbp.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:14>
Sage
Reporter: elixyre | Owner: sage-combinat
Type: enhancement | Status: needs_work
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: Jean-Baptiste Priez | Merged in:
----------------------------------------------+-----------------------------
Changes (by chapoton):
* status: needs_review => needs_work
Comment:
the patch does not apply on 5.11.beta3
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14498#comment:15>