#12587 closed defect (fixed)
simplicial complexes lack hash function
Reported by: | vpilaud | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | combinatorics | Keywords: | |
Cc: | sage-combinat | Merged in: | sage-5.6.beta1 |
Authors: | Travis Scrimshaw | Reviewers: | Christian Stump, John Palmieri |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13226, #13244, #13590 | Stopgaps: |
Description (last modified by )
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:
Attachments (3)
Change History (55)
comment:1 Changed 9 years ago by
- Milestone changed from sage-5.3 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
Why not instead modify the SimplicialComplex
class so that it is immutable?
comment:3 follow-up: ↓ 4 Changed 9 years ago by
- Milestone changed from sage-duplicate/invalid/wontfix to sage-5.3
- Status changed from needs_review to needs_work
- Type changed from enhancement to defect
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.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 9 years ago by
Replying to 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.
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?
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 9 years ago by
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.
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 9 years ago by
Replying to 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())
comment:7 in reply to: ↑ 6 Changed 9 years ago by
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__
.
comment:8 Changed 9 years ago by
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).
comment:9 follow-up: ↓ 11 Changed 9 years ago by
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
comment:10 Changed 9 years ago by
remove_face
is not a mutator.
comment:11 in reply to: ↑ 9 ; follow-up: ↓ 12 Changed 9 years ago by
Replying to tscrim:
I feel like it should raise a
TypeError
since making it immutable is, in essence, a class property. Additionally Graph raises aTypeError
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.
comment:12 in reply to: ↑ 11 ; follow-ups: ↓ 13 ↓ 15 Changed 9 years ago by
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
, alaset
andfrozenset
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.
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 19 Changed 9 years ago by
- Status changed from needs_work to needs_review
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?
comment:14 Changed 9 years ago by
comment:15 in reply to: ↑ 12 ; follow-up: ↓ 16 Changed 9 years ago by
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?
comment:16 in reply to: ↑ 15 ; follow-up: ↓ 17 Changed 9 years ago by
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
).
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 9 years ago by
Replying to tscrim:
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 withGraph
(and by my understandingSequence
andMatrix
).
For what it's worth, I just searched through simplicial_complex.py, and I don't see add_face()
used anywhere except for some doctests.
I think consistency with other classes is secondary. I think the central question is: is there a good reason for simplicial complexes to be mutable?
comment:18 in reply to: ↑ 17 Changed 9 years ago by
Replying to jhpalmieri:
Replying to tscrim:
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 withGraph
(and by my understandingSequence
andMatrix
).For what it's worth, I just searched through simplicial_complex.py, and I don't see
add_face()
used anywhere except for some doctests.I think consistency with other classes is secondary. I think the central question is: is there a good reason for simplicial complexes to be mutable?
A priori, no. You're right, I could not find any code either (I looked through both the homology and combinat directories) which used add_face()
other than for the doc-tests. I feel like there are many constructions which iteratively build-up simplicial complexes or break them down piece by piece (such as k-decomposeability) and creating copies would create transient objects and inflate the memory usage. This is why I feel that we should have SimplicialComplex? be mutable.
comment:19 in reply to: ↑ 13 Changed 9 years ago by
Replying to tscrim:
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__()
ofSimplex
. So vpiluad, would it be okay if I just delete your patch?
My collaborator vpilaud actually opened this ticket (as his very first ticket). You can delete his small patch in the combinat queue concerning the hash of simplicial complexes.
We were/are working on a patch on implementing "subword complexes" (which are simplicial complexes) as defined by Knutson and Miller in [1]. In this context, we needed fast hashing of simplicies and of simplicial complexes for constructing them. We now use a different algorithm, but if there will eventually be an immutable version of simplicial complexes with fast hashing, we might go back to another, faster algorithm.
Anyway, I appreciate your work on this!
Christian
[1] A. Knutson and E. Miller, Subword complexes in Coxeter groups, Adv. Math. 184(1), 2004.
comment:20 follow-up: ↓ 21 Changed 9 years ago by
Since you propose to make the hash only dependent on the facets:
sage: S = SimplicialComplex([1,2,3],[[1,2]]) sage: S Simplicial complex with vertex set (1, 2, 3) and facets {(1, 2)}
([1,2,3]
is actually not the vertex set, but the *ground set*, while the vertex set is [1,2]
.) The proposed implementation only takes the facets into account for hashing, thus we get the same hash for
sage: S = SimplicialComplex([1,2],[[1,2]]) sage: S Simplicial complex with vertex set (1, 2) and facets {(1, 2)}
Is this the desired behaviour - or should the ground set be used as well for hashing?
(I don't have a strong opinion on this question, but I thought I bring it up anyway. If you don't want to take care of the vertex set vs. ground set issue in this ticket here, I will open another and ask for other peoples opinion there.)
comment:21 in reply to: ↑ 20 Changed 9 years ago by
Replying to stumpc5:
Since you propose to make the hash only dependent on the facets:
sage: S = SimplicialComplex([1,2,3],[[1,2]]) sage: S Simplicial complex with vertex set (1, 2, 3) and facets {(1, 2)}(
[1,2,3]
is actually not the vertex set, but the *ground set*, while the vertex set is[1,2]
.) The proposed implementation only takes the facets into account for hashing, thus we get the same hash forsage: S = SimplicialComplex([1,2],[[1,2]]) sage: S Simplicial complex with vertex set (1, 2) and facets {(1, 2)}Is this the desired behaviour - or should the ground set be used as well for hashing?
(I don't have a strong opinion on this question, but I thought I bring it up anyway. If you don't want to take care of the vertex set vs. ground set issue in this ticket here, I will open another and ask for other peoples opinion there.)
There are a few possibilities:
- This is a bug, in that
(3,)
should also be listed as a facet. - We handle this more like a matroid (I believe this is what you're suggesting) and add methods like
ground_set()
. - Split the difference and make an optional argument.
- We just do a stopgap here and make the hash depend upon the vertex/ground set and push this to another ticket.
My thought is we handle this as a bug, but I'm happy to implement whichever is decided upon. I have no strong opinions either.
Best,
Travis
comment:22 follow-up: ↓ 23 Changed 9 years ago by
Is this the desired behaviour?
Well, it's certainly the documented behavior (I mean the documented behavior of simplicial complexes). Note that you can also do
S = SimplicialComplex([[1,2]])
to get a complex with a single facet. So the vertex list is already an optional argument, in some sense.
I think that the hash should only depend on the facets; the unused vertices shouldn't have any effect. That makes the most mathematical sense to me.
comment:23 in reply to: ↑ 22 Changed 9 years ago by
Replying to jhpalmieri:
I think that the hash should only depend on the facets; the unused vertices shouldn't have any effect. That makes the most mathematical sense to me.
I agree.
But I still think that mathematically, a vertex is a 0-dimensional face, and thus must be contained in some facet, see [1] or basically any book on simplicial complexes. In the example above, 3
is therefore not a vertex. (In particular, "unused vertices" do not exist.) But this is then another issue, and we can discuss it on another ticket, as Travis suggested as well.
[1] http://en.wikipedia.org/wiki/Abstract_simplicial_complex : "The vertex set of Δ is defined as V(Δ) = ∪Δ, the union of all faces of Δ"
comment:24 follow-up: ↓ 25 Changed 9 years ago by
I think it would be absolutely fine to change the documentation of SimplicialComplex
to encourage the use of
sage: SimplicialComplex( list of facets )
instead of
sage: SimplicialComplex( vertex set, list of facets )
We could also go further and change the behavior of SimplicialComplex
so it ignores vertex_set
even if it is present, thus essentially deprecating its use. We could formally deprecate its use, in fact.
comment:25 in reply to: ↑ 24 Changed 9 years ago by
Replying to jhpalmieri:
I think it would be absolutely fine to change the documentation of
SimplicialComplex
to encourage the use ofsage: SimplicialComplex( list of facets )instead of
sage: SimplicialComplex( vertex set, list of facets )We could also go further and change the behavior of
SimplicialComplex
so it ignoresvertex_set
even if it is present, thus essentially deprecating its use. We could formally deprecate its use, in fact.
I'd be happy with deprecating vertex_set
. I could go through and make those changes on this ticket.
comment:26 Changed 9 years ago by
- Dependencies set to #13244
- Milestone changed from sage-5.4 to sage-5.5
Deprecated vertex_set
and made all of the appropriate changes. This is now based on (the to be merged) #13244.
comment:27 Changed 9 years ago by
Minor tweaks. Ready for review.
comment:28 Changed 9 years ago by
- Dependencies changed from #13244 to #13244 #13590
Rebased over #13590.
comment:29 Changed 9 years ago by
- Reviewers set to Christian Stump
- Status changed from needs_review to needs_work
Hi Travis,
I started to review the patch. Everything looks quite well, but you seem to have missed handling the parameters properly, see below:
sage: S = SimplicialComplex(maximal_faces=[[1,4], [2,4]]) ... TypeError: 'NoneType' object is not iterable
and with this
sage: S = SimplicialComplex(vertex_set=[1,2,4],maximal_faces=[[1,4], [2,4]]) sage: S Simplicial complex with vertex set (1, 2, 4) and facets {(2, 4), (1, 4)}
The deprecation could maybe as well quickly be mentioned in the init of SimplicialComplex, since vertex_set
is still there as an optional argument.
comment:30 Changed 9 years ago by
- Status changed from needs_work to needs_review
Thanks for reviewing this. Here's the updated patch fixing the above and with the added documentation in __init__()
.
comment:31 Changed 9 years ago by
What about
sage: S = SimplicialComplex(vertex_set=[1,2,3,4],maximal_faces=[[1,4], [2,4]]) /home/stumpc5/progs/sage-5.5.beta1/local/bin/sage-ipython:1: DeprecationWarning: vertex_set is deprecated. See http://trac.sagemath.org/12587 for details. #!/usr/bin/env python sage: S Simplicial complex with vertex set (1, 2, 3, 4) and facets {(2, 4), (1, 4)}
sorry to be picky here: I thought we agreed that the input vertex_set
is ignored, didn't we ? Mathematically, the above is simply wrong (see comment:22), so I would prefer if we could get rid of
Simplicial complex with vertex set (1, 2, 3, 4) and facets {(2, 4), (1, 4)}
Or do you think that deprecation enough?
comment:32 follow-up: ↓ 33 Changed 9 years ago by
I left it there in case someone was relying on that behavior as I thought the agreement was to just deprecate the functionality. However I have no problem completely ignoring it and can make the appropriate changes. Alternatively I can make a more robust warning in the init or class description about it being wrong. Which would you prefer?
comment:33 in reply to: ↑ 32 Changed 9 years ago by
Replying to tscrim:
I left it there in case someone was relying on that behavior as I thought the agreement was to just deprecate the functionality. However I have no problem completely ignoring it and can make the appropriate changes. Alternatively I can make a more robust warning in the init or class description about it being wrong. Which would you prefer?
I'd prefer that if the user puts in something mathematically wrong, then he should be getting an error. But you're writing the patch, so you decide. I will finish my review as soon as I have your decision...
comment:34 Changed 9 years ago by
I've uploaded the new patch which ignores the vertex_set
option. Thanks for the review.
comment:35 Changed 9 years ago by
- Dependencies changed from #13244 #13590 to #13244 #13590 #13226
Rebased off of #13226.
Changed 9 years ago by
comment:36 Changed 9 years ago by
- Dependencies #13244 #13590 #13226 deleted
Changed 9 years ago by
comment:37 follow-up: ↓ 38 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:38 in reply to: ↑ 37 Changed 9 years ago by
Replying to stumpc5:
Everything looks good to me now -- I fixed a typo and a missing remove of the vertex_set, plus two doc strings.
So: I give it a positive review!
comment:39 Changed 9 years ago by
Thank you for the review.
comment:40 follow-up: ↓ 43 Changed 9 years ago by
- Status changed from positive_review to needs_work
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.
comment:41 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:42 Changed 9 years ago by
- Reviewers changed from Christian Stump to Christian Stump, John Palmieri
- Status changed from needs_review to positive_review
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.
comment:43 in reply to: ↑ 40 ; follow-up: ↓ 44 Changed 9 years ago by
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
comment:44 in reply to: ↑ 43 ; follow-up: ↓ 45 Changed 9 years ago by
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
).
comment:45 in reply to: ↑ 44 Changed 9 years ago by
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 thensage --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!
comment:46 Changed 9 years ago by
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 #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...
comment:47 Changed 9 years ago by
- Milestone changed from sage-5.5 to sage-5.6
Changed 9 years ago by
comment:48 Changed 9 years ago by
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.
comment:49 Changed 9 years ago by
(See also #13769, which fixes optional doctests for interfaces/chomp.py
when CHomP is installed.)
comment:50 Changed 9 years ago by
- Dependencies set to #13226, #13244, #13590
comment:51 Changed 9 years ago by
- Merged in set to sage-5.6.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:52 Changed 9 years ago by
- Cc sage-combinat added
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.