Opened 6 years ago

Last modified 6 years ago

#14498 closed enhancement

trees and binary trees — at Version 14

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:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8703 Stopgaps:

Description (last modified by chapoton)

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

Apply:

Change History (21)

Changed 6 years ago by elixyre

comment:1 Changed 6 years ago by elixyre

  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by chapoton

Maybe there is a dependency on #8703 ?

comment:3 in reply to: ↑ 2 Changed 6 years ago by elixyre

  • Dependencies set to #8703

Replying to chapoton:

Maybe there is a dependency on #8703 ?

Yes that's true.

comment:4 Changed 6 years ago 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.

comment:5 follow-up: Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

Some doctests are failing, please correct them.

Changed 6 years ago by elixyre

comment:6 in reply to: ↑ 5 Changed 6 years ago by elixyre

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 6 years ago by elixyre

  • Cc viviane.pons@… added

comment:8 Changed 6 years ago by elixyre

  • Status changed from needs_work to needs_review

comment:9 Changed 6 years ago 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

comment:10 Changed 6 years ago 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

comment:11 follow-up: Changed 6 years ago by chapoton

please write which patches should be applied

  • in a comment, for the bot
  • in the description, for humans

comment:12 Changed 6 years ago 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...

Changed 6 years ago by darij

not a review but just a fix for a couple typos. Jean-Baptiste, can you please look this over and qfold into your patch?

comment:13 in reply to: ↑ 11 Changed 6 years ago 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 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 6 years ago by chapoton

  • 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

Note: See TracTickets for help on using tickets.