Sage: Ticket #15322: Testing for antichains and chains in arbitrary posets
https://trac.sagemath.org/ticket/15322
<p>
<code>sage/combinat/posets.py</code> currently has an <code>is_chain</code> 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.
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15322/trac_15322-chains-and-antichains-dg.patch" title="Attachment 'trac_15322-chains-and-antichains-dg.patch' in Ticket #15322">trac_15322-chains-and-antichains-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15322/trac_15322-chains-and-antichains-dg.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15322/trac_15322-some-edits-dg.patch" title="Attachment 'trac_15322-some-edits-dg.patch' in Ticket #15322">trac_15322-some-edits-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15322/trac_15322-some-edits-dg.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15322
Trac 1.2Darij GrinbergFri, 25 Oct 2013 01:31:27 GMTstatus changed
https://trac.sagemath.org/ticket/15322#comment:1
https://trac.sagemath.org/ticket/15322#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketDarij GrinbergFri, 25 Oct 2013 01:32:40 GMTattachment set
https://trac.sagemath.org/ticket/15322
https://trac.sagemath.org/ticket/15322
<ul>
<li><strong>attachment</strong>
set to <em>trac_15322-chains-and-antichains-dg.patch</em>
</li>
</ul>
TicketNathann CohenFri, 25 Oct 2013 09:20:50 GMT
https://trac.sagemath.org/ticket/15322#comment:2
https://trac.sagemath.org/ticket/15322#comment:2
<p>
Hellooooooo !
</p>
<p>
Is there any reason why <code>_element_to_vertex</code> should represent a linear extension of <code>P</code> ?
</p>
<p>
Nathann
</p>
TicketDarij GrinbergFri, 25 Oct 2013 13:29:16 GMT
https://trac.sagemath.org/ticket/15322#comment:3
https://trac.sagemath.org/ticket/15322#comment:3
<p>
Hi Nathannnnnn,
</p>
<p>
I remember asking myself the same question, but this is explicitly claimed in some docstring (either <code>sage/combinat/posets/posets.py</code> or <code>sage/combinat/posets/hasse_diagram.py</code>).
</p>
<p>
Darij
</p>
TicketNathann CohenSat, 26 Oct 2013 08:55:02 GMTcc changed
https://trac.sagemath.org/ticket/15322#comment:4
https://trac.sagemath.org/ticket/15322#comment:4
<ul>
<li><strong>cc</strong>
<em>Nicolas M. Thiéry</em> added
</li>
</ul>
<p>
Well, then if you insist on this <code>is_chain_of_poset</code> instead of <code>is_chain</code> and as <code>_element_to_vertex</code> can be assumed to be a linear extension, this patch looks right. What would you think of removing the second implementation of <code>is_chain_of_posets</code> 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.
</p>
<p>
The "ordered" version would be the same, and then you could just check for the existence of this <code>._element_to_vertex</code> attribute. Would it also be possible to add a comment like <code># _element_to_vertex can be assumed to be a linear extension of the poset</code> just before the call to <code>sorted</code> ? I really wondered what was going on before remembering that this may be the case <code>:-)</code>
</p>
<p>
Oh, and also : you use <code>Poset.le</code> from time to time, and the docstring seem to indicate that it should be a <code>Poset.lt</code>. Plus in <code>is_antichain_of_poset</code> you copy some part of the list in the second loop (so manyyy many times) while you actually test <code>.gt</code> AND <code>.lt</code>.
</p>
<p>
This could be rewritten, I think more efficiently as :
</p>
<pre class="wiki">return all(not self.lt(x,y) for x in o for y in o)
</pre><p>
....
AND BY THE WAY (angry voice, right after wondering how <code>Poset.gt</code> was implemented)
</p>
<p>
it looks like <code>Poset.lt</code> and <code>Poset.gt</code> actually call <code>Poset.compare_elements</code>. And the code of <code>Poset.compare_elements</code> first checks if <code>x<y</code> THEN if <code>x>y</code>.
</p>
<p>
As a result : any call to <code>.gt</code> or to <code>.lt</code> totally determines the relationship between the two elements, and computing both <code>.lt</code> and <code>.gt</code> actually computes TWICE whether the two elements are incomparable. As they both call <code>.compare_elements</code>. 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.
</p>
<p>
Hence with the current implementation you should only call <code>.compare_elements()</code> directly and use the full information it returns (as <code>.lt</code> and <code>.gt</code> do the same and ignore some part of this information).
</p>
<p>
And these <code>.gt</code> and <code>.lt</code> functions will have to be patches eventually to compute ONLY what they are asked to, and not twice as much.
</p>
<p>
Nathann
</p>
TicketDarij GrinbergSat, 26 Oct 2013 16:54:35 GMT
https://trac.sagemath.org/ticket/15322#comment:5
https://trac.sagemath.org/ticket/15322#comment:5
<p>
Hi Nathann,
</p>
<p>
very good observation about the docstring indicating <code>lt</code> instead of <code>le</code>. 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 <code>_element_to_vertex</code> and added your improvement to the antichain code.
</p>
<p>
I don't understand the issue with calling <code>compare_elements</code> (what file is that in?) and anyway the <code>compare_elements</code> method seems to exist only for finite posets. I have not merged the two <code>is_chain_of_poset</code> methods so far because IMHO using overshadowing by inheritance is nicer than <code>getattr</code> (and probably faster?).
</p>
<p>
for the <strong>patchbots</strong>
</p>
<p>
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
</p>
<p>
for the <strong>patchbot</strong>
</p>
<p>
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
</p>
<p>
for the <strong>patchbots</strong>:
</p>
<p>
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
</p>
<p>
for the <strong>patchbot</strong>:
</p>
<p>
apply trac_15322-chains-and-antichains-dg.patch trac_15322-some-edits-dg.patch
</p>
TicketNathann CohenSat, 26 Oct 2013 19:52:58 GMT
https://trac.sagemath.org/ticket/15322#comment:6
https://trac.sagemath.org/ticket/15322#comment:6
<p>
Hellooooooooo !!
</p>
<blockquote class="citation">
<p>
very good observation about the docstring indicating <code>lt</code> instead of <code>le</code>. 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 <code>_element_to_vertex</code> and added your improvement to the antichain code.
</p>
</blockquote>
<p>
Thaaaaaaaanks !
</p>
<blockquote class="citation">
<p>
I don't understand the issue with calling <code>compare_elements</code> (what file is that in?) and anyway the <code>compare_elements</code> method seems to exist only for finite posets.
</p>
</blockquote>
<p>
Indeed, indeed. Well, I just typed
</p>
<pre class="wiki">sage: P = Poset(); P.compare_elements
</pre><p>
And the problem is that when you just want to know <code>Poset.lt(x,y)</code> it also computes <code>Poset.gt(x,y)</code> 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.
</p>
<blockquote class="citation">
<p>
I have not merged the two <code>is_chain_of_poset</code> methods so far because IMHO using overshadowing by inheritance is nicer than <code>getattr</code> (and probably faster?).
</p>
</blockquote>
<p>
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.
</p>
<p>
I'll go check my pasta then give your new patch a final look !
</p>
<p>
Nathann
</p>
TicketNathann CohenSat, 26 Oct 2013 20:48:04 GMT
https://trac.sagemath.org/ticket/15322#comment:7
https://trac.sagemath.org/ticket/15322#comment:7
<p>
Ahem. Sorry but there is still something to add : this patch depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/15283" title="#15283: enhancement: Rowmotion and Panyushev orbits: iterators for orbits and better doc (closed: fixed)">#15283</a> and so it would be a pity to not call <code>is_antichain</code> from there.
</p>
<p>
Aaaaaaand that will be the end. Sorry for the slow review <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketDarij GrinbergSat, 26 Oct 2013 20:59:47 GMTattachment set
https://trac.sagemath.org/ticket/15322
https://trac.sagemath.org/ticket/15322
<ul>
<li><strong>attachment</strong>
set to <em>trac_15322-some-edits-dg.patch</em>
</li>
</ul>
TicketDarij GrinbergSat, 26 Oct 2013 21:01:20 GMTdescription changed
https://trac.sagemath.org/ticket/15322#comment:8
https://trac.sagemath.org/ticket/15322#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15322?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
Hi Nathann,
</p>
<p>
done. I've also done the same to the order ideal checks. Positive review then?
</p>
<p>
Best regards,<br />
Darij
</p>
TicketNathann CohenSat, 26 Oct 2013 21:19:18 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15322#comment:9
https://trac.sagemath.org/ticket/15322#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Yooooooooooo !
</p>
<blockquote class="citation">
<p>
done. I've also done the same to the order ideal checks. Positive review then?
</p>
</blockquote>
<p>
Tests pass, no problem, good to go ! <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketDarij GrinbergSat, 26 Oct 2013 21:19:57 GMTreviewer deleted
https://trac.sagemath.org/ticket/15322#comment:10
https://trac.sagemath.org/ticket/15322#comment:10
<ul>
<li><strong>reviewer</strong>
<em>Nathann Cohen</em> deleted
</li>
</ul>
<p>
Thank youuuuuuuuuuuuu!
</p>
TicketNathann CohenSat, 26 Oct 2013 21:24:37 GMTreviewer set
https://trac.sagemath.org/ticket/15322#comment:11
https://trac.sagemath.org/ticket/15322#comment:11
<ul>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
?... Well I *did* review that patch <code>:-P</code>
</p>
TicketDarij GrinbergSat, 26 Oct 2013 21:26:21 GMT
https://trac.sagemath.org/ticket/15322#comment:12
https://trac.sagemath.org/ticket/15322#comment:12
<p>
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?
</p>
TicketNathann CohenSat, 26 Oct 2013 21:51:19 GMT
https://trac.sagemath.org/ticket/15322#comment:13
https://trac.sagemath.org/ticket/15322#comment:13
<p>
No idea.
</p>
<p>
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<strong></strong> criminal.
</p>
<pre class="wiki">sage: p = Poset(DiGraph({0:[1],2:[1]})); p.show(); print p.is_chain()
True
</pre><p>
Nathann
</p>
TicketJeroen DemeyerWed, 06 Nov 2013 12:49:48 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/15322#comment:14
https://trac.sagemath.org/ticket/15322#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.13.beta3</em>
</li>
</ul>
Ticket