Sage: Ticket #25080: code for Cartesian factorization of posets
https://trac.sagemath.org/ticket/25080
<p>
as a very useful tool to have
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/25080
Trac 1.1.6chapotonMon, 02 Apr 2018 15:35:57 GMTstatus, description changed; cc, commit, branch set
https://trac.sagemath.org/ticket/25080#comment:1
https://trac.sagemath.org/ticket/25080#comment:1
<ul>
<li><strong>cc</strong>
<em>jmantysalo</em> added
</li>
<li><strong>commit</strong>
set to <em>aaafd6a148397470a9cb6350b50991fc4b8b1e85</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/25080?action=diff&version=1">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/chapoton/25080</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=aaafd6a148397470a9cb6350b50991fc4b8b1e85"><span class="icon"></span>aaafd6a</a></td><td><code>code for cartesian factorisation of posets</code>
</td></tr></table>
TicketgitMon, 02 Apr 2018 16:01:45 GMTcommit changed
https://trac.sagemath.org/ticket/25080#comment:2
https://trac.sagemath.org/ticket/25080#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>aaafd6a148397470a9cb6350b50991fc4b8b1e85</em> to <em>e1d1276ec1309b296a312bfc8cbc587d1981b947</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=e1d1276ec1309b296a312bfc8cbc587d1981b947"><span class="icon"></span>e1d1276</a></td><td><code>adding doi</code>
</td></tr></table>
TicketjmantysaloMon, 02 Apr 2018 17:58:41 GMTstatus changed
https://trac.sagemath.org/ticket/25080#comment:3
https://trac.sagemath.org/ticket/25080#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Fails with disconnected posets, see <code>posets.AntichainPoset(4).factorize()</code>. Works with the empty poset, but a test for the corner case would be nice.
</p>
<p>
Maybe this is the best name for this function; however, what will be the name for the converse of ordinal product?
</p>
<p>
I think that a factor of a lattice is always a lattice. Or is it? Got to think about this later.
</p>
<p>
E: Also, a test where the underlying undirected graph can be factorized, but the poset can not, would be nice.
</p>
TicketjmantysaloMon, 02 Apr 2018 18:04:04 GMT
https://trac.sagemath.org/ticket/25080#comment:4
https://trac.sagemath.org/ticket/25080#comment:4
<p>
Wrong indentation in the reference, i.e. may break Sphinx.
</p>
TicketgitMon, 02 Apr 2018 19:00:44 GMTcommit changed
https://trac.sagemath.org/ticket/25080#comment:5
https://trac.sagemath.org/ticket/25080#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>e1d1276ec1309b296a312bfc8cbc587d1981b947</em> to <em>c5e9234572681e19ede6a4e4dfbbd510996c09b5</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=c5e9234572681e19ede6a4e4dfbbd510996c09b5"><span class="icon"></span>c5e9234</a></td><td><code>trac 25080 adding check that poset is connected</code>
</td></tr></table>
TicketgitMon, 02 Apr 2018 19:20:57 GMTcommit changed
https://trac.sagemath.org/ticket/25080#comment:6
https://trac.sagemath.org/ticket/25080#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>c5e9234572681e19ede6a4e4dfbbd510996c09b5</em> to <em>4a72873d0c8a9bb4daebc0effc446e29c305b46f</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=4a72873d0c8a9bb4daebc0effc446e29c305b46f"><span class="icon"></span>4a72873</a></td><td><code>trac 25080 adding more tests</code>
</td></tr></table>
TicketchapotonMon, 02 Apr 2018 19:45:01 GMT
https://trac.sagemath.org/ticket/25080#comment:7
https://trac.sagemath.org/ticket/25080#comment:7
<p>
Thanks for the comments, Jori.
</p>
<p>
For the name, my favorite choice would be just "factor". Other possibilies are "factor_cartesian" and "factor_ordinal" ; or maybe "cartesian_factor" and "ordinal_factor".
</p>
<p>
For the lattice property, I think this holds for the factors, and the same for <a class="missing wiki">MeetSemiLattice?</a>, etc. But I do not feel any need for that.
</p>
TicketjmantysaloTue, 03 Apr 2018 04:19:56 GMT
https://trac.sagemath.org/ticket/25080#comment:8
https://trac.sagemath.org/ticket/25080#comment:8
<p>
See <a class="ext-link" href="http://www.phy.olemiss.edu/~luca/Topics/p/poset_types.html"><span class="icon"></span>http://www.phy.olemiss.edu/~luca/Topics/p/poset_types.html</a>: "Prime poset: One such that all its autonomous subsets are trivial." Is this the same concept with different words? If not, should that be mentioned in <code>OUTPUT</code> section?
</p>
<p>
Maybe "factor" or "factorize" is good, as also plain "product" means the Cartesian product.
</p>
<p>
Is it really a <code>ValueError</code> to run this with unconnected posets? IMO it should be seen as a missing implementation, as an unconnected poset can be a Cartesian product of two posets.
</p>
TicketjmantysaloTue, 03 Apr 2018 06:00:00 GMT
https://trac.sagemath.org/ticket/25080#comment:9
https://trac.sagemath.org/ticket/25080#comment:9
<p>
Error in seealso-link, cartesian_product() should be product().
</p>
<p>
Also there is now two seealso-blocks in product(), and it seems a little strange.
</p>
TicketgitTue, 03 Apr 2018 06:29:45 GMTcommit changed
https://trac.sagemath.org/ticket/25080#comment:10
https://trac.sagemath.org/ticket/25080#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>4a72873d0c8a9bb4daebc0effc446e29c305b46f</em> to <em>6ad6d4400abe1e32812683da1a8301283bdb199c</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=6ad6d4400abe1e32812683da1a8301283bdb199c"><span class="icon"></span>6ad6d44</a></td><td><code>trac 25080 change name to factor, other details</code>
</td></tr></table>
TicketchapotonTue, 03 Apr 2018 06:31:25 GMTstatus changed
https://trac.sagemath.org/ticket/25080#comment:11
https://trac.sagemath.org/ticket/25080#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
All done.
</p>
<p>
There remains, maybe, the question of using <code>LatticePoset</code> for the factors when handling products of lattices.
</p>
TicketjmantysaloTue, 03 Apr 2018 06:36:45 GMT
https://trac.sagemath.org/ticket/25080#comment:12
https://trac.sagemath.org/ticket/25080#comment:12
<p>
Thanks. Now, to the code. When is <code>if A1 != B1:</code> evaluated as true? I guess you have implemented an algorithm to factor general digraph, and for poset you don't need all of that.
</p>
TicketchapotonTue, 03 Apr 2018 07:01:25 GMT
https://trac.sagemath.org/ticket/25080#comment:13
https://trac.sagemath.org/ticket/25080#comment:13
<p>
The idea is to check that every little square is a commutative square. There are certainly better ways than what I did quickly. The <code>A1 != B1</code> test is meant to check that parallel arrows in one square go the same way.
</p>
<p>
The algorithm would possibly work for simple digraphs with no 2-cycles. Given this restricted domain, I think it is best to keep it here for the moment.
</p>
TicketjmantysaloTue, 03 Apr 2018 07:42:30 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/25080#comment:14
https://trac.sagemath.org/ticket/25080#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jori Mäntysalo</em>
</li>
</ul>
<p>
OK, I'll mark this as positive review. (Change milestone when 8.3 is available.)
</p>
<p>
I don't see how there could be parallel arrows when the graph is the Hasse diagram of some poset. However, almost all the time is spent in factoring undirected graph, so this makes no real difference.
</p>
<p>
Output type for lattices can be changed later.
</p>
<p>
There are some shortcuts that could be used: for example the numbers of minimal elements must not be a prime. Also the number of edges in the Hasse diagram can show that a poset can't be a Cartesian product etc. However, all this can also be added later.
</p>
TicketjmantysaloTue, 17 Apr 2018 08:12:50 GMTmilestone changed
https://trac.sagemath.org/ticket/25080#comment:15
https://trac.sagemath.org/ticket/25080#comment:15
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.2</em> to <em>sage-8.3</em>
</li>
</ul>
TicketvbraunSat, 12 May 2018 11:46:31 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/25080#comment:16
https://trac.sagemath.org/ticket/25080#comment:16
<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/chapoton/25080</em> to <em>6ad6d4400abe1e32812683da1a8301283bdb199c</em>
</li>
</ul>
Ticket