Opened 9 years ago
Closed 9 years ago
#15322 closed enhancement (fixed)
Testing for antichains and chains in arbitrary posets
Reported by: | Darij Grinberg | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | combinatorics | Keywords: | posets, combinat, categories |
Cc: | Nils Bruin, Travis Scrimshaw, Nathann Cohen, Sage Combinat CC user, Nicolas M. Thiéry | Merged in: | sage-5.13.beta3 |
Authors: | Darij Grinberg | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #15283 | Stopgaps: |
Description (last modified by )
sage/combinat/posets.py
currently has an is_chain
method testing whether a poset is a chain, but there is no method to test if a subset of a poset is a chain; moreover, no comparable functionality for antichains exists. The present patch implements this functionality. Chain testing is implemented twice, once for finite and once for arbitrary posets.
Apply:
Attachments (2)
Change History (16)
comment:1 Changed 9 years ago by
Status: | new → needs_review |
---|
Changed 9 years ago by
Attachment: | trac_15322-chains-and-antichains-dg.patch added |
---|
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
Hi Nathannnnnn,
I remember asking myself the same question, but this is explicitly claimed in some docstring (either sage/combinat/posets/posets.py
or sage/combinat/posets/hasse_diagram.py
).
Darij
comment:4 Changed 9 years ago by
Cc: | Nicolas M. Thiéry added |
---|
Well, then if you insist on this is_chain_of_poset
instead of is_chain
and as _element_to_vertex
can be assumed to be a linear extension, this patch looks right. What would you think of removing the second implementation of is_chain_of_posets
and merge it with the first one though ? The docstrings are mostly similar, the documentation too. It would be cool not to have copies of those.
The "ordered" version would be the same, and then you could just check for the existence of this ._element_to_vertex
attribute. Would it also be possible to add a comment like # _element_to_vertex can be assumed to be a linear extension of the poset
just before the call to sorted
? I really wondered what was going on before remembering that this may be the case :-)
Oh, and also : you use Poset.le
from time to time, and the docstring seem to indicate that it should be a Poset.lt
. Plus in is_antichain_of_poset
you copy some part of the list in the second loop (so manyyy many times) while you actually test .gt
AND .lt
.
This could be rewritten, I think more efficiently as :
return all(not self.lt(x,y) for x in o for y in o)
....
AND BY THE WAY (angry voice, right after wondering how Poset.gt
was implemented)
it looks like Poset.lt
and Poset.gt
actually call Poset.compare_elements
. And the code of Poset.compare_elements
first checks if x<y
THEN if x>y
.
As a result : any call to .gt
or to .lt
totally determines the relationship between the two elements, and computing both .lt
and .gt
actually computes TWICE whether the two elements are incomparable. As they both call .compare_elements
. When you compute if one is smaller than the other Sage also wonder if it is not the opposite, or whether they are incomparable. Only nobody asked it to.
Hence with the current implementation you should only call .compare_elements()
directly and use the full information it returns (as .lt
and .gt
do the same and ignore some part of this information).
And these .gt
and .lt
functions will have to be patches eventually to compute ONLY what they are asked to, and not twice as much.
Nathann
comment:5 follow-up: 6 Changed 9 years ago by
Hi Nathann,
very good observation about the docstring indicating lt
instead of le
. I've changed this now (in the ordered version; the unordered one is right because it only refers to the set). Also I've added a comment on _element_to_vertex
and added your improvement to the antichain code.
I don't understand the issue with calling compare_elements
(what file is that in?) and anyway the compare_elements
method seems to exist only for finite posets. I have not merged the two is_chain_of_poset
methods so far because IMHO using overshadowing by inheritance is nicer than getattr
(and probably faster?).
for the patchbots
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
for the patchbot
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
for the patchbots:
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
for the patchbot:
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
comment:6 Changed 9 years ago by
Hellooooooooo !!
very good observation about the docstring indicating
lt
instead ofle
. I've changed this now (in the ordered version; the unordered one is right because it only refers to the set). Also I've added a comment on_element_to_vertex
and added your improvement to the antichain code.
Thaaaaaaaanks !
I don't understand the issue with calling
compare_elements
(what file is that in?) and anyway thecompare_elements
method seems to exist only for finite posets.
Indeed, indeed. Well, I just typed
sage: P = Poset(); P.compare_elements
And the problem is that when you just want to know Poset.lt(x,y)
it also computes Poset.gt(x,y)
and though I'm totally willing to think of how graphs could be improved so that Posets get faster, if the Poset code is that not-optimized I'm just working for nothing. I'll write a patch for that.
I have not merged the two
is_chain_of_poset
methods so far because IMHO using overshadowing by inheritance is nicer thangetattr
(and probably faster?).
Hmmmmm... Okay. It's just that the docstring is 99% of that function's code, and that it ends up being copied as a result.
I'll go check my pasta then give your new patch a final look !
Nathann
comment:7 Changed 9 years ago by
Ahem. Sorry but there is still something to add : this patch depends on #15283 and so it would be a pity to not call is_antichain
from there.
Aaaaaaand that will be the end. Sorry for the slow review :-P
Nathann
Changed 9 years ago by
Attachment: | trac_15322-some-edits-dg.patch added |
---|
comment:8 follow-up: 9 Changed 9 years ago by
Description: | modified (diff) |
---|
Hi Nathann,
done. I've also done the same to the order ideal checks. Positive review then?
Best regards,
Darij
comment:9 Changed 9 years ago by
Reviewers: | → Nathann Cohen |
---|---|
Status: | needs_review → positive_review |
Yooooooooooo !
done. I've also done the same to the order ideal checks. Positive review then?
Tests pass, no problem, good to go ! ;-)
Nathann
comment:11 Changed 9 years ago by
Reviewers: | → Nathann Cohen |
---|
?... Well I *did* review that patch :-P
comment:12 Changed 9 years ago by
WTF, how did that come? Oh, I see -- I posted my comment using an obsolete form (had this ticket open in my browser before you set yourself to reviewer). Sorry. Is there a place to report trac bugs?
comment:13 Changed 9 years ago by
No idea.
I am about to commit murder though. I am writing this patch to not compute twice what you need when comparing elements of a poset and I read code which is so WRONG it's f criminal.
sage: p = Poset(DiGraph({0:[1],2:[1]})); p.show(); print p.is_chain() True
Nathann
comment:14 Changed 9 years ago by
Merged in: | → sage-5.13.beta3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Hellooooooo !
Is there any reason why
_element_to_vertex
should represent a linear extension ofP
?Nathann