Opened 8 years ago

Closed 8 years ago

#15322 closed enhancement (fixed)

Testing for antichains and chains in arbitrary posets

Reported by: darij Owned by:
Priority: major Milestone: sage-5.13
Component: combinatorics Keywords: posets, combinat, categories
Cc: nbruin, tscrim, ncohen, sage-combinat, nthiery Merged in: sage-5.13.beta3
Authors: Darij Grinberg Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #15283 Stopgaps:

Status badges

Description (last modified by darij)

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)

trac_15322-chains-and-antichains-dg.patch (11.8 KB) - added by darij 8 years ago.
trac_15322-some-edits-dg.patch (5.3 KB) - added by darij 8 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 8 years ago by darij

  • Status changed from new to needs_review

Changed 8 years ago by darij

comment:2 Changed 8 years ago by ncohen

Hellooooooo !

Is there any reason why _element_to_vertex should represent a linear extension of P ?

Nathann

comment:3 Changed 8 years ago by darij

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 8 years ago by ncohen

  • Cc nthiery 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: Changed 8 years ago by darij

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 in reply to: ↑ 5 Changed 8 years ago by ncohen

Hellooooooooo !!

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.

Thaaaaaaaanks !

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.

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 than getattr (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 8 years ago by ncohen

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 8 years ago by darij

comment:8 follow-up: Changed 8 years ago by darij

  • 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 in reply to: ↑ 8 Changed 8 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to 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:10 Changed 8 years ago by darij

  • Reviewers Nathann Cohen deleted

Thank youuuuuuuuuuuuu!

comment:11 Changed 8 years ago by ncohen

  • Reviewers set to Nathann Cohen

?... Well I *did* review that patch :-P

comment:12 Changed 8 years ago by darij

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 8 years ago by ncohen

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 8 years ago by jdemeyer

  • Merged in set to sage-5.13.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.