Opened 8 years ago
Closed 3 years ago
#15206 closed task (fixed)
Poset show should accept nonhashable or noninjective element labels
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  combinatorics  Keywords:  combinat, show, plot, posets, days94, sagedays@icerm 
Cc:  jmantysalo, vittucek  Merged in:  
Authors:  Vít Tuček  Reviewers:  Jori Mäntysalo, Darij Grinberg, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  9a81c6d (Commits, GitHub, GitLab)  Commit:  9a81c6df3d6ba3d950e6c566825f20eea41d6577 
Dependencies:  Stopgaps: 
Description (last modified by )
sage: P = Poset({1: [2,3]}) sage: labs = {i: P.rank(i) for i in range(1, 4)} sage: labs {1: 0, 2: 1, 3: 1} sage: P.show(element_labels=labs)  NotImplementedError Traceback (most recent call last) <ipythoninput38dfd00191eb55> in <module>() > 1 P.show(element_labels=labs) /home/darij/sage5.12.beta5/local/lib/python2.7/sitepackages/sage/combinat/posets/posets.pyc in show(self, label_elements, element_labels, vertex_size, vertex_colors, layout, **kwds) 1440 """ 1441 self.plot(label_elements=label_elements, element_labels=element_labels, > 1442 vertex_size=vertex_size, vertex_colors=vertex_colors, layout=layout).show(**kwds) 1443 1444 @combinatorial_map(name="to graph") /home/darij/sage5.12.beta5/local/lib/python2.7/sitepackages/sage/combinat/posets/posets.pyc in plot(self, label_elements, element_labels, vertex_size, vertex_colors, layout, **kwds) 1402 relabelling = dict((self(element), label) 1403 for (element, label) in element_labels.items()) > 1404 graph = graph.relabel(relabelling, inplace = False) 1405 if rank_function: # use the rank function to set the heights 1406 for i in self: /home/darij/sage5.12.beta5/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in relabel(self, perm, inplace, return_map, check_input, complete_partial_function) 16208 return_map= return_map, 16209 check_input = check_input, > 16210 complete_partial_function = complete_partial_function) 16211 16212 if return_map: /home/darij/sage5.12.beta5/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in relabel(self, perm, inplace, return_map, check_input, complete_partial_function) 16263 if check_input: 16264 if len(set(perm.values())) < len(perm): > 16265 raise NotImplementedError("Non injective relabeling") 16266 16267 for v in perm.iterkeys(): NotImplementedError: Non injective relabeling
I understand that this, along with the lack of support for nonhashable labels, is owed to the implementation, but IMHO this means that the implementation (via relabelling the poset before plotting it, rather than as one would expect via doing everything as if the labels weren't there and then introducing them at the very end) is bad. (Incidentally, I'm not even sure that the shape of the image doesn't depend on the labels  in the examples I've checked it seems to not depend on them, but I don't trust the code very much.)
I am not the type of mathematician who gets any enlightenment out of pictures, but even I do need to use show()
when I'm making a presentation. Issues like this harm the presentability of Sage code.
Fixing this would also help with problem when combining vertex_colors
and element_labels
. See for example
Poset({1:[]}).plot(vertex_colors={'red':[1]}, element_labels={1: 2})
Change History (50)
comment:1 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:2 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:3 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:4 Changed 7 years ago by
 Cc jmantysalo added
comment:5 Changed 6 years ago by
 Description modified (diff)
comment:6 Changed 4 years ago by
 Cc vittucek added
comment:7 Changed 3 years ago by
 Branch set to u/vittucek/poset_show_should_accept_non_hashable_or_non_injective_element_labels
comment:8 Changed 3 years ago by
 Commit set to 9421575232da114b3fb936c3e906b65b2dbedcf3
 Keywords days94 added
 Status changed from new to needs_review
comment:9 followup: ↓ 10 Changed 3 years ago by
 Milestone changed from sage6.4 to sage8.3
 Status changed from needs_review to needs_work
comment:10 in reply to: ↑ 9 Changed 3 years ago by
I propose the following as it has saner behaviour:
class ElementWithLabel: """ Auxiliary class for showing Posets with nonijective relabeling. """ def __init__(self, element, label): self.element = element self.label = label def _latex_(self): return latex(self.label) def __str__(self): return str(self.label) def __repr__(self): return repr(self.label) def __hash__(self): return hash((hash(self.element), hash(self.label))) def __eq__(self, other): return self.element == other.element and self.label == other.label
It seems that this could be useful somewhere else as well. Is there some utility module where I could move this?
Replying to tscrim:
I would do this as:
class ElementWithLabel: """ Auxiliary class for showing Posets with nonijective relabeling. """ def __init__(self, element, label): self.element = element self.label = label def _latex_(self): return latex(self.label) def __repr__(self): return repr(self.label) def __hash__(self): return hash(repr(self.label)) ^ hash(repr(self.element))or something like that for the hash. It should not need a
__str__
because of the__repr__
. Typically we userepr
in Sage, but I don't care if that becomes astr
.Also, all methods need doctests.
comment:11 Changed 3 years ago by
That is a better hash, yes. Good catch about the __eq__
, and you should also implement a __ne__
. However, I still disagree about the __str__
as it is overkill:
sage: class Foo(object): ....: def __repr__(self): ....: return "hi" ....: sage: str(Foo()) 'hi' sage: repr(Foo()) 'hi'
comment:12 Changed 3 years ago by
 Commit changed from 9421575232da114b3fb936c3e906b65b2dbedcf3 to 82536307866951ce7ad52705d87660d053952a34
Branch pushed to git repo; I updated commit sha1. New commits:
8253630  add docstrings, equality and hashing

comment:13 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:14 Changed 3 years ago by
 Commit changed from 82536307866951ce7ad52705d87660d053952a34 to ac4607d1a548484d9d8f1860aa743fd51cc2b553
Branch pushed to git repo; I updated commit sha1. New commits:
ac4607d  adds forgotten tests for __ne__

comment:15 Changed 3 years ago by
 Commit changed from ac4607d1a548484d9d8f1860aa743fd51cc2b553 to 98c8fbd43f6477a9690c25afeb51cb46f61a9d05
Branch pushed to git repo; I updated commit sha1. New commits:
98c8fbd  need __str__as well

comment:16 Changed 3 years ago by
It is better (safer) to always do:
sage: from sage.combinat.posets.posets import ElementWithLabel
Your __ne__
is missing a blankline after TESTS::
. Also, I didn't read your proposed hash close enough when you proposed it. I think a better one would be
return hash((repr(self.element), repr(self.label)))
Because your current version would not cover nonhashable labels. You also need to add a test for both of these two cases (nonhashable (e.g., mutable matrices) and noninjective labels).
comment:17 Changed 3 years ago by
 Branch changed from u/vittucek/poset_show_should_accept_non_hashable_or_non_injective_element_labels to public/ticket/15206
 Commit changed from 98c8fbd43f6477a9690c25afeb51cb46f61a9d05 to 30b8d837b95c8709f44a69e4cf810a09992f6968
 Keywords daysICERM2018 added
 Reviewers set to Darij Grinberg
The branch I've just pushed fixes the above, but the following needs to be done:
 check that my two doctests actually look reasonably (I can't launch my png viewer currently);
 similarly modify the graph code (and doctest it too).
New commits:
2848d9a  Merge branch 'u/vittucek/poset_show_should_accept_non_hashable_or_non_injective_element_labels' of git://trac.sagemath.org/sage into label

4ce2829  improve doc

30b8d83  move ElementWithLabel class to sage.misc

comment:18 Changed 3 years ago by
 Commit changed from 30b8d837b95c8709f44a69e4cf810a09992f6968 to 3a013a395193b9c8f442d702accc115b101667fd
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3a013a3  move ElementWithLabel class to sage.misc

comment:19 Changed 3 years ago by
 Commit changed from 3a013a395193b9c8f442d702accc115b101667fd to 00c7ec320aa927bf2fd6064755d36462e642e90e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
00c7ec3  move ElementWithLabel class to sage.misc

comment:20 Changed 3 years ago by
OK, it seems that the graph plot functionality doesn't even allow vertex labels. So it's not urgent. Once the functionality is there, we should be easily able to use the ElementWithLabel? class to make them noninjective.
comment:21 Changed 3 years ago by
 Commit changed from 00c7ec320aa927bf2fd6064755d36462e642e90e to ebac4959372f54f9909bf9fabb6fc195bad230e9
Branch pushed to git repo; I updated commit sha1. New commits:
ebac495  change __hash__ and __eq__

comment:22 Changed 3 years ago by
 Commit changed from ebac4959372f54f9909bf9fabb6fc195bad230e9 to b1e7b37a8e632d46e0612f509be3f0420b31fe19
comment:23 Changed 3 years ago by
 Commit changed from b1e7b37a8e632d46e0612f509be3f0420b31fe19 to 2a10cfcc31afc43c4e3662b97d384c8b4a513749
comment:24 Changed 3 years ago by
comment:25 Changed 3 years ago by
 Keywords sagedays@ICERM added; daysICERM2018 removed
comment:26 Changed 3 years ago by
 Keywords sagedays@icerm added; sagedays@ICERM removed
comment:27 Changed 3 years ago by
LGTM :)
But patchbot is complaining and I don't know why.
comment:28 Changed 3 years ago by
 Commit changed from 2a10cfcc31afc43c4e3662b97d384c8b4a513749 to b107cd1877353d09a321cb3942ef8755fbb3fc51
Branch pushed to git repo; I updated commit sha1. New commits:
b107cd1  Made a test that has a poset with only one linear extension

comment:29 Changed 3 years ago by
 Milestone changed from sage8.3 to sage8.4
 Reviewers changed from Darij Grinberg to Darij Grinberg, Travis Scrimshaw
Two more small things (sorry!). The first is you should make ElementWithLabel
a "newstyle" class (inherit from object
). Second, I thought a little bit more about the __hash__
, the self.element
should be guaranteed to be hashable. So I'm thinking we should just have
def __hash__(self): return hash(self.element)
comment:30 Changed 3 years ago by
 Commit changed from b107cd1877353d09a321cb3942ef8755fbb3fc51 to 5d97480084a9939f2ec07fc2665ef2635501dcbe
Branch pushed to git repo; I updated commit sha1. New commits:
5d97480  make ElementWithLabel new style class

comment:31 Changed 3 years ago by
I have actually run into some caching issues when it was just hash(self.element)
so after discussion with Nicolas and Darij I reverted my patch to the current combinantion of hashes of element and label. I guess the best argument, which iirc came from Darij, is that we might want to have same posets but with different labels and so we need to take labels into account for equality testing and for hashing.
comment:32 Changed 3 years ago by
Since elements are both distinct and hashable since they are used for the vertices, adding the labels does not affect the equality or hashing. I guess since this is meant to be used in a more general setting, we do not have same guarantees on the elements. So this is fine. Just one little more change to simplify the hashing code (which is the "same" as the repr
version):
return hash((hash(self.element), hash(self.label))) +return hash((self.element), self.label))
comment:33 Changed 3 years ago by
Say you want to create a poset with nonijective labels and plot it several times with different options (e.g. cover labels or vertex colors etc). In that case you want to do something like this my_poset.relabel(lambda e: ElementWithLabel(e, my_label(e)))
If we hashed only self.element
it could happen (see e.g. the test case with WeylGroup.bruhat_poset
) that the new relabeled poset would have the same hash as the original poset and that would break things.
comment:34 Changed 3 years ago by
 Commit changed from 5d97480084a9939f2ec07fc2665ef2635501dcbe to 1100f6b1a962e26598ab759511f66b5b3934896f
Branch pushed to git repo; I updated commit sha1. New commits:
1100f6b  simplify hash

comment:35 Changed 3 years ago by
It doesn't matter if the poset has the same hash, it is the equality that matters. It is a problem if and only if they are being considered as equal and getting different hashes. Can you give explicit code that is breaking if two posets are not equal (isomorphic is okay) but have the same hash?
comment:36 Changed 3 years ago by
sage: from sage.misc.element_with_label import ElementWithLabel sage: P1 = Poset({1:[2,3]}) sage: P2 = Poset({ElementWithLabel(1, "a"): [ElementWithLabel(2, "b"), ElementWithLabel(3, "c")]})
With the current implementation (i.e. hash((self.element, self.label))
) this works. If we did just hash(self.element)
then we would get
 AttributeError Traceback (most recent call last) <ipythoninput2974e94a2baaf3> in <module>() > 1 P2 = Poset({ElementWithLabel(Integer(1), "a"): [ElementWithLabel(Integer(2), "b"), ElementWithLabel(Integer(3), "c")]}) /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/combinat/posets/posets.pyc in Poset(data, element_labels, cover_relations, linear_extension, category, facade, key) 745 else: 746 elements = None > 747 return FinitePoset(D, elements=elements, category=category, facade=facade, key=key) 748 749 /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1639)() 327 """ 328 if cls.classcall is not None: > 329 return cls.classcall(cls, *args, **kwds) 330 else: 331 # Fast version of type.__call__(cls, *args, **kwds) /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/combinat/posets/posets.pyc in __classcall__(cls, hasse_diagram, elements, category, facade, key) 964 elements=elements, 965 category=category, facade=facade, > 966 key=key) 967 968 def __init__(self, hasse_diagram, elements, category, facade, key): /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6174)() 998 try: 999 try: > 1000 return self.cache[k] 1001 except TypeError: # k is not hashable 1002 k = dict_key(k) /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/misc/weak_dict.pyx in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (build/cythonized/sage/misc/weak_dict.c:3538)() 704 705 """ > 706 cdef PyObject* wr = PyDict_GetItemWithError(self, k) 707 if wr == NULL: 708 raise KeyError(k) /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/cpython/dict_del_by_value.pyx in sage.cpython.dict_del_by_value.PyDict_GetItemWithError (build/cythonized/sage/cpython/dict_del_by_value.c:1199)() 56 cdef PyDictEntry* ep 57 cdef PyDictObject* mp = <PyDictObject*><void *>op > 58 ep = mp.ma_lookup(mp, <PyObject*><void*>key, PyObject_Hash(key)) 59 if ep: 60 return ep.me_value /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in __eq__(self, other) 588 return False 589 # Vertices > 590 if any(x not in other for x in self): 591 return False 592 # Finally, we are prepared to check edges: /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in <genexpr>((x,)) 588 return False 589 # Vertices > 590 if any(x not in other for x in self): 591 return False 592 # Finally, we are prepared to check edges: /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in has_vertex(self, vertex) 9263 except Exception: 9264 return False > 9265 return self._backend.has_vertex(vertex) 9266 9267 __contains__ = has_vertex /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/graphs/base/static_sparse_backend.pyx in sage.graphs.base.static_sparse_backend.StaticSparseBackend.has_vertex (build/cythonized/sage/graphs/base/static_sparse_backend.c:10628)() 464 False 465 """ > 466 return v in self._vertex_to_int 467 468 def relabel(self, perm, directed): /home/vit/src/sage/local/lib/python2.7/sitepackages/sage/misc/element_with_label.pyc in __eq__(self, other) 147 True 148 """ > 149 return self.element == other.element and self.label == other.label 150 151 def __ne__(self, other): AttributeError: 'int' object has no attribute 'element'
If I remember correctly, what's going on is that the constructor of FinitePoset
looks into cache which has as keys _hasse_diagram
and then it finds the _hasse_diagram
of P1
and just uses that which causes these problems (self
is ElementWithLabel? while other
is int
... or the other way around).
comment:37 followup: ↓ 38 Changed 3 years ago by
The hash space may be large, but I don't like the idea of relying on distinctness of hashes.
comment:38 in reply to: ↑ 37 Changed 3 years ago by
Replying to ghdarijgr:
The hash space may be large, but I don't like the idea of relying on distinctness of hashes.
Cnstructor of Poset
could use some love https://trac.sagemath.org/ticket/23825
comment:39 Changed 3 years ago by
 Branch changed from public/ticket/15206 to public/misc/non_hashable_injective_labels15206
 Commit changed from 1100f6b1a962e26598ab759511f66b5b3934896f to 9b21a674710b710e46830905222b765507b25bee
The problem is not with posets but with the equality check:
sage: from sage.misc.element_with_label import ElementWithLabel sage: 1 == ElementWithLabel(1, 'a') # BOOM
Here is a fix for the __eq__
(which I think is my fault for not caching it earlier as I thought this would only be compared internally). The example now works with the simplified hash.
If my changes are good, then I think we can set a positive review.
New commits:
9b21a67  Fixing __eq__ method and simplifying hash.

comment:40 Changed 3 years ago by
ping?
comment:41 Changed 3 years ago by
 Commit changed from 9b21a674710b710e46830905222b765507b25bee to dc46c1bb90262abb84205364e756a00e88413512
Branch pushed to git repo; I updated commit sha1. New commits:
dc46c1b  fix doctest in __hash__

comment:42 Changed 3 years ago by
Actually, that hash
output is almost certainly different on 32 and 64 bit machines. We probably want to change said test to hash(a) == hash(a.element)
. Also the hash docstring is now incorrect (my fault).
comment:43 Changed 3 years ago by
 Commit changed from dc46c1bb90262abb84205364e756a00e88413512 to 9a81c6df3d6ba3d950e6c566825f20eea41d6577
Branch pushed to git repo; I updated commit sha1. New commits:
9a81c6d  fix docstring and test

comment:44 Changed 3 years ago by
Any idea why patchbot is not green?
comment:45 Changed 3 years ago by
Unrelated failures (you can consider it green).
comment:46 Changed 3 years ago by
Ping? (Now a clearly green patchbot.)
comment:47 Changed 3 years ago by
Seems to be a clear code. I can check this one later today.
comment:48 Changed 3 years ago by
 Reviewers changed from Darij Grinberg, Travis Scrimshaw to Jori Mäntysalo, Darij Grinberg, Travis Scrimshaw
Not sure who should be author and who should be reviewed, but at least the code works.
(Got a headache when comparing vertex_labels
in graphs and elements_labels
in posets, but that's another story.)
comment:49 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:50 Changed 3 years ago by
 Branch changed from public/misc/non_hashable_injective_labels15206 to 9a81c6df3d6ba3d950e6c566825f20eea41d6577
 Resolution set to fixed
 Status changed from positive_review to closed
I would do this as:
or something like that for the hash. It should not need a
__str__
because of the__repr__
. Typically we userepr
in Sage, but I don't care if that becomes astr
.Also, all methods need doctests.