Testing for antichains and chains in arbitrary posets

[Darij Grinberg]

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:

• trac_15322-chains-and-antichains-dg.patch​
• trac_15322-some-edits-dg.patch​

[Nathann Cohen]

Hellooooooo !

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

Nathann

[Darij Grinberg]

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

[Nathann Cohen]

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

[Darij Grinberg]

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​

[Nathann Cohen]

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

[Nathann Cohen]

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

[Darij Grinberg]

Hi Nathann,

done. I've also done the same to the order ideal checks. Positive review then?

Best regards,
Darij

[Nathann Cohen]

Yooooooooooo !

done. I've also done the same to the order ideal checks. Positive review then?

Tests pass, no problem, good to go ! ;-)

Nathann

[Darij Grinberg]

Thank youuuuuuuuuuuuu!

[Nathann Cohen]

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

[Darij Grinberg]

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?

[Nathann Cohen]

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