Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#5280 closed defect (fixed)

[with patch, positive review] problem with a subposet coming from an order_filter

Reported by: jhpalmieri Owned by: somebody
Priority: minor Milestone: sage-4.1
Component: combinatorics Keywords:
Cc: sage-combinat Merged in: sage-4.1.alpha0
Authors: Franco Saliola Reviewers: Mike Hansen, Robert Miller
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

With sage-3.3.rc0:

sage: B = BooleanLattice(3)
sage: 4 in B
True
sage: B.principal_order_filter(4)  # all elements >= 4
[4, 5, 6, 7]
sage: B.subposet(B.principal_order_filter(4))
Finite poset containing 4 elements
sage: show(B.subposet(B.principal_order_filter(4)))
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
NotImplementedError: BUG: sort algorithm for elements of 'Finite lattice containing 8 elements' not implemented

I get the same problem with 'order_filter' instead of 'principal_order_filter', and also for 'order_ideal' (e.g., show(B.subposet(B.order_ideal([2, 4]))) produces a similar message). Note, though, that show(B.subposet(B.principal_order_ideal(4))) works just fine.

Attachments (4)

trac_5280.patch (5.4 KB) - added by saliola 13 years ago.
trac_5280-review.patch (1021 bytes) - added by mhansen 13 years ago.
trac_5280-ne-docfixes.patch (2.5 KB) - added by saliola 13 years ago.
Apply on top of the previous two.
trac_5280-switch-to-zero.patch (1.6 KB) - added by saliola 13 years ago.
Apply on top of the previous three

Download all attachments as: .zip

Change History (23)

comment:1 Changed 13 years ago by nthiery

  • Cc sage-combinat added

Changed 13 years ago by saliola

comment:2 Changed 13 years ago by saliola

I implemented __cmp__ for poset elements, which deals with these problems.

The patch depends on #5918.

comment:3 Changed 13 years ago by saliola

  • Summary changed from problem with a subposet coming from an order_filter to [with patch; needs review] problem with a subposet coming from an order_filter

comment:4 Changed 13 years ago by jhpalmieri

This fixes the problem, and all tests pass. I'd like to give this a positive review since I reported the original problem, but I'm not familiar enough with the posets code to evaluate all of the changes here. Can anyone else help out?

comment:5 follow-up: Changed 13 years ago by rlm

  • Summary changed from [with patch; needs review] problem with a subposet coming from an order_filter to [with patch; needs work] problem with a subposet coming from an order_filter

I'd also give this a positive review, but I have to ask: why is __cmp__ returning 1 (cmp(a,b)==1 indicates a < b) when elements are incomparable? Shouldn't it be raising an error instead?

Changed 13 years ago by mhansen

comment:6 Changed 13 years ago by mhansen

  • Summary changed from [with patch; needs work] problem with a subposet coming from an order_filter to [with patch, positive review] problem with a subposet coming from an order_filter

I've added a patch which fixes some doc formatting.

comment:7 Changed 13 years ago by mhansen

  • Authors set to Franco Saliola

comment:8 in reply to: ↑ 5 Changed 13 years ago by rlm

mhansen, care to at least comment why this doesn't concern you?:

Replying to rlm:

Why is __cmp__ returning 1 when elements are incomparable? Shouldn't it be raising an error instead?

comment:9 Changed 13 years ago by saliola

Replying to rlm:

Why is __cmp__ returning 1 when elements are incomparable? Shouldn't it be raising an error instead?

Here are a couple of reasons why it shouldn't.

(1) __cmp__ should never raise an error, otherwise you won't be able to sort a list of elements:

sage: class C(object):
...       def __cmp__(self, other):
...           raise ValueError, 'elements are incomparable'

sage: sorted([C(), C()])
------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython console>", line 1, in <module>
  File "<ipython console>", line 3, in __cmp__
ValueError: elements are incomparable

(2) All the rich comparisons have been implemented for PosetElement, so x<y is handled by x.__lt__(y). That is, the answer will be correct.

So you might wonder why __cmp__ even needs to be implemented. Shouldn't cmp just use the rich comparison methods to determine its value?

In theory, yes. But PosetElement inherits from Element, which defines __cmp__. It seems to be that since __cmp__ is not the default implementation (object.__cmp__), the cmp function ignores all the rich comparison operations and calls __cmp__ directly. See the following example, which was adapted from http://docs.sympy.org/_sources/python-comparisons.txt.

sage: class C_without_cmp(SageObject):
...       def __init__(self, a):
...           self.a = a
...       def __repr__(self):
...           return str(self.a)
...       def __eq__(self, o):
...           print "%s.__eq__(%s)" % (self.a, o.a)
...           return NotImplemented
...       def __ne__(self, o):
...           print "%s.__ne__(%s)" % (self.a, o.a)
...           return NotImplemented
...       def __lt__(self, o):
...           print "%s.__lt__(%s)" % (self.a, o.a)
...           return NotImplemented
...       def __le__(self, o):
...           print "%s.__le__(%s)" % (self.a, o.a)
...           return NotImplemented
...       def __gt__(self, o):
...           print "%s.__gt__(%s)" % (self.a, o.a)
...           return NotImplemented
...       def __ge__(self, o):
...           print "%s.__ge__(%s)" % (self.a, o.a)
...           return NotImplemented

# cmp uses the rich comparison methods if no __cmp__ is found
sage: a = C_without_cmp("a"); b = C_without_cmp("b")
sage: cmp(a,b)
a.__eq__(b)
b.__eq__(a)
b.__eq__(a)
a.__eq__(b)
a.__lt__(b)
b.__gt__(a)
b.__gt__(a)
a.__lt__(b)
a.__gt__(b)
b.__lt__(a)
b.__lt__(a)
a.__gt__(b)
1

sage: class C_with_cmp(C_without_cmp):
...       def __cmp__(self, o):
...           print "%s.__cmp__(%s)" % (self.a, o.a)
...           return NotImplemented

# cmp uses __cmp__, ignoring the rich comparison methods if it is defined
sage: a = C_with_cmp("a"); b = C_with_cmp("b")
sage: cmp(a,b)
a.__cmp__(b)
b.__cmp__(a)
-1

This leads to the following error for posets, which is what this ticket is about.

sage: P = Poset([[1,2],[3],[3],[]])
sage: sorted(P)
[0, 1, 2, 3]
sage: sorted(P, cmp)
------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython console>", line 1, in <module>
  File "element.pyx", line 648, in sage.structure.element.Element.__cmp__ (sage/structure/element.c:6062)
  File "element.pyx", line 561, in sage.structure.element.Element._cmp (sage/structure/element.c:5133)
  File "element.pyx", line 663, in sage.structure.element.Element._cmp_c_impl (sage/structure/element.c:6237)
NotImplementedError: BUG: sort algorithm for elements of 'Finite poset containing 4 elements' not implemented

> /home/saliola/Applications/sage-4.0.2-busted/local/bin/element.pyx(663)sage.structure.element.Element._cmp_c_impl (sage/structure/element.c:6237)()

So I implemented __cmp__ for PosetElement.

Are these satisfactory reasons?

comment:10 follow-ups: Changed 13 years ago by rlm

Franco,

Thanks for the incredibly detailed explanation! The main reason I was asking is that there is no indication why this is okay in the code itself. Could you put a sentence or two, maybe just in a comment, explaining why this is done? Maybe something like "When the user asks for a<b, rich comparison is used, and this is implemented only to enable sorting." Also, if the result of sorting isn't consistent (e.g. cmp(a,b) == cmp(b,a)), this should be mentioned too, I think.

comment:11 in reply to: ↑ 10 Changed 13 years ago by saliola

Replying to rlm:

Franco,

Thanks for the incredibly detailed explanation! The main reason I was asking is that there is no indication why this is okay in the code itself. Could you put a sentence or two, maybe just in a comment, explaining why this is done? Maybe something like "When the user asks for a<b, rich comparison is used, and this is implemented only to enable sorting." Also, if the result of sorting isn't consistent (e.g. cmp(a,b) == cmp(b,a)), this should be mentioned too, I think.

I'm attaching a patch with the docfixes, and that also implements the __ne__ method, which I must have forgot to define. (Unfortunately, in Python __ne__ does not default to !__eq__.)

Changed 13 years ago by saliola

Apply on top of the previous two.

comment:12 Changed 13 years ago by saliola

  • Summary changed from [with patch, positive review] problem with a subposet coming from an order_filter to [with patch, needs review] problem with a subposet coming from an order_filter

comment:13 Changed 13 years ago by rlm

  • Reviewers set to Mike Hansen, Robert Miller
  • Summary changed from [with patch, needs review] problem with a subposet coming from an order_filter to [with patch, positive review] problem with a subposet coming from an order_filter

Looks good, applies and passes tests.

comment:14 in reply to: ↑ 10 ; follow-up: Changed 13 years ago by nthiery

Replying to rlm:

Franco,

Thanks for the incredibly detailed explanation! The main reason I was asking is that there is no indication why this is okay in the code itself. Could you put a sentence or two, maybe just in a comment, explaining why this is done? Maybe something like "When the user asks for a<b, rich comparison is used, and this is implemented only to enable sorting." Also, if the result of sorting isn't consistent (e.g. cmp(a,b) == cmp(b,a)), this should be mentioned too, I think.

Thanks also! I am having similar problems in several other places. This really should be though of once for all, and a systematic policy should be set up for all occurences of this issue. Actually, it would be best if this could be solved once for all at a higher level (in Element)?

One fine point (which certainly does not jeopardize this patch): I would feel better returning 0 for incomparable elements rather than +1.

Would you mind starting a discussion about this on sage-devel?

comment:15 in reply to: ↑ 14 Changed 13 years ago by saliola

Replying to nthiery:

One fine point (which certainly does not jeopardize this patch): I would feel better returning 0 for incomparable elements rather than +1.

That's fine with me. I just picked one randomly, but 0 is better. I will make the change.

Would you mind starting a discussion about this on sage-devel?

http://groups.google.com/group/sage-devel/browse_thread/thread/44dbe252426c3831

Changed 13 years ago by saliola

Apply on top of the previous three

comment:16 Changed 13 years ago by saliola

  • Summary changed from [with patch, positive review] problem with a subposet coming from an order_filter to [with patch, needs review] problem with a subposet coming from an order_filter

The last change that switches to returning 0 instead of 1 for incomparable elements needs reviewing.

comment:17 Changed 13 years ago by rlm

  • Summary changed from [with patch, needs review] problem with a subposet coming from an order_filter to [with patch, positive review] problem with a subposet coming from an order_filter

Looks good.

comment:18 Changed 13 years ago by rlm

  • Merged in set to sage-4.1.alpha0
  • Resolution set to fixed
  • Status changed from new to closed

comment:19 Changed 13 years ago by rlm

  • Milestone changed from sage-combinat to sage-4.1
Note: See TracTickets for help on using tickets.