Opened 9 years ago
Last modified 6 weeks ago
#13987 needs_review enhancement
Combinatorial mary trees
Reported by:  VivianePons  Owned by:  VivianePons 

Priority:  major  Milestone:  sage9.7 
Component:  combinatorics  Keywords:  trees 
Cc:  hivert, sagecombinat, tscrim, darij  Merged in:  
Authors:  Viviane Pons  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  public/new13987 (Commits, GitHub, GitLab)  Commit:  a2d92f4bef643eeaf495760b50d6eb17551d51d3 
Dependencies:  Stopgaps: 
Description (last modified by )
Change History (58)
comment:1 Changed 9 years ago by
 Dependencies set to #8703
 Owner changed from sagecombinat to VivianePons
comment:2 Changed 9 years ago by
 Description modified (diff)
comment:3 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 9 years ago by
 Branch set to public/combinat/13987marytrees
 Commit set to e77258175ffb845f0b81909cdd5d4eb8c951981b
comment:5 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 8 years ago by
 Commit changed from e77258175ffb845f0b81909cdd5d4eb8c951981b to 34daa2fa2cda3ee069ed73fd44a254cf18d60160
Branch pushed to git repo; I updated commit sha1. New commits:
34daa2f  Merge branch 'develop' into marytrees

comment:8 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:9 Changed 6 years ago by
 Commit changed from 34daa2fa2cda3ee069ed73fd44a254cf18d60160 to 0334ad221609680f9ba9d0bff3ce0165259a2941
Branch pushed to git repo; I updated commit sha1. New commits:
0334ad2  Merge branch 'public/combinat/13987marytrees' into 7.3.b3

comment:10 Changed 6 years ago by
 Commit changed from 0334ad221609680f9ba9d0bff3ce0165259a2941 to aac90aa8536e73e83ce939fd0298f647ce0fd0b5
comment:11 Changed 6 years ago by
 Milestone changed from sage6.4 to sage7.3
comment:12 Changed 5 years ago by
 Commit changed from aac90aa8536e73e83ce939fd0298f647ce0fd0b5 to 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f
comment:13 Changed 5 years ago by
 Commit changed from 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f to 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553
comment:14 Changed 5 years ago by
 Dependencies #8703 deleted
 Milestone changed from sage7.3 to sage7.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 5 years ago by
 Cc tscrim added
comment:16 Changed 5 years ago by
 Commit changed from 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553 to 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904
comment:17 Changed 5 years ago by
 Milestone changed from sage7.6 to sage8.0
comment:18 Changed 5 years ago by
 Commit changed from 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904 to edf57d7b9ec04475ce4868a19a0c65b4e4a69e31
comment:19 Changed 5 years ago by
ok, green bot at last. Now one can start looking at the code..
comment:20 Changed 5 years ago by
 Commit changed from edf57d7b9ec04475ce4868a19a0c65b4e4a69e31 to 20237b884dafa0d569666911c84eaea6d3f232e2
comment:22 Changed 5 years ago by
Are these trees plane?
comment:23 Changed 5 years ago by
yes, these are the rooted trees where every vertex has a list of m sons.
comment:24 Changed 4 years ago by
 Commit changed from 20237b884dafa0d569666911c84eaea6d3f232e2 to bcb6784136e4e80caca487bdf7670676d764bf21
comment:25 Changed 4 years ago by
Is my doc correct? (In particular, am I right in assuming that leaves can carry no labels?)
comment:26 Changed 4 years ago by
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
comment:27 Changed 4 years ago by
 Commit changed from bcb6784136e4e80caca487bdf7670676d764bf21 to 05a7600052c045c2116cd78cc503556931610bed
Branch pushed to git repo; I updated commit sha1. New commits:
05a7600  clarify connection to binary trees

comment:28 Changed 4 years ago by
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 years ago by
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) <ipythoninput4b7269fa25085> in <module>() > 1 t /home/dgrinber/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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 backendspecific containers 635 plain_text = self._promote_output(plain_text) /home/dgrinber/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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/sage7.5.1/local/lib/python2.7/sitepackages/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.
comment:30 Changed 4 years ago by
 Commit changed from 05a7600052c045c2116cd78cc503556931610bed to 792074f867eb1a3053e1fdc83b70d6250987e064
Branch pushed to git repo; I updated commit sha1. New commits:
792074f  actually, the conversions do work

comment:31 followup: ↓ 37 Changed 4 years ago by
(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?
comment:32 Changed 4 years ago by
 Commit changed from 792074f867eb1a3053e1fdc83b70d6250987e064 to 3db34fab096d7b911267c79738d4d58aa626e38d
Branch pushed to git repo; I updated commit sha1. New commits:
3db34fa  math review

comment:33 Changed 4 years ago by
 Milestone changed from sage8.0 to sage8.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 years ago by
 Reviewers set to Darij Grinberg
comment:35 Changed 4 years ago by
 Commit changed from 3db34fab096d7b911267c79738d4d58aa626e38d to e23b756c28608ee5a9529d40b9ebddcec4fe570b
Branch pushed to git repo; I updated commit sha1. New commits:
e23b756  trac 13987 fixing the ascii and unicode art, plus details

comment:36 Changed 4 years ago by
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 years ago by
(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 3ary tree
comment:38 Changed 4 years ago by
Some comments:
 I think it would be good to do a
TestSuite
on something likeMAryTree(3, [])
as an extra security check in theMAryTree.__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 theMAryTrees
path?  Do we want to have 2ary 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 correspondingMAryTree*
class?  The
LabelledMAryTrees.__call__
can be removed.  Lowercase error messages:
"Invalid word"
and"Wrong number of nodes"
.  There is a nonstandard
.. note::
block.  We should also specify in the
MAryTree
classlevel doc that mary trees are plane/ordered trees.
I can make these changes tomorrow (tonight I am feeling a little lazy ^^;;
).
comment:39 Changed 4 years ago by
 Commit changed from e23b756c28608ee5a9529d40b9ebddcec4fe570b to 153b2d759bace1dc7741c88d3f8169fb7af12070
Branch pushed to git repo; I updated commit sha1. New commits:
153b2d7  trac 13987 some details

comment:40 followup: ↓ 42 Changed 4 years ago by
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 years ago by
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 years ago by
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?
comment:43 Changed 3 years ago by
 Milestone changed from sage8.1 to sage8.8
comment:44 Changed 3 years ago by
 Milestone changed from sage8.8 to sage8.9
Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).
comment:45 Changed 3 years ago by
 Branch changed from public/combinat/13987marytrees to public/new13987
 Commit changed from 153b2d759bace1dc7741c88d3f8169fb7af12070 to eb12c0334921516d37c8dd10ae18c6d702b2ffad
I have made a fresh new branch with a single commit, as the previous one was polluted by many merge commits.
New commits:
eb12c03  mary trees

comment:46 Changed 2 years ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:47 Changed 2 years ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:48 Changed 22 months ago by
 Commit changed from eb12c0334921516d37c8dd10ae18c6d702b2ffad to a2d92f4bef643eeaf495760b50d6eb17551d51d3
comment:49 Changed 21 months ago by
What's the status of the review on this ticket?
comment:50 Changed 21 months ago by
I don't remember more than is said in the comments above, and I'm not going to have time for this in the foreseeable time... sorry, not very useful I know.
comment:51 Changed 21 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:52 Changed 14 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:53 Changed 10 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
comment:54 Changed 10 months ago by
I'd like to try and help get this finished, though I'm not sure I'm qualified to be final judge and jury on the OOP/MRO aspects. At the very least, I can implement Travis's suggestion of removing LabelledMAryTrees.__call__
, and try to reverse the order of inheritance for
class MAryTrees_all(DisjointUnionEnumeratedSets, MAryTrees)
and remove the
__call__
` and make sure nothing breaks.
In terms of m=2, people seem fine with having conversion for now, and having inheritance be part of a later ticket to get this finished.
I can implement Travis's suggestion that the documentation being clearer about these being ordered/plane trees.
In terms of check
only checking the outer layer, I'm pretty sure this should be fine, and it will recursively check the entire tree. But I can try and make a test case to be sure.
I'll make a thorough pass in the next day or two to test things out, check doc and examples for clarity to somebody that may not be as familiar with mary trees, and make sure the doc compiles properly. One thing that's more a note to self to fix later when I do this is that enumerated mary trees of a given size is still labeled as 'enumerated set of binary trees of a given size' in the code.
Also reminder to self to check (1) as part of comment:37.
comment:55 Changed 10 months ago by
In terms of class MAryTrees_all(DisjointUnionEnumeratedSets, MAryTrees)
versus
class MAryTrees_all(MAryTrees, DisjointUnionEnumeratedSets)
, the way it is now matches what is done in binary trees.
I can't manage to track down exactly what's happening, but as the doc indicates, the __call__
methods are necessary to make sure that empty input is treated as
None
instead of getting passed as
0
. Maybe something inherited from
OrderedTrees
and their assumption that there are no empty trees (and thus
OrderedTrees()() == OrderedTrees()([])
? Switching the MRO above did not resolve the issue.
This fix/hack is also implemented in BinaryTrees
, though only for
BinaryTrees_all
. So
BinaryTrees()() == BinaryTrees()(None) == .
, but in
BinaryTrees_size
,
BinaryTrees(0)()
gives an error about the int 0 not being callable, whereas
BinaryTrees(0)(None) ==
.
I would be of the opinion that if the way things done here is the way they've been forever in BinaryTrees
, then they shouldn't be holding back this ticket from getting a positive review.
comment:56 Changed 10 months ago by
 Description modified (diff)
comment:57 Changed 5 months ago by
 Milestone changed from sage9.5 to sage9.6
Stalled in needs_review
or needs_info
; likely won't make it into Sage 9.5.
comment:58 Changed 6 weeks ago by
 Milestone changed from sage9.6 to sage9.7
New commits: