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

Priority:  major  Milestone:  sage8.1 
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/combinat/13987marytrees (Commits)  Commit:  153b2d759bace1dc7741c88d3f8169fb7af12070 
Dependencies:  Stopgaps: 
Description (last modified by )
Change History (42)
comment:1 Changed 6 years ago by
 Dependencies set to #8703
 Owner changed from sagecombinat to VivianePons
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 5 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 5 years ago by
 Branch set to public/combinat/13987marytrees
 Commit set to e77258175ffb845f0b81909cdd5d4eb8c951981b
comment:5 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 4 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 4 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 4 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:9 Changed 2 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 2 years ago by
 Commit changed from 0334ad221609680f9ba9d0bff3ce0165259a2941 to aac90aa8536e73e83ce939fd0298f647ce0fd0b5
comment:11 Changed 2 years ago by
 Milestone changed from sage6.4 to sage7.3
comment:12 Changed 23 months ago by
 Commit changed from aac90aa8536e73e83ce939fd0298f647ce0fd0b5 to 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f
comment:13 Changed 20 months ago by
 Commit changed from 847d49aa9dabc5e0ec50d45d50a5722fa2f08d4f to 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553
comment:14 Changed 20 months 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 20 months ago by
 Cc tscrim added
comment:16 Changed 20 months ago by
 Commit changed from 1a27ad0c19d3f4d5edf6cdd682c070970d9d2553 to 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904
comment:17 Changed 19 months ago by
 Milestone changed from sage7.6 to sage8.0
comment:18 Changed 19 months ago by
 Commit changed from 5dcc0fe9b38e6be9bfeafd7807f1a7926c8e3904 to edf57d7b9ec04475ce4868a19a0c65b4e4a69e31
comment:19 Changed 19 months ago by
ok, green bot at last. Now one can start looking at the code..
comment:20 Changed 17 months ago by
 Commit changed from edf57d7b9ec04475ce4868a19a0c65b4e4a69e31 to 20237b884dafa0d569666911c84eaea6d3f232e2
comment:22 Changed 15 months ago by
Are these trees plane?
comment:23 Changed 15 months ago by
yes, these are the rooted trees where every vertex has a list of m sons.
comment:24 Changed 11 months ago by
 Commit changed from 20237b884dafa0d569666911c84eaea6d3f232e2 to bcb6784136e4e80caca487bdf7670676d764bf21
comment:25 Changed 11 months ago by
Is my doc correct? (In particular, am I right in assuming that leaves can carry no labels?)
comment:26 Changed 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months ago by
 Reviewers set to Darij Grinberg
comment:35 Changed 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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 11 months 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?
New commits: