Combinatorial m-ary trees

VivianePons commented 11 years ago

In the same manner as #8703 we want to implement trees with a fixed number of subtrees (equivalent of binary trees but with m subtrees). Especially to use them in the context of the m-Tamari lattices.

This ticket depends on #8703 as we use the implementation of OrderedTrees.

11369: generate k-trees up to symmetry
19479: Implement k-ary trees

CC: @hivert @sagetrac-sage-combinat @tscrim @darijgr

Component: combinatorics

Keywords: trees

Author: Viviane Pons

Branch/Commit: public/new-13987 @ a2d92f4

Reviewer: Darij Grinberg

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

VivianePons commented 11 years ago

Dependencies: #8703

VivianePons commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-Just as in #8703 we want to implement trees with a fixed number of subtrees (equivalent of binary trees but with m subtrees). Especially to use them in the context of the m-Tamari lattices. 
+In the same manner as #8703 we want to implement trees with a fixed number of subtrees (equivalent of binary trees but with m subtrees). Especially to use them in the context of the m-Tamari lattices.

-This ticket depends on #8703 as we use the implantation of RootedTrees
+This ticket depends on #8703 as we use the implementation of OrderedTrees.

VivianePons commented 10 years ago

Commit: e772581

VivianePons commented 10 years ago

New commits:

[changeset:e772581] #N: a patch to implement m-ary trees

VivianePons commented 10 years ago

Branch: public/combinat/13987-mary-trees

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

34daa2f Merge branch 'develop' into mary-trees

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from e772581 to 34daa2f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 34daa2f to 0334ad2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

0334ad2 Merge branch 'public/combinat/13987-mary-trees' into 7.3.b3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`21ea566`	`Merge branch 'public/combinat/13987-mary-trees' in 7.3.b6`
`aac90aa`	`trac 13987 refreshed branch`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 0334ad2 to aac90aa

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from aac90aa to 847d49a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`4cf00a2`	`Merge branch 'public/combinat/13987-mary-trees' in 7.5.b4`
`847d49a`	`trac 13987 some details, no more xrange`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 847d49a to 1a27ad0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`8e03a46`	`Merge branch 'public/combinat/13987-mary-trees' in 7.6.b5`
`1a27ad0`	`trac 13987 get rid of __metaclass__`

fchapoton commented 7 years ago

Changed dependencies from #8703 to none

fchapoton commented 7 years ago

comment:14

I am going to set this to needs_review. I hope that somebody else is still interested.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`a8c7c7a`	`Merge branch 'public/combinat/13987-mary-trees' in 7.6.b6`
`5dcc0fe`	`trac 13987 some doc details`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 1a27ad0 to 5dcc0fe

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 5dcc0fe to edf57d7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`384b80c`	`Merge branch 'public/combinat/13987-mary-trees' in 8.0.b0`
`edf57d7`	`trac 13987 lazy import of mary trees`

fchapoton commented 7 years ago

comment:19

ok, green bot at last. Now one can start looking at the code..

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`6c73e55`	`Merge branch 'public/combinat/13987-mary-trees' in 8.0.b9`
`20237b8`	`trac 13987 change TEST to TESTS`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from edf57d7 to 20237b8

fchapoton commented 6 years ago

comment:21

Green bot, please review.

darijgr commented 6 years ago

comment:22

Are these trees plane?

fchapoton commented 6 years ago

comment:23

yes, these are the rooted trees where every vertex has a list of m sons.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 20237b8 to bcb6784

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`5543075`	`Merge branch 'public/combinat/13987-mary-trees' of git://trac.sagemath.org/sage into mary`
`bcb6784`	`doc improvement?`

darijgr commented 6 years ago

comment:25

Is my doc correct? (In particular, am I right in assuming that leaves can carry no labels?)

fchapoton commented 6 years ago

comment:26

yes.

some remarks:

you can see the trees using %display unicode_art
there is a doctest still using binary trees
maybe the import of BinaryTrees is not needed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

05a7600 clarify connection to binary trees

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from bcb6784 to 05a7600

darijgr commented 6 years ago

comment:28

Thanks. I've fixed the doctest. I don't know why the import of BinaryTrees wouldn't be needed. A good point can be made for conversions between MaryTree(2, ...) and BinaryTree(...), but this can wait for another ticket.

Now to review the rest of this...

darijgr commented 6 years ago

comment:29

Unicode Art doesn't seem to work:

sage: t = MAryTree(2, [[], []])
sage: t
[[., .], [., .]]
sage: %display unicode_art
sage: t
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-4-b7269fa25085> in <module>()
----> 1 t

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/IPython/core/displayhook.pyc in __call__(self, result)
    244             self.start_displayhook()
    245             self.write_output_prompt()
--> 246             format_dict, md_dict = self.compute_format_data(result)
    247             self.update_user_ns(result)
    248             self.fill_exec_result(result)

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/IPython/core/displayhook.pyc in compute_format_data(self, result)
    148 
    149         """
--> 150         return self.shell.display_formatter.format(result)
    151 
    152     # This can be set to True by the write_output_prompt method in a subclass

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/repl/display/formatter.pyc in format(self, obj, include, exclude)
    200         """
    201         # First, use Sage rich output if there is any
--> 202         sage_format, sage_metadata = self.dm.displayhook(obj)
    203         assert PLAIN_TEXT in sage_format, 'plain text is always present'
    204         if not set(sage_format.keys()).issubset(self.default_mime()):

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/repl/rich_output/display_manager.pyc in displayhook(self, obj)
    805             return
    806         self._backend.set_underscore_variable(obj)
--> 807         plain_text, rich_output = self._rich_output_formatter(obj, dict())
    808         return self._backend.displayhook(plain_text, rich_output)
    809 

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/repl/rich_output/display_manager.pyc in _rich_output_formatter(self, obj, rich_repr_kwds)
    631         if rich_output is None:
    632             rich_output = self._preferred_text_formatter(
--> 633                 obj, plain_text=plain_text, **rich_repr_kwds)
    634         # promote output container types to backend-specific containers
    635         plain_text = self._promote_output(plain_text)

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/repl/rich_output/display_manager.pyc in _preferred_text_formatter(self, obj, plain_text, **kwds)
    528             return out
    529         if want == 'unicode_art' and OutputUnicodeArt in supported:
--> 530             out = self._backend.unicode_art_formatter(obj, **kwds)
    531             if type(out) is not OutputUnicodeArt:
    532                 raise OutputTypeException('backend returned wrong output type, require UnicodeArt')

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/repl/rich_output/backend_base.pyc in unicode_art_formatter(self, obj, **kwds)
    422             result = unicode_art(*obj, sep=' ')
    423         else:
--> 424             result = unicode_art(obj)
    425         from sage.repl.rich_output.output_basic import OutputUnicodeArt
    426         return OutputUnicodeArt(str(result))

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/typeset/unicode_art.pyc in unicode_art(*obj, **kwds)
    119         raise ValueError('unknown keyword arguments: {0}'.format(list(kwds)))
    120     if len(obj) == 1:
--> 121         return _unicode_art_factory.build(obj[0])
    122     if not isinstance(separator, UnicodeArt):
    123         separator = _unicode_art_factory.build(separator)

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/typeset/character_art_factory.pyc in build(self, obj)
    124                 return self.build_set(obj)
    125         elif isinstance(obj, SageObject):
--> 126             return self.build_from_magic_method(obj)
    127         else:
    128             return self.build_from_string(obj)

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/typeset/character_art_factory.pyc in build_from_magic_method(self, obj)
    156         """
    157         magic_method = getattr(obj, self.magic_method_name)
--> 158         return magic_method()
    159 
    160     def build_from_string(self, obj):

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/combinat/abstract_tree.pyc in _unicode_art_(self)
   1294 
   1295         # General case
-> 1296         l_repr = [subtree._unicode_art_() for subtree in self]
   1297         acc = l_repr.pop(0)
   1298         whitesep = acc._root

/home/dgrinber/sage-7.5.1/local/lib/python2.7/site-packages/sage/combinat/abstract_tree.pyc in _unicode_art_(self)
   1296         l_repr = [subtree._unicode_art_() for subtree in self]
   1297         acc = l_repr.pop(0)
-> 1298         whitesep = acc._root
   1299         lf_sep = u" " * whitesep + u"╭" + u"─" * (acc._l - acc._root)
   1300         ls_sep = u" " * whitesep + u"│" + u" " * (acc._l - acc._root)

AttributeError: 'UnicodeArt' object has no attribute '_root'

Not sure if this is much of an issue, though.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

792074f actually, the conversions do work

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 05a7600 to 792074f

darijgr commented 6 years ago

comment:31

(2) Not sure why this behavior:

sage: MAryTree(4, 4)
[., ., ., .]
sage: MAryTree(4, 3)
[., ., ., .]
sage: MAryTree(4, 2)
[., ., ., .]
sage: MAryTree(4, 1)
[., ., ., .]

What is the purpose of the numerical second parameter if it makes no difference?

(3) Is it intentional that check only checks the "outer layer", i.e., the list of the direct children of the root?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

3db34fa math review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 792074f to 3db34fa

darijgr commented 6 years ago

comment:33

I've reviewed the mathematics and documentation. Now we need someone to check the OOP, specifically the methods with the following names:

__classcall_private__
_auto_parent
__init__
__call__
_element_constructor_
_parent_for_
element_class

and someone to fix the issues in comment:29 and comment:31.

darijgr commented 6 years ago

Reviewer: Darij Grinberg

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 3db34fa to e23b756

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

e23b756 trac 13987 fixing the ascii and unicode art, plus details

fchapoton commented 6 years ago

comment:36

I have fixed the ascii and unicode art.

Also enhanced the "an_element" method for labelled case.

fchapoton commented 6 years ago

comment:37

(3) Is it intentional that check only checks the "outer layer", i.e., the list of the direct children of the root?

This is exactly the existing behaviour in binary trees. So I guess we can keep that for the moment. The recursive check is handled when creating a tree, I think.

sage: from sage.combinat.abstract_tree import from_hexacode
sage: M = MAryTrees(3)
sage: from_hexacode('300200', M)
...
TypeError: This is not a 3-ary tree

tscrim commented 6 years ago

comment:38

Some comments:

I think it would be good to do a TestSuite on something like MAryTree(3, []) as an extra security check in the MAryTree.__init__.
Do we want this MRO: class MAryTrees_all(DisjointUnionEnumeratedSets, MAryTrees)? If it is the other way -- class MAryTrees_all(MAryTrees, DisjointUnionEnumeratedSets) -- then I think we can remove the __call__. Even without changing the order, do we need it to go up the MAryTrees path?
Do we want to have 2-ary trees create the corresponding BinaryTree* class? This would mean we do not have to convert back and forth.
Related, do we want to have BinaryTree* inherit from its corresponding MAryTree* class?
The LabelledMAryTrees.__call__ can be removed.
Lowercase error messages: "Invalid word" and "Wrong number of nodes".
There is a non-standard .. note:: block.
We should also specify in the MAryTree class-level doc that m-ary trees are plane/ordered trees.

I can make these changes tomorrow (tonight I am feeling a little lazy ^^;;).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

153b2d7 trac 13987 some details

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from e23b756 to 153b2d7

fchapoton commented 6 years ago

comment:40

I did some of the simple suggested changes.

I would rather not have any inheritance between BinaryTrees and MAryTrees. Conversion is enough.

sagemath / sage

Combinatorial m-ary trees #13987

11369: generate k-trees up to symmetry

19479: Implement k-ary trees