Opened 9 years ago
Closed 8 years ago
#14498 closed enhancement (fixed)
trees and binary trees
Reported by: | elixyre | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | combinatorics | Keywords: | trees, binary trees, latex |
Cc: | florent.hivert@…, viviane.pons@…, chapoton, ncohen | Merged in: | |
Authors: | Jean-Baptiste Priez | Reviewers: | Darij Grinberg, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | public/ticket/14498 (Commits, GitHub, GitLab) | Commit: | 4e8fdd036a5644ca661b3b39191cfce37d5b22b9 |
Dependencies: | #8703, #14784 | Stopgaps: |
Description (last modified by )
Hi,
I propose 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 algorithm
- 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
Apply:
Attachments (15)
Change History (84)
Changed 9 years ago by
Changed 9 years ago by
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 9 years ago by
comment:3 in reply to: ↑ 2 Changed 9 years ago by
- Dependencies set to #8703
comment:4 Changed 9 years ago by
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.
comment:5 follow-up: ↓ 6 Changed 9 years ago by
- Status changed from needs_review to needs_work
Some doctests are failing, please correct them.
Changed 9 years ago by
comment:6 in reply to: ↑ 5 Changed 9 years ago by
This new patch contains all the modifications.
Replying to 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 chapoton:
Some doctests are failing, please correct them.
OK
comment:7 Changed 9 years ago by
- Cc viviane.pons@… added
comment:8 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:9 Changed 9 years ago by
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
Changed 9 years ago by
comment:10 Changed 9 years ago by
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
comment:11 follow-up: ↓ 13 Changed 9 years ago by
please write which patches should be applied
- in a comment, for the bot
- in the description, for humans
comment:12 Changed 9 years ago by
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...
Changed 9 years ago by
not a review but just a fix for a couple typos. Jean-Baptiste, can you please look this over and qfold into your patch?
Changed 9 years ago by
comment:13 in reply to: ↑ 11 Changed 9 years ago by
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 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
comment:14 Changed 9 years ago by
- Description modified (diff)
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
comment:15 Changed 9 years ago by
- Status changed from needs_review to needs_work
the patch does not apply on 5.11.beta3
comment:16 Changed 9 years ago by
- Dependencies changed from #8703 to #8703, #14784
- Status changed from needs_work to needs_review
comment:17 Changed 9 years ago by
Hi every one,
I don't understand why the patchbot don't work... I try (again) on my 5.11beta3 and all seems to be for me... Someone can looks that??
Thanks,
Jean-Baptiste Priez
comment:18 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:19 follow-up: ↓ 20 Changed 9 years ago by
Have you made your patch using "hg export" or in some other strange way (by hand) ?
The standard process is to use
hg export tip > $HOME/trac_xxx.patch
to export the patch as a file, after making sure your patch is the top applied patch. Then upload the resulting file to trac.
Any other way is bound to have strange results..
It looks like you have concatenated several patches by hand maybe ? You must use hg qfold to do that.
---
Quick comments on the code:
it is a bad idea to use
q = SymbolicRing().var('q')
to have a polynomial variable. Much better is
q = polygen(QQ, 'q')
In the same hook-length function, you should write "There are 20 permutations"
comment:20 in reply to: ↑ 19 Changed 9 years ago by
Hello,
Replying to chapoton:
Have you made your patch using "hg export" or in some other strange way (by hand) ?
The standard process is to use
hg export tip > $HOME/trac_xxx.patchto export the patch as a file, after making sure your patch is the top applied patch. Then upload the resulting file to trac.
I use
sage: hg_sage.apply(...)
Any other way is bound to have strange results..
I will try to use hg export
...
It looks like you have concatenated several patches by hand maybe ? You must use hg qfold to do that.
---
Quick comments on the code:
it is a bad idea to use
q = SymbolicRing().var('q')to have a polynomial variable. Much better is
q = polygen(QQ, 'q')In the same hook-length function, you should write "There are 20 permutations"
Thanks for comment, i will modify that.
comment:21 Changed 9 years ago by
- Status changed from needs_review to needs_work
the patch does not applies on 5.12.beta3
as long as the patch is not clean, this cannot be considered as "needs review"
comment:22 Changed 9 years ago by
- Status changed from needs_work to needs_info
Hello,
May be, I understand nothing but my patch apply in sage 5.12.beta5.
If there is a problem, it doesn't appear on my laptop. (Sage on Mac os is more clever than on linux!)
So if the patch does not applies again, please correct that because I don't have that problem... when that thing will be solve I will modify _q = SymbolicRing?.._ if you don't do it but now I don't want spend 3hours to make a new patch (which doesn't applies) for one simple line...
comment:23 Changed 9 years ago by
Hey Jean-Baptiste,
The patch applies for me on 5.12.beta5 (in the combinat queue), but there doesn't seem to be anything that could be a dependency. My guess is the patched together patch (sorry, couldn't resist the pun) is why it's not applying, and I agree that this needs to be fixed.
Also, because of the accented character, you need to add
# -*- coding: utf-8 -*-
as the first line of binary_tree.py
(I put a small patch in the combinat queue which does this).
Thanks,
Travis
comment:24 Changed 9 years ago by
Hello Travis,
maybe you can backport the patch from the sage-combinat queue to trac (folded with your small patch) ?
Frederic
comment:25 Changed 9 years ago by
- Description modified (diff)
comment:26 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
Hey everyone,
Here's a new version with my patch small header patch folded in, the patch file cleaned up, and my docstring tweaks (I also marked some tests as # long time
).
Best,
Travis
For patchbot:
Apply: trac_14498-algorithms_trees-rebased.patch
Changed 9 years ago by
comment:27 Changed 9 years ago by
apply trac_14498-algorithms_trees-rebased.patch
comment:28 Changed 9 years ago by
- Cc chapoton ncohen added
comment:29 Changed 9 years ago by
I have just uploaded trac_14498-tree-imps-dg.patch (to be applied after trac_14498-algorithms_trees-rebased.patch) which should fix #15060 and clear up some of the vertex-vs.-node confusion on binary trees. Can anyone look over it and tell me if I got things right? I cannot really start reviewing this patch before this is sorted out.
comment:30 Changed 9 years ago by
I have renamed and mostly redone the q-hook length formula method. Elixyre, is it still what you wanted? Among other changes,
- the default option now has no q-factor,
- the q-factor is determined by the right child (as the doc said) rather than the left one (as the earlier code did),
- the computation is being done in whatever ring the user is given, rather than the symbolic ring.
comment:31 Changed 9 years ago by
I have posted a new version of trac_14498-tree-imps-dg.patch. Unfortunately a lot more is needed for a review, but I think this is a step forward. The following issues have been fixed:
- The issues discussed in #14564 (leaves vs. leaves-and-nodes inconsistencies, and border cases) have been fixed.
- The implementation and the documentation of the q-hook-length formula has been revamped (even the name is now different).
- Various documentation has been rewritten.
Things that remain to be done:
BinaryTree()
is a functioning shortcut forBinaryTree(None)
, butLabelledBinaryTree()
is not a functioning shortcut forLabelledBinaryTree(None)
. Should this be fixed? Using init_extra?
- It is not obvious to me that the
tamari_succ
andtamari_prec
methods actually compute the successors resp. predecessors in the Tamari order. Is there a proof somewhere in the literature? It's clear that every successor of a tree t in the Tamari poset is obtained by a right rotation, but is it clear that every right rotate is actually a successor?
- The
over
method defines the "over" operation. As I wrote in the docstring: " Fix this doc and figure out which of the different (inconsistent?) notations to follow. I don't see the "over" operation defined in [LodayRonco?]_, although [HNT05]_ pretends that it is defined there. In [HNT05]_ the definition is somewhat vague about the order of the operads. Loday and Ronco seem to define "over" on page 2 of "Order structure on the algebra of permutations and of planar binary trees", but with a different choice of left/right."
- The docstring of the class
LabelledBinaryTree
could be less barren; in particular it could explain how to initialize these.
- The
binary_search_insert
docstring might use a definition of binary search insertion, given that most sources only do it in the standard (i. e., no two equal labels) case.
I fear I won't come back to this patch very soon, so everyone who feels like improving these is invited to do so.
For the patchbot:
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg.patch
comment:32 Changed 9 years ago by
- Description modified (diff)
comment:33 Changed 9 years ago by
patchbot apply trac_14498-algorithms_trees-rebased.patch,trac_14498-tree-imps-dg.patch
comment:34 Changed 9 years ago by
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg.patch
comment:35 Changed 9 years ago by
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg.patch
comment:36 Changed 9 years ago by
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg.patch
comment:37 Changed 9 years ago by
- Description modified (diff)
Darij, I have rebased your patch, it was not applying cleanly.
patchbots, please
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch
comment:38 Changed 9 years ago by
new patch, correcting the failing doctest
comment:39 Changed 9 years ago by
Frederic, I think that my patch was supposed to apply atop of trac_14498-algorithms_trees-rebased.2.patch , not atop of trac_14498-algorithms_trees-rebased.patch. Is that the reason for the unclean apply?
EDIT: OOPS, I am just seeing that it was me who fucked up the apply declaration. Sorry!
It should be
apply trac_14498-algorithms_trees-rebased.2.patch trac_14498-tree-imps-dg.patch
Is there a chance you could rebase your changes back? Thanks a lot. (A qfold would probably be best. It seems that once a something.2.patch file appears, chaos is bound to happen.)
comment:40 Changed 9 years ago by
Hello,
well, I would rather not change anything back. It was a very simple rebase, and I am rather sure there is nothing lost in your patch. I have checked that nothing has got lost in Travis patch, too.
So let us stay with
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch
Changed 9 years ago by
comment:41 Changed 9 years ago by
I have now made further corrections to the documentation.
comment:42 Changed 9 years ago by
Hi Federic,
I didn't want to say anything got lost in *my* patch. It's Travis' patch where things could have gotten lost. But I'm seeing that you re-did all of the edits present in trac_14498-algorithms_trees-rebased.2.patch but absent from trac_14498-algorithms_trees-rebased.patch. So nothing got lost. Sorry again for the trouble!
Darij
comment:43 Changed 9 years ago by
The non-ascii character should be okay since the corresponding file has UTF-8 encoding. I'm thinking the startup time increase is due to setting up the latex stuff in abstract_tee.py
and that probably should be done in the _latex_()
method the first time it is called. Any objections to moving it there?
Best,
Travis
comment:44 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Darij Grinberg, Frederic Chapoton
I've completed my review of this patch, but due to its size (and its introduction of another method for my own research) someone will have to review my review. Frederic?
Thanks Viviane for the help with Loday's over/under operations. I still can't find them in the Loday-Ronco paper, but at least I now know their definitions!
Yes, my patch applies *on top* of the algorithms and tree-imps patches. Sorry for the typo in the trac number.
for the patchbot:
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch trac_14998-more-edits-dg.patch
comment:45 follow-up: ↓ 46 Changed 9 years ago by
- Description modified (diff)
Sorry guys. Had to introduce further docfixes after noticing that several methods fail to preserves labels on leaves of binary trees. The whole issue of leaves not being fully-accepted vertices of binary trees is extremely confusing...
for the patchbot:
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch trac_14998-more-edits-dg.patch trac_14498-further-docfixes-dg.patch
comment:46 in reply to: ↑ 45 Changed 8 years ago by
Corrected sphinx in my latest .patch file.
for the patchbot:
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch trac_14998-more-edits-dg.patch trac_14498-further-docfixes-dg.patch
comment:47 Changed 8 years ago by
Darij, there was an unvisible space in your last order for the patchbot. Beware of unvisible spaces !
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-dg-rebased.patch trac_14998-more-edits-dg.patch trac_14498-further-docfixes-dg.patch
comment:48 Changed 8 years ago by
- Branch set to u/chapoton/14498
- Commit set to ab20878830b3a18a1496bf2917db4ed71cdf04d5
I have made a branch.
New commits:
ab20878 | trac #14498: more doc fixes |
6e528a1 | trac #14498: Darij's review patch, to be applied ATOP of trac_14498-algorithms_trees-rebased.patch and trac_14498-tree-imps-dg-rebased.patch |
2a51f2c | trac #14498: some improvements on trees |
b186d9e | algorithms for trees and latex output |
comment:49 Changed 8 years ago by
I thought I had gotten rid of the ghost spaces in my latest post? (That was actually the reason why I reposted the patchbot instructions.)
comment:50 Changed 8 years ago by
- Commit changed from ab20878830b3a18a1496bf2917db4ed71cdf04d5 to 0df978e3100c0325aebdb97372d51e479b91d381
Branch pushed to git repo; I updated commit sha1. New commits:
9af8039 | algorithms for trees and latex output
|
54a4116 | trac #14498: some improvements on trees
|
285db68 | trac #14498: Darij's review patch, to be applied ATOP of trac_14498-algorithms_trees-rebased.patch and trac_14498-tree-imps-dg-rebased.patch
|
fc5e604 | trac #14498: more doc fixes
|
c929ca3 | trac #14498 whitespace removal and rebase on 6.1.beta5
|
0df978e | Merge branch 'u/chapoton/14498' of ssh://trac.sagemath.org:22/sage into 14498
|
comment:51 Changed 8 years ago by
Uhm, what happened here? Rebase AND merge? Looks like the branch is doubled now...
comment:52 Changed 8 years ago by
Hello,
not sure of what I did.. I wanted to clean up a few whitespace errors. And to rebase on 6.1.beta5, to try to get the patchbot do something useful. I guess I am still not a master of git.. Hope that I broke nothing.
comment:53 Changed 8 years ago by
Ah, no problem. Your branch is fine if you ask me; it just is way more complicated than necessary. (But I'm not good at merging myself; when there is conflict, I usually end up reverting the conflicting edits from my branch and then reinstating them after the merge.)
comment:54 Changed 8 years ago by
Oops, I messed up the definition of the overlapping shuffle product. I'll fix this shortly.
comment:55 Changed 8 years ago by
- Branch changed from u/chapoton/14498 to public/ticket/14498
- Commit changed from 0df978e3100c0325aebdb97372d51e479b91d381 to 812926abb310ea224ac98fb71544c50503d845f0
comment:56 Changed 8 years ago by
Fixed! (Note the branch change.)
Sorry for creating that bug in the first place.
comment:57 Changed 8 years ago by
- Commit changed from 812926abb310ea224ac98fb71544c50503d845f0 to d54d45fc65fa87dc03d8f47e9739fd9fc5d3235d
Branch pushed to git repo; I updated commit sha1. New commits:
d54d45f | oops one more
|
comment:58 Changed 8 years ago by
- Commit changed from d54d45fc65fa87dc03d8f47e9739fd9fc5d3235d to f81e14f40670cc8d3948579034869fcb2b93479b
Branch pushed to git repo; I updated commit sha1. New commits:
f81e14f | trac #14498 details, review in progress
|
comment:59 Changed 8 years ago by
I am trying to read all this stuff. It looks almost good to go. Review is in progress.
comment:60 Changed 8 years ago by
- Reviewers changed from Darij Grinberg, Frederic Chapoton to Darij Grinberg, Frédéric Chapoton
comment:61 Changed 8 years ago by
- Commit changed from f81e14f40670cc8d3948579034869fcb2b93479b to 91953899f4a7c76ccf4f8a44555bf2a53f554642
Branch pushed to git repo; I updated commit sha1. New commits:
9195389 | trac #14498 more details, review
|
comment:62 Changed 8 years ago by
Ok, things look good to me. Darij, could you please look at my last two commits and give a positive review if you agree with them ?
comment:63 Changed 8 years ago by
Frederic: thanks a lot, but I think the LodayRonco? reference is confusing and a warning about it should be there (whether it's mine or a new one). I don't see them defining "over" and "under"; I see them defining two operations called "left and right product", denoted \succ and \prec. Are they the same operations? Either way, it would be better to also add the "Order structure on the algebra of permutations and of planar binary trees" reference.
Everything else is fine!
comment:64 Changed 8 years ago by
Actually, they have nothing to do with over and under. The reference is wrong here. Let me fix this.
comment:65 Changed 8 years ago by
- Commit changed from 91953899f4a7c76ccf4f8a44555bf2a53f554642 to 4e8fdd036a5644ca661b3b39191cfce37d5b22b9
comment:66 Changed 8 years ago by
Changes committed. (Apart from the over/under issue, I noticed that removing the root should not be mentioned as part of a recursive procedure.) If you are fine with them, please set to positive review -- and thanks a lot for making sense of this ticket!
comment:67 Changed 8 years ago by
- Status changed from needs_review to positive_review
ok, thanks. Positive review.
comment:68 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:69 Changed 8 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Maybe there is a dependency on #8703 ?