Opened 9 years ago
Last modified 6 years ago
#8703 closed enhancement
Combinatorial Rooted Ordered and Binary Trees — at Version 25
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: | |
Authors: | Florent Hivert, Frédéric Chapoton | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #8702 | Stopgaps: |
Description (last modified by )
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:
Change History (27)
comment:1 Changed 9 years ago by
- Cc chapoton added
comment:2 Changed 8 years ago by
Updated a new patch after modification in #8702. Close to but not ready for review.
comment:3 Changed 8 years ago by
Added Frédéric as an author to make sure not to forget him. He contributed several functions.
comment:4 Changed 8 years ago by
- 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 8 years ago by
I just uploaded a new patch wich speedup element creation and remove some unnecessary imports.
comment:6 follow-up: ↓ 7 Changed 8 years ago by
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 8 years ago by
- 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 8 years ago by
- Status changed from needs_info to needs_review
comment:9 Changed 7 years ago by
- Description modified (diff)
- Work issues Backward incompat change decision deleted
comment:10 Changed 7 years ago by
Fixed 'labeled' vs 'labelled'
comment:11 Changed 7 years ago by
Addressed Frederic Chaponton's remark (private email) about labelled/unlabelled.
comment:12 Changed 7 years ago by
Fixed doctests.
comment:13 Changed 7 years ago by
- Keywords Cernay2012 added
comment:14 Changed 7 years ago by
- 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 7 years ago by
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: ↓ 20 Changed 6 years ago by
- Cc VivianePons added
comment:17 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
- 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 6 years ago by
Replying to VivianePons:
Viviane, do you want to take this over, should we do that later together, or should I do this?
Changed 6 years ago by
comment:21 Changed 6 years ago by
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 6 years ago by
I added an extra patch to do exactly what you were asking. You can check and merge the two patches.
comment:23 follow-up: ↓ 24 Changed 6 years ago by
(I added the feature for both ordered tree and binary trees)
comment:24 in reply to: ↑ 23 ; follow-up: ↓ 25 Changed 6 years ago by
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 6 years ago by
comment:25 in reply to: ↑ 24 Changed 6 years ago by
- 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
This is an experiment to see if user chapoton is receiving e-mail from trac...