Sage: Ticket #15283: Rowmotion and Panyushev orbits: iterators for orbits and better doc
https://trac.sagemath.org/ticket/15283
<p>
This patch adds documentation to some rowmotion-related methods in <code>sage/categories/posets.py</code> and <code>sage/categories/finite_posets.py</code> and introduces new methods which return iterators over single rowmotion / Panyushev complementation / toggle orbits instead of computing *all* orbits at once and returning them as lists. This allows experimenting with big posets (at least if one can find a way to more or less randomly sample order ideals or antichains).
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15283/trac_15283-rowmotion-dg.patch" title="Attachment 'trac_15283-rowmotion-dg.patch' in Ticket #15283">trac_15283-rowmotion-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15283/trac_15283-rowmotion-dg.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15283
Trac 1.2Darij GrinbergWed, 16 Oct 2013 05:38:17 GMTstatus changed
https://trac.sagemath.org/ticket/15283#comment:1
https://trac.sagemath.org/ticket/15283#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketNathann CohenMon, 21 Oct 2013 13:02:40 GMTstatus changed
https://trac.sagemath.org/ticket/15283#comment:2
https://trac.sagemath.org/ticket/15283#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooooooooooooooooooo !!
</p>
<p>
I read this patch and even though I am not from the field I feel that it could get in. I only have some small remarks to make :
</p>
<ul><li>Could the Poset class need a <code>.is_antichain(vertices=[...])</code> method to check if this set of vertices induces an antichain ? You have a <code>.is_chain()</code> method, but it does not take any argument.
</li><li><code>``panyushev_complement``</code> should be <code>:meth:`panyushev_complement`</code>
</li><li>isn't "generated by the antichain <code>antichain</code>, represented by its generating antichain" slightly redundant ? <code>:-P</code>
</li><li>With my first reading, I understood <code></code>toggling_orbit_iter<code></code> would take a set and a list of points, and return the toggle of the set with the first point, then this new set toggled with the second point, then this new set with the third point, ... I does not make much sense it is true, especially with <code></code>stop=True<code></code>, but if you think somebody from the field could make the same mistake perhaps it could be made clearer <code>:-)</code>
</li></ul><p>
Nathann
</p>
TicketDarij GrinbergMon, 21 Oct 2013 16:09:33 GMT
https://trac.sagemath.org/ticket/15283#comment:3
https://trac.sagemath.org/ticket/15283#comment:3
<p>
Hi Nathannnnn and thanks for the comments!
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15283#comment:2" title="Comment 2">ncohen</a>:
</p>
<blockquote class="citation">
<ul><li>Could the Poset class need a <code>.is_antichain(vertices=[...])</code> method to check if this set of vertices induces an antichain ? You have a <code>.is_chain()</code> method, but it does not take any argument.
</li></ul></blockquote>
<p>
Probably, but I am not sure about adding such methods. <code>.is_chain</code> would have to then be given two meanings, which people might not be happy about.
</p>
<blockquote class="citation">
<ul><li><code>``panyushev_complement``</code> should be <code>:meth:`panyushev_complement`</code>
</li></ul></blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<ul><li>isn't "generated by the antichain <code>antichain</code>, represented by its generating antichain" slightly redundant ? <code>:-P</code>
</li></ul></blockquote>
<p>
I think I've improved this sentence now.
</p>
<blockquote class="citation">
<ul><li>With my first reading, I understood <code></code>toggling_orbit_iter<code></code> would take a set and a list of points, and return the toggle of the set with the first point, then this new set toggled with the second point, then this new set with the third point, ... I does not make much sense it is true, especially with <code></code>stop=True<code></code>, but if you think somebody from the field could make the same mistake perhaps it could be made clearer <code>:-)</code>
</li></ul></blockquote>
<p>
Good point -- added a warning!
</p>
<p>
Since I forgot to qnew, I've made the changes in my old patch rather than adding a new patch. I hope this is fine, and I'll just update the old patch and upload the new changes as a txt file.
</p>
TicketDarij GrinbergMon, 21 Oct 2013 16:10:34 GMTattachment set
https://trac.sagemath.org/ticket/15283
https://trac.sagemath.org/ticket/15283
<ul>
<li><strong>attachment</strong>
set to <em>trac_15283-rowmotion-dg.patch</em>
</li>
</ul>
<p>
revised version
</p>
TicketDarij GrinbergMon, 21 Oct 2013 16:11:23 GMTattachment set
https://trac.sagemath.org/ticket/15283
https://trac.sagemath.org/ticket/15283
<ul>
<li><strong>attachment</strong>
set to <em>newdiff.txt</em>
</li>
</ul>
<p>
differences to the old file. don't apply, just read
</p>
TicketDarij GrinbergMon, 21 Oct 2013 16:13:37 GMTstatus changed
https://trac.sagemath.org/ticket/15283#comment:4
https://trac.sagemath.org/ticket/15283#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketNathann CohenMon, 21 Oct 2013 16:49:47 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15283#comment:5
https://trac.sagemath.org/ticket/15283#comment:5
<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>
Yoooooooooo !
</p>
<blockquote class="citation">
<p>
Probably, but I am not sure about adding such methods. <code>.is_chain</code> would have to then be given two meanings, which people might not be happy about.
</p>
</blockquote>
<p>
Well, the meaning of <code>is_chain</code> stays the same when used without argument, and a feature is added. Better than creating a <code>is_chain_subset</code> method to do the very same, and if people often check whether a set is a chain or an antichain, it can be useful.
</p>
<blockquote class="citation">
<p>
Since I forgot to qnew, I've made the changes in my old patch rather than adding a new patch. I hope this is fine, and I'll just update the old patch and upload the new changes as a txt file.
</p>
</blockquote>
<p>
No prob ! Good to go <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketDarij GrinbergMon, 21 Oct 2013 16:54:42 GMT
https://trac.sagemath.org/ticket/15283#comment:6
https://trac.sagemath.org/ticket/15283#comment:6
<p>
The other problem is that it's not clear whether <code>[6, 3]</code> should be a chain of the poset <code>divisors(6)</code> with divisibility order. Sometimes chains defined as comparable subsets (hence yes), sometimes as actual ordered lists (then no). I fear this method will be harder to use than to rewrite for most users...
</p>
TicketNathann CohenTue, 22 Oct 2013 08:21:32 GMT
https://trac.sagemath.org/ticket/15283#comment:7
https://trac.sagemath.org/ticket/15283#comment:7
<p>
Right. Now that I think of it, though, it can be implemented better :
</p>
<ul><li>Check that an ordered list is indeed a chain : only <code>n-1</code> comparisons
</li><li>Check that a set is indeed a chain : quicksort using <code>n log(n)</code> comparisons, then check if the (ordered) result makes sense with <code>n-1</code> comparisons.
</li></ul><p>
Anyway, if this function is useful at some point it can still be implemented in a <code>.is_chain</code> method with a <code>vertices=[...]</code> argument (possibly equal to <code>None</code> to mean "self") and a <code>ordered=True</code> parameter for this second problem <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketDarij GrinbergWed, 23 Oct 2013 14:16:33 GMTattachment set
https://trac.sagemath.org/ticket/15283
https://trac.sagemath.org/ticket/15283
<ul>
<li><strong>attachment</strong>
set to <em>trac_15283-additions-dg.patch</em>
</li>
</ul>
TicketDarij GrinbergWed, 23 Oct 2013 14:17:36 GMT
https://trac.sagemath.org/ticket/15283#comment:8
https://trac.sagemath.org/ticket/15283#comment:8
<p>
Hi Nathann,
</p>
<p>
I've uploaded an additional patch for this. It disappointingly required some <code>__cmp__</code> hackery, so please check it and tell me if that could have been done in a nicer way.
</p>
<p>
Best regards,<br />
Darij
</p>
TicketNathann CohenWed, 23 Oct 2013 14:34:51 GMT
https://trac.sagemath.org/ticket/15283#comment:9
https://trac.sagemath.org/ticket/15283#comment:9
<p>
Hellooooo again !
</p>
<p>
Hmmmm... I don't get why you needed this hack, actually. What's wrong with the following ?
</p>
<p>
<code>sorted_o = sorted(o, cmp=self.lt)</code>
</p>
<p>
If the set is a chain then it behaves exactly as a quicksort, and otherwise <code>.lt</code> will answer "no" from time to time -- but who cares, you will find this out in the terminal check :
</p>
<p>
<code>all(self.lt(x[i],x[i+1]) for i in range(len(o))-1)</code>
</p>
<p>
And I still believe that this would be better in side of <code>Poset.is_chain()</code> <code>:-P</code>
</p>
<p>
Aaaaaaand Nicolas did not think that it would be a problem but well... That's up to you <code>:-P</code>
</p>
<p>
Have fuuuuuuuuuuuuuuuuuuuuuun !
</p>
<p>
Nathann
</p>
TicketDarij GrinbergWed, 23 Oct 2013 14:49:32 GMT
https://trac.sagemath.org/ticket/15283#comment:10
https://trac.sagemath.org/ticket/15283#comment:10
<p>
I don't think <code>self.lt</code> returns the right format for <code>sorted</code>. It seems that the <code>cmp</code> keyword of <code>sorted</code> wants a total -1,0,1-valued function, not a boolean one. See how this prints the same list twice:
</p>
<pre class="wiki">P = Poset({i: divisors(i) for i in divisors(24)})
print sorted(list(P), cmp=P.lt)
print sorted(list(P), cmp=P.gt)
</pre><p>
And either way, I don't know how <code>sorted</code> would react if <code>cmp</code> fails to be antisymmetric, i. e., if there are two distinct elements which compare as equal or each smaller than the other. I'd hope the result would still be sorted, but who knows? Why is there no good doc for <code>sorted</code>??
</p>
<p>
I originally wanted to implement these functions as semantics for <code>is_chain</code> and <code>is_antichain</code>, but found that this would make the docstring rather confusing.
</p>
TicketJeroen DemeyerWed, 23 Oct 2013 16:03:56 GMTstatus changed
https://trac.sagemath.org/ticket/15283#comment:11
https://trac.sagemath.org/ticket/15283#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Which patch(es) should be applied? Please check that the patches apply to sage-5.13.beta1.
</p>
TicketNathann CohenWed, 23 Oct 2013 16:16:33 GMT
https://trac.sagemath.org/ticket/15283#comment:12
https://trac.sagemath.org/ticket/15283#comment:12
<blockquote class="citation">
<p>
I don't think <code>self.lt</code> returns the right format for <code>sorted</code>. It seems that the <code>cmp</code> keyword of <code>sorted</code> wants a total -1,0,1-valued function, not a boolean one.
</p>
</blockquote>
<p>
Well. If you insist on that, I can make it <code>lambda x,y : 2*self.lt(x,y)-1</code> <code>:-P</code>
</p>
<blockquote class="citation">
<p>
I originally wanted to implement these functions as semantics for <code>is_chain</code> and <code>is_antichain</code>, but found that this would make the docstring rather confusing.
</p>
</blockquote>
<p>
Really ? What do you think of this ?
</p>
<pre class="wiki">def is_chain(verts=None):
Checks whether the Poset (or a specific subset of it) is a chain
INPUT:
- ``verts`` (list of vertices) -- If ``verts`` is ``None`` (default),
the function returns ``True`` if and only if the poset is a chain.
If ``verts`` is a list of points, the function returns ``True`` if
and only if ``verts`` is a chain of the poset.
- ``ordered`` (boolean) -- Whether to consider ``verts`` as a list,
or as a set. If ``ordered`` is set to ``True`` (default), only
checks whether the vertices of ``verts`` are totally ordered in
the poset. If ``ordered`` is set to ``False`` (default), checks
whether these vertices are totally ordered with the ordering
given by the list ``verts``
</pre><p>
Nathann
</p>
TicketNathann CohenWed, 23 Oct 2013 16:17:10 GMT
https://trac.sagemath.org/ticket/15283#comment:13
https://trac.sagemath.org/ticket/15283#comment:13
<p>
Jeroen : the only patch that should be applied is <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15283/trac_15283-rowmotion-dg.patch" title="Attachment 'trac_15283-rowmotion-dg.patch' in Ticket #15283">trac_15283-rowmotion-dg.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15283/trac_15283-rowmotion-dg.patch" title="Download"></a>. The other one is about additional modifications that could be made on another ticket.
</p>
<p>
Nathann
</p>
TicketDarij GrinbergWed, 23 Oct 2013 16:17:27 GMTstatus, description changed
https://trac.sagemath.org/ticket/15283#comment:14
https://trac.sagemath.org/ticket/15283#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15283?action=diff&version=14">diff</a>)
</li>
</ul>
<p>
Oops, I didn't notice that this was positive_review. Thanks, Nathann!
In view of the changes, needs_review is probably more appropriate now.
</p>
<p>
@Jeroen: sorry, I can't tell about beta1, but they do apply on 5.13beta0.
</p>
<p>
for the <strong>patchbots</strong>:
</p>
<p>
apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch
</p>
<p>
for the <strong>patchbot</strong>:
</p>
<p>
apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch
</p>
<p>
for the <strong>patchbots</strong>
</p>
<p>
apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch
</p>
<p>
for the <strong>patchbot</strong>
</p>
<p>
apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch
</p>
<p>
(because I can't remember which syntax is correct).
</p>
TicketDarij GrinbergWed, 23 Oct 2013 16:20:21 GMTstatus, description changed
https://trac.sagemath.org/ticket/15283#comment:15
https://trac.sagemath.org/ticket/15283#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15283?action=diff&version=15">diff</a>)
</li>
</ul>
<p>
OK, Nathann is right, this ticket should be split:
</p>
<p>
for the <strong>patchbots</strong>:
</p>
<p>
apply trac_15283-rowmotion-dg.patch
</p>
<p>
for the <strong>patchbot</strong>:
</p>
<p>
apply trac_15283-rowmotion-dg.patch
</p>
<p>
for the <strong>patchbots</strong>
</p>
<p>
apply trac_15283-rowmotion-dg.patch
</p>
<p>
for the <strong>patchbot</strong>
</p>
<p>
apply trac_15283-rowmotion-dg.patch
</p>
<p>
This can then be set to positive_review since Nathann did review the rowmotion patch.
</p>
TicketNils BruinFri, 25 Oct 2013 00:07:40 GMT
https://trac.sagemath.org/ticket/15283#comment:16
https://trac.sagemath.org/ticket/15283#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15283#comment:10" title="Comment 10">darij</a>:
</p>
<blockquote class="citation">
<p>
I don't think <code>self.lt</code> returns the right format for <code>sorted</code>. It seems that the <code>cmp</code> keyword of <code>sorted</code> wants a total -1,0,1-valued function, not a boolean one. See how this prints the same list twice:
</p>
<pre class="wiki">P = Poset({i: divisors(i) for i in divisors(24)})
print sorted(list(P), cmp=P.lt)
print sorted(list(P), cmp=P.gt)
</pre></blockquote>
<p>
The recommended way is to use <code>sorted(...,key=...)</code> where <code>key</code> should map the sequence elements into a totally ordered set (for instance, the integers). This provides a concise way of the decorate-sort-undecorate pattern, or <em>Schwartzian transform</em>, which is generally more efficient than sorting with a likely expensive custom sort function.
</p>
<p>
The <code>cmp</code> keyword is actually removed in Python 3. See <code>functools.cmp_to_key</code> to convert a legitimate <code>cmp</code> function into a value suitable for <code>key</code>.
</p>
TicketDarij GrinbergFri, 25 Oct 2013 01:31:21 GMT
https://trac.sagemath.org/ticket/15283#comment:17
https://trac.sagemath.org/ticket/15283#comment:17
<p>
Thanks, Nathann and Nils, for your comments. I've decided to provide two implementations for <code>is_chain</code>, one using sorting when the poset is finite (in which case, as Nils suggests, I'll use a <code>key</code> attribute), one by checking all pairs of possible relations when the poset is not assumed finite.
</p>
<p>
I'm still reluctant to make this part of the existing <code>is_chain</code> method. One reason is that the existing <code>is_chain</code> exists only for finite posets, so I'd have to move it from <code>sage/combinat/posets.py</code> to <code>sage/categories/posets.py</code> and give it some stupid error behavior when the poset is not finite.
</p>
<p>
I'm carrying this over into a new ticket: <a class="closed ticket" href="https://trac.sagemath.org/ticket/15322" title="#15322: enhancement: Testing for antichains and chains in arbitrary posets (closed: fixed)">#15322</a>. Please disregard the additions-dg.patch I posted here, as it is buggy.
</p>
TicketJeroen DemeyerThu, 31 Oct 2013 19:17:56 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/15283#comment:18
https://trac.sagemath.org/ticket/15283#comment:18
<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.beta2</em>
</li>
</ul>
Ticket