Opened 5 years ago

Last modified 4 weeks ago

#13987 needs_review enhancement

Combinatorial m-ary trees

Reported by: VivianePons Owned by: VivianePons
Priority: major Milestone: sage-8.1
Component: combinatorics Keywords: trees
Cc: hivert, sage-combinat, tscrim, darij Merged in:
Authors: Viviane Pons Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: public/combinat/13987-mary-trees (Commits) Commit: 153b2d759bace1dc7741c88d3f8169fb7af12070
Dependencies: Stopgaps:

Description (last modified by VivianePons)

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.

Change History (42)

comment:1 Changed 5 years ago by VivianePons

  • Dependencies set to #8703
  • Owner changed from sage-combinat to VivianePons

comment:2 Changed 5 years ago by VivianePons

  • Description modified (diff)

comment:3 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 4 years ago by VivianePons

  • Branch set to public/combinat/13987-mary-trees
  • Commit set to e77258175ffb845f0b81909cdd5d4eb8c951981b

New commits:

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

comment:5 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 4 years ago by git

  • Commit changed from e77258175ffb845f0b81909cdd5d4eb8c951981b to 34daa2fa2cda3ee069ed73fd44a254cf18d60160

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

34daa2fMerge branch 'develop' into mary-trees

comment:8 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 19 months ago by git

  • Commit changed from 34daa2fa2cda3ee069ed73fd44a254cf18d60160 to 0334ad221609680f9ba9d0bff3ce0165259a2941

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

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

comment:10 Changed 18 months ago by git

  • Commit changed from 0334ad221609680f9ba9d0bff3ce0165259a2941 to aac90aa8536e73e83ce939fd0298f647ce0fd0b5

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

21ea566Merge branch 'public/combinat/13987-mary-trees' in 7.3.b6
aac90aatrac 13987 refreshed branch

comment:11 Changed 18 months ago by chapoton

  • Milestone changed from sage-6.4 to sage-7.3

comment:12 Changed 13 months ago by git

  • Commit changed from aac90aa8536e73e83ce939fd0298f647ce0fd0b5 to 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f

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

4cf00a2Merge branch 'public/combinat/13987-mary-trees' in 7.5.b4
847d49atrac 13987 some details, no more xrange

comment:13 Changed 10 months ago by git

  • Commit changed from 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f to 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553

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

8e03a46Merge branch 'public/combinat/13987-mary-trees' in 7.6.b5
1a27ad0trac 13987 get rid of __metaclass__

comment:14 Changed 10 months ago by chapoton

  • Dependencies #8703 deleted
  • Milestone changed from sage-7.3 to sage-7.6
  • Status changed from new to needs_review

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

comment:15 Changed 10 months ago by tscrim

  • Cc tscrim added

comment:16 Changed 9 months ago by git

  • Commit changed from 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553 to 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904

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

a8c7c7aMerge branch 'public/combinat/13987-mary-trees' in 7.6.b6
5dcc0fetrac 13987 some doc details

comment:17 Changed 9 months ago by chapoton

  • Milestone changed from sage-7.6 to sage-8.0

comment:18 Changed 9 months ago by git

  • Commit changed from 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904 to edf57d7b9ec04475ce4868a19a0c65b4e4a69e31

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

384b80cMerge branch 'public/combinat/13987-mary-trees' in 8.0.b0
edf57d7trac 13987 lazy import of mary trees

comment:19 Changed 9 months ago by chapoton

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

comment:20 Changed 7 months ago by git

  • Commit changed from edf57d7b9ec04475ce4868a19a0c65b4e4a69e31 to 20237b884dafa0d569666911c84eaea6d3f232e2

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

6c73e55Merge branch 'public/combinat/13987-mary-trees' in 8.0.b9
20237b8trac 13987 change TEST to TESTS

comment:21 Changed 5 months ago by chapoton

  • Cc darij added

Green bot, please review.

comment:22 Changed 5 months ago by darij

Are these trees plane?

comment:23 Changed 5 months ago by chapoton

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

comment:24 Changed 4 weeks ago by git

  • Commit changed from 20237b884dafa0d569666911c84eaea6d3f232e2 to bcb6784136e4e80caca487bdf7670676d764bf21

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

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

comment:25 Changed 4 weeks ago by darij

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

comment:26 Changed 4 weeks ago by chapoton

yes.

some remarks:

  • you can see the trees using %display unicode_art
  • there is a doctest still using binary trees

comment:27 Changed 4 weeks ago by git

  • Commit changed from bcb6784136e4e80caca487bdf7670676d764bf21 to 05a7600052c045c2116cd78cc503556931610bed

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

05a7600clarify connection to binary trees

comment:28 Changed 4 weeks ago by darij

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

comment:29 Changed 4 weeks ago by darij

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.

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

comment:30 Changed 4 weeks ago by git

  • Commit changed from 05a7600052c045c2116cd78cc503556931610bed to 792074f867eb1a3053e1fdc83b70d6250987e064

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

792074factually, the conversions do work

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

(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?

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

comment:32 Changed 4 weeks ago by git

  • Commit changed from 792074f867eb1a3053e1fdc83b70d6250987e064 to 3db34fab096d7b911267c79738d4d58aa626e38d

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

3db34famath review

comment:33 Changed 4 weeks ago by darij

  • Milestone changed from sage-8.0 to sage-8.1

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.

comment:34 Changed 4 weeks ago by darij

  • Reviewers set to Darij Grinberg

comment:35 Changed 4 weeks ago by git

  • Commit changed from 3db34fab096d7b911267c79738d4d58aa626e38d to e23b756c28608ee5a9529d40b9ebddcec4fe570b

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

e23b756trac 13987 fixing the ascii and unicode art, plus details

comment:36 Changed 4 weeks ago by chapoton

I have fixed the ascii and unicode art.

Also enhanced the "an_element" method for labelled case.

comment:37 in reply to: ↑ 31 Changed 4 weeks ago by chapoton

(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

comment:38 Changed 4 weeks ago by tscrim

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 ^^;;).

comment:39 Changed 4 weeks ago by git

  • Commit changed from e23b756c28608ee5a9529d40b9ebddcec4fe570b to 153b2d759bace1dc7741c88d3f8169fb7af12070

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

153b2d7trac 13987 some details

comment:40 follow-up: Changed 4 weeks ago by chapoton

I did some of the simple suggested changes.

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

comment:41 Changed 4 weeks ago by darij

OK, what about point (2)?

And I'm fine with no inheritance; it's enough that the constructor is working.

comment:42 in reply to: ↑ 40 Changed 4 weeks ago by tscrim

Replying to chapoton:

I did some of the simple suggested changes.

Thank you.

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

Why not? It doesn't make sense to me both mathematically and programmatically. I can understand you wanting to postpone it for a later ticket (although I think change it really quickly), but I don't understand the opposition to having inheritance (and the constructors returning the BinaryTree* object when m = 2). Am I missing something about the structures of these classes?

Note: See TracTickets for help on using tickets.