Combinatorial Rooted Ordered and Binary Trees

[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:

• attachment: trac_8703-trees-rebased.patch

Depends on #8702
Depends on #14433

Dependencies: #8702, merge with #14433

CC: @fchapoton @sagetrac-sage-combinat @VivianePons @darijgr

Component: combinatorics

Keywords: trees, Cernay2012

Author: Florent Hivert, Frédéric Chapoton

Reviewer: Florent Hivert, Frédéric Chapoton, Viviane Pons

Merged: sage-5.10.beta0

Issue created by migration from https://trac.sagemath.org/ticket/8703

[hivert]

comment:1

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

[hivert]

comment:2

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

[hivert]

comment:3

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

[hivert]

Changed author from Florent Hivert to Florent Hivert, Frédéric Chapoton

[hivert]

Changed keywords from none to trees

[hivert]

Dependencies: #8702

[hivert]

comment:5

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

[fchapoton]

comment:6

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

[hivert]

comment:7

Replying to @fchapoton:

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

[hivert]

Work Issues: Backward incompat change decision

[hivert]

Changed work issues from Backward incompat change decision to none

[hivert]

comment:10

Fixed 'labeled' vs 'labelled'

[hivert]

comment:11

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

[hivert]

comment:12

Fixed doctests.

[hivert]

Changed keywords from trees to trees, Cernay2012

[nathanncohen]

comment:14

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 !

[VivianePons]

comment:58

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!

[hivert]

Reviewer: Florent Hivert, Frédéric Chapoton, Viviane Pons

[hivert]

comment:61

Attachment: trac_8703-trees-folded.patch.gz

I folded the patches for the release manager.

Florent

[jdemeyer]

comment:62

This shouldn't be in the commit message:

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

[jdemeyer]

comment:63

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

[jdemeyer]

Changed dependencies from #8702 to #8702, merge with #14433

[tscrim]

comment:65

Attachment: trac_8703-trees-rebased.patch.gz

Rebased patch.

For patchbot:

Apply: trac_8703-trees-rebased.patch

[jdemeyer]

comment:66

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

[jdemeyer]

Merged: sage-5.10.beta0