simplicial complexes lack hash function

[sagetrac-vpilaud]

Simplicial complexes are lacking a proper hash function. See the example below.

sage: S = SimplicialComplex([[]]); S
Simplicial complex with vertex set () and facets {()}
sage: hash(S)
-3899221226149827755
sage: S.__hash__??
Source:
    def __hash__(self):
        return hash(self.__repr__())

---

Apply:

• attachment: trac_12587-simplicial_complex_hash-ts.patch
• attachment: trac_12587-simplicial_complex_hash_review-cs.patch
• attachment: trac_12587-ref-jhp.patch

Depends on #13226
Depends on #13244
Depends on #13590

CC: @sagetrac-sage-combinat

Component: combinatorics

Author: Travis Scrimshaw

Reviewer: Christian Stump, John Palmieri

Merged: sage-5.6.beta1

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

[tscrim]

comment:1

Since SimplicialComplex is mutable, the hash function must depend on something immutable. Because of this, I would like for it to be handled like Graph and throw a TypeError. However there are many dependencies on SimplicialComplex being hashable, so my thought behind setting this to wontfix is that repr is the only immutable part of the class.

[jhpalmieri]

comment:2

Why not instead modify the SimplicialComplex class so that it is immutable?

[sagetrac-sluther]

comment:3

Being mutable and hashable is definetly a bug. See [1].

I don't understand what you mean with repr is the only immutable part, because it may change when the object changes.

[1] http://docs.python.org/glossary.html#term-hashable

[tscrim]

comment:4

Replying to @sagetrac-sluther:

Being mutable and hashable is definetly a bug. See [1].

I don't understand what you mean with repr is the only immutable part, because it may change when the object changes.

[1] http://docs.python.org/glossary.html#term-hashable

You're correct. I forgot that repr outputs the facets.

However I'm not in favor of making SimplicialComplex an immutable object outright since it contains mutators and there are inductive constructions which would require you to build copies. For example, suppose you had an algorithm which built a simplicial complex facet by facet, at each step you would need to clone the SimplicialComplex object in the mutator. Thus extra memory handling and multiple transient objects.

Perhaps we should do something closer to ClonableArray and have an attribute _is_mutable which we set to True when __hash__() is called and in any mutators, we do something of the following:

if _is_mutable:
    raise TypeError, "This simplicial complex is no longer mutable"

Thus making it immutable as soon as it becomes hashed?

Also we'd have

__hash__(self):
    _is_mutable = True
    return hash(self.facets())

Your thoughts?

[sagetrac-sluther]

comment:5

Replying to @tscrim:

Perhaps we should do something closer to ClonableArray and have an attribute _is_mutable which we set to True when __hash__() is called and in any mutators, we do something of the following:

if _is_mutable:
    raise TypeError, "This simplicial complex is no longer mutable"

Thus making it immutable as soon as it becomes hashed?

Also we'd have

__hash__(self):
    _is_mutable = True
    return hash(self.facets())

Your thoughts?

I don't like this idea because it violoates the principle of least suprise. For example the question if an object can be modified depends upon the question if it has been added into a set or not.
Better add an explicit method that sets this attribute.

[tscrim]

comment:6

Replying to @sagetrac-sluther:

I don't like this idea because it violoates the principle of least suprise. For example the question if an object can be modified depends upon the question if it has been added into a set or not.
Better add an explicit method that sets this attribute.

Good point. Then how about this?

def set_immutable(self):
    self._is_mutable = False

def __hash__(self):
    if not _is_mutable:
        raise TypeError, "This simplicial complex must be set to immutable by calling set_immutable()"
    return hash(self.facets())

[sagetrac-sluther]

comment:7

Replying to @tscrim:

Good point. Then how about this?

def set_immutable(self):
    self._is_mutable = False

def __hash__(self):
    if not _is_mutable:
        raise TypeError, "This simplicial complex must be set to immutable by calling set_immutable()"
    return hash(self.facets())

Fine, just be careful with not reversing the meaning of _is_mutable like in __hash__.

[nbruin]

comment:8

I have no opinion on what the best error types and messages are for this, but it is probably good if they are consistent. Since this is completely analogous to matrices, you should probably follow that example or change it to conform to yours (if you have good arguments to change it):

sage: M=matrix([[1,2],[3,4]])
sage: M.__hash__()
TypeError: mutable matrices are unhashable
sage: M[0,0]=5
sage: M.set_immutable()
sage: M.__hash__()
sage: M[0,0]=5
ValueError: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).

On the other hand:

sage: t=(1,2,3)
sage: t[0]=4
TypeError: 'tuple' object does not support item assignment

but then again a ValueError indicates something that something is wrong with the value, not with the type (tuple is never mutable, but matrix can be).

[tscrim]

comment:9

I feel like it should raise a TypeError since making it immutable is, in essence, a class property. Additionally Graph raises a TypeError anytime __hash__() is called.

Also more of a random thought: what if we delete the mutators when we make it immutable?

def is_mutable(self):
    del self.add_face
    del self.remove_face

[jhpalmieri]

comment:10

remove_face is not a mutator.

[nbruin]

comment:11

Replying to @tscrim:

I feel like it should raise a TypeError since making it immutable is, in essence, a class property. Additionally Graph raises a TypeError anytime __hash__() is called.

Sage isn't consistent (yet?) in this regard:

sage: L=Sequence([1,2,3])
sage: hash(L)
ValueError: mutable sequences are unhashable
sage: L.append(4)
sage: L.set_immutable()
sage: hash(L)
...
sage: L.append(4)
ValueError: object is immutable; please change a copy instead.

On the one hand, it's convenient if "hash(...)" always gives the same kind of
error on an unhashable object (easier to catch). This is what Matrix does.

One the other, if a class instance can change from being unhashable to being
hashable it's obviously not a property of the class, but of this individual
object (its "value"). This is what Sequence does.

Don't go deleting methods! That's just a hack. Cython classes can't even do it.
If you want to go that way, you should make it a separate category
FrozenSimplicialComplex, ala set and frozenset in python itself, but the
approach you currently propose is more in line with other sage classes.

[tscrim]

comment:12

Replying to @jhpalmieri:

remove_face is not a mutator.

To be consistant, I changed it into a mutator. Let me know if there are any objections.

Replying to @nbruin:

On the one hand, it's convenient if "hash(...)" always gives the same kind of
error on an unhashable object (easier to catch). This is what Matrix does.

One the other, if a class instance can change from being unhashable to being
hashable it's obviously not a property of the class, but of this individual
object (its "value"). This is what Sequence does.

I've changed everything to raise a ValueError. I'm wondering if we should create a new exception class for mutable objects such as MutableError. Probabily needs a discussion and for sure another ticket.

Don't go deleting methods! That's just a hack. Cython classes can't even do it.
If you want to go that way, you should make it a separate category
FrozenSimplicialComplex, ala set and frozenset in python itself, but the
approach you currently propose is more in line with other sage classes.

That's a good point about the cython class. I'm going to keep with the current methodology.

[tscrim]

comment:13

I'd be appreciative if anyone is willing to review this.

Also, I found another patch by vp (which I presume is vpiluad) in the sage-combinat queue which makes very small tweaks to __hash__() and __cmp__() of Simplex. So vpiluad, would it be okay if I just delete your patch?

[tscrim]

Author: Travis Scrimshaw

[jhpalmieri]

comment:15

Replying to @tscrim:

Replying to @jhpalmieri:

remove_face is not a mutator.

To be consistant, I changed it into a mutator. Let me know if there are any objections.

Why not change add_face so it's not a mutator. Wouldn't that simplify the hashing issue?

[tscrim]

comment:16

Replying to @jhpalmieri:

Replying to @tscrim:

Replying to @jhpalmieri:

remove_face is not a mutator.

To be consistant, I changed it into a mutator. Let me know if there are any objections.

Why not change add_face so it's not a mutator. Wouldn't that simplify the hashing issue?

Doing that would fix it. However some of the methods in SimplicialComplex use add_face() (as I recall _enlarge_subcomplex() is the main culprit), so it'd cut down on the number of transient objects. Also I feel like this is becomes consistent with Graph (and by my understanding Sequence and Matrix).

[tscrim]

comment:39

Thank you for the review.

[jhpalmieri]

comment:40

This looks very good. I have a few more changes, though: we should make sure that the various deprecations are documented in the reference manual (which does not include methods like __init__). Also, when I built the documentation, I got a warning about a duplicated reference for [Hat], so I removed one of them. Finally, I added doctests to the __init__ method to test the new deprecations. I think my patch needs review.

[tscrim]

comment:42

I also got the duplicate reference once (a long while ago), but never on any subsequent docbuild. I've looked over you review patch and looks good to me. Thank you for your diligence.

[tscrim]

Changed reviewer from Christian Stump to Christian Stump, John Palmieri

[stumpc5]

comment:43

Replying to @jhpalmieri:

Also, when I built the documentation, I got a warning about a duplicated reference for [Hat], so I removed one of them.

I also had this problem only the first time I built the documentation.

Now, the reference is missing in the documentation of Simplex.product, which I don't think is the solution either. When I was doing the review, I spent some time to figure out how to solve this issue but didn't manage to do so.

Do you happen to know how to either reference a citation in a different file, or to have the same citation in different files without getting a warning?

Best, Christian

[jhpalmieri]

comment:44

Replying to @stumpc5:

Replying to @jhpalmieri:

Also, when I built the documentation, I got a warning about a duplicated reference for [Hat], so I removed one of them.

I also had this problem only the first time I built the documentation.

I would guess that if you delete the documentation output, or if you somehow force Sage to rebuild the documentation of delta_complex.py, you'll see the warning again.

Now, the reference is missing in the documentation of Simplex.product, which I don't think is the solution either. When I was doing the review, I spent some time to figure out how to solve this issue but didn't manage to do so.

I still see the reference, and if I click on the citation, I get taken to the reference in the other file. Also, most people reading the docstring will know what "Hatcher" means – it's not an obscure reference – so won't even need to look it up.

Do you happen to know how to either reference a citation in a different file

It works for me. Try rebuilding all of the documentation (rm -rf SAGE_ROOT/devel/sage/doc/output/ and then sage --docbuild reference html).

[stumpc5]

comment:45

Replying to @jhpalmieri:

Replying to @stumpc5:

Replying to @jhpalmieri:

I still see the reference, and if I click on the citation, I get taken to the reference in the other file. Also, most people reading the docstring will know what "Hatcher" means – it's not an obscure reference – so won't even need to look it up.

Saying this: might it be even worth adding the reference of the freely available pdf version of the book?

It works for me. Try rebuilding all of the documentation (rm -rf SAGE_ROOT/devel/sage/doc/output/ and then sage --docbuild reference html).

This indeed solved the issue on my machine as well, thanks!

If any one of you wanna go ahead: I am happy with giving it a positive review again!

[tscrim]

comment:46

Here's what happened (in writing this patch):

• I wrote the reference into simplicial_complex.py,
• compiled doc and got the warning,
• remove the reference and rebuilt the doc from that (i.e. just that file),
• it did not link, so put the reference back in and no warning showed up,
• rebuilt the entire documentation without any simplicial complexes lack hash function #12587 patches applied
• added the review patches, then all references/linking worked.

Rebuilding the entire documentation is the only way to get it to work since references are global and global changes are (currently) only removed/edited when the entire documentation is rebuilt. (This is unbelievably annoying to me when working between patches that add/modify .rst files.) Or something like that...

[jhpalmieri]

Attachment: trac_12587-ref-jhp.patch.gz

[jhpalmieri]

comment:48

I updated my referee patch to deal with one more instance of SimplicialComplex begin called with a vertex set (in interfaces/chomp.py). There is probably one more that needs fixing (in sandpiles/sandpile.py), but I haven't installed the optional package 4ti2 to check it. I have installed CHomP, so I can verify the one I added to the patch.

[jhpalmieri]

comment:49

(See also #13769, which fixes optional doctests for interfaces/chomp.py when CHomP is installed.)

[jhpalmieri]

Dependencies: #13226, #13244, #13590

[jdemeyer]

Merged: sage-5.6.beta1