Sage: Ticket #20727: LatticePoset: about complements
https://trac.sagemath.org/ticket/20727
<p>
There is a slight corner-case -error:
</p>
<pre class="wiki">LatticePoset({1: []}).complements()
</pre><p>
will give <code>{1: [1, 1]}</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/20727
Trac 1.1.6jmantysaloTue, 31 May 2016 08:00:44 GMTbranch set
https://trac.sagemath.org/ticket/20727#comment:1
https://trac.sagemath.org/ticket/20727#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/jmantysalo/hasse_complements</em>
</li>
</ul>
TicketjmantysaloTue, 31 May 2016 08:02:10 GMTstatus changed; cc, commit set
https://trac.sagemath.org/ticket/20727#comment:2
https://trac.sagemath.org/ticket/20727#comment:2
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
<li><strong>commit</strong>
set to <em>2481a494167fa56b15742fd9b507559232517069</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2481a494167fa56b15742fd9b507559232517069"><span class="icon"></span>2481a49</a></td><td><code>Corner-case for complements and more.</code>
</td></tr></table>
TicketjmantysaloMon, 04 Jul 2016 13:02:41 GMT
https://trac.sagemath.org/ticket/20727#comment:3
https://trac.sagemath.org/ticket/20727#comment:3
<p>
Just a <code>ping</code>.
</p>
<p>
If wanted, I can make a patch that only corrects the corner case in <code>lattices.py</code>.
</p>
TickettscrimTue, 05 Jul 2016 06:52:20 GMTreviewer set
https://trac.sagemath.org/ticket/20727#comment:4
https://trac.sagemath.org/ticket/20727#comment:4
<ul>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
This is essentially a positive review, but I don't know the definition of the complements of elements in a poset. I think it would be good to give this.
</p>
TicketjmantysaloTue, 05 Jul 2016 07:05:47 GMT
https://trac.sagemath.org/ticket/20727#comment:5
https://trac.sagemath.org/ticket/20727#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20727#comment:4" title="Comment 4">tscrim</a>:
</p>
<blockquote class="citation">
<p>
This is essentially a positive review, but I don't know the definition of the complements of elements in a poset. I think it would be good to give this.
</p>
</blockquote>
<p>
(I guess you mean lattice and not poset, even if it is easy to extend the definition to every bounded poset.)
</p>
<p>
It is said in <code>lattices.py</code> at function <code>complements()</code> already: Elements <code>x</code> and <code>y</code> are complements if their meet and join are respectively the bottom and the top element of the lattice.
</p>
<p>
In how many places should it be said? In <code>hasse_diagram.py</code>? In <code>is_complemented()</code>, <code>is_relatively_complemented()</code>, and maybe later in <code>is_sectionally_complemented()</code>? This is a real question, and I can see arguments for both directions.
</p>
TicketkdilksMon, 11 Jul 2016 14:34:17 GMT
https://trac.sagemath.org/ticket/20727#comment:6
https://trac.sagemath.org/ticket/20727#comment:6
<p>
I think it definitely needs to be defined in <code>hasse_diagram.py</code>, to distinguish between the inherited method of <code>complement()</code> coming from <code>Digraphs</code>, which is entirely different.
</p>
<p>
For the other ones, I would include a line at the end of each linking to similar/relevant methods (ie, <code>is_complemented()</code> would have a line at the end saying <code>see: complements(), is_relatively_complemented(), etc.</code>.
</p>
TicketjmantysaloMon, 11 Jul 2016 18:38:45 GMT
https://trac.sagemath.org/ticket/20727#comment:7
https://trac.sagemath.org/ticket/20727#comment:7
<p>
First, thanks for reviews!
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20727#comment:6" title="Comment 6">kdilks</a>:
</p>
<blockquote class="citation">
<p>
I think it definitely needs to be defined in <code>hasse_diagram.py</code>, to distinguish between the inherited method of <code>complement()</code> coming from <code>Digraphs</code>, which is entirely different.
</p>
</blockquote>
<p>
This patch will do that. Althought I must admit that now <code>lattices.py</code> copies code from <code>hasse_diagram.py</code>, and that is not needed.
</p>
<blockquote class="citation">
<p>
For the other ones, I would include a line at the end of each linking to similar/relevant methods (ie, <code>is_complemented()</code> would have a line at the end saying <code>see: complements(), is_relatively_complemented(), etc.</code>.
</p>
</blockquote>
<p>
True. I guess that <a class="closed ticket" href="https://trac.sagemath.org/ticket/20940" title="enhancement: LatticePoset: add is_sectionally_complemented() (closed: fixed)">#20940</a> will be last of this serie, so it is propably right place to add seealso-links. Before that I wait comment from Travis at <a class="closed ticket" href="https://trac.sagemath.org/ticket/20972" title="enhancement: Add certificate to is_relatively_complemented() (closed: fixed)">#20972</a>.
</p>
TicketgitTue, 09 Aug 2016 05:12:28 GMTcommit changed
https://trac.sagemath.org/ticket/20727#comment:8
https://trac.sagemath.org/ticket/20727#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>2481a494167fa56b15742fd9b507559232517069</em> to <em>fcbf57e355d100bd2da269b5ffe474443fa56c6a</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="https://git.sagemath.org/sage.git/commit/?id=fcbf57e355d100bd2da269b5ffe474443fa56c6a"><span class="icon"></span>fcbf57e</a></td><td><code>Add definition of complement.</code>
</td></tr></table>
TicketjmantysaloTue, 09 Aug 2016 05:22:26 GMTmilestone changed
https://trac.sagemath.org/ticket/20727#comment:9
https://trac.sagemath.org/ticket/20727#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-7.3</em> to <em>sage-7.4</em>
</li>
</ul>
<p>
OK, I added the definition of complement directly to this function in <code>hasse_diagram.py</code>.
</p>
<p>
It feels good design to have "internals" in <code>hasse_diagram.py</code> and have "interface" at <code>posets.py</code> and <code>lattices.py</code>. But it means that some definitions and tests must be written twise, maybe with collisions (definitions of graded vs. ranked). Also some functions at <code>hasse_diagram.py</code> are only meaningfull for lattices.
</p>
<p>
Now we have <code>certificate</code>-option in <code>is_relatively_complemented()</code> and <code>is_sectionally_complemented()</code>. I think we should add the same to <code>is_complemented()</code>. But that's a task for another ticket.
</p>
TicketkdilksTue, 09 Aug 2016 05:57:28 GMT
https://trac.sagemath.org/ticket/20727#comment:10
https://trac.sagemath.org/ticket/20727#comment:10
<p>
What makes you think it's good design? It seems like poor design to have the code for a single function spread across different files. If somebody is working with a poset/lattice and wants to figure out what this function is doing, instead of <code>??</code> giving them the code for the algorithm, they get the interface, and they have to try and hunt down the actual internals.
</p>
TicketjmantysaloTue, 09 Aug 2016 06:10:56 GMT
https://trac.sagemath.org/ticket/20727#comment:11
https://trac.sagemath.org/ticket/20727#comment:11
<p>
For example series-parallel decomposition should be doable without temporary posets, i.e. using <code>connected_components()</code> and <code>vertical_summands()</code> in Hasse diagram. Partly the problem is <code>UniqueRepresentation</code>, which means that every poset is saved to memory, and takes more time to create. And if we make a code to generate all lattices of given type (see <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/20516" title="enhancement: Generating non-isomorphic lattices (needs_info)">#20516</a>) we need test functions that does not need poset generation.
</p>
<p>
But even having all functions at <code>posets.py</code> and <code>lattices.py</code> would be simpler than current system where we internal code splitted without any logic.
</p>
TickettscrimThu, 11 Aug 2016 12:47:20 GMT
https://trac.sagemath.org/ticket/20727#comment:12
https://trac.sagemath.org/ticket/20727#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20727#comment:10" title="Comment 10">kdilks</a>:
</p>
<blockquote class="citation">
<p>
What makes you think it's good design? It seems like poor design to have the code for a single function spread across different files. If somebody is working with a poset/lattice and wants to figure out what this function is doing, instead of <code>??</code> giving them the code for the algorithm, they get the interface, and they have to try and hunt down the actual internals.
</p>
</blockquote>
<p>
You're forgetting the fact that by working in <code>HasseDiagram</code>, you can assume the vertices are <code>(0, 1, ..., n-1)</code> and that is a linear extension. I agree that we loose a small bit of clarity (and an extra Python function call) for the indirection, but we often gain much more speed and code simplicity by utilizing these assumptions. One way you can think of <code>Poset</code> is that it adds the extra layer of the element labels.
</p>
<p>
I think we can remove all references to the deprecation because this function is no longer broken AFAIK.
</p>
TickettscrimThu, 11 Aug 2016 12:52:34 GMTstatus changed
https://trac.sagemath.org/ticket/20727#comment:13
https://trac.sagemath.org/ticket/20727#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TickettscrimThu, 11 Aug 2016 12:53:09 GMTstatus changed
https://trac.sagemath.org/ticket/20727#comment:14
https://trac.sagemath.org/ticket/20727#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Whoops, that's right, I wanted to the comment about the deprecation removed.
</p>
TicketjmantysaloThu, 11 Aug 2016 13:07:37 GMT
https://trac.sagemath.org/ticket/20727#comment:15
https://trac.sagemath.org/ticket/20727#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20727#comment:12" title="Comment 12">tscrim</a>:
</p>
<blockquote class="citation">
<p>
You're forgetting the fact that by working in <code>HasseDiagram</code>, you can assume the vertices are <code>(0, 1, ..., n-1)</code> and that is a linear extension. I agree that we loose a small bit of clarity (and an extra Python function call) for the indirection, but we often gain much more speed and code simplicity by utilizing these assumptions. One way you can think of <code>Poset</code> is that it adds the extra layer of the element labels.
</p>
</blockquote>
<p>
But we could have it all in one file, without <code>hasse_diagram.py</code>. But OTOH this design is quite clear to me. Also I suppose that everything can be changed in that file, as long as "interfaces", i.e. mostly <code>posets.py</code> and <code>lattices.py</code> stays.
</p>
<blockquote class="citation">
<p>
I think we can remove all references to the deprecation because this function is no longer broken AFAIK.
</p>
</blockquote>
<p>
OK, I can remove them.
</p>
TicketgitMon, 15 Aug 2016 07:05:29 GMTcommit changed
https://trac.sagemath.org/ticket/20727#comment:16
https://trac.sagemath.org/ticket/20727#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>fcbf57e355d100bd2da269b5ffe474443fa56c6a</em> to <em>89dbcf480dbe452c0f9dcbde634777b3659c5a8d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=89dbcf480dbe452c0f9dcbde634777b3659c5a8d"><span class="icon"></span>89dbcf4</a></td><td><code>Corner case for complements().</code>
</td></tr></table>
TicketjmantysaloMon, 15 Aug 2016 07:07:35 GMTstatus, description changed
https://trac.sagemath.org/ticket/20727#comment:17
https://trac.sagemath.org/ticket/20727#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/20727?action=diff&version=17">diff</a>)
</li>
</ul>
<p>
Hmm... There were no deprecations left in my code.
</p>
<p>
But anyway, I guess this can be thinked later. I changed this patch to only correct the corner case error and added tests for that.
</p>
TicketchapotonWed, 17 Aug 2016 09:14:35 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/20727#comment:18
https://trac.sagemath.org/ticket/20727#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Travis Scrimshaw</em> to <em>Travis Scrimshaw, Frédéric Chapoton</em>
</li>
</ul>
<p>
ok, looks good to me
</p>
TicketvbraunFri, 19 Aug 2016 22:45:07 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/20727#comment:19
https://trac.sagemath.org/ticket/20727#comment:19
<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>u/jmantysalo/hasse_complements</em> to <em>89dbcf480dbe452c0f9dcbde634777b3659c5a8d</em>
</li>
</ul>
Ticket