Opened 6 years ago

Closed 3 years ago

#11529 closed enhancement (fixed)

Rooted trees

Reported by: hivert Owned by: hivert
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords: rooted trees
Cc: sage-combinat, tscrim, darij Merged in:
Authors: Florent Hivert Reviewers: Frédéric Chapoton, Darij Grinberg, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: dc8120f (Commits) Commit: dc8120fd74f1d65a812e96c33afc9a8ca9a0bc8e
Dependencies: Stopgaps:

Description (last modified by chapoton)

Implement combinatorial (unordered) rooted trees

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

Attachments (1)

trac_11529-rooted_trees-fh.patch (21.8 KB) - added by hivert 6 years ago.

Download all attachments as: .zip

Change History (97)

comment:1 Changed 6 years ago by hivert

  • Dependencies changed from #11407 to #11407, #10194
  • Description modified (diff)
  • Status changed from new to needs_review

Changed 6 years ago by hivert

comment:2 Changed 6 years ago by dkrenn

  • Status changed from needs_review to needs_work

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

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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 4 years ago by 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.

comment:6 Changed 4 years ago by chapoton

  • Branch set to u/chapoton/11529
  • Commit set to bad859055dcfc8e014125b31e25702359d6e462a

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.
bad8590trac #11529 pyflakes details

comment:7 Changed 4 years ago by git

  • Commit changed from bad859055dcfc8e014125b31e25702359d6e462a to f0bd1323350839e28c20e43d6e813e73b4880278

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

f0bd132trac #11529 minor details

comment:8 Changed 4 years ago by git

  • Commit changed from f0bd1323350839e28c20e43d6e813e73b4880278 to 5a15e0796b249344ef66b5a6f9a1d7e1a17107f7

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

5a15e07trac #11529 trying to make it work

comment:9 Changed 4 years ago by git

  • Commit changed from 5a15e0796b249344ef66b5a6f9a1d7e1a17107f7 to 5849b284ed4e139efebc38a8f1d7bbf8a09e301b

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

5849b28trac #11529 tests seem to pass

comment:10 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 3 years ago by git

  • Commit changed from 5849b284ed4e139efebc38a8f1d7bbf8a09e301b to 0047c1acc3c446c706c76d98033b75569d14494d

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

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

comment:12 Changed 3 years ago by git

  • Commit changed from 0047c1acc3c446c706c76d98033b75569d14494d to ca7005437d488c5a036eff909ddec4bf501b2c62

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

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

comment:13 Changed 3 years ago by git

  • Commit changed from ca7005437d488c5a036eff909ddec4bf501b2c62 to be21430e31d03f77405df68b91f83e90352aaac1

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

be21430trac #11529 two more useful methods

comment:14 Changed 3 years ago by git

  • Commit changed from be21430e31d03f77405df68b91f83e90352aaac1 to 6bf100e78976d7c56b5ba8843b40e80dec3265ad

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

6bf100etrac #11529 make tests pass

comment:15 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:16 Changed 3 years ago by git

  • Commit changed from 6bf100e78976d7c56b5ba8843b40e80dec3265ad to 9aa6ab2d1927fcc526a186d0025e96068476702f

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

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

comment:17 Changed 3 years ago by chapoton

  • Branch changed from u/chapoton/11529 to u/chapoton/11529_alone
  • Cc tscrim darij added
  • Commit changed from 9aa6ab2d1927fcc526a186d0025e96068476702f to a4b4c6ee3ce9f82864e3b179380517ff123582ef
  • Dependencies changed from #11407, #10194 to #11407
  • Milestone changed from sage-6.4 to sage-6.5
  • Status changed from needs_work to needs_review

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:

dd078faMerge branch 'u/chapoton/11529' into 6.5.rc3
a4b4c6etrac #11529 Remove dependency to set factories

comment:18 follow-up: Changed 3 years ago by 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 .)

Last edited 3 years ago by darij (previous) (diff)

comment:19 in reply to: ↑ 18 Changed 3 years ago by 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).

comment:20 Changed 3 years ago by git

  • Commit changed from a4b4c6ee3ce9f82864e3b179380517ff123582ef to b8f8004bae8ebff79b313c571a64c81aba89281a

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

49681fctrac #11529 little more doc and change name of cayley_normalize
b8f8004trac #11529 remove the word Cayley as asked

comment:21 Changed 3 years ago by git

  • Commit changed from b8f8004bae8ebff79b313c571a64c81aba89281a to 76f695772807e9cad8d48a6fb0fc14e78289a2aa

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

76f6957trac #11529 inclusion of doc into table of contents, etc

comment:22 Changed 3 years ago by 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?

Last edited 3 years ago by darij (previous) (diff)

comment:23 Changed 3 years ago by git

  • Commit changed from 76f695772807e9cad8d48a6fb0fc14e78289a2aa to ac7687a92a4b288aa58ba140515da7f1e5f357b4

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

dc7e79eMerge branch 'u/chapoton/11529_alone' into 6.5
ac7687atrac #11529 a few changes in the doc

comment:24 Changed 3 years ago by git

  • Commit changed from ac7687a92a4b288aa58ba140515da7f1e5f357b4 to 3e619b011df83fe7782a2b31c35354f1dd4dfda6

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

3e619b0trac #11529 more doc again

comment:25 Changed 3 years ago by 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.

comment:26 Changed 3 years ago by 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 ?

comment:27 Changed 3 years ago by darij

  • Branch changed from u/chapoton/11529_alone to public/combinat/11529
  • Commit changed from 3e619b011df83fe7782a2b31c35354f1dd4dfda6 to 5219d2e4ef7c38fe5ce7a40289cdc118cac2bff3

New commits:

5219d2edeterministic normalization of rooted ordered trees

comment:28 Changed 3 years ago by 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.

comment:29 Changed 3 years ago by git

  • Commit changed from 5219d2e4ef7c38fe5ce7a40289cdc118cac2bff3 to 14a8d8b995df1562750441027f0cc3560cf8e061

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

f16a183Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into trees
03a8862x
14a8d8breverting changes, keeping dendrographical order

comment:30 Changed 3 years ago by git

  • Commit changed from 14a8d8b995df1562750441027f0cc3560cf8e061 to c1aca706fd40900e59024f19a4e29fe190fd65f2

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

c1aca70reverting changes, keeping dendrographical order

comment:31 Changed 3 years ago by darij

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

comment:32 follow-up: Changed 3 years ago by 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?

comment:33 in reply to: ↑ 32 Changed 3 years ago by 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 :)

comment:34 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.5 to sage-6.6

comment:35 Changed 3 years ago by git

  • Commit changed from c1aca706fd40900e59024f19a4e29fe190fd65f2 to 44d4e924423f122e9c485bc93d292e63fa098d7b

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

39a4e17disambiguating the notions of trees involved
44d4e92abstract base class of LabelledRootedTrees separated from actual _all class; ordered_tree.py reviewed

comment:36 Changed 3 years ago by git

  • Commit changed from 44d4e924423f122e9c485bc93d292e63fa098d7b to ac12f31827a5073a4f03fe6cc4db8e7714e51603

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

ac12f31more edits

comment:37 Changed 3 years ago by 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.

comment:38 Changed 3 years ago by git

  • Commit changed from ac12f31827a5073a4f03fe6cc4db8e7714e51603 to 1c3bfeab259395574fd0fdc3c4653415600448fc

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

1c3bfeaanother doctest

comment:39 Changed 3 years ago by git

  • Commit changed from 1c3bfeab259395574fd0fdc3c4653415600448fc to ce230e2caa809deb6ac90ece8ce6e3717848827b

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

ce230e2further edits

comment:40 Changed 3 years ago by darij

  • Reviewers set to Frederic Chapoton, Darij Grinberg,

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

  • RootedTree.__classcall_private__
  • RootedTree.normalize
  • LabelledRootedTree.__classcall_private__
Last edited 3 years ago by darij (previous) (diff)

comment:41 Changed 3 years ago by tscrim

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

comment:42 Changed 3 years ago by chapoton

  • Description modified (diff)
  • Keywords Cayley removed

comment:43 Changed 3 years ago by chapoton

  • Reviewers changed from Frederic Chapoton, Darij Grinberg, to Frédéric Chapoton, Darij Grinberg,

comment:44 Changed 3 years ago by git

  • Commit changed from ce230e2caa809deb6ac90ece8ce6e3717848827b to 554020502657566ed334823ac0d36e39b2fcb22d

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

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

comment:45 Changed 3 years ago by tscrim

  • Reviewers changed from Frédéric Chapoton, Darij Grinberg, to Frédéric Chapoton, Darij Grinberg, Travis Scrimshaw

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

comment:46 follow-up: Changed 3 years ago by 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!

Last edited 3 years ago by darij (previous) (diff)

comment:47 in reply to: ↑ 46 Changed 3 years ago by 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.

comment:48 follow-up: Changed 3 years ago by darij

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

comment:49 in reply to: ↑ 48 Changed 3 years ago by 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?

comment:50 Changed 3 years ago by darij

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

comment:51 Changed 3 years ago by tscrim

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

comment:52 Changed 3 years ago by 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!

comment:53 Changed 3 years ago by git

  • Commit changed from 554020502657566ed334823ac0d36e39b2fcb22d to 1c377ad3988c9ac47e54922a6722fd714b2a7e3d

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

1c377adOne last fix for a unless check.

comment:54 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Done, thanks.

comment:55 Changed 3 years ago by vbraun

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

comment:56 Changed 3 years ago by vbraun

sorry, wrong ticket ;-)

comment:57 Changed 3 years ago by chapoton

Follow-up ticket at #15635

comment:58 Changed 3 years ago by darij

Hello Volker :)

comment:59 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.6 to sage-6.7

comment:60 Changed 3 years ago by vbraun

  • Dependencies #11407 deleted

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

comment:61 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Conflict, probably with #18179

comment:62 Changed 3 years ago by git

  • Commit changed from 1c377ad3988c9ac47e54922a6722fd714b2a7e3d to eeb2487181515d62efb4551e1ac98fb2c0125ab9

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

42e505edo not use pip to install mistune
eeb2487Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into root

comment:63 Changed 3 years ago by darij

  • Status changed from needs_work to positive_review

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


New commits:

42e505edo not use pip to install mistune
eeb2487Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into root

comment:64 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

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

comment:65 Changed 3 years ago by git

  • Commit changed from eeb2487181515d62efb4551e1ac98fb2c0125ab9 to 05a15fd83d9d9000be2591bfaa3a35fdf4b34379

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

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

comment:66 Changed 3 years ago by darij

  • Status changed from needs_work to positive_review

comment:67 Changed 3 years ago by chapoton

  • Status changed from positive_review to needs_work

Damn, there is a failing doctest !

comment:68 Changed 3 years ago by chapoton

I am working on that..

comment:69 Changed 3 years ago by git

  • Commit changed from 05a15fd83d9d9000be2591bfaa3a35fdf4b34379 to 4234b0403bd321e9da5d64f59650f52b56074d37

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

d4866c6trac #11529 making it work without ranker
4c9cc11trac #11529 fixing doc for rooted trees
4234b04trac #11529 taking care of normalize in ordered trees, and doc

comment:70 Changed 3 years ago by chapoton

  • Status changed from needs_work to needs_review

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.

comment:71 Changed 3 years ago by git

  • Commit changed from 4234b0403bd321e9da5d64f59650f52b56074d37 to 27c586dd6b4b05cefd80cb5ffbfc145a3b565541

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

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

comment:72 Changed 3 years ago by 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.

Last edited 3 years ago by darij (previous) (diff)

comment:73 Changed 3 years ago by 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 ?

comment:74 Changed 3 years ago by 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...

Last edited 3 years ago by darij (previous) (diff)

comment:75 Changed 3 years ago by 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.

comment:76 Changed 3 years ago by git

  • Commit changed from 27c586dd6b4b05cefd80cb5ffbfc145a3b565541 to a190d1f1f16ccab76ac2812c5b9a923ed6ff3e9c

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

a190d1fsome weasel words I feel uncomfortable without

comment:77 Changed 3 years ago by git

  • Commit changed from a190d1f1f16ccab76ac2812c5b9a923ed6ff3e9c to 99f6de56e5d8bc4b834d4d22abb0303560103b32

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

99f6de5review patch

comment:78 Changed 3 years ago by git

  • Commit changed from 99f6de56e5d8bc4b834d4d22abb0303560103b32 to dc0ebfeb5a185b5a1ab3bedfbe2f786ca6de0965

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

dc0ebfealso improve the doc of left_right_symmetry

comment:79 Changed 3 years ago by 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 :(

comment:80 Changed 3 years ago by 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 ?

comment:81 Changed 3 years ago by darij

  • Status changed from needs_review to positive_review

Thank you!

comment:82 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

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]

comment:83 Changed 3 years ago by git

  • Commit changed from dc0ebfeb5a185b5a1ab3bedfbe2f786ca6de0965 to 811a7975d60133f5bd9e69be251982f04939f5a8

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

811a797fix two hash docstrings

comment:84 Changed 3 years ago by darij

  • Status changed from needs_work to positive_review

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

comment:85 Changed 3 years ago by chapoton

  • Status changed from positive_review to needs_work

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

comment:86 Changed 3 years ago by darij

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

comment:87 Changed 3 years ago by 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

comment:88 Changed 3 years ago by darij

Oh! Should it be marked #random?

comment:89 Changed 3 years ago by chapoton

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

comment:90 Changed 3 years ago by git

  • Commit changed from 811a7975d60133f5bd9e69be251982f04939f5a8 to dc8120fd74f1d65a812e96c33afc9a8ca9a0bc8e

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

e8ed592Merge branch 'public/combinat/11529' of git://trac.sagemath.org/sage into tree
dc8120fnew attempt at fixing doctests, can only check 32bit

comment:91 Changed 3 years ago by chapoton

  • Status changed from needs_work to positive_review

good for me on 64-bit

comment:92 Changed 3 years ago by darij

Thank you!

comment:93 follow-up: Changed 3 years ago by 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.

comment:94 in reply to: ↑ 93 Changed 3 years ago by 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 !

Last edited 3 years ago by hivert (previous) (diff)

comment:95 Changed 3 years ago by 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.

comment:96 Changed 3 years ago by vbraun

  • Branch changed from public/combinat/11529 to dc8120fd74f1d65a812e96c33afc9a8ca9a0bc8e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.