Opened 8 years ago

Closed 3 years ago

#15206 closed task (fixed)

Poset show should accept non-hashable or non-injective element labels

Reported by: darij Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by jmantysalo)

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)
<ipython-input-38-dfd00191eb55> in <module>()
----> 1 P.show(element_labels=labs)

/home/darij/sage-5.12.beta5/local/lib/python2.7/site-packages/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/sage-5.12.beta5/local/lib/python2.7/site-packages/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/sage-5.12.beta5/local/lib/python2.7/site-packages/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/sage-5.12.beta5/local/lib/python2.7/site-packages/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 non-hashable 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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:4 Changed 7 years ago by jmantysalo

  • Cc jmantysalo added

comment:5 Changed 6 years ago by jmantysalo

  • Description modified (diff)

comment:6 Changed 4 years ago by vittucek

  • Cc vittucek added

comment:7 Changed 3 years ago by vittucek

  • Branch set to u/vittucek/poset_show_should_accept_non_hashable_or_non_injective_element_labels

comment:8 Changed 3 years ago by vittucek

  • Authors set to Vít Tuček
  • Commit set to 9421575232da114b3fb936c3e906b65b2dbedcf3
  • Keywords days94 added
  • Status changed from new to needs_review

comment:9 follow-up: Changed 3 years ago by tscrim

  • Milestone changed from sage-6.4 to sage-8.3
  • Status changed from needs_review to needs_work

I would do this as:

class ElementWithLabel:
    """
    Auxiliary class for showing Posets with non-ijective 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 use repr in Sage, but I don't care if that becomes a str.

Also, all methods need doctests.

comment:10 in reply to: ↑ 9 Changed 3 years ago by vittucek

I propose the following as it has saner behaviour:

class ElementWithLabel:
    """
    Auxiliary class for showing Posets with non-ijective 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 non-ijective 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 use repr in Sage, but I don't care if that becomes a str.

Also, all methods need doctests.

comment:11 Changed 3 years ago by tscrim

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 git

  • Commit changed from 9421575232da114b3fb936c3e906b65b2dbedcf3 to 82536307866951ce7ad52705d87660d053952a34

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

8253630add docstrings, equality and hashing

comment:13 Changed 3 years ago by vittucek

  • Status changed from needs_work to needs_review

comment:14 Changed 3 years ago by git

  • Commit changed from 82536307866951ce7ad52705d87660d053952a34 to ac4607d1a548484d9d8f1860aa743fd51cc2b553

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

ac4607dadds forgotten tests for __ne__

comment:15 Changed 3 years ago by git

  • Commit changed from ac4607d1a548484d9d8f1860aa743fd51cc2b553 to 98c8fbd43f6477a9690c25afeb51cb46f61a9d05

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

98c8fbdneed __str__as well

comment:16 Changed 3 years ago by tscrim

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 non-hashable labels. You also need to add a test for both of these two cases (non-hashable (e.g., mutable matrices) and non-injective labels).

comment:17 Changed 3 years ago by gh-darijgr

  • 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:

2848d9aMerge branch 'u/vittucek/poset_show_should_accept_non_hashable_or_non_injective_element_labels' of git://trac.sagemath.org/sage into label
4ce2829improve doc
30b8d83move ElementWithLabel class to sage.misc

comment:18 Changed 3 years ago by git

  • Commit changed from 30b8d837b95c8709f44a69e4cf810a09992f6968 to 3a013a395193b9c8f442d702accc115b101667fd

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

3a013a3move ElementWithLabel class to sage.misc

comment:19 Changed 3 years ago by git

  • Commit changed from 3a013a395193b9c8f442d702accc115b101667fd to 00c7ec320aa927bf2fd6064755d36462e642e90e

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

00c7ec3move ElementWithLabel class to sage.misc

comment:20 Changed 3 years ago by gh-darijgr

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 non-injective.

comment:21 Changed 3 years ago by git

  • Commit changed from 00c7ec320aa927bf2fd6064755d36462e642e90e to ebac4959372f54f9909bf9fabb6fc195bad230e9

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

ebac495change __hash__ and __eq__

comment:22 Changed 3 years ago by git

  • Commit changed from ebac4959372f54f9909bf9fabb6fc195bad230e9 to b1e7b37a8e632d46e0612f509be3f0420b31fe19

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

cd855c5Revert "change __hash__ and __eq__"
4d21e16drop unnecessary import
b1e7b37add examples of usage

comment:23 Changed 3 years ago by git

  • Commit changed from b1e7b37a8e632d46e0612f509be3f0420b31fe19 to 2a10cfcc31afc43c4e3662b97d384c8b4a513749

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

f12a6b5Merge branch 'public/ticket/15206' of git://trac.sagemath.org/sage into 15206
2a10cfctrivial doc fix

comment:24 Changed 3 years ago by gh-darijgr

LGTM.

https://pbs.twimg.com/media/DiWsOPgW4AAYTSD.jpg

LGTY?

comment:25 Changed 3 years ago by gh-darijgr

  • Keywords sagedays@ICERM added; daysICERM2018 removed

comment:26 Changed 3 years ago by gh-darijgr

  • Keywords sagedays@icerm added; sagedays@ICERM removed

comment:27 Changed 3 years ago by vittucek

LGTM :)

But patchbot is complaining and I don't know why.

comment:28 Changed 3 years ago by git

  • Commit changed from 2a10cfcc31afc43c4e3662b97d384c8b4a513749 to b107cd1877353d09a321cb3942ef8755fbb3fc51

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

b107cd1Made a test that has a poset with only one linear extension

comment:29 Changed 3 years ago by tscrim

  • Milestone changed from sage-8.3 to sage-8.4
  • Reviewers changed from Darij Grinberg to Darij Grinberg, Travis Scrimshaw

Two more small things (sorry!). The first is you should make ElementWithLabel a "new-style" 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 git

  • Commit changed from b107cd1877353d09a321cb3942ef8755fbb3fc51 to 5d97480084a9939f2ec07fc2665ef2635501dcbe

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

5d97480make ElementWithLabel new style class

comment:31 Changed 3 years ago by vittucek

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 tscrim

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 vittucek

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 git

  • Commit changed from 5d97480084a9939f2ec07fc2665ef2635501dcbe to 1100f6b1a962e26598ab759511f66b5b3934896f

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

1100f6bsimplify hash

comment:35 Changed 3 years ago by tscrim

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 vittucek

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)
<ipython-input-29-74e94a2baaf3> 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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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/site-packages/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 follow-up: Changed 3 years ago by gh-darijgr

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 vittucek

Replying to gh-darijgr:

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 tscrim

  • Branch changed from public/ticket/15206 to public/misc/non_hashable_injective_labels-15206
  • 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:

9b21a67Fixing __eq__ method and simplifying hash.

comment:40 Changed 3 years ago by tscrim

ping?

comment:41 Changed 3 years ago by git

  • Commit changed from 9b21a674710b710e46830905222b765507b25bee to dc46c1bb90262abb84205364e756a00e88413512

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

dc46c1bfix doctest in __hash__

comment:42 Changed 3 years ago by tscrim

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 git

  • Commit changed from dc46c1bb90262abb84205364e756a00e88413512 to 9a81c6df3d6ba3d950e6c566825f20eea41d6577

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

9a81c6dfix docstring and test

comment:44 Changed 3 years ago by vittucek

Any idea why patchbot is not green?

comment:45 Changed 3 years ago by tscrim

Unrelated failures (you can consider it green).

comment:46 Changed 3 years ago by tscrim

Ping? (Now a clearly green patchbot.)

comment:47 Changed 3 years ago by jmantysalo

Seems to be a clear code. I can check this one later today.

comment:48 Changed 3 years ago by jmantysalo

  • 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 jmantysalo

  • Status changed from needs_review to positive_review

comment:50 Changed 3 years ago by vbraun

  • Branch changed from public/misc/non_hashable_injective_labels-15206 to 9a81c6df3d6ba3d950e6c566825f20eea41d6577
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.