Sage: Ticket #17023: Adding width() function to poset
https://trac.sagemath.org/ticket/17023
<p>
Add a <code>.width()</code> -- i.e. number of elements in the longest antichain -- to poset. Seems to have polynomial time algorithm based on Dilworth's Theorem.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17023
Trac 1.1.6ncohenSun, 21 Sep 2014 09:38:07 GMTcc set
https://trac.sagemath.org/ticket/17023#comment:1
https://trac.sagemath.org/ticket/17023#comment:1
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
</ul>
TicketncohenSun, 21 Sep 2014 10:28:12 GMT
https://trac.sagemath.org/ticket/17023#comment:2
https://trac.sagemath.org/ticket/17023#comment:2
<p>
I am writing this code right now.
</p>
TicketjmantysaloSun, 21 Sep 2014 11:23:09 GMT
https://trac.sagemath.org/ticket/17023#comment:3
https://trac.sagemath.org/ticket/17023#comment:3
<p>
Fast catch! So there is no function for maximum match at graphs available for wrapping?
</p>
TicketncohenSun, 21 Sep 2014 11:29:23 GMT
https://trac.sagemath.org/ticket/17023#comment:4
https://trac.sagemath.org/ticket/17023#comment:4
<blockquote class="citation">
<p>
Fast catch! So there is no function for maximum match at graphs available for wrapping?
</p>
</blockquote>
<p>
There is, but I want to do the job properly.
</p>
<p>
You can get the width with <code>len(Graph(your_poset.hasse_diagram().transitive_closure()).independent_set())</code> in the meantime.
</p>
<p>
Nathann
</p>
TicketncohenSun, 21 Sep 2014 11:57:04 GMTstatus changed; branch, author set
https://trac.sagemath.org/ticket/17023#comment:5
https://trac.sagemath.org/ticket/17023#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/17023</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
TicketgitSun, 21 Sep 2014 11:57:46 GMTcommit set
https://trac.sagemath.org/ticket/17023#comment:6
https://trac.sagemath.org/ticket/17023#comment:6
<ul>
<li><strong>commit</strong>
set to <em>50e349b5255c0efd24b4f152d7bc0f3d17ae85bd</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ad47132453d5bca8ea076357be87db9313f0ae64"><span class="icon"></span>ad47132</a></td><td><code>trac #16909: transitive_closure() and mutable graphs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=711236c7b660a32740d60e8e530551f23cc22607"><span class="icon"></span>711236c</a></td><td><code>trac #16909: Merged with 6.4.beta3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=50e349b5255c0efd24b4f152d7bc0f3d17ae85bd"><span class="icon"></span>50e349b</a></td><td><code>trac #17023: Poset.width and Poset.dilworth_decomposition</code>
</td></tr></table>
TicketjmantysaloSun, 21 Sep 2014 12:17:04 GMTstatus changed
https://trac.sagemath.org/ticket/17023#comment:7
https://trac.sagemath.org/ticket/17023#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
If <code>height()</code> has description "Return the height (number of elements in the longest chain) of the poset.", then I think that this should have
</p>
<p>
"Return the height (number of elements in the longest antichain) of the poset.
</p>
<p>
For information about algorithm, see :wikipedia:<code>Dilworth's_theorem</code>."
</p>
<p>
Because Dilworth's theorem is not really part of function definition but an implementation detail.
</p>
TicketgitSun, 21 Sep 2014 12:31:39 GMTcommit changed
https://trac.sagemath.org/ticket/17023#comment:8
https://trac.sagemath.org/ticket/17023#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>50e349b5255c0efd24b4f152d7bc0f3d17ae85bd</em> to <em>235fc282be25432da0f3e224ffab6ac9c7c5f5e5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=235fc282be25432da0f3e224ffab6ac9c7c5f5e5"><span class="icon"></span>235fc28</a></td><td><code>trac #17023: Reviwer's remarks</code>
</td></tr></table>
TicketncohenSun, 21 Sep 2014 12:32:57 GMTstatus changed
https://trac.sagemath.org/ticket/17023#comment:9
https://trac.sagemath.org/ticket/17023#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjmantysaloSun, 21 Sep 2014 15:07:02 GMT
https://trac.sagemath.org/ticket/17023#comment:10
https://trac.sagemath.org/ticket/17023#comment:10
<p>
Seems to work. I checked extreme cases: empty poset, one-element poset, chains and antichains, all poset of size n up to n=7 and few thousand random posets with varying parameters.
</p>
<p>
Reading code is propably best done with someone wiser than I am.
</p>
<p>
One line descriptions should have a dot at the end, because they are full sentences.
</p>
TicketchapotonWed, 24 Sep 2014 18:47:50 GMTcommit, branch changed
https://trac.sagemath.org/ticket/17023#comment:11
https://trac.sagemath.org/ticket/17023#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>235fc282be25432da0f3e224ffab6ac9c7c5f5e5</em> to <em>99f8ed04511d4422eb0874a5332132b4058d8e34</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/17023</em> to <em>public/ticket/17023</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
I made a few little changes. Not a review, sorry.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=99f8ed04511d4422eb0874a5332132b4058d8e34"><span class="icon"></span>99f8ed0</a></td><td><code>trac #17023 code and doc formatting + one ref</code>
</td></tr></table>
TicketjmantysaloThu, 25 Sep 2014 05:07:31 GMT
https://trac.sagemath.org/ticket/17023#comment:12
https://trac.sagemath.org/ticket/17023#comment:12
<p>
About "return" vs. "returns" on documentation: at least <a class="ext-link" href="http://legacy.python.org/dev/peps/pep-0008/#documentation-strings"><span class="icon"></span>http://legacy.python.org/dev/peps/pep-0008/#documentation-strings</a> shows example with "return". There was also some discussion about this at sage-devel -list at last month. Hence I think that Nathan's code follows style manual.
</p>
TicketjmantysaloThu, 25 Sep 2014 05:31:36 GMT
https://trac.sagemath.org/ticket/17023#comment:13
https://trac.sagemath.org/ticket/17023#comment:13
<p>
I did some timings. It seems that for something like <code>P=Posets.RandomPoset(100,0.15)</code> or so it is faster to run <code>max(len(x) for x in P.antichains())</code> than <code>P.width()</code>. On the other hand the measured complexity of <code>.width()</code> seems to be polynomial as it should.
</p>
<p>
I will do more test on faster computer, this was done quickly with an oooold machine.
</p>
TicketjmantysaloThu, 25 Sep 2014 07:52:00 GMT
https://trac.sagemath.org/ticket/17023#comment:14
https://trac.sagemath.org/ticket/17023#comment:14
<p>
How fast is <code>connected_components()</code> on graphs? Because this can be done simply by summing widths of connected subposets.
</p>
<p>
If posets are more "chain-like", then simply looking antichains seems to be faster. For posets more "antichain-like" it is much faster to use this new <code>.width()</code> method. Where is the turning point? Can there be some heuristic based on ratio of number of edges to number of vertices?
</p>
TicketncohenThu, 25 Sep 2014 08:08:48 GMT
https://trac.sagemath.org/ticket/17023#comment:15
https://trac.sagemath.org/ticket/17023#comment:15
<blockquote class="citation">
<p>
About "return" vs. "returns" on documentation: at least <a class="ext-link" href="http://legacy.python.org/dev/peps/pep-0008/#documentation-strings"><span class="icon"></span>http://legacy.python.org/dev/peps/pep-0008/#documentation-strings</a> shows example with "return". There was also some discussion about this at sage-devel -list at last month. Hence I think that Nathan's code follows style manual.
</p>
</blockquote>
<p>
I think that it follows manual, for not so long ago one of my patches was set to 'needs_work' because I wrote "returns" instead of "return". I do not care if the convention changes at every review for as long as I am not the one who writes the commits.
</p>
<p>
Nathann
</p>
TicketncohenThu, 25 Sep 2014 08:09:17 GMT
https://trac.sagemath.org/ticket/17023#comment:16
https://trac.sagemath.org/ticket/17023#comment:16
<blockquote class="citation">
<p>
I did some timings. It seems that for something like <code>P=Posets.RandomPoset(100,0.15)</code> or so it is faster to run <code>max(len(x) for x in P.antichains())</code> than <code>P.width()</code>. On the other hand the measured complexity of <code>.width()</code> seems to be polynomial as it should.
</p>
</blockquote>
<p>
Seems that random posets have a very very small width <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketjmantysaloThu, 25 Sep 2014 08:25:22 GMT
https://trac.sagemath.org/ticket/17023#comment:17
https://trac.sagemath.org/ticket/17023#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17023#comment:16" title="Comment 16">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Seems that random posets have a very very small width <code>O_o</code>
</p>
</blockquote>
<p>
Actually this has been thinked already. Brinkmann & <a class="missing wiki">McKay?</a> says at the end of paper Posets on up to 16 points "Our results do not show this behaviour, emphasizing again that the convergence of posets to their asymptotic behaviour is quite slow." Hence no help from that.
</p>
TicketncohenThu, 25 Sep 2014 08:25:49 GMT
https://trac.sagemath.org/ticket/17023#comment:18
https://trac.sagemath.org/ticket/17023#comment:18
<p>
Hello !
</p>
<blockquote class="citation">
<p>
How fast is <code>connected_components()</code> on graphs? Because this can be done simply by summing widths of connected subposets.
</p>
</blockquote>
<p>
What do you mean ? If the poset is not connected you can indeed split it and compute the result on each connected components but I don't think the code I implemented will run any faster because of that. It would decrease the number of antichains though. But add an element superior to all others in your posets and you lost connectivity for the very same width.
</p>
<blockquote class="citation">
<p>
If posets are more "chain-like", then simply looking antichains seems to be faster. For posets more "antichain-like" it is much faster to use this new <code>.width()</code> method. Where is the turning point? Can there be some heuristic based on ratio of number of edges to number of vertices?
</p>
</blockquote>
<p>
Well, maybe there is some algorithm to recognize posets with width <=2. And we already have a <code>is_chain</code> for width 1. Also, I think that something like
</p>
<pre class="wiki">len(Graph(posets.ChainPoset(6).hasse_diagram().transitive_closure()).independent_set())
</pre><p>
should be a bit faster than enumerating the antichains. Even though enumerating the antichains may be faster for very very line-looking posets, for you don't have any graphs to copy around, ...
</p>
<p>
Nathann
</p>
TicketjmantysaloThu, 25 Sep 2014 12:12:37 GMT
https://trac.sagemath.org/ticket/17023#comment:19
https://trac.sagemath.org/ticket/17023#comment:19
<p>
You are right, on average connected posets are far more common than non-connected. Hence this should be like it now is.
</p>
<p>
Duh, should I try to understand theorem and read the code...
</p>
TicketjmantysaloFri, 26 Sep 2014 10:32:23 GMT
https://trac.sagemath.org/ticket/17023#comment:20
https://trac.sagemath.org/ticket/17023#comment:20
<p>
I read the code. As a side not, almost all examples use "P =", you have used "p =".
</p>
<p>
But as far as I can say, code seems to do what it should. I think this could be marked as positive review after trivial modifications like "returns" vs. "return".
</p>
TicketncohenFri, 26 Sep 2014 13:13:48 GMT
https://trac.sagemath.org/ticket/17023#comment:21
https://trac.sagemath.org/ticket/17023#comment:21
<blockquote class="citation">
<p>
I read the code. As a side not, almost all examples use "P =", you have used "p =".
</p>
</blockquote>
<p>
Pleaaaaaase let's not have a rule about upper/lower case <code>T_T</code>
</p>
<blockquote class="citation">
<p>
But as far as I can say, code seems to do what it should. I think this could be marked as positive review after trivial modifications like "returns" vs. "return".
</p>
</blockquote>
<p>
Frédéric ? Could you remove the 's' you added ?
</p>
<p>
Nathann
</p>
TicketchapotonFri, 26 Sep 2014 18:44:48 GMTstatus, description changed
https://trac.sagemath.org/ticket/17023#comment:22
https://trac.sagemath.org/ticket/17023#comment:22
<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/17023?action=diff&version=22">diff</a>)
</li>
</ul>
<p>
I think the <code>s</code> in the list of methods should stay there for coherence of this list.
</p>
<p>
As there is no <code>s</code> in the first line of the new functions, things are good as they are.
</p>
<p>
LGTM. Let us not lose time on stupid things.
</p>
TicketchapotonFri, 26 Sep 2014 18:45:32 GMTreviewer set
https://trac.sagemath.org/ticket/17023#comment:23
https://trac.sagemath.org/ticket/17023#comment:23
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton, Jori Mäntysalo</em>
</li>
</ul>
TicketjmantysaloTue, 14 Oct 2014 09:50:22 GMTmilestone changed
https://trac.sagemath.org/ticket/17023#comment:24
https://trac.sagemath.org/ticket/17023#comment:24
<ul>
<li><strong>milestone</strong>
changed from <em>sage-wishlist</em> to <em>sage-6.4</em>
</li>
</ul>
TicketvbraunWed, 15 Oct 2014 18:12:35 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17023#comment:25
https://trac.sagemath.org/ticket/17023#comment:25
<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>branch</strong>
changed from <em>public/ticket/17023</em> to <em>99f8ed04511d4422eb0874a5332132b4058d8e34</em>
</li>
</ul>
Ticket