Opened 7 years ago

Closed 4 years ago

#8703 closed enhancement (fixed)

Combinatorial Rooted Ordered and Binary Trees

Reported by: hivert Owned by: hivert
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords: trees, Cernay2012
Cc: chapoton, sage-combinat, VivianePons, darij Merged in: sage-5.10.beta0
Authors: Florent Hivert, Frédéric Chapoton Reviewers: Florent Hivert, Frédéric Chapoton, Viviane Pons
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8702, merge with #14433 Stopgaps:

Description (last modified by tscrim)

The patch defines several new classes for dealing with

  • rooted recursive ordered trees (labelled and not)
  • binary trees (labelled and not)

It also add the computation of the binary search tree and the decreasing or increasing tree for a permutation

It finally defines the bijection to Dyck words

Apply:

Attachments (10)

trac_8703-trees-fh.patch (96.0 KB) - added by stumpc5 4 years ago.
trac_8703-additional-feature-fh.patch (3.2 KB) - added by hivert 4 years ago.
trees.tar.gz (20.3 KB) - added by darij 4 years ago.
attempting manual override
trac_8703-trees_addition-dg.patch (4.3 KB) - added by darij 4 years ago.
docstrings improved. let's see if this works…
trac_8703-trees-fh-rebase.patch (96.0 KB) - added by VivianePons 4 years ago.
trac_8703-additional-feature-vp.patch (3.3 KB) - added by VivianePons 4 years ago.
trac_8703-trees_addition-dg-v2.patch (23.4 KB) - added by chapoton 4 years ago.
trac_8703-review-fc.patch (11.2 KB) - added by chapoton 4 years ago.
trac_8703-trees-folded.patch (94.5 KB) - added by hivert 4 years ago.
trac_8703-trees-rebased.patch (94.3 KB) - added by tscrim 4 years ago.

Download all attachments as: .zip

Change History (77)

comment:1 Changed 7 years ago by hivert

  • Cc chapoton added

This is an experiment to see if user chapoton is receiving e-mail from trac...

comment:2 Changed 7 years ago by hivert

Updated a new patch after modification in #8702. Close to but not ready for review.

comment:3 Changed 7 years ago by hivert

  • Authors changed from Florent Hivert to Florent Hivert, Frédéric Chapoton

Added Frédéric as an author to make sure not to forget him. He contributed several functions.

comment:4 Changed 6 years ago by hivert

  • Cc sage-combinat added
  • Dependencies set to #8702
  • Description modified (diff)
  • Keywords trees added
  • Milestone set to sage-4.7.1
  • Status changed from new to needs_review
  • Type changed from defect to enhancement

comment:5 Changed 6 years ago by hivert

I just uploaded a new patch wich speedup element creation and remove some unnecessary imports.

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

There seems to be a problem with attributes insert, contains, get, get_min, get_max and contains. Please see the report of the buildbot.

comment:7 in reply to: ↑ 6 Changed 6 years ago by hivert

  • Status changed from needs_review to needs_info
  • Work issues set to Backward incompat change decision

Replying to chapoton:

There seems to be a problem with attributes insert, contains, get, get_min, get_max and contains. Please see the report of the buildbot.

Yes ! There is already something in sage which is called BinaryTree. I just asked for an incompatible change on sage-devel and sage-combinat-devel

comment:8 Changed 6 years ago by hivert

  • Status changed from needs_info to needs_review

comment:9 Changed 6 years ago by hivert

  • Description modified (diff)
  • Work issues Backward incompat change decision deleted

comment:10 Changed 6 years ago by hivert

Fixed 'labeled' vs 'labelled'

comment:11 Changed 5 years ago by hivert

Addressed Frederic Chaponton's remark (private email) about labelled/unlabelled.

comment:12 Changed 5 years ago by hivert

Fixed doctests.

comment:13 Changed 5 years ago by hivert

  • Keywords Cernay2012 added

comment:14 Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_work

Hellooooooo Florent !

Here is a patch with some more documentation for the class. We discussed it a lot already, and there were two more things I had stored in a file while beginning the review.

Some notes before we forget :

  • The symmetry_factor should not be there, and only works for RootedTrees? (not OrderedDDTrees)
  • What about the name itself ? I know "automorphism_group_size" is a bit long, but it woul be nice to find something more meaningful.
  • And I probably already forgot what I should have written there. Well, we wll find it again ^^;

Nathann

P.S. : I updated the combinat queue -- how unusual for me !

comment:15 Changed 5 years ago by chapoton

Hello,

Nathan, your review patch has 2 problems :

  • there lacks the ticket number in the first line of the description
  • there is a trailing whitespace, see the bot report for the exact location

Florent, it seems the you are using several non-existing options for DiGraph?, unless these options are introduced in another ticket ?

DiGraph(loop=False, layout='tree', tree_root=0)

I guess it has to be replaced by

DiGraph(loops=False)

comment:16 follow-up: Changed 4 years ago by VivianePons

  • Cc VivianePons added

comment:17 Changed 4 years ago by stumpc5

Hi,

I wonder what the the current situation is here: we would very much appreciate if we could have a version of this patch that we can actually review. Do you think this is feasible during this week, or are there any complicated issues remaining?

Thanks, Christian

comment:18 Changed 4 years ago by hivert

Hi Christian,

No there is nothing complicated. The doc still need to be reread. I did some improvement in the train yesterday so I can upload a new version of the patch which can readily stated to be reviewed. However, I won't get time to rework it before the end of the week. So feel free to do whatever you think is good to improve the doc.

Florent

comment:19 Changed 4 years ago by hivert

  • Status changed from needs_work to needs_review

Also the LateX output is currently crappy. Jean-Baptiste has a much better tikz output but it needs some cleanup. So I think we should leave this for another ticket.

comment:20 in reply to: ↑ 16 Changed 4 years ago by stumpc5

Replying to VivianePons:

Viviane, do you want to take this over, should we do that later together, or should I do this?

Changed 4 years ago by stumpc5

comment:21 Changed 4 years ago by stumpc5

The patch looks very complete, thanks you!

One thing I noticed: I would like to be able to reconstruct a tree from its string representation. I.e.,

sage: BinaryTree("[., [[., [., .]], .]]")

Unfortunately, this resulted in an infinite recursion. It would be great if you could fix this.

(I am not yet done with my review...)

Cheers, Christian

comment:22 Changed 4 years ago by VivianePons

I added an extra patch to do exactly what you were asking. You can check and merge the two patches.

comment:23 follow-up: Changed 4 years ago by VivianePons

(I added the feature for both ordered tree and binary trees)

comment:24 in reply to: ↑ 23 ; follow-up: Changed 4 years ago by stumpc5

Replying to VivianePons:

(I added the feature for both ordered tree and binary trees)

Thanks -- I wait for Florent or Fred for approval of your change.

Changed 4 years ago by hivert

comment:25 in reply to: ↑ 24 ; follow-up: Changed 4 years ago by hivert

  • Description modified (diff)

Replying to stumpc5:

Thanks -- I wait for Florent or Fred for approval of your change.

Thanks Viviane for this very good idea ! However, I feel that it should be more documented as well as tested. That's why I revamped your patch in a bigger patch. Please review it knowing that I'm Ok with your changes (the tests I added pass :-).

Florent

comment:26 in reply to: ↑ 25 ; follow-up: Changed 4 years ago by stumpc5

Replying to hivert:

Two more things:

  • what about lazily importing the new trees as this should be done by default?
  • an_example / some_examples do not exist, so how am I supposed to get some binary tree to see what I can do with it?

btw: I would be okay with folding trac_8703-additional-feature-fh.patch and removing Viviane's patch in order to keep the ticket organized and the patchbot happy.

Cheers, Christian

comment:27 in reply to: ↑ 26 Changed 4 years ago by hivert

Replying to stumpc5:

Replying to hivert:

Two more things:

  • what about lazily importing the new trees as this should be done by default?

All the combinatorial objects are currently imported (not lazily). So I'd rather switching this once for all. Also there are some problems with lazy import (see eg #10906).

  • an_example / some_examples do not exist, so how am I supposed to get some binary tree to see what I can do with it?

For combinatorial sets the convention is element rather than example which is for categories. Anyway, if I had forgotten, TestSuite would had complained.

sage: BinaryTrees().an_element()
.
sage: list(BinaryTrees().some_elements())
[., [., .],
...
[., [[[., .], [[., .], .]], .]]]

btw: I would be okay with folding trac_8703-additional-feature-fh.patch and removing Viviane's patch in order to keep the ticket organized and the patchbot happy.

I kept thing separated to ease the review, planning to fold everything at the end.

Florent

comment:28 follow-up: Changed 4 years ago 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, 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.

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 aka what you call ordered, 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...

Last edited 4 years ago by darij (previous) (diff)

comment:29 Changed 4 years ago by darij

  • Cc darij added

comment:30 in reply to: ↑ 28 Changed 4 years ago 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 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 ?

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 :-).

comment:31 follow-up: Changed 4 years ago by darij

Hi Florent! Thanks for the reply. One reason why I did not propose any concrete changes to the code is that I have no idea what patches are currently dependent on this one (I only knew of Viviane's new one with the Dyck paths) and I want to avoid merge conflicts. I hoped some of you had a better overview of what's happening with trees these days. If you tell me there's no danger of conflicting changes, I can add the fixes I'd like to see; otherwise I'd prefer someone else to do it or to wait until the current slew of tree patches is merged. I'll try to come up with a doc for the initialization later today, though, provided I can wrap my head around it.

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.

Can we have a docstring warning about this, or a _ in the function name so as to avoid people getting a wrong impression?

The particular case of None is by chance handled by the graph but I'm not sure we should rely on it.

As my second example shows, we should definitely *not* rely on it. Apparently None labels get translated into 0, 1, 2, 3, ..., but this translation starts anew for every subtree, so the resulting graph isn't the one you would expect.

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 ?

Good idea.

I completely agree with you that planar/plane aren't good terms for this kind of trees. What I'd like is a mention in the docstring that these terms are occasionally used, whereas "ordered" is occasionally used for something else.

I can't wait to work with a real Loday-Ronco Hopf algebra rather than my hacky implementation from a year ago...

comment:32 in reply to: ↑ 31 Changed 4 years ago by hivert

Hi Darij,

Replying to darij:

Hi Florent! Thanks for the reply. One reason why I did not propose any concrete changes to the code is that I have no idea what patches are currently dependent on this one (I only knew of Viviane's new one with the Dyck paths) and I want to avoid merge conflicts. I hoped some of you had a better overview of what's happening with trees these days.

Here is some basic overview :-)

popcorn-*inat/.hg/patches $ grep -l Trees *.patch
algebras_over_operads-fc.patch
finite_semigroup-nt.patch
operads-fh.patch
operads_more-fc.patch
poset-from-tree-fc.patch
pretty_console_print-EliX-jbp.patch
q_tree_factorial-fc.patch
sage-demos-and-tutorials-nt.patch
shape_tree-fc.patch
shuffle-operads-fc.patch
trac_11529-rooted_trees-fh.patch
trac_13855_planar_binary_trees_hopf_algebra-EliX-jbp.patch
trac_13987_mary_trees-vp.patch
trac_14086-parking_functions-dm.patch
trac_8703-trees-fh.patch
trees_symmetry_factor-fh.patch

If you tell me there's no danger of conflicting changes, I can add the fixes I'd like to see; otherwise I'd prefer someone else to do it or to wait until the current slew of tree patches is merged. I'll try to come up with a doc for the initialization later today, though, provided I can wrap my head around it.

I think if it's just docstring, there will only be trivial rebasing. Anyway, they must be fixed. Unfortunately, I'm moving from my flat from a new house on Saturday and Sunday so I won't have a lot of time working on trees... If you can take care of all the docstring problem you mentioned once for all in a review patch, I will really appreciate.

Changed 4 years ago by darij

attempting manual override

comment:33 Changed 4 years ago by darij

OK, I'm really not getting this:

darij@travis-virtualbox:~/sage-5.6/devel/sage-combinat$ hg commit
abort: cannot commit over an applied mq patch

Anyway, attaching my changed versions as a tar.gz [trees.tar.gz] containing the three relevant .py files (I only modified docstrings). Sorry for the format :( Hope someone transforms it into a .patch.

Here's something else I'm finding weird:

sage: a = []
sage: BinaryTree(a)
[., .]
sage: b = ()
sage: BinaryTree(b)
.

Or shouldn't lists and tuples behave alike here?

Last edited 4 years ago by darij (previous) (diff)

comment:34 Changed 4 years ago by VivianePons

Hi Darij,

I looked at your files, but you seemed to have also other patches applied because I see methods in your file that are not in mine. I don't want to mess everything up, so I would prefer if you put your changes into a patch: the reason it was not working is because the right command is "hg qrefresh". Thank's for reading the doc by the way.

Also, does anyone have sage 5.8.b2 to see why it is not applying ?

comment:35 Changed 4 years ago by darij

Hmm......

darij@travis-virtualbox:~/sage-5.6$ ./sage -hg qrefresh
/bin/sh: 1: [[: not found
Are you sure you want to refresh the following changes:
into the patch: no patches applied
(y/n)y
no patches applied
darij@travis-virtualbox:~/sage-5.6$ 

But maybe it's the wrong folder?

darij@travis-virtualbox:~/sage-5.6$ cd devel/sage-combinat/
darij@travis-virtualbox:~/sage-5.6/devel/sage-combinat$ ../../sage -hg qrefresh
/bin/sh: 1: [[: not found
Are you sure you want to refresh the following changes:
into the patch: patch.patch
(y/n)y
darij@travis-virtualbox:~/sage-5.6/devel/sage-combinat$ 

The fact that I have a newer file than you, Viviane, surprises me a bit since I remember the last trees-related activity on Sage to be from you...

comment:36 Changed 4 years ago by VivianePons

I think you're working on sage-combinat and you have other patches applied. There are patches on sage-combinat that are changing these files. I work on sage with only these two patches applied.

I think your problem comes from the fact that you made changes but didn't create a patch beforehand to put your changes into.

comment:37 Changed 4 years ago by darij

Thanks! Looks like I missed qnew. Will redo when sage 5.7 is finished installing.

comment:38 Changed 4 years ago by VivianePons

And by the way, you don't have to install sage-combinat to do that. You can clone your sage version and apply only the two patches which are on the ticket (this way, you're sure you don't have other changes to these files applied).

comment:39 follow-up: Changed 4 years ago by darij

Viviane: thanks -- but I was installing 5.7 anyway due to the conference in a couple of days.

It seems I'm getting crazy or something, but now that I reinstalled sage again (and, yes, sage-combinat), there is no abstract_tree.py file in my devel/sage-combinat/sage/combinat folder. What did I do wrong? And how can I manually apply a patch that I've downloaded from trac?

comment:40 in reply to: ↑ 39 Changed 4 years ago by stumpc5

Replying to darij:

Viviane: thanks -- but I was installing 5.7 anyway due to the conference in a couple of days.

It seems I'm getting crazy or something, but now that I reinstalled sage again (and, yes, sage-combinat), there is no abstract_tree.py file in my devel/sage-combinat/sage/combinat folder. What did I do wrong? And how can I manually apply a patch that I've downloaded from trac?

I think you should

  • build the main Sage branch
    $ sage -b main
    
  • and clone it
    $ sage -clone 8703
    
  • then apply the patches
    $ cd SAGEROOT/devel/sage-8703
    $ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8703/trac_8703-trees-fh.patch
    $ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8703/trac_8703-additional-feature-fh.patch
    

You should then have everything set to work on your features...

Cheers, Christian

comment:41 follow-up: Changed 4 years ago by darij

Thank you, at least I've got the trees patch on my machine now... too bad hg still considers the patch itself, rather than only my meager additions to it, as my changes. Well, I guess it's easier if you just show me the right workflow in Providence in about 2 days; I'm groping in the dark for now as far as hg mq is concerned.

comment:42 in reply to: ↑ 41 Changed 4 years ago by stumpc5

Replying to darij:

Thank you, at least I've got the trees patch on my machine now... too bad hg still considers the patch itself, rather than only my meager additions to it, as my changes. Well, I guess it's easier if you just show me the right workflow in Providence in about 2 days; I'm groping in the dark for now as far as hg mq is concerned.

Okay. After the above steps, you have to start a new patch

$ hg qnew trac_8703-trees_addition-dg.patch

and then you do your changes. Afterwards, you can review which files you have changed

$ hg status

and what you changed

$ hg diff

If you are happy with your changes, save them in the path using

$ hg qrefresh

and save this patch in your home folder

$ hg export tip > ~/trac_8703-trees_addition-dg.patch

Finally, upload it to trac!

comment:43 Changed 4 years ago by darij

Finally, it worked. Thank you!!

Is there a quick way to check the validity of the patch? I ended up with some changes I didn't want to make due to being new to kdiff3's merging function; I sanitized them out of the .patch file manually. Here's hoping I didn't corrupt it...

EDIT: Ooops... The changes to ordered_tree.py look weird to me; I certainly did not delete stuff but I added a sentence and fixed two typos. Am I reading the diff wrong or does it really have rogue changes?

Last edited 4 years ago by darij (previous) (diff)

comment:44 Changed 4 years ago by stumpc5

  • Description modified (diff)

Changed 4 years ago by darij

docstrings improved. let's see if this works...

comment:45 Changed 4 years ago by darij

File updated. Please ignore trees.tar.gz (no longer relevant), trac_8703-trees_addition-dg.2.patch (accidentally created by forgetting to check the "Replace existing file" toolbox) and trac_8703-trees_addition-dg.2.2.patch (accidentally created by trying to overwrite previous file).

Rogue edits are gone (they were due to me incorrectly resolving a conflict with fh's changes).

Changed 4 years ago by VivianePons

comment:46 Changed 4 years ago by VivianePons

  • Description modified (diff)

comment:47 Changed 4 years ago by VivianePons

I have rebased trac_8703-trees-fh.patch so that it applies on sage-5.8. I cannot get trac_8703-trees_addition-dg.patch to apply, I get a "bad hunck" error and really, I just don't know what is wrong...

comment:48 Changed 4 years ago by chapoton

  • Description modified (diff)

I have redone the dg review patch (with one or two more things)

for the bot:

apply trac_8703-trees-fh-rebase.patch trac_8703-additional-feature-fh.patch trac_8703-trees_addition-dg-v2.patch

comment:49 Changed 4 years ago by darij

Thanks, Frédéric! I was about to tell Viviane not to bother fixing my patch, as it was way more trouble than it was ever worth.

(I'm not surprised it had bank hunk errors since I messed around with the ,patch file in a text editor...)

Changed 4 years ago by VivianePons

comment:50 Changed 4 years ago by VivianePons

Thanks a lot Frédéric.

I just uploaded a new version of "additional feature", it's just a small fix about the "eval" function. I was using the "eval" function to transform a string into an object, I changed it to use "litteral_eval" which is more secured (it won't eval just any python code, it is restricted to simple objects).

Once the bot is happy, is there anything else to do on this patch or can it go with "positive review" ?

for the bot:

apply trac_8703-trees-fh-rebase.patch trac_8703-additional-feature-vp.patch trac_8703-trees_addition-dg-v2.patch

comment:51 Changed 4 years ago by VivianePons

  • Description modified (diff)

comment:52 Changed 4 years ago by chapoton

better not import all of ast, but rather

from ast import literal_eval

comment:53 Changed 4 years ago by chapoton

There is still work to be done

  • a whole paragraph about partitions at the beginning of BinaryTrees? should be removed
  • a typo "only if they canonical labelled trees"
  • a typo "labellel ordered tree"

I will try to make a review patch later.

comment:54 Changed 4 years ago by darij

Has anyone looked at the weirdness in http://trac.sagemath.org/sage_trac/ticket/8703#comment:33 ? It's not a serious problem, but might deserve documentation.

comment:55 Changed 4 years ago by chapoton

I have made more changes in the new review patch. And yes, comment 33 should be clarified.

Changed 4 years ago by chapoton

comment:56 Changed 4 years ago by chapoton

new patch, solving all issues in comments 33,52 and 53

comment:57 Changed 4 years ago by chapoton

  • Description modified (diff)

a new small review patch, with typos essentially

Maybe this is good to go ?

for the bot:

apply trac_8703-trees-fh-rebase.patch trac_8703-additional-feature-vp.patch trac_8703-trees_addition-dg-v2.patch trac_8703-review-fc.patch

Changed 4 years ago by chapoton

comment:58 Changed 4 years ago by VivianePons

Thanks Frédéric for the review patches.

I have had a quick look and it seems alright. Anyway, Florent should look at the state of things now to see if he's happy and maybe we can go for a positive review!

comment:59 Changed 4 years ago by hivert

  • Reviewers set to Florent Hivert, Frédéric Chapoton, Viviane Pons
  • Status changed from needs_review to positive_review

comment:60 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.9 to sage-5.10

Changed 4 years ago by hivert

comment:61 Changed 4 years ago by hivert

  • Description modified (diff)

I folded the patches for the release manager.

Florent

comment:62 Changed 4 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This shouldn't be in the commit message:

[mq]: trac_8703-additional-feature-vp.patch

comment:63 Changed 4 years ago by jdemeyer

And this patch should be rebased to sage-5.9.beta5.

comment:64 Changed 4 years ago by jdemeyer

  • Dependencies changed from #8702 to #8702, merge with #14433

Changed 4 years ago by tscrim

comment:65 Changed 4 years ago by tscrim

  • Description modified (diff)
  • Status changed from needs_work to positive_review

Rebased patch.

For patchbot:

Apply: trac_8703-trees-rebased.patch

comment:66 Changed 4 years ago by jdemeyer

Please review #14433, otherwise this patch cannot be merged.

comment:67 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.10.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.