Sage: Ticket #19123: LatticePoset: add is_vertically_decomposable
https://trac.sagemath.org/ticket/19123
<p>
This patch adds a function <code>is_vertically_decomposable</code> to finite lattices.
</p>
<p>
For testing see <a class="ext-link" href="https://oeis.org/A058800"><span class="icon"></span>https://oeis.org/A058800</a> ; for example
</p>
<pre class="wiki">sum([1 for L in Posets(6) if L.is_lattice() and
not LatticePoset(L).is_vertically_decomposable()])
</pre><p>
returns 7 as it should.
</p>
<p>
There is a place for possible optimization: If there is, say, covering relations <code>bottom -> 5</code>, <code>3 -> 8</code> and <code>7 -> top</code>, is suffices to show that the lattice is not vertically decomposable. This might be faster on average. Now the complexity is linear to number of covering relations.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19123
Trac 1.1.6jmantysaloTue, 01 Sep 2015 14:53:34 GMTbranch set
https://trac.sagemath.org/ticket/19123#comment:1
https://trac.sagemath.org/ticket/19123#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/jmantysalo/vertically_decomposable</em>
</li>
</ul>
TicketjmantysaloTue, 01 Sep 2015 14:56:46 GMTstatus changed; cc, commit set
https://trac.sagemath.org/ticket/19123#comment:2
https://trac.sagemath.org/ticket/19123#comment:2
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>0d472a68c9edf4ddea1404ff0cb6d2f508de55d0</em>
</li>
</ul>
<p>
Quite easy one. Nathann selected as a random victim for a possible reviewer. <code>:=)</code>
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=decffe66347c675513bec7be9ea5411e9e123706"><span class="icon"></span>decffe6</a></td><td><code>Added function is_vertically_decomposable().</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0d472a68c9edf4ddea1404ff0cb6d2f508de55d0"><span class="icon"></span>0d472a6</a></td><td><code>Spaces on empty lines.</code>
</td></tr></table>
TicketncohenTue, 01 Sep 2015 18:25:09 GMT
https://trac.sagemath.org/ticket/19123#comment:3
https://trac.sagemath.org/ticket/19123#comment:3
<p>
Sounds good, but don't you think it may be useful to *know* where the poset splits? Also, why is it only defined for lattices? The algorithm works in all cases.
</p>
<p>
I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?
</p>
<p>
Nathann
</p>
TicketjmantysaloTue, 01 Sep 2015 18:39:40 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:4
https://trac.sagemath.org/ticket/19123#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:3" title="Comment 3">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Sounds good, but don't you think it may be useful to *know* where the poset splits?
</p>
</blockquote>
<p>
Yes, I think that will be usefull. For posets we have <code>is_connected()</code>, <code>connected_components()</code> and <code>disjoint_union()</code>. I guess we should have <code>is_vertically_decomposable()</code>, <code>vertically_indecomposable_parts()</code> and <code>vertical_sum()</code> for lattices.
</p>
<p>
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements". The user could then run <code>interval()</code> on them to get parts.
</p>
<blockquote class="citation">
<p>
Also, why is it only defined for lattices? The algorithm works in all cases.
</p>
</blockquote>
<p>
How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.
</p>
<blockquote class="citation">
<p>
I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?
</p>
</blockquote>
<p>
Arghs! You are right, of course. I forget the special case when writing the code. I'll correct it.
</p>
<p>
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
</p>
TicketncohenTue, 01 Sep 2015 18:45:13 GMT
https://trac.sagemath.org/ticket/19123#comment:5
https://trac.sagemath.org/ticket/19123#comment:5
<blockquote class="citation">
<p>
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".
</p>
</blockquote>
<p>
+1 to that.
</p>
<blockquote class="citation">
<p>
How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.
</p>
</blockquote>
<p>
Hmmm, okay okay... I attempted to write a definition, but indeed for non-lattices you have 1000 different corner-cases, and th definition would be a mess.
</p>
<blockquote class="citation">
<p>
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
</p>
</blockquote>
<p>
What do you mean? Your algorithm looks very reliable. I do not see it waste much.
</p>
<p>
Nathann
</p>
TicketjmantysaloTue, 01 Sep 2015 20:02:42 GMT
https://trac.sagemath.org/ticket/19123#comment:6
https://trac.sagemath.org/ticket/19123#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".
</p>
</blockquote>
<p>
+1 to that.
</p>
</blockquote>
<p>
OK. What should be the name of the argument? <code>certificate</code>? <code>give_me_the_list=True</code>?
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.
</p>
</blockquote>
<p>
Hmmm, okay okay... I attempted to write a definition, but indeed for non-lattices you have 1000 different corner-cases, and th definition would be a mess.
</p>
</blockquote>
<p>
Except for the 2-element lattice there is one simple definition that generalizes this:
</p>
<pre class="wiki">any(P.cover_relations_graph().is_cut_vertex(e) for e in P)
</pre><p>
But in any case, it is easy to move this to posets later if we want so.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)
</p>
</blockquote>
<p>
What do you mean? Your algorithm looks very reliable. I do not see it waste much.
</p>
</blockquote>
<p>
If the poset has coverings <code>2 -> 6</code> and <code>4 -> 9</code>, then no element <code>3..8</code> can be a decomposition element. After founding, say, <code>2 -> 6</code> we could check <code>5 -></code>, <code>4 -></code> and so on. But after founding <code>4 -> 9</code> we should have a somewhat complicated stack to skip re-checking biggest covers of <code>4</code> and <code>5</code>. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.
</p>
TicketncohenTue, 01 Sep 2015 20:25:25 GMT
https://trac.sagemath.org/ticket/19123#comment:7
https://trac.sagemath.org/ticket/19123#comment:7
<blockquote class="citation">
<p>
OK. What should be the name of the argument? <code>certificate</code>? <code>give_me_the_list=True</code>?
</p>
</blockquote>
<p>
Isn't there a terminology for those points? If it is only for lattices, maybe you could have <code>return_cutvertices=True</code> or something?
</p>
<blockquote class="citation">
<p>
Except for the 2-element lattice there is one simple definition that generalizes this:
</p>
<pre class="wiki">any(P.cover_relations_graph().is_cut_vertex(e) for e in P)
</pre></blockquote>
<p>
Wouldn't work for a poset on three elements, one being greater than the two others (which are incomparable).
</p>
<blockquote class="citation">
<p>
If the poset has coverings <code>2 -> 6</code> and <code>4 -> 9</code>, then no element <code>3..8</code> can be a decomposition element. After founding, say, <code>2 -> 6</code> we could check <code>5 -></code>, <code>4 -></code> and so on. But after founding <code>4 -> 9</code> we should have a somewhat complicated stack to skip re-checking biggest covers of <code>4</code> and <code>5</code>. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.
</p>
</blockquote>
<p>
HMmm... Skipping some edges without additional assumption on the order in which they are returned? I do not know... This is not so bad, for the moment <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketgitWed, 02 Sep 2015 06:44:06 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:8
https://trac.sagemath.org/ticket/19123#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>0d472a68c9edf4ddea1404ff0cb6d2f508de55d0</em> to <em>893ecc133183398f0932e02c146f235230784915</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=893ecc133183398f0932e02c146f235230784915"><span class="icon"></span>893ecc1</a></td><td><code>Added an option to get "decomposing elements".</code>
</td></tr></table>
TicketncohenWed, 02 Sep 2015 06:46:44 GMT
https://trac.sagemath.org/ticket/19123#comment:9
https://trac.sagemath.org/ticket/19123#comment:9
<p>
You don't have to write this algorithm twice to make it work in all situations. Once is enough. And if you are worried of the cost of a 'if' inside of the loop, then you should not be writing Python code.
</p>
<p>
Furthermore, be careful with '::' as they are not needed after an INPUT block. Build the doc to check it.
</p>
<p>
Nathann
</p>
TicketjmantysaloWed, 02 Sep 2015 06:56:04 GMT
https://trac.sagemath.org/ticket/19123#comment:10
https://trac.sagemath.org/ticket/19123#comment:10
<p>
Now it should work with empty lattice, 1-element lattice and 2-element lattice. There is backend ready for extending the function in <code>lattices.py</code>. I may modify it as suggested by Nathann at comment 9. But the more important question:
</p>
<p>
How should we exactly define "decomposing elements"? Let's start with
</p>
<pre class="wiki">Posets.ChainPoset(2).ordinal_sum(Posets.BooleanLattice(3), labels='integers')
</pre><p>
Is <code>0</code> a decomposing element? What are "components" for the lattice? Maybe <code>0-1</code>, <code>1-2</code> and <code>2-9</code>. But then, what are components of 2-element lattice?
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
If the poset has coverings <code>2 -> 6</code> and <code>4 -> 9</code>, then no element <code>3..8</code> can be a decomposition element. After founding, say, <code>2 -> 6</code> we could check <code>5 -></code>, <code>4 -></code> and so on. But after founding <code>4 -> 9</code> we should have a somewhat complicated stack to skip re-checking biggest covers of <code>4</code> and <code>5</code>. I guess that the algorithm would be slower in reality, but I am quite sure that it would be better in some theoretical meaning.
</p>
</blockquote>
<p>
HMmm... Skipping some edges without additional assumption on the order in which they are returned?
</p>
</blockquote>
<p>
I dont' mean that. If the lattice has <code>100</code> elements, then <code>0</code> is the bottom and <code>99</code> is the top. If the lattice has coverings <code>0 -> 37</code>, <code>34 -> 88</code> and <code>77 -> 99</code>, then it is not vertically decomposable. There might be faster way to find those coverings than going throught all elements. But the code would be much more complicated.
</p>
TicketncohenWed, 02 Sep 2015 07:11:14 GMT
https://trac.sagemath.org/ticket/19123#comment:11
https://trac.sagemath.org/ticket/19123#comment:11
<p>
Could you also add to your docstring a reference toward a textbook that defines this notion?
</p>
TicketgitWed, 02 Sep 2015 10:47:57 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:12
https://trac.sagemath.org/ticket/19123#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>893ecc133183398f0932e02c146f235230784915</em> to <em>ca909a0c05fee489a071ff672b9f3b5392ba8158</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=ca909a0c05fee489a071ff672b9f3b5392ba8158"><span class="icon"></span>ca909a0</a></td><td><code>Indentation of INPUT block.</code>
</td></tr></table>
TicketjmantysaloWed, 02 Sep 2015 11:12:13 GMTcc, description changed
https://trac.sagemath.org/ticket/19123#comment:13
https://trac.sagemath.org/ticket/19123#comment:13
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/19123?action=diff&version=13">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Could you also add to your docstring a reference toward a textbook that defines this notion?
</p>
</blockquote>
<p>
Duh. Counting Finite Lattices by Heitzig and Reinhold defines it "- - contains an element which is neither the greatest not the least element of L but comparable to every element of L." On the other hand, On the number of distributive lattices by Erné and (same) Heitzig and Reinhold says "- - if it is either a singleton or the vertical sum of two nonempty posets - -", and vertical sum on two two-element lattice by their definition is the two-element lattice.
</p>
<p>
I select tscrim as another random victim. Travis, should we define the two-element lattice to be vertically decomposable or indecomposable?
</p>
<p>
(Or raise <code>OtherError("developers don't know how to define this")</code>? <code>:=)</code>)
</p>
TicketjmantysaloWed, 09 Sep 2015 07:05:57 GMT
https://trac.sagemath.org/ticket/19123#comment:14
https://trac.sagemath.org/ticket/19123#comment:14
<p>
OEIS uses the definition where the two-element lattice is vertically indecomposable: <a class="ext-link" href="https://oeis.org/A058800"><span class="icon"></span>https://oeis.org/A058800</a>. Does this suffice as a base for the definition?
</p>
TicketncohenWed, 09 Sep 2015 07:45:53 GMT
https://trac.sagemath.org/ticket/19123#comment:15
https://trac.sagemath.org/ticket/19123#comment:15
<p>
Helloooooooo !
</p>
<p>
Yeah yeah I guess. Could you just add a link in the doc toward a textbook/paper that defines it the way you use it?
</p>
<blockquote class="citation">
<p>
(Or raise <a class="missing wiki">OtherError?</a>("developers don't know how to define this")?
</p>
</blockquote>
<p>
We have had very non-enlightening debates here about whether the empty graph is connected or not. In such a situation, I would add such a warning rather than have those stupid conversations <code>:-P</code>
Nathann
</p>
TicketgitWed, 09 Sep 2015 12:21:53 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:16
https://trac.sagemath.org/ticket/19123#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>ca909a0c05fee489a071ff672b9f3b5392ba8158</em> to <em>667173c9117e910378f3bc959821a7922a1f9c39</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=667173c9117e910378f3bc959821a7922a1f9c39"><span class="icon"></span>667173c</a></td><td><code>Options to is_vertically_decomposable().</code>
</td></tr></table>
TicketjmantysaloWed, 09 Sep 2015 12:29:54 GMTdescription changed
https://trac.sagemath.org/ticket/19123#comment:17
https://trac.sagemath.org/ticket/19123#comment:17
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19123?action=diff&version=17">diff</a>)
</li>
</ul>
<p>
This code should now work.
</p>
<p>
I still don't know how to make the user interface... For posets we have boolean-valued <code>is_connected()</code> and subposets-valued <code>connected_components()</code>. But what should then be the function returning only "decomposing elements". I will ask in sage-devel.
</p>
<p>
Comments on documentation are welcome.
</p>
TicketncohenWed, 09 Sep 2015 12:39:16 GMT
https://trac.sagemath.org/ticket/19123#comment:18
https://trac.sagemath.org/ticket/19123#comment:18
<p>
return_type vs return_elements.
</p>
TicketgitWed, 09 Sep 2015 12:43:46 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:19
https://trac.sagemath.org/ticket/19123#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>667173c9117e910378f3bc959821a7922a1f9c39</em> to <em>5e7224a20d6341a09821779ebdeb38cbf0130817</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=5e7224a20d6341a09821779ebdeb38cbf0130817"><span class="icon"></span>5e7224a</a></td><td><code>Check for 0- and 1-element lattices.</code>
</td></tr></table>
TicketjmantysaloWed, 09 Sep 2015 12:46:07 GMT
https://trac.sagemath.org/ticket/19123#comment:20
https://trac.sagemath.org/ticket/19123#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:18" title="Comment 18">ncohen</a>:
</p>
<blockquote class="citation">
<p>
return_type vs return_elements.
</p>
</blockquote>
<p>
But they are different things. "Internal" function in <code>hasse_diagram.py</code> has only one yes/no -argument, so a Boolean seems right. "Interface" function in <code>lattices.py</code> has three possible inputs.
</p>
TicketncohenWed, 09 Sep 2015 12:48:41 GMT
https://trac.sagemath.org/ticket/19123#comment:21
https://trac.sagemath.org/ticket/19123#comment:21
<blockquote class="citation">
<p>
But they are different things. "Internal" function in <code>hasse_diagram.py</code> has only one yes/no -argument, so a Boolean seems right. "Interface" function in <code>lattices.py</code> has three possible inputs.
</p>
</blockquote>
<p>
Sorry, I removed my comment on the argument's type right after I posted it, it was a mistake. The one I left, however, is about the fact that the argument that appears in the doc is not the one that appears in the function's definition.
</p>
<p>
Nathann
</p>
TicketgitThu, 10 Sep 2015 11:03:53 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:22
https://trac.sagemath.org/ticket/19123#comment:22
<ul>
<li><strong>commit</strong>
changed from <em>5e7224a20d6341a09821779ebdeb38cbf0130817</em> to <em>d42f0ab3e5bba8a005407f9e864ac6fa5f420318</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=d42f0ab3e5bba8a005407f9e864ac6fa5f420318"><span class="icon"></span>d42f0ab</a></td><td><code>Splitted function, added examples. Also categorized the index of function.</code>
</td></tr></table>
TicketjmantysaloThu, 10 Sep 2015 11:09:11 GMT
https://trac.sagemath.org/ticket/19123#comment:23
https://trac.sagemath.org/ticket/19123#comment:23
<p>
I will wait until <a class="closed ticket" href="https://trac.sagemath.org/ticket/17226" title="enhancement: LatticePoset: add Frattini sublattice (closed: fixed)">#17226</a> gets to beta, and then rebase this. (Forgot that it was not there yet.) This will also categorize the index of functions.
</p>
<p>
I split the function to two parts. I will also wait if somebody comments this on sage-devel. I don't know what should be the name of argument for <code>vertical_decomposition()</code>.
</p>
<p>
So this is open for comments and <em>de facto</em> ready for review, but not <em>de iure</em> in needs_review -phase.
</p>
TicketjmantysaloFri, 11 Sep 2015 07:24:50 GMTcommit, branch deleted
https://trac.sagemath.org/ticket/19123#comment:24
https://trac.sagemath.org/ticket/19123#comment:24
<ul>
<li><strong>commit</strong>
<em>d42f0ab3e5bba8a005407f9e864ac6fa5f420318</em> deleted
</li>
<li><strong>branch</strong>
<em>u/jmantysalo/vertically_decomposable</em> deleted
</li>
</ul>
TicketjmantysaloFri, 11 Sep 2015 07:25:35 GMTbranch set
https://trac.sagemath.org/ticket/19123#comment:25
https://trac.sagemath.org/ticket/19123#comment:25
<ul>
<li><strong>branch</strong>
set to <em>u/jmantysalo/vertically_decomposable2</em>
</li>
</ul>
TicketgitFri, 11 Sep 2015 07:25:47 GMTcommit set
https://trac.sagemath.org/ticket/19123#comment:26
https://trac.sagemath.org/ticket/19123#comment:26
<ul>
<li><strong>commit</strong>
set to <em>c0455d6e94d30e62494888814bdea5c3c8f2be3f</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=c0455d6e94d30e62494888814bdea5c3c8f2be3f"><span class="icon"></span>c0455d6</a></td><td><code>Added vertical decomposition of the lattice. Also change index of function.</code>
</td></tr></table>
TicketjmantysaloFri, 11 Sep 2015 07:28:20 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:27
https://trac.sagemath.org/ticket/19123#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
OK, here is one possible way to split the functionality. Ready for review.
</p>
TicketgitMon, 14 Sep 2015 05:00:32 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:28
https://trac.sagemath.org/ticket/19123#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>c0455d6e94d30e62494888814bdea5c3c8f2be3f</em> to <em>abe1642631b63035568761fd34699929f8afdc8f</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=abe1642631b63035568761fd34699929f8afdc8f"><span class="icon"></span>abe1642</a></td><td><code>Simplification as suggested by ncohen.</code>
</td></tr></table>
TicketjmantysaloMon, 14 Sep 2015 05:04:53 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:29
https://trac.sagemath.org/ticket/19123#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:9" title="Comment 9">ncohen</a>:
</p>
<blockquote class="citation">
<p>
You don't have to write this algorithm twice to make it work in all situations. Once is enough.
</p>
</blockquote>
<p>
Done this. Compiling, will change to needs_review if this seems to work.
</p>
TicketgitMon, 14 Sep 2015 05:42:10 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:30
https://trac.sagemath.org/ticket/19123#comment:30
<ul>
<li><strong>commit</strong>
changed from <em>abe1642631b63035568761fd34699929f8afdc8f</em> to <em>0abc93861d121a172abfb11203821d34fecfd78e</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=0abc93861d121a172abfb11203821d34fecfd78e"><span class="icon"></span>0abc938</a></td><td><code>Special cases for empty, one- and two-element lattices.</code>
</td></tr></table>
TicketjmantysaloMon, 14 Sep 2015 05:44:30 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:31
https://trac.sagemath.org/ticket/19123#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
And yes, there was a bug. Now at last this should be ready for review.
</p>
<p>
(Thematic index of functions might look unnecessary for now. However, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/19197" title="enhancement: LatticePoset: add breadth() (closed: fixed)">#19197</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/19197" title="enhancement: LatticePoset: add breadth() (closed: fixed)">#19197</a> etc.)
</p>
TicketjmantysaloSat, 19 Sep 2015 12:41:29 GMT
https://trac.sagemath.org/ticket/19123#comment:32
https://trac.sagemath.org/ticket/19123#comment:32
<p>
Nathann, what about this. You already read the code and the 2-element lattice case is now documented. Hence there is two questions left:
</p>
<ul><li>Is the thematic index of functions OK in lattices?
</li><li>Is this splitting of functionality OK?
</li></ul>
TicketncohenSun, 20 Sep 2015 11:33:08 GMT
https://trac.sagemath.org/ticket/19123#comment:33
https://trac.sagemath.org/ticket/19123#comment:33
<p>
Jori,
</p>
<p>
I thought a bit before answering your email, because the reason I had not done
anything on the ticket during the last 6 days is that I had chosen to not work
on it anymore. I do not often "forget" things like tickets in needs_review: my
mail inbox contains all the things I must attend to, and they all remain there
until I do what I think I should do with them.
</p>
<p>
Among the reasons that led me there is that nothing specific makes your code
invalid, and I have no reason to ask you to change it just because it does not
suit my taste. I like things short, simple, concise. Three functions for only
one feature is beyond me, it angers me by itself.
</p>
<p>
If I were to write it, you would have one Lattice method which would directly
work on the hasse diagram, with a <code>return_recomposition</code> boolean flag to return
lists instead of boolean answers. One function, 20 lines, end of the story.
</p>
<p>
Right now, the Lattice method <code>vertical_decomposition</code> contains around 20 lines
of code, none of which has the slightest interest to me. It's just wrapping
things into other things, and testing things that are already tested elsewhere.
</p>
<p>
What I know, however, is that it is impossible for you to get any kind of code
into Sage and to work with it unless you have somebody to review your code. I
surely know that. Depending on what I work on, depending on the times, it is
either easy or hard to get anything in there, and from time to time I think that
it would be better if you were allowed to put any code that you like into Sage
without needing reviewers like me who drag their feet at every occasion.
</p>
<p>
Also, I admit that I do not have the energy to discuss the implementation
details endlessly, and I also hate that this process may require you to
implement code only because the only reviewer you have has a different taste.
</p>
<p>
Truth is, I don't want to be the reason why you cannot work properly on Sage's
code, and I don't have a lot of ways out as not many would do the reviewing job
otherwise. So I will try this: I will implement this as is the most natural to
me, and you can feel free to not use it if you do not like it. Let's see how it
works.
</p>
<p>
Sorry for the painful reviews.
</p>
<p>
Nathann
</p>
<p>
P.S.: the code is at u/ncohen/19123
</p>
TicketjmantysaloSun, 20 Sep 2015 15:55:09 GMT
https://trac.sagemath.org/ticket/19123#comment:34
https://trac.sagemath.org/ticket/19123#comment:34
<p>
Hmm... I continue to think. Or hope that somebody else reviews this.
</p>
<p>
I hope that having this on <code>hasse_diagram.py</code> is useful later - it can be a quick optimization before <code>frattini_sublattice</code>.
</p>
TicketchapotonMon, 28 Sep 2015 16:58:26 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:35
https://trac.sagemath.org/ticket/19123#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
does not apply, needs rebase
</p>
TicketgitMon, 28 Sep 2015 17:34:56 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:36
https://trac.sagemath.org/ticket/19123#comment:36
<ul>
<li><strong>commit</strong>
changed from <em>0abc93861d121a172abfb11203821d34fecfd78e</em> to <em>1356d17b1bd124fa573767ee8b7e5d50798004c0</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=1356d17b1bd124fa573767ee8b7e5d50798004c0"><span class="icon"></span>1356d17</a></td><td><code>Rebasing.</code>
</td></tr></table>
TicketncohenMon, 28 Sep 2015 17:37:15 GMT
https://trac.sagemath.org/ticket/19123#comment:37
https://trac.sagemath.org/ticket/19123#comment:37
<p>
Err. Terminology nazi here: what you did is a 'merge'. A rebase is a difference operation which moves the commits around.
</p>
<p>
Nathann
</p>
TicketjmantysaloMon, 28 Sep 2015 17:38:33 GMTstatus changed
https://trac.sagemath.org/ticket/19123#comment:38
https://trac.sagemath.org/ticket/19123#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Merged. Sorry for wrong term.
</p>
TicketjmantysaloWed, 30 Sep 2015 17:45:56 GMTcc changed
https://trac.sagemath.org/ticket/19123#comment:39
https://trac.sagemath.org/ticket/19123#comment:39
<ul>
<li><strong>cc</strong>
<em>kdilks</em> added
</li>
</ul>
<p>
Kevin, if you are interested in docs, you might want to review this. It does some polishing together with adding little new functionality.
</p>
TicketkdilksSat, 10 Oct 2015 20:56:02 GMT
https://trac.sagemath.org/ticket/19123#comment:40
https://trac.sagemath.org/ticket/19123#comment:40
<p>
I still think that formal definitions should come first, without being labelled as formal definitions, and then informal definitions can come after.
</p>
TicketkdilksSat, 10 Oct 2015 21:10:31 GMT
https://trac.sagemath.org/ticket/19123#comment:41
https://trac.sagemath.org/ticket/19123#comment:41
<p>
I'm not sure if I like the backend code living in <code>hasse_diagram.py</code>. Even if the code applies to more than lattices, you seem to still be making assumptions about the poset being bounded. Plus the initial docstring there is written in a way that implies it only works for lattices.
</p>
TicketjmantysaloMon, 12 Oct 2015 08:46:25 GMT
https://trac.sagemath.org/ticket/19123#comment:42
https://trac.sagemath.org/ticket/19123#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:40" title="Comment 40">kdilks</a>:
</p>
<blockquote class="citation">
<p>
I still think that formal definitions should come first, without being labelled as formal definitions, and then informal definitions can come after.
</p>
</blockquote>
<p>
OK, I can change that.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:41" title="Comment 41">kdilks</a>:
</p>
<blockquote class="citation">
<p>
I'm not sure if I like the backend code living in <code>hasse_diagram.py</code>. Even if the code applies to more than lattices, you seem to still be making assumptions about the poset being bounded. Plus the initial docstring there is written in a way that implies it only works for lattices.
</p>
</blockquote>
<p>
I think that all code in <code>hasse_diagram.py</code> is "internal", i.e. it is user's fault if something break for direct call to it.
</p>
<p>
If this is not in <code>hasse_diagram.py</code>, then I guess it must be copied if I want to optimize <code>frattini_sublattice()</code> with it. Or <code>linear_extensions_number()</code> maybe?
</p>
TicketgitWed, 21 Oct 2015 04:56:04 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:43
https://trac.sagemath.org/ticket/19123#comment:43
<ul>
<li><strong>commit</strong>
changed from <em>1356d17b1bd124fa573767ee8b7e5d50798004c0</em> to <em>b408d0c9dd34b9c07ca3472d7e12615dc7072457</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=b408d0c9dd34b9c07ca3472d7e12615dc7072457"><span class="icon"></span>b408d0c</a></td><td><code>Change order of formal and informal definition.</code>
</td></tr></table>
TicketjmantysaloWed, 21 Oct 2015 04:57:51 GMT
https://trac.sagemath.org/ticket/19123#comment:44
https://trac.sagemath.org/ticket/19123#comment:44
<p>
Better docstring now?
</p>
<p>
If this seems hard one to decide, then I can split the (non-relating) part that rearranges the index of functions.
</p>
TicketjmantysaloSun, 01 Nov 2015 19:15:16 GMT
https://trac.sagemath.org/ticket/19123#comment:45
https://trac.sagemath.org/ticket/19123#comment:45
<p>
<code>ping -c 1 Kevin</code>. This could be nice to have before <a class="closed ticket" href="https://trac.sagemath.org/ticket/18511" title="enhancement: LatticePoset: add is_sublattice() (closed: fixed)">#18511</a>, as this modifies the index of function.
</p>
<p>
(Funny. I have a poset of dependencies between poset-related tickets.)
</p>
TicketjmantysaloFri, 04 Dec 2015 19:42:01 GMT
https://trac.sagemath.org/ticket/19123#comment:46
https://trac.sagemath.org/ticket/19123#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:3" title="Comment 3">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Also, why is it only defined for lattices? The algorithm works in all cases.
</p>
</blockquote>
<p>
Here is a kind of followup: <a class="closed ticket" href="https://trac.sagemath.org/ticket/19659" title="enhancement: Poset: inverse function of ordinal_sum() (closed: fixed)">#19659</a>. I think that it is most natural generalization to all posets.
</p>
TicketjmantysaloMon, 11 Jan 2016 16:12:13 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/19123#comment:47
https://trac.sagemath.org/ticket/19123#comment:47
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-7.0</em>
</li>
</ul>
<p>
Documentation part (i.e. index of functions) done in <a class="closed ticket" href="https://trac.sagemath.org/ticket/19854" title="enhancement: Index of functions to finite lattices (closed: fixed)">#19854</a>, so this one needs work.
</p>
<p>
Also this should be thinked about. There is also <a class="closed ticket" href="https://trac.sagemath.org/ticket/19659" title="enhancement: Poset: inverse function of ordinal_sum() (closed: fixed)">#19659</a> waiting, and in principle it is same thing as this one; a poset that is also a lattice can be expressed as an ordinal sum of two posets only if it vertically decomposable. At least <a class="ext-link" href="http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf"><span class="icon"></span>http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf</a> by Brinkmann and <a class="missing wiki">McKay?</a> uses term "vertically decomposable" with non-lattice posets.
</p>
<p>
(Actually after <a class="closed ticket" href="https://trac.sagemath.org/ticket/19659" title="enhancement: Poset: inverse function of ordinal_sum() (closed: fixed)">#19659</a> it is easy to make a simple function for <a class="closed ticket" href="https://trac.sagemath.org/ticket/19215" title="enhancement: Posets: Add is_series_parallel() (closed: fixed)">#19215</a>, and then use it as a "precompiler" for <a class="closed ticket" href="https://trac.sagemath.org/ticket/14126" title="enhancement: Count Number of Linear Extensions of a Poset (closed: fixed)">#14126</a>. But that's another story.)
</p>
TicketchapotonMon, 14 Mar 2016 19:33:10 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/19123#comment:48
https://trac.sagemath.org/ticket/19123#comment:48
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>b408d0c9dd34b9c07ca3472d7e12615dc7072457</em> to <em>0ee8b96dbb37a87c5c43b4fd0ad6c7ee8c8a97c4</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jmantysalo/vertically_decomposable2</em> to <em>public/19123</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=0ee8b96dbb37a87c5c43b4fd0ad6c7ee8c8a97c4"><span class="icon"></span>0ee8b96</a></td><td><code>Merge branch 'u/jmantysalo/vertically_decomposable2' into 7.1.rc0</code>
</td></tr></table>
TicketkdilksTue, 29 Mar 2016 22:44:12 GMT
https://trac.sagemath.org/ticket/19123#comment:49
https://trac.sagemath.org/ticket/19123#comment:49
<p>
Minor grammatical corrections:
</p>
<ul><li>In <code>vertical_decomposition()</code>, 'Let <code>d_1, \ldots , d_n</code> be elements comparable to every element of the lattice, excluding the top and bottom elements.' Should be rephrased as 'Let <code>d_1, \ldots, d_n</code> be elements (excluding the top and bottom elements) comparable to every element of the lattice.' The original version makes it sound like the top and bottom elements are being excluded from the set of things that <code>d_1...d_n</code> need to be comparable to, instead of being excluded from the set <code>d_1...d_n</code> itself.
</li></ul><ul><li>Immediately following that, 'Let <code>b</code> be THE bottom element and <code>t</code> be the top element.'
</li></ul><ul><li>'Informally said, this returns the lattice SPLIT INTO parts AT every single-element "cutting point".'
</li></ul><ul><li>Under <code>INPUT:</code>, 'return the list OF decomposing elements'.
</li></ul><ul><li>In the definition of <code>is_vertically_decomposable()</code>, 'A lattice is vertically decomposable if it has an element that is comparable to all elements and is NEITHER the bottom NOR the top element.'
</li></ul><p>
Besides that, I think I'm happy with it. I'll just need to check the rendered documentation once those changes are made.
</p>
TicketgitWed, 30 Mar 2016 04:34:25 GMTcommit changed
https://trac.sagemath.org/ticket/19123#comment:50
https://trac.sagemath.org/ticket/19123#comment:50
<ul>
<li><strong>commit</strong>
changed from <em>0ee8b96dbb37a87c5c43b4fd0ad6c7ee8c8a97c4</em> to <em>bf4d108440d0533d57cd433d0f0432fab630d193</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=bf4d108440d0533d57cd433d0f0432fab630d193"><span class="icon"></span>bf4d108</a></td><td><code>Docstring corrections.</code>
</td></tr></table>
TicketjmantysaloWed, 30 Mar 2016 04:39:09 GMT
https://trac.sagemath.org/ticket/19123#comment:51
https://trac.sagemath.org/ticket/19123#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19123#comment:49" title="Comment 49">kdilks</a>:
</p>
<blockquote class="citation">
<p>
Minor grammatical corrections:
</p>
</blockquote>
<p>
Thanks! Done those.
</p>
<blockquote class="citation">
<ul><li>'Informally said, this returns the lattice SPLIT INTO parts AT every single-element "cutting point".'
</li></ul></blockquote>
<p>
These are hard ones... In Finnish 'hila'='lattice', 'hilassani'='in my lattice' etc.
</p>
TicketkdilksWed, 30 Mar 2016 18:04:55 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/19123#comment:52
https://trac.sagemath.org/ticket/19123#comment:52
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Kevin Dilks</em>
</li>
</ul>
TicketvbraunThu, 31 Mar 2016 18:41:46 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19123#comment:53
https://trac.sagemath.org/ticket/19123#comment:53
<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/19123</em> to <em>bf4d108440d0533d57cd433d0f0432fab630d193</em>
</li>
</ul>
Ticket