Opened 10 years ago
Closed 9 years ago
#12848 closed defect (fixed)
Bug in order_ideal_complement_generators: 'down'
Reported by: | nthiery | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.11 |
Component: | combinatorics | Keywords: | posets, days49 |
Cc: | sage-combinat | Merged in: | sage-5.11.beta3 |
Authors: | Nicolas M. Thiéry, Frédéric Chapoton | Reviewers: | Darij Grinberg, Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The down option is broken in order_ideal_complement_generators due to a glitch:
sage: P = Poset( ( [1,2,3], [ [1,3], [2,3] ] ) ) sage: sage: P.order_ideal_complement_generators([1,2], direction='up') set([3]) sage: P.order_ideal_complement_generators([1,2], direction='down') set([3])
The result should be [] in the later case.
Upcoming patch on the Sage-Combinat queue
Apply:
trac_12848-posets-order_ideal_complement_generators_fix-nt-v2.patch trac_12848-posets-modifications.patch
Attachments (3)
Change History (32)
comment:1 follow-up: ↓ 2 Changed 10 years ago by
comment:2 in reply to: ↑ 1 Changed 10 years ago by
Replying to aschilling:
I am looking at the patch on the sage-combinat queue. The method
+ def upper_set(self, elements, direction='up'): + if direction=='up': + return self.order_filter(elements) + else: + return self.order_ideal(elements)
is missing a doctest.
Ah right. And we need to discuss the name for this method, and use it in order_ideal_complement_generators
comment:3 Changed 9 years ago by
could you please upload the patch here ?
Changed 9 years ago by
comment:4 follow-up: ↓ 5 Changed 9 years ago by
Here is a modified patch, that should pass all tests and is fully documented.
There is an annoying issue with the names of the methods "upper_ideal", "lower_ideal", "order_ideal", "order_filter"
comment:5 in reply to: ↑ 4 Changed 9 years ago by
There is an annoying issue with the names of the methods "upper_ideal", "lower_ideal", "order_ideal", "order_filter"
What is the precise issue with the names?
Anne
comment:6 Changed 9 years ago by
Well, the issue is that of "order_ideal" is a synonym for "lower ideal" and "order_filter" is a synonym for "upper_ideal". Before this patch, everywhere one uses "order_ideal" and "order_filter". In my opinion, these are bad names, and "lower ideal" and "upper ideal" are much better.
And, well, I think that "upper set" and "lower set" are very bad too.
In any case, there is still some cleanup to do.
comment:7 Changed 9 years ago by
- Status changed from new to needs_review
ok, here is a new patch, 100% doctest, should pass all tests.
In principle, it should not break anything anywhere.
comment:8 Changed 9 years ago by
- Type changed from PLEASE CHANGE to defect
comment:9 Changed 9 years ago by
The bot has turned green, and the patch is ready for review !
comment:10 Changed 9 years ago by
anybody out there ? maybe it is ready to go ?
comment:11 follow-up: ↓ 12 Changed 9 years ago by
- Description modified (diff)
comment:12 in reply to: ↑ 11 Changed 9 years ago by
Replying to chapoton:
If you put the patch on the sage-combinat queue, I will review it!
comment:13 follow-up: ↓ 14 Changed 9 years ago by
done, the patch is in the queue..
comment:14 in reply to: ↑ 13 Changed 9 years ago by
Hi Frédéric,
Thank you for getting this patch ready for submission!
One small technical issue is that the header of the patch needs to start with #14828: ... description of the patch ... Could you change this?
I am not so happy about the naming conventions that you used. Could you please give me references that use order filter and order ideal? Why don't you like upper set and lower set? That seems like a standard name, see
http://en.wikipedia.org/wiki/Upper_set
Best,
Anne
comment:15 Changed 9 years ago by
Oh, I have not seen your answer, for some reason.
I will take care of the header question soon.
Concerning terminology, it seems that confusion is everywhere, see for instance
http://en.wikipedia.org/wiki/Order_ideal
saying "The terms order ideal, order filter, semi-ideal, down-set and decreasing subset are sometimes used for arbitrary lower or upper sets"
So far, in sage, we have the following definition (in P.order_ideal?)
I is an order ideal if, for any x in I and y such that y <= x, then y is in I.
So I have tried to stick at this convention and not to introduce two competing notations in sage. I do not like upper set and lower set because of the word set, which does not has the idea of closure. I do not like order ideal and order filter because I never remember which one is which. I would like to use upper ideal and lower ideal, but nobody seems to use that. This is rather boring.
comment:16 Changed 9 years ago by
Hi Frederic.
I agree that this naming thing is a pain; which is actually what stopped me from cleaning this earlier. Thanks for pushing it forward ...
order_ideal and order_filter are definitely bad for the reason you mention (which one is up, which one is down). So at least this is settled: we want to move away from those.
upper_set and lower_set has the advantage of being unambiguous and
relatively clear (though I see your point about "closures"). So I
would vote for this. But ... we also would want to be able to pass
upper/lower as argument, and I agree that set(dir="up")
really
does not make sense :-) And
upper_set(dir='down') is not great
either.
I am really not keen with "ideal" because it has two conflicting meanings. But it's been in Sage for a while and we already do ideal(side="left/right") in rings/monoids, so ideal(dir="up/down") is consistent.
Would we have a nice method name for the other definition of ideal (e.g. a upper set such that any meet of two elements is also in it)?
Cheers,
Nicolas
comment:17 follow-up: ↓ 18 Changed 9 years ago by
The other definition of "order filter" is not quite that: it says "an upper set such that any two elements have a common lowest bound in the upper set"
It seems to imply (for finite posets) that it has a unique minimal element, and that this other definition could be called a "principal upper ideal" or "principal upper set".
There are subtle issues for infinite posets, but should we be concerned about that ?
comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 9 years ago by
Replying to chapoton:
The other definition of "order filter" is not quite that: it says "an upper set such that any two elements have a common lowest bound in the upper set"
Oops, you are right; I formulated this to fast.
It seems to imply (for finite posets) that it has a unique minimal element, and that this other definition could be called a "principal upper ideal" or "principal upper set".
Indeed.
There are subtle issues for infinite posets, but should we be concerned about that ?
Not right now. But that will come! So it would be good to know that there exist a plan, even if we don't know right away which plan it should be.
comment:19 in reply to: ↑ 18 Changed 9 years ago by
upper ideal and lower ideal is ok with me if really nobody is using this with another meaning!
Anne
Changed 9 years ago by
comment:20 Changed 9 years ago by
Here is new patch, with correct header.
I have chosen to do the following:
- keep the names "order_ideal" and "order_filter" for backward compatibility
- introduce "upper_set" and "lower_set" as aliases
- use the names "ideal_of_subset" and "ideals_of_subsets" for generic cases
This is clearly not at all coherent. Should we try to reach coherence in this ticket, or should we rather use this ticket to solve the issue that has been raised ?
comment:21 Changed 9 years ago by
"Returns the order ideal in self
generated by
gens
."
Shouldn't that
gens
be
elements
now?
"generaly" generally
comment:22 Changed 9 years ago by
We (Tom, Emma, me) have a couple of suggestions on this patch (which we are working from). What do you think of them? Mainly it changes ideal_of_subset
and ideals_of_subsets
into directed_subset
and directed_subsets
, which IMHO are much less confusing (it's as much ideals as it's filters).
comment:23 Changed 9 years ago by
Yes, it is indeed a better name. I have no time right now to take part in the action, so please do what you want.
comment:24 Changed 9 years ago by
- Status changed from needs_review to needs_work
please correct the failing doctests
comment:25 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:26 Changed 9 years ago by
- Keywords days49 added
- Reviewers set to Darij Grinberg, Anne Schilling
comment:27 follow-up: ↓ 28 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:28 in reply to: ↑ 27 Changed 9 years ago by
Ok, looks good now and the tests pass!
Anne
comment:29 Changed 9 years ago by
- Merged in set to sage-5.11.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
I am looking at the patch on the sage-combinat queue. The method
+ def upper_set(self, elements, direction='up'): + if direction=='up': + return self.order_filter(elements) + else: + return self.order_ideal(elements)
is missing a doctest.