Rooted trees

[hivert]

Implement combinatorial (unordered) rooted trees

This is done using ordered rooted trees as data structure, and recursive normalization.

[dkrenn]

Patch cannot be applied. If this is just because of the unfinished #10194 (I don't know the current status of that), then it can be set back to "need review".

[chapoton]

Florent, is this the latest patch from the sage-combinat queue ? If not, it would be good to refresh, so that one can start working on it here.

[chapoton]

I have made a branch from the latest sage-combinat patch, plus some details corrected.

---

New commits:

​3375d21	#11529: data structure and enumerated sets for rooted trees.
​bad8590	trac #11529 pyflakes details

[git]

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

​f0bd132

trac #11529 minor details

[git]

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

​5a15e07

trac #11529 trying to make it work

[git]

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

​5849b28

trac #11529 tests seem to pass

[git]

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

​0047c1a

Merge branch 'u/chapoton/11529' of ssh://trac.sagemath.org:22/sage into 11529

[git]

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

​ca70054

Merge branch 'u/chapoton/11529' of ssh://trac.sagemath.org:22/sage into 11529

[git]

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

​be21430

trac #11529 two more useful methods

[git]

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

​6bf100e

trac #11529 make tests pass

[git]

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

​9aa6ab2

Merge branch 'u/chapoton/11529' of trac.sagemath.org:sage into 6.5.b5

[chapoton]

I have removed the dependency to the ticket #10194. Now progress is possible here.

There is current interest in this matter, see ​https://groups.google.com/forum/#!topic/sage-combinat-devel/oi4VtGr1g5A

---

New commits:

​dd078fa	Merge branch 'u/chapoton/11529' into 6.5.rc3
​a4b4c6e	trac #11529 Remove dependency to set factories

[darij]

These are (rooted) trees modulo permutation of children, right? I'm asking because I don't see much of a documentation here.

(Let me add that I have never seen them called "Cayley trees" in my life. This notation contradicts ​http://en.wikipedia.org/wiki/Bethe_lattice and ​http://mathworld.wolfram.com/CayleyTree.html .)

[tscrim]

Replying to darij:

These are (rooted) trees modulo permutation of children, right? I'm asking because I don't see much of a documentation here.

From looking at the code and the normalize() doctest, that is right (i.e., they are not ordered/planer trees). I think we need to expand the documentation before this can get into Sage.

(Let me add that I have never seen them called "Cayley trees" in my life. This notation contradicts ​http://en.wikipedia.org/wiki/Bethe_lattice and ​http://mathworld.wolfram.com/CayleyTree.html .)

+1 from me to removing this terminology (at least for now since Cayley trees aren't implemented).

[git]

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

​49681fc	trac #11529 little more doc and change name of cayley_normalize
​b8f8004	trac #11529 remove the word Cayley as asked

[git]

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

​76f6957

trac #11529 inclusion of doc into table of contents, etc

[darij]

OK. Are you sure on_fly is a good idea? It behaves nondeterministically:

sage: OT = OrderedTree
sage: OT([[[],[]], [[],[],[]]]).normalize()
[[[], []], [[], [], []]]
sage: OT([[[],[],[]], [[],[]]]).normalize()
[[[], []], [[], [], []]]
sage: 
Exiting Sage (CPU time 0m0.29s, Wall time 1m31.05s).
skraeling@angband ~/sage $ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ Sage Version 6.5.rc1, Release Date: 2015-02-08                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: OT = OrderedTree
sage: OT([[[],[],[]], [[],[]]]).normalize()
[[[], [], []], [[], []]]
sage: OT([[[],[]], [[],[],[]]]).normalize()
[[[], [], []], [[], []]]

Is this what we want? And does it behave well in regard to the other features of our tree classes, such as the clone context manager?

If we just want a comparison method for normalization, we can compare two trees "lexicographically" by number of children, number of children of the leftmost child, etc.. If we want an actual ranker, then this is not enough...

Also, the doc of LabelledRootedTrees says that this class is a parent stub to be inherited from by classes of labelled rooted trees with specific properties; but the unlabelled_trees and cardinality methods look like they are specific to the class of *all* labelled rooted trees. Shouldn't they go into LabelledRootedTrees_all?

[git]

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

​dc7e79e	Merge branch 'u/chapoton/11529_alone' into 6.5
​ac7687a	trac #11529 a few changes in the doc

[git]

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

​3e619b0

trac #11529 more doc again

[chapoton]

Hello,

concerning the ranker, I do not care about the possible non-deterministic aspect. There is no clear canonical way to generate and number all rooted trees, so there is no best choice.

concerning the methods of LabelledRootedTrees, well, there is no LabelledRootedTrees_all. And I do not think one need that for now.

At some point later, it would be good to have classes for labelled rooted trees with labels in a fixed set. So far, all possible labels are allowed. This is needed for operads.

It is true that the content of this ticket is rather minimalistic. But it is enough for #15635, which is my main motivation.

[darij]

OK, I am not saying that this nondeterminism is bad, but I think it is avoidable in this specific setting. When it comes to building combinatorial Hopf algebras, I don't want to have to harden all the doctests because a change somewhere else might lead to all trees getting rotated. What do you think about my deterministic normalization method in public/combinat/11529 ?

[darij]

New commits:

​5219d2e

deterministic normalization of rooted ordered trees

[chapoton]

This proposal of yours will not work (at least in its current state) for labelled rooted trees. Besides, if I remember well (this is already a few years old), the recursive approach was tried and rejected for being slower than the ranker approach.

[git]

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

​f16a183	Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into trees
​03a8862	x
​14a8d8b	reverting changes, keeping dendrographical order

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​c1aca70

reverting changes, keeping dendrographical order

[darij]

Ah, I see. I've reinstated your definition of normalization, while keeping mine as a method for doctesting pruposes.

[darij]

+        with self.clone() as t:
+            t.append(other)
+            resu = t
+        return resu

Why not remove the "resu = t" line and just return t? I'm wondering because I'm not sure if my understanding of the clone context manager is correct.

Also, is it OK if I split LabelledRootedTrees into an abstract base class and a concrete class?

[chapoton]

Replying to darij:

+        with self.clone() as t:
+            t.append(other)
+            resu = t
+        return resu

Why not remove the "resu = t" line and just return t? I'm wondering because I'm not sure if my understanding of the clone context manager is correct.

Yes, I guess one can return t. I am not very sure either to understand the clone mantra.

Also, is it OK if I split LabelledRootedTrees into an abstract base class and a concrete class?

Yes, please do as you want, but try to keep things simple enough for me :)

[git]

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

​39a4e17	disambiguating the notions of trees involved
​44d4e92	abstract base class of LabelledRootedTrees separated from actual _all class; ordered_tree.py reviewed

[git]

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

​ac12f31

more edits

[darij]

Is this:

        tst = (children.__class__ is self.__class__
               and children.parent() == parent)
        if not tst:
            children = [self.__class__(parent, x) for x in children]

supposed to catch the case of children being a rooted tree? Because I'm not sure I understand the logic. childen is a list; maybe you want x.__class__ for x in children instead of children.__class__?

Also, as usual, I don't understand the classcall metaclass magic, so I am just reading past it.

[git]

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

​1c3bfea

another doctest

[git]

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

​ce230e2

further edits

[darij]

OK, almost positive_review. I leave the following functions to someone who understands our OOP better:

• RootedTree.__classcall_private__

• RootedTree.__init__ (see also ​http://trac.sagemath.org/ticket/11529#comment:37 )

• RootedTree.normalize

• LabelledRootedTree.__classcall_private__

[tscrim]

I will try to take a look at them over the weekend (unless someone beats me to it).

[git]

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

​891b1cc	Merge branch 'public/combinat/11529' of trac.sagemath.org:sage into public/combinat/11529
​5540205	Some minor reviewer tweaks.

[tscrim]

I made some minor changes, so if you're happy with them, then positive review since the class heirachy looks good. (Sorry it's almost the following weekend.)

[darij]

The changes look OK to me (except I still don't understand the

if not (children.__class__ is self.__class__
        and children.parent() == parent):

check). What about you, Frederic?

Thank you for looking at this, Travis!

[tscrim]

Replying to darij:

The changes look OK to me (except I still don't understand the

if not (children.__class__ is self.__class__
        and children.parent() == parent):

check).

That is making sure that the children are also rooted subtrees of the same parent (you can think of it like a linked list, but instead of a separate class for nodes, it links to a smaller list).

Thank you for looking at this, Travis!

The least I could do.

[darij]

But isn't children a list by the moment this check is happening?

[tscrim]

Replying to darij:

But isn't children a list by the moment this check is happening?

You're right; this check is worthless. An artifact of refactoring out #10194 perhaps?

[darij]

Maybe. Would you suggest fixing it or just blanket casting children to the appropriate class?

[tscrim]

I'd comment out the if and do the blanket casting. Want me to do it?

[darij]

Yeah, I'm slowly going to bed so I'd rather not fire up the virtual machine. Feel free to set this to positive_review then!

[git]

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

​1c377ad

One last fix for a unless check.

[tscrim]

Done, thanks.

[vbraun]

just as a general PSA, i'm not merging tickets that are milestone: sage-pending

[vbraun]

sorry, wrong ticket ;-)

[chapoton]

Follow-up ticket at #15635

[darij]

Hello Volker :)

[vbraun]

Don't make pre-git tickets a dependency if you want auutomatic merging to work...

[vbraun]

Conflict, probably with #18179

[git]

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

​42e505e	do not use pip to install mistune
​eeb2487	Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into root

[darij]

I don't see any conflict, but here is a merge for convenience.

---

New commits:

​42e505e	do not use pip to install mistune
​eeb2487	Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into root

[vbraun]

If you didn't get a conflict then the conflict was elsewhere. Try 6.7.beta1

[git]

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

​05a15fd

manual merge with 6.7.beta1, fixing the conflict in sage/combinat/ordered_tree.py

[chapoton]

Damn, there is a failing doctest !

[chapoton]

I am working on that..

[git]

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

​d4866c6	trac #11529 making it work without ranker
​4c9cc11	trac #11529 fixing doc for rooted trees
​4234b04	trac #11529 taking care of normalize in ordered trees, and doc

[chapoton]

ok, I have got rid of ranker, so that the order is now deterministic.

Maybe it will be slow, but speed can be taken care later on.

I have tried to use cached_method for the sort_key function, but it does not interact well with the ClonableTree? setup.

The patchbot should be happy, let us see.

[git]

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

​27c586d

partial review; ensure that labelled trees get normalized correctly if their children have equal shapes

[darij]

Stupid question: If a class inherits both from LabelledOrderedTree and another subclass of OrderedTree, then is there a way to tell which class's sort_key method it will get? Because if it gets it from OrderedTree, then its normalization won't work properly (sort_key will ignore the labels).

Same for methods such as left_right_symmetry.

[chapoton]

Well, I do not know. Do you think that it matters for the present ticket ?

By the way, do you you want to keep the "dendrographical" stuff ?

[darij]

I am slightly biased towards keeping things that work -- or do you see the dendrographical stuff as broken in some way? (When we get to combinatorial Hopf algerbas based on trees and transfers between different bases, every order will be useful...)

I don't know if the double inheritance (MRO) issue is a problem; this is why I'm asking. I would default to adding some warnings into the docstring, but I know of some people that are allergic to my warnings, and some other people who might find them not sufficient, so I prefer to ask...

[chapoton]

No problem, let us keep the 'dendrographical' stuff. The name sounds somewhat funny to me.

I am not sure I see the point on warning about issues that look not very likely to be met in the near future. But if you want to add them, I will not resist.

My aim now is to have this ticket in, as soon as possible, so that I can start to work on the algebraic follow-up ticket #15635.

[git]

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

​a190d1f

some weasel words I feel uncomfortable without

[git]

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

​99f6de5

review patch

[git]

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

​dc0ebfe

also improve the doc of left_right_symmetry

[darij]

Done. Are you OK with my changes?

I've added documentation for the pitfall I have mentioned in comment:72. Generally, I think Sage is lacking many warnings and implementation notes that would make it easier (or even possible) to extend from the existing classes as opposed to implementing new things from scratch because one doesn't understand the old classes' structure. In many cases, they would also help the reviewers review the patches (although in the current case this was simple enough).

I'm also waiting for #15635 to be ready, but alas I cannot help with the coercion :(

[chapoton]

ok, the bot is happy. Darij, I agree with your changes (even if they make me think about the keyword "verbosity").

So, please put that into positive review, if you want ?

[darij]

Thank you!

[vbraun]

On 32-bit:

sage -t --long src/sage/combinat/rooted_tree.py
**********************************************************************
File "src/sage/combinat/rooted_tree.py", line 259, in sage.combinat.rooted_tree.RootedTree.__hash__
Failed example:
    hash(RT([[],[[]]]))  # indirect doctest
Expected:
    2578595415271398032
Got:
    1119083152
**********************************************************************
File "src/sage/combinat/rooted_tree.py", line 891, in sage.combinat.rooted_tree.LabelledRootedTree.__hash__
Failed example:
    hash(lb)  # indirect doctest
Expected:
    686798862222558969
Got:
    652936953
**********************************************************************
2 items had failures:
   1 of   3 in sage.combinat.rooted_tree.LabelledRootedTree.__hash__
   1 of   3 in sage.combinat.rooted_tree.RootedTree.__hash__
    [155 tests, 2 failures, 1.79 s]

[git]

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

​811a797

fix two hash docstrings

[darij]

Good call -- I don't know how I missed them.

[chapoton]

No, no ! This hash should be different for 32 and 64 bits !

[darij]

You mean "should be" or "is"? What is going on here? Why should a hash (computed via sort_key) be machine-dependent?

[chapoton]

The hash is different. See many places, for example:

            sage: F = CombinatorialFreeModule(QQ, ['a','b','c'])
            sage: B = F.basis()
            sage: f = B['a'] + 3*B['c']
            sage: hash(f)
            6429418278783588506           # 64-bit
            726440090                     # 32-bit

[darij]

Oh! Should it be marked #random?

[chapoton]

No, it should have the two possible answers as in the example above.

[git]

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

​e8ed592	Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into tree
​dc8120f	new attempt at fixing doctests, can only check 32bit

[chapoton]

good for me on 64-bit

[darij]

Thank you!

[tscrim]

The easier test to make sure the hash is working is to do something like hash(x) == hash(x) (unless of course you're expecting a specific value, like hash(1) == 1), and it doesn't cause trivial doctest failures for changes to the hash function, but it probably doesn't really matter here.

[hivert]

Replying to tscrim:

The easier test to make sure the hash is working is to do something like hash(x) == hash(x) (unless of course you're expecting a specific value, like hash(1) == 1), and it doesn't cause trivial doctest failures for changes to the hash function, but it probably doesn't really matter here.

If you use the same x then you are not testing anything serious. A good test would be hash(x) == hash(y) with x and y two distinct but equal objects.

Florent which is coming back to Sage after a long absence.

By the way : Tanks to all of you for finishing this one !

[chapoton]

Hello Florent. Glad to see you back.

To finish this ticket, I had to get rid of the dependency to #10194. If I could suggest something, that would be to take care of #10194. It would certainly help several people, that have based many of their tickets on that one.