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 hivert)

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 hivert

  • Cc chapoton added

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

comment:2 Changed 9 years ago by hivert

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

comment:3 Changed 9 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 8 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 8 years ago by hivert

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

comment:6 follow-up: Changed 8 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 8 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 8 years ago by hivert

  • Status changed from needs_info to needs_review

comment:9 Changed 8 years ago by hivert

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

comment:10 Changed 8 years ago by hivert

Fixed 'labeled' vs 'labelled'

comment:11 Changed 8 years ago by hivert

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

comment:12 Changed 7 years ago by hivert

Fixed doctests.

comment:13 Changed 7 years ago by hivert

  • Keywords Cernay2012 added

comment:14 Changed 7 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 7 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 6 years ago by VivianePons

  • Cc VivianePons added

comment:17 Changed 6 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 6 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 6 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 6 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 6 years ago by stumpc5

comment:21 Changed 6 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 6 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 6 years ago by VivianePons

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

comment:24 in reply to: ↑ 23 ; follow-up: Changed 6 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 6 years ago by hivert

comment:25 in reply to: ↑ 24 Changed 6 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

Note: See TracTickets for help on using tickets.