Rooted trees

[hivert]

Implement combinatorial (unordered) rooted trees

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

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

Component: combinatorics

Keywords: rooted trees

Author: Florent Hivert

Branch/Commit: dc8120f

Reviewer: Frédéric Chapoton, Darij Grinberg, Travis Scrimshaw

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

[hivert]

Changed dependencies from #11407 to #11407, #10194

[dkrenn]

comment:2

Attachment: trac_11529-rooted_trees-fh.patch.gz

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

[fchapoton]

comment:5

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.

[fchapoton]

Branch: u/chapoton/11529

[fchapoton]

comment:6

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

[fchapoton]

Commit: bad8590

[sagetrac-git]

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

f0bd132

trac #11529 minor details

[sagetrac-git]

Changed commit from bad8590 to f0bd132

[sagetrac-git]

Changed commit from f0bd132 to 5a15e07

[sagetrac-git]

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

5a15e07

trac #11529 trying to make it work

[sagetrac-git]

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

5849b28

trac #11529 tests seem to pass

[sagetrac-git]

Changed commit from 5a15e07 to 5849b28

[sagetrac-git]

Changed commit from 5849b28 to 0047c1a

[sagetrac-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

[sagetrac-git]

Changed commit from 0047c1a to ca70054

[vbraun]

comment:82

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]

[sagetrac-git]

Changed commit from dc0ebfe to 811a797

[sagetrac-git]

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

811a797

fix two hash docstrings

[darijgr]

comment:84

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

[fchapoton]

comment:85

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

[darijgr]

comment:86

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

[fchapoton]

comment:87

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

[darijgr]

comment:88

Oh! Should it be marked #random?

[fchapoton]

comment:89

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

[sagetrac-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

[sagetrac-git]

Changed commit from 811a797 to dc8120f

[fchapoton]

comment:91

good for me on 64-bit

[darijgr]

comment:92

Thank you!

[tscrim]

comment:93

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]

comment:94

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 !

[fchapoton]

comment:95

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.

[vbraun]

Changed branch from public/combinat/11529 to dc8120f