Sage: Ticket #10998: Categories for posets
https://trac.sagemath.org/ticket/10998
<p>
This patch creates categories for posets and lattices, refactors the
poset code, and adds new features. See the header of the patch for a
complete description.
</p>
<p>
Apply: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/10998/trac_10998-categories-posets-nt.patch" title="Attachment 'trac_10998-categories-posets-nt.patch' in Ticket #10998">trac_10998-categories-posets-nt.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/10998/trac_10998-categories-posets-nt.patch" title="Download"></a>
</p>
<p>
Apply on sagenb repo: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/10998/trac_10998-categories-posets-sagenb-nt.patch" title="Attachment 'trac_10998-categories-posets-sagenb-nt.patch' in Ticket #10998">trac_10998-categories-posets-sagenb-nt.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/10998/trac_10998-categories-posets-sagenb-nt.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10998
Trac 1.1.6nthieryWed, 23 Mar 2011 16:07:35 GMTtype, description changed
https://trac.sagemath.org/ticket/10998#comment:1
https://trac.sagemath.org/ticket/10998#comment:1
<ul>
<li><strong>type</strong>
changed from <em>task</em> to <em>enhancement</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=1">diff</a>)
</li>
</ul>
TicketnthieryMon, 28 Mar 2011 14:28:33 GMTstatus, description changed
https://trac.sagemath.org/ticket/10998#comment:2
https://trac.sagemath.org/ticket/10998#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=2">diff</a>)
</li>
</ul>
TicketnthieryMon, 28 Mar 2011 14:31:29 GMTdescription changed
https://trac.sagemath.org/ticket/10998#comment:3
https://trac.sagemath.org/ticket/10998#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=3">diff</a>)
</li>
</ul>
TicketnthieryMon, 28 Mar 2011 15:02:09 GMTdescription changed
https://trac.sagemath.org/ticket/10998#comment:4
https://trac.sagemath.org/ticket/10998#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=4">diff</a>)
</li>
</ul>
TicketnilesTue, 29 Mar 2011 12:32:16 GMTcc changed
https://trac.sagemath.org/ticket/10998#comment:5
https://trac.sagemath.org/ticket/10998#comment:5
<ul>
<li><strong>cc</strong>
<em>niles</em> added
</li>
</ul>
TicketnthieryMon, 04 Apr 2011 22:08:10 GMT
https://trac.sagemath.org/ticket/10998#comment:6
https://trac.sagemath.org/ticket/10998#comment:6
<p>
Fixed trivial non commutation with trac_10193-graded_enumerated_sets-nt.patch in the Sage-Combinat queue. In principle the patch should now apply on vanilla sage + listed dependencies.
</p>
Ticketstumpc5Tue, 05 Apr 2011 14:37:16 GMT
https://trac.sagemath.org/ticket/10998#comment:7
https://trac.sagemath.org/ticket/10998#comment:7
<p>
Salut Nicolas,
</p>
<p>
I must say: there is a lot of code where I don't really understand what you do, and why you do it. E.g., which code is generic enough to put in categories and which is not, how are examples organized, how do you properly test the code, ...
</p>
<p>
In my (not yet final) review patch, I place some questions on implementations, some suggestions for additional methods, and I fixed several typos.
</p>
<p>
Best, Christian
</p>
TicketnthieryTue, 05 Apr 2011 15:58:58 GMT
https://trac.sagemath.org/ticket/10998#comment:8
https://trac.sagemath.org/ticket/10998#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:7" title="Comment 7">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
I must say: there is a lot of code where I don't really understand
what you do, and why you do it.
</p>
</blockquote>
<p>
Hmm, more specific questions (like the one below) would be useful to
get a constructive discussion :-)
</p>
<blockquote class="citation">
<p>
E.g., which code is generic enough to put in categories and which is
not,
</p>
</blockquote>
<p>
The rule of thumb is: does the code use the data structure or not?
For example, a method like has_top uses the internal hasse diagram,
and therefore remains in Poset. On the other hand a method like
join_irreducibles just requires that there is a method "lower_covers",
and so can be implemented generically in the category.
</p>
<p>
But that's just a rule thumb; I left in Poset all the code that was on
the edge, so as to avoid moving too much code around.
</p>
<blockquote class="citation">
<p>
how are examples organized, how do you properly test the code, ...
</p>
</blockquote>
<p>
Are those questions about the category framework in general, or about
this specific patch?
</p>
<blockquote class="citation">
<p>
In my (not yet final) review patch, I place some questions on
implementations, some suggestions for additional methods, and I
fixed several typos.
</p>
</blockquote>
<p>
Ok, thanks!
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryThu, 21 Apr 2011 21:13:07 GMTdescription, milestone changed; reviewer set
https://trac.sagemath.org/ticket/10998#comment:9
https://trac.sagemath.org/ticket/10998#comment:9
<ul>
<li><strong>reviewer</strong>
set to <em>Franco Saliola, Christian Stump, Nicolas M. Thiéry</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=9">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.0</em> to <em>sage-4.7.1</em>
</li>
</ul>
Ticketstumpc5Fri, 22 Apr 2011 15:27:24 GMT
https://trac.sagemath.org/ticket/10998#comment:10
https://trac.sagemath.org/ticket/10998#comment:10
<p>
Apply only trac_10998-categories-posets-nt.patch
</p>
TickethivertFri, 22 Apr 2011 22:14:46 GMT
https://trac.sagemath.org/ticket/10998#comment:11
https://trac.sagemath.org/ticket/10998#comment:11
<p>
There where a few bad sphinx markup. I just pushed a review patch on sage-combinat queue. I let you decide if you want to fold it or upload it.
</p>
<p>
Cheers,
</p>
<p>
Florent
</p>
TicketnthierySat, 23 Apr 2011 02:15:19 GMT
https://trac.sagemath.org/ticket/10998#comment:12
https://trac.sagemath.org/ticket/10998#comment:12
<p>
Folded; thanks!
</p>
TicketnthierySat, 23 Apr 2011 02:43:58 GMT
https://trac.sagemath.org/ticket/10998#comment:13
https://trac.sagemath.org/ticket/10998#comment:13
<p>
Fixed failing test.
</p>
TicketnthierySat, 23 Apr 2011 03:03:50 GMT
https://trac.sagemath.org/ticket/10998#comment:14
https://trac.sagemath.org/ticket/10998#comment:14
<p>
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
</p>
TickethivertSat, 23 Apr 2011 12:30:54 GMTreviewer changed
https://trac.sagemath.org/ticket/10998#comment:15
https://trac.sagemath.org/ticket/10998#comment:15
<ul>
<li><strong>reviewer</strong>
changed from <em>Franco Saliola, Christian Stump, Nicolas M. Thiéry</em> to <em>Franco Saliola, Christian Stump, Nicolas M. Thiéry, Florent Hivert</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:14" title="Comment 14">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
</p>
</blockquote>
<p>
I also just spotted a few more wrong sphinx markup ! I'm fixing those.
</p>
TickethivertSat, 23 Apr 2011 13:30:19 GMT
https://trac.sagemath.org/ticket/10998#comment:16
https://trac.sagemath.org/ticket/10998#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:15" title="Comment 15">hivert</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:14" title="Comment 14">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
</p>
</blockquote>
<p>
I also just spotted a few more wrong sphinx markup ! I'm fixing those.
</p>
</blockquote>
<p>
Please see my new review patch on sage-combinat queue <code>trac_10998-categories-posets-docfix-fh.patch</code>
</p>
TicketsaliolaThu, 05 May 2011 01:37:00 GMTstatus changed
https://trac.sagemath.org/ticket/10998#comment:17
https://trac.sagemath.org/ticket/10998#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I started with a fresh install of sage-4.7.rc1 and applied the patches at <a class="closed ticket" href="https://trac.sagemath.org/ticket/9065" title="enhancement: Add support for facade parents (closed: fixed)">#9065</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/10938" title="enhancement: Add subset and superset methods to Sage's finite sets ... (closed: fixed)">#10938</a>, followed by the patch for this ticket on the sage-combinat queue. I get a the following doctest failures.
</p>
<pre class="wiki">The following tests failed:
sage -t devel/sage-trac/sage/geometry/fan_morphism.py # 25 doctests failed
sage -t devel/sage-trac/sage/geometry/fan.py # 4 doctests failed
sage -t devel/sage-trac/sage/schemes/generic/toric_variety.py # 1 doctests failed
sage -t devel/sage-trac/sage/schemes/generic/toric_divisor.py # 3 doctests failed
sage -t devel/sage-trac/sage/schemes/generic/toric_chow_group.py # 10 doctests failed
sage -t devel/sage-trac/sage/structure/sage_object.pyx # 1 doctests failed
</pre><p>
I verified that they are not caused by the other patches. (I also get these errors on 4.6.2 with the sage-combinat patches applied.)
</p>
<p>
I don't understand the problem. If you copy and paste the offending doctests into the sage command-line, I don't get the errors reported by the doctest system. Any ideas?
</p>
TicketnthieryThu, 05 May 2011 02:11:09 GMTcc changed
https://trac.sagemath.org/ticket/10998#comment:18
https://trac.sagemath.org/ticket/10998#comment:18
<ul>
<li><strong>cc</strong>
<em>novoselt</em> added
</li>
</ul>
<p>
Oh right, I had forgotten about those. I tried a bit to find the problem, but to not avail yet.
</p>
<p>
Andrey, would you have any clue?
</p>
TicketnovoseltThu, 05 May 2011 05:04:35 GMT
https://trac.sagemath.org/ticket/10998#comment:19
https://trac.sagemath.org/ticket/10998#comment:19
<p>
Hi Nicolas, thanks for ccing me!
</p>
<p>
Given that the problem is not reproducible in the command line, I am not exactly sure how to attack it, but we probably need to focus on the failing doctest in <code>fan.py</code>.
</p>
<p>
The problem as shown by the doctest framework is that cones which are supposed to know that they sit inside a fan appear to be "standalone" and breaking this relation messes up everything that builds up on top of it.
</p>
<p>
I'll try to trace it down further, but it may take me a few days due to traveling and conferencing...
</p>
TicketnthieryThu, 05 May 2011 05:17:33 GMT
https://trac.sagemath.org/ticket/10998#comment:20
https://trac.sagemath.org/ticket/10998#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:19" title="Comment 19">novoselt</a>:
</p>
<blockquote class="citation">
<p>
Hi Nicolas, thanks for ccing me!
</p>
<p>
Given that the problem is not reproducible in the command line, I am not exactly sure how to attack it, but we probably need to focus on the failing doctest in <code>fan.py</code>.
</p>
<p>
The problem as shown by the doctest framework is that cones which are supposed to know that they sit inside a fan appear to be "standalone" and breaking this relation messes up everything that builds up on top of it.
</p>
<p>
I'll try to trace it down further, but it may take me a few days due to traveling and conferencing...
</p>
</blockquote>
<p>
Thanks!
</p>
<p>
For the record: finite posets and their elements, now have <a class="missing wiki">UniqueRepresentation?</a>. This could have an influence if the same poset is created several times when constructing several fans.
</p>
TicketnovoseltThu, 05 May 2011 05:40:11 GMT
https://trac.sagemath.org/ticket/10998#comment:21
https://trac.sagemath.org/ticket/10998#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:20" title="Comment 20">nthiery</a>:
</p>
<blockquote class="citation">
<p>
For the record: finite posets and their elements, now have <a class="missing wiki">UniqueRepresentation?</a>. This could have an influence if the same poset is created several times when constructing several fans.
</p>
</blockquote>
<p>
Yes, this is it. Repeating the failing code twice in the command line reproduced the error. This raises two questions:
1) Out of curiosity: Why does it show up in doctests? Shouldn't the state of Sage be clean before running a new test?
2) To the point: How to fix it?
</p>
<p>
I really don't want to make fans unique at this point as I am planning some adjustments to them and related objects.
</p>
<p>
Does uniqueness test rely on <code>==</code> test? Is there any way to change it? Currently <code>==</code> for fans checks that fans have the same rays and the same generating cones in the same order. Things relates to facets require even stronger <code>is</code>-equivalence. On the other hand, Volker votes for <code>==</code> being mathematical equivalence without taking order into account. Such equivalence definitely would not be acceptable deep inside implementation which relies on fixed order.
</p>
<p>
So I guess my preferred solution for now would be to trick posets into creating different face lattices for fans and cones even if they are <code>==</code>. Can I somehow attach <code>id(fan)</code> to the poset without altering its structure?..
</p>
TicketsaliolaThu, 05 May 2011 16:32:03 GMT
https://trac.sagemath.org/ticket/10998#comment:22
https://trac.sagemath.org/ticket/10998#comment:22
<p>
Here is a reviewer patch. This applies on top of the latest version of Nicolas's patch that can be found on the sage-combinat queue. These are mostly documentation fixes.
</p>
<p>
With the exception of the issue highlighted above, I give a positive review to the changes.
</p>
<ul><li>someone needs to review my patch
</li><li>someone needs to post a patch addressing the broken doctests
</li></ul>
TicketsaliolaThu, 05 May 2011 18:30:00 GMTdescription changed
https://trac.sagemath.org/ticket/10998#comment:23
https://trac.sagemath.org/ticket/10998#comment:23
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=23">diff</a>)
</li>
</ul>
<p>
I made sure that the patches (on the sage-combinat queue) apply on top of Rob Beezer's recent patches surrounding posets (ticket numbers <a class="closed ticket" href="https://trac.sagemath.org/ticket/11289" title="enhancement: Random posets, documentation and error-checking (closed: fixed)">#11289</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11293" title="enhancement: All relations of a poset (closed: fixed)">#11293</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11292" title="enhancement: Allow broader inputs to lattice meet and join (closed: fixed)">#11292</a>). There was a slight conflict with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11289" title="enhancement: Random posets, documentation and error-checking (closed: fixed)">#11289</a>, so this patch now depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11289" title="enhancement: Random posets, documentation and error-checking (closed: fixed)">#11289</a>. I updated the description accordingly.
</p>
TicketsaliolaThu, 05 May 2011 18:31:10 GMT
https://trac.sagemath.org/ticket/10998#comment:24
https://trac.sagemath.org/ticket/10998#comment:24
<p>
My previous comment refers to the patches on the sage-combinat queue.
</p>
TicketnthieryTue, 10 May 2011 14:35:00 GMTkeywords set
https://trac.sagemath.org/ticket/10998#comment:25
https://trac.sagemath.org/ticket/10998#comment:25
<ul>
<li><strong>keywords</strong>
<em>days30</em> added
</li>
</ul>
TicketchapotonFri, 10 Jun 2011 07:57:12 GMT
https://trac.sagemath.org/ticket/10998#comment:26
https://trac.sagemath.org/ticket/10998#comment:26
<p>
Trying to help the buildbot to do its job
</p>
<p>
Apply trac_10998-categories-posets-nt.patch
Apply trac_10998-review-fs.patch
</p>
TicketchapotonFri, 10 Jun 2011 08:02:06 GMT
https://trac.sagemath.org/ticket/10998#comment:27
https://trac.sagemath.org/ticket/10998#comment:27
<p>
try again
</p>
<p>
Apply trac_10998-categories-posets-nt.patch trac_10998-review-fs.patch
</p>
TicketchapotonFri, 10 Jun 2011 19:10:10 GMTdependencies set
https://trac.sagemath.org/ticket/10998#comment:28
https://trac.sagemath.org/ticket/10998#comment:28
<ul>
<li><strong>dependencies</strong>
set to <em>#11289, #10938, #9065</em>
</li>
</ul>
TicketchapotonFri, 10 Jun 2011 19:26:58 GMT
https://trac.sagemath.org/ticket/10998#comment:29
https://trac.sagemath.org/ticket/10998#comment:29
<p>
trying to help the bot again
</p>
<p>
Apply trac_10998-categories-posets-nt.patch trac_10998-review-fs.patch
</p>
TicketchapotonFri, 10 Jun 2011 20:51:56 GMT
https://trac.sagemath.org/ticket/10998#comment:30
https://trac.sagemath.org/ticket/10998#comment:30
<p>
ok, the bot has found a HUNK problem in poset_examples.py
</p>
<p>
Could somebody solve that ?
</p>
TicketnthieryTue, 14 Jun 2011 10:33:46 GMT
https://trac.sagemath.org/ticket/10998#comment:31
https://trac.sagemath.org/ticket/10998#comment:31
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:30" title="Comment 30">chapoton</a>:
</p>
<blockquote class="citation">
<p>
ok, the bot has found a HUNK problem in poset_examples.py
</p>
<p>
Could somebody solve that ?
</p>
</blockquote>
<p>
Done! There just remains the cone issue.
</p>
TicketnthieryTue, 14 Jun 2011 10:43:19 GMT
https://trac.sagemath.org/ticket/10998#comment:32
https://trac.sagemath.org/ticket/10998#comment:32
<p>
Btw: I reviewed and folded in Franco's reviewer's patch. Thanks Franco!
</p>
TicketnthieryTue, 14 Jun 2011 11:12:07 GMT
https://trac.sagemath.org/ticket/10998#comment:33
https://trac.sagemath.org/ticket/10998#comment:33
<blockquote>
<p>
Hi Andrei,
</p>
</blockquote>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:21" title="Comment 21">novoselt</a>:
</p>
<blockquote class="citation">
<p>
2) To the point: How to fix it?
</p>
<p>
I really don't want to make fans unique at this point as I am planning some adjustments to them and related objects.
</p>
<p>
Does uniqueness test rely on <code>==</code> test? Is there any way to change it? Currently <code>==</code> for fans checks that fans have the same rays and the same generating cones in the same order. Things relates to facets require even stronger <code>is</code>-equivalence. On the other hand, Volker votes for <code>==</code> being mathematical equivalence without taking order into account. Such equivalence definitely would not be acceptable deep inside implementation which relies on fixed order.
</p>
<p>
So I guess my preferred solution for now would be to trick posets into creating different face lattices for fans and cones even if they are <code>==</code>. Can I somehow attach <code>id(fan)</code> to the poset without altering its structure?..
</p>
</blockquote>
<p>
I have (finally!) just looked at this again. I traced through the execution of <code>f.cone_containing(0)</code>, and did not find the place where the construction of the cone (and in particular its unique representation or not) depended on a poset. Could you give me a pointer? Or ideally, a minimal example where two cones are constructed involving the same poset, and where the cones should be different (but are not with this patch)?
</p>
<p>
We are both at FPSAC with Franco; it would be great if we could finish this patch today or tomorrow.
</p>
<p>
Thanks!
</p>
TicketnovoseltTue, 14 Jun 2011 17:23:54 GMTkeywords, cc changed
https://trac.sagemath.org/ticket/10998#comment:34
https://trac.sagemath.org/ticket/10998#comment:34
<ul>
<li><strong>keywords</strong>
<em>sd31</em> added
</li>
<li><strong>cc</strong>
<em>vbraun</em> added
</li>
</ul>
<p>
Hi Nicolas!
</p>
<p>
With the patch:
</p>
<pre class="wiki">sage: F1 = FaceFan(lattice_polytope.octahedron(3))
sage: F2 = FaceFan(lattice_polytope.octahedron(3))
sage: F1 == F2
True
sage: F1 is F2
False
sage: F1(2)[0]
2-d cone of Rational polyhedral fan in 3-d lattice N
sage: F1(2)[0].ambient() is F1
True
sage: F2(2)[0].ambient() is F2
False
</pre><p>
The last command is heavily assumed to return True in the toric-related code. The problem is that when the cone lattice of <code>F2</code> is constructed, it is considered as the same poset as the cone lattice of <code>F1</code> and so all cones of <code>F2</code> become linked to <code>F1</code>. Possible solutions are:
</p>
<ul><li>Make cone lattices of fans which are "==" but not "is" distinct. This should fix the issue without any complications as it will basically restore the current state.
</li><li>Make "==" and "is" comparisons the same for fans. I think that this is undesirable as there are arguments for making "==" be the mathematical equivalence, which is even weaker than the current behaviour.
</li><li>Make fans unique based on the ordered list of rays and cone generators. This should fix the issue but may have consequences. Also, while in general unique fans may be good, it would be nice to still have a possibility to make "==" the mathematical equivalence and IMHO it would be absolutely terrible for performance and convenience of use if uniqueness of fans was based on their mathematical equivalence.
</li></ul><p>
Note: I'd rather not make cones unique based on the ordered list of rays as I want to have a possibility to create different cones with the same order of rays but different order of facet normals. This is not currently implemented but would be extremely convenient for handling all kinds of dualities and correspondences.
</p>
<p>
So, in short, I prefer to be able to create different posets of cones for fans which are "==".
</p>
<p>
Thank you,
Andrey
</p>
TicketnthieryTue, 14 Jun 2011 17:31:27 GMT
https://trac.sagemath.org/ticket/10998#comment:35
https://trac.sagemath.org/ticket/10998#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:34" title="Comment 34">novoselt</a>:
</p>
<blockquote class="citation">
<p>
Hi Nicolas!
</p>
<p>
With the patch:
</p>
<pre class="wiki">sage: F1 = FaceFan(lattice_polytope.octahedron(3))
sage: F2 = FaceFan(lattice_polytope.octahedron(3))
sage: F1 == F2
True
sage: F1 is F2
False
sage: F1(2)[0]
2-d cone of Rational polyhedral fan in 3-d lattice N
sage: F1(2)[0].ambient() is F1
True
sage: F2(2)[0].ambient() is F2
False
</pre><p>
The last command is heavily assumed to return True in the toric-related code. The problem is that when the cone lattice of <code>F2</code> is constructed, it is considered as the same poset as the cone lattice of <code>F1</code> and so all cones of <code>F2</code> become linked to <code>F1</code>. Possible solutions are:
</p>
<ul><li>Make cone lattices of fans which are "==" but not "is" distinct. This should fix the issue without any complications as it will basically restore the current state.
</li><li>Make "==" and "is" comparisons the same for fans. I think that this is undesirable as there are arguments for making "==" be the mathematical equivalence, which is even weaker than the current behaviour.
</li><li>Make fans unique based on the ordered list of rays and cone generators. This should fix the issue but may have consequences. Also, while in general unique fans may be good, it would be nice to still have a possibility to make "==" the mathematical equivalence and IMHO it would be absolutely terrible for performance and convenience of use if uniqueness of fans was based on their mathematical equivalence.
</li></ul><p>
Note: I'd rather not make cones unique based on the ordered list of rays as I want to have a possibility to create different cones with the same order of rays but different order of facet normals. This is not currently implemented but would be extremely convenient for handling all kinds of dualities and correspondences.
</p>
<p>
So, in short, I prefer to be able to create different posets of cones for fans which are "==".
</p>
</blockquote>
<p>
Thanks a lot! I'll look at this tonight.
</p>
<p>
I am still confused a bit: do you know where technically in the cone code is there an <code></code>==<code></code> or <code></code>is<code></code> test done on some posets, which cause the change of behaviour above?
</p>
TicketnovoseltTue, 14 Jun 2011 18:32:27 GMT
https://trac.sagemath.org/ticket/10998#comment:36
https://trac.sagemath.org/ticket/10998#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:35" title="Comment 35">nthiery</a>:
</p>
<blockquote class="citation">
<p>
I am still confused a bit: do you know where technically in the cone code is there an <code></code>==<code></code> or <code></code>is<code></code> test done on some posets, which cause the change of behaviour above?
</p>
</blockquote>
<p>
When a fan computes its cone lattice, it constructs all of the required cones (which are bound to the correct fan) and then converts them into a poset. All further methods work with this poset. Since now posets are unique and involve "==" checks for fans and cones, the poset of the second fan is treated as the same one as the first one, so the second fan gets a poset of cones bound to the first fan. The precise method of fans is <code>_compute_cone_lattice</code>.
</p>
<p>
Now, I have actually realized, that it will have the same issue for cones, it just does not break the existent doctests yet:
</p>
<pre class="wiki">sage: C1 = Cone([(0,1)])
sage: C2 = Cone([(0,1)])
sage: C1 == C2
True
sage: C1 is C2
False
sage: C1.facets()[0]
0-d face of 1-d cone in 2-d lattice N
sage: C1.facets()[0].ambient() is C1
True
sage: C2.facets()[0].ambient() is C1
True
sage: C2.facets()[0].ambient() is C2
False
</pre><p>
The code for cones is in <code>face_lattice</code> method. Again, I don't want to get the same posets even for cones that have the same order of rays, and there are arguments that "==" should treat rays as sets. So it would be nice to force different posets for "==" objects.
</p>
<p>
Why exactly are posets unique? Isn't it expensive to check that two posets are equivalent? I am interested in dealing with face lattices of about 10<sup>5</sup> elements, how long would it take to check their equality? Maybe elements of posets should be unique, but not posets themselves?
</p>
TickethivertTue, 14 Jun 2011 21:17:11 GMT
https://trac.sagemath.org/ticket/10998#comment:37
https://trac.sagemath.org/ticket/10998#comment:37
<blockquote class="citation">
<p>
Why exactly are posets unique? Isn't it expensive to check that two posets
are equivalent? I am interested in dealing with face lattices of about 10<sup>5</sup>
elements, how long would it take to check their equality? Maybe elements of
posets should be unique, but not posets themselves?
</p>
</blockquote>
<p>
As far as I understood, there is not check for equivalence, is it ? Actually,
I'm not sure what you mean by equivalence opposed to equality. However I see
no reason why two posets with the same element and the same ordering should be
different object: mathematically they are the same set with the same
ordering...
</p>
<p>
More pragmatically, I have some code using poset as key for hash tables. At
first I didn't ensure that posets were unique then the code end-up spending
all the time comparing poset that is comparing the underlying graph.
</p>
<p>
In my opinion, if you need to see two equal poset as different, this is
because you have some more information on those poset (eg: some tag saying
where it come from). If it is the case, I have the feeling that you should
inherit a class from poset which adds the tag and use it for comparison and
creation so that two differently tagged posets will be different for is as for
==.
</p>
<p>
My two cents,
</p>
<p>
Florent
</p>
TicketnovoseltTue, 14 Jun 2011 21:38:24 GMT
https://trac.sagemath.org/ticket/10998#comment:38
https://trac.sagemath.org/ticket/10998#comment:38
<p>
As I understand the uniqueness framework, it is based on checking that the input to the constructor is the same as was already used before. So if posets are unique, the constructor input is somehow normalized (using Hasse diagram, perhaps?) and then compared with those that were already constructed.
</p>
<p>
In this cases fans and cones report that "==" is true for all the elements and therefore the posets are considered to be the same and become a unique object.
</p>
<p>
However for implementation purposes there is a big difference between treating two cones as cones of the same fan and as two arbitrary cones. In the first case the intersection is internally computed as the intersection of two ordered sets of integers. In the second one it involves constructing a new polyhedral object and determining its minimal generator set. With old PALP/cdd interfaces this takes forever (compared to intersection two short lists of integers). With Volker's new PPL interface it is much better, yet still it requires many more operations.
</p>
<p>
I agree that we have here more structure than poset itself but it is basically the question of "the same" and "isomorphic". We have a similar issue with toric lattices: if M = ZZ<sup>n</sup>, then the dual space is also ZZ<sup>n</sup>, yet they are isomorphic but not equal. It would be great actually to have some standard way in Sage to tag objects. Maybe ZZ is unique as a ring, but it is possible that one wants to consider several modules which are isomorphic to ZZ and treat them as different ones.
</p>
TicketnthieryThu, 23 Jun 2011 10:34:09 GMTstatus changed
https://trac.sagemath.org/ticket/10998#comment:39
https://trac.sagemath.org/ticket/10998#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
The updated patch fixes the issue with cones and fans by adding a <code></code>key<code></code> argument to <a class="missing wiki">FinitePoset?</a>. Using it, equal but not identical Cone's and Fan's create distinct posets.
I also folded in Christian's order_complex fix.
</p>
<p>
To me the whole thing seems ready to go.
</p>
<p>
Sorry, I screwed up and refreshed my changes directly in the main patch. So I have attached a diff between the previous and new version. It's not super-readable, but it should point to those few places that need review.
</p>
TicketnthieryThu, 23 Jun 2011 10:48:22 GMT
https://trac.sagemath.org/ticket/10998#comment:40
https://trac.sagemath.org/ticket/10998#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:38" title="Comment 38">novoselt</a>:
</p>
<blockquote class="citation">
<p>
As I understand the uniqueness framework, it is based on checking that the input to the constructor is the same as was already used before. So if posets are unique, the constructor input is somehow normalized (using Hasse diagram, perhaps?) and then compared with those that were already constructed.
</p>
</blockquote>
<p>
Correct.
</p>
<blockquote class="citation">
<p>
However for implementation purposes there is a big difference between treating two cones as cones of the same fan and as two arbitrary cones. In the first case the intersection is internally computed as the intersection of two ordered sets of integers. In the second one it involves constructing a new polyhedral object and determining its minimal generator set. With old PALP/cdd interfaces this takes forever (compared to intersection two short lists of integers). With Volker's new PPL interface it is much better, yet still it requires many more operations.
</p>
</blockquote>
<p>
To me this sounds like two cones/fans shall be equal (as in A==B) only if they really have the same ambient space / ... and otherwise be only isomorphic (as in A.is_isomorphic(B)).
In general, equality is often used by Python at a very low level, e.g. for hash table lookups. So it should be fast and simple.
</p>
<p>
Anyway, this does not need to be settled now, and we can discuss this more efficiently face to face at the next occasion.
</p>
<blockquote class="citation">
<p>
I agree that we have here more structure than poset itself but it is basically the question of "the same" and "isomorphic". We have a similar issue with toric lattices: if M = ZZ<sup>n</sup>, then the dual space is also ZZ<sup>n</sup>, yet they are isomorphic but not equal. It would be great actually to have some standard way in Sage to tag objects. Maybe ZZ is unique as a ring, but it is possible that one wants to consider several modules which are isomorphic to ZZ and treat them as different ones.
</p>
</blockquote>
<p>
We definitely have had such use cases as well. However we were lucky enough that we usually wanted to add some more structure, or change a bit the structure, and in those cases we would either derive a new class, or use a facade parent together with Cat.<a class="missing wiki">IsomorphicObjects?</a>() to transfer the part of the structure that was to be kept.
</p>
<p>
But we could think of generalizing the use of a key=<code>...</code> in <a class="missing wiki">UniqueRepresentation?</a> as I used here for posets.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnovoseltThu, 23 Jun 2011 19:07:45 GMT
https://trac.sagemath.org/ticket/10998#comment:41
https://trac.sagemath.org/ticket/10998#comment:41
<p>
Hi Nicolas, thanks for the reply!
</p>
<p>
Changes to the cones and fans seem fine to me. I think that we do care about the possibility of pickling faces, but it is not something desperate. In my prior experience it was sometimes faster to recompute faces than to store them, I have not tested it for the current toric framework.
</p>
<p>
Generalizing your <code>key</code> argument for all <code>UniqueRepresentation</code>s sound like a good idea to me!
</p>
<p>
Andrey
</p>
TicketnthieryThu, 23 Jun 2011 20:53:41 GMT
https://trac.sagemath.org/ticket/10998#comment:42
https://trac.sagemath.org/ticket/10998#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:41" title="Comment 41">novoselt</a>:
</p>
<blockquote class="citation">
<p>
Changes to the cones and fans seem fine to me. I think that we do care about the possibility of pickling faces, but it is not something desperate.
</p>
</blockquote>
<p>
Nope. I just went this way because it was the quickest to setup to get this patch done. Worst case, a bit of getstate/setstate magic will do the job.
</p>
<blockquote class="citation">
<p>
In my prior experience it was sometimes faster to recompute faces than to store them, I have not tested it for the current toric framework.
</p>
</blockquote>
<p>
Ok.
</p>
<blockquote class="citation">
<p>
Generalizing your <code>key</code> argument for all <code>UniqueRepresentation</code>s sound like a good idea to me!
</p>
</blockquote>
<p>
Ok. I'll keep this in mind, and wait until we get enough other use cases.
</p>
<p>
Thanks Andrey for your fast review.
</p>
TicketnthieryThu, 23 Jun 2011 20:54:23 GMT
https://trac.sagemath.org/ticket/10998#comment:43
https://trac.sagemath.org/ticket/10998#comment:43
<p>
Christian, Franco: any chances for one of you to check my latest changes shortly? Then we could be done, and get this in 4.7.2.
</p>
<p>
Thanks in advance,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryTue, 28 Jun 2011 12:19:05 GMTdependencies, description changed
https://trac.sagemath.org/ticket/10998#comment:44
https://trac.sagemath.org/ticket/10998#comment:44
<ul>
<li><strong>dependencies</strong>
changed from <em>#11289, #10938, #9065</em> to <em>#8288,#10651,#11289, #10938, #9065,#11183</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=44">diff</a>)
</li>
</ul>
TicketnthieryTue, 28 Jun 2011 12:21:28 GMTdependencies changed
https://trac.sagemath.org/ticket/10998#comment:45
https://trac.sagemath.org/ticket/10998#comment:45
<ul>
<li><strong>dependencies</strong>
changed from <em>#8288,#10651,#11289, #10938, #9065,#11183</em> to <em>#8288,#10651,#11289, #10938, #9065</em>
</li>
</ul>
TicketvbraunThu, 07 Jul 2011 22:07:35 GMT
https://trac.sagemath.org/ticket/10998#comment:46
https://trac.sagemath.org/ticket/10998#comment:46
<p>
The poset elements have two attributes, <code>.element</code> and <code>.vertex</code>. Is there a one-to-one correspondence between elements and vertices? I do think so, but maybe there is something I'm overlooking.
</p>
<p>
If it is true, can we get rid of the superfluous element comparison in <code>PosetElement.__eq__</code>? This causes a serious slowdown in the toric code - its much cheaper to compare vertices than cones.
</p>
Ticketstumpc5Wed, 10 Aug 2011 00:37:38 GMT
https://trac.sagemath.org/ticket/10998#comment:47
https://trac.sagemath.org/ticket/10998#comment:47
<p>
I don't know what the current status here is; I just saw that the optional arguments label_elements and element_labels for show/plot do not work anymore (I fixed that a while ago somewhere is this big cluster patch). Can someone confirm that and/or see where my changes got lost?
</p>
<p>
As an example, I tried
</p>
<pre class="wiki">sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(label_elements=False)
sage: D.show()
sage: elm_labs = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'}
sage: D.show(element_labels=elm_labs)
</pre><p>
In both cases, I see the numbers as labels.
</p>
<p>
Best, Christian
</p>
TicketnovoseltThu, 29 Dec 2011 16:48:56 GMT
https://trac.sagemath.org/ticket/10998#comment:48
https://trac.sagemath.org/ticket/10998#comment:48
<p>
Hello, I wonder - what are the current plans for this ticket? (I am interested in <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/11559" title="enhancement: Speed up Posets and toric Chow group (needs_work)">#11559</a> which depends on it.)
</p>
TicketnthierySun, 08 Jan 2012 19:59:19 GMT
https://trac.sagemath.org/ticket/10998#comment:49
https://trac.sagemath.org/ticket/10998#comment:49
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:48" title="Comment 48">novoselt</a>:
</p>
<blockquote class="citation">
<p>
Hello, I wonder - what are the current plans for this ticket? (I am interested in <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/11559" title="enhancement: Speed up Posets and toric Chow group (needs_work)">#11559</a> which depends on it.)
</p>
</blockquote>
<p>
I really want to get rid of it. I should have more time working on Sage shortly, so hopefully that will be soon!
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingFri, 27 Jan 2012 09:39:32 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/10998#comment:50
https://trac.sagemath.org/ticket/10998#comment:50
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase relative sage-5.0.beta0</em>
</li>
</ul>
<p>
I get numerous mismatches when applying the patch on top of sage-5.0.prealpha0. I think it is due to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>. Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> is merged, I suggest to rebase the patch from here.
</p>
TicketnthieryWed, 08 Feb 2012 00:47:58 GMT
https://trac.sagemath.org/ticket/10998#comment:51
https://trac.sagemath.org/ticket/10998#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:47" title="Comment 47">stumpc5</a>:
</p>
<blockquote class="citation">
<p>
I don't know what the current status here is; I just saw that the optional arguments label_elements and element_labels for show/plot do not work anymore (I fixed that a while ago somewhere is this big cluster patch). Can someone confirm that and/or see where my changes got lost?
</p>
<p>
As an example, I tried
</p>
<pre class="wiki">sage: D = Poset({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(label_elements=False)
sage: D.show()
sage: elm_labs = {0:'a', 1:'b', 2:'c', 3:'d', 4:'e'}
sage: D.show(element_labels=elm_labs)
</pre><p>
In both cases, I see the numbers as labels.
</p>
</blockquote>
<p>
Fixed and tested in the updated patch!
</p>
TicketnthieryWed, 08 Feb 2012 01:20:57 GMTstatus, keywords changed
https://trac.sagemath.org/ticket/10998#comment:52
https://trac.sagemath.org/ticket/10998#comment:52
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>keywords</strong>
<em>Cernay2012</em> added
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/10998#comment:46" title="Comment 46">vbraun</a>:
</p>
<blockquote class="citation">
<p>
The poset elements have two attributes, <code>.element</code> and <code>.vertex</code>. Is there a one-to-one correspondence between elements and vertices? I do think so, but maybe there is something I'm overlooking.
</p>
<p>
If it is true, can we get rid of the superfluous element comparison in <code>PosetElement.__eq__</code>? This causes a serious slowdown in the toric code - its much cheaper to compare vertices than cones.
</p>
</blockquote>
<p>
Thanks for the suggestion. I implemented this in the latest version of my patch!
</p>
TicketnthieryWed, 08 Feb 2012 01:43:13 GMT
https://trac.sagemath.org/ticket/10998#comment:53
https://trac.sagemath.org/ticket/10998#comment:53
<p>
The latest version of the patch is here and in the Sage-Combinat queue. Florent will make the final review tomorrow morning.
</p>
TicketnthieryWed, 08 Feb 2012 10:13:04 GMTattachment set
https://trac.sagemath.org/ticket/10998
https://trac.sagemath.org/ticket/10998
<ul>
<li><strong>attachment</strong>
set to <em>trac_10998-categories-posets-sagenb-nt.patch</em>
</li>
</ul>
<p>
Patch to be applied on the sagenb repo
</p>
TicketnthieryWed, 08 Feb 2012 10:23:45 GMTdescription changed
https://trac.sagemath.org/ticket/10998#comment:54
https://trac.sagemath.org/ticket/10998#comment:54
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10998?action=diff&version=54">diff</a>)
</li>
</ul>
TicketnthieryThu, 09 Feb 2012 00:39:46 GMTattachment set
https://trac.sagemath.org/ticket/10998
https://trac.sagemath.org/ticket/10998
<ul>
<li><strong>attachment</strong>
set to <em>trac_10998-categories-posets-nt.patch</em>
</li>
</ul>
TicketnthieryThu, 09 Feb 2012 00:41:12 GMTstatus changed
https://trac.sagemath.org/ticket/10998#comment:55
https://trac.sagemath.org/ticket/10998#comment:55
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Final patch uploaded, after polishing of the doc and a final failing doctest. Crossreviewed with Florent. All tests pass. Positive review!
</p>
<p>
Thanks everyone!
</p>
TicketjdemeyerThu, 09 Feb 2012 19:16:07 GMTwork_issues deleted
https://trac.sagemath.org/ticket/10998#comment:56
https://trac.sagemath.org/ticket/10998#comment:56
<ul>
<li><strong>work_issues</strong>
<em>rebase relative sage-5.0.beta0</em> deleted
</li>
</ul>
<p>
Wow, you win the award for longest commit message.
</p>
TicketjdemeyerTue, 14 Feb 2012 14:19:48 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10998#comment:57
https://trac.sagemath.org/ticket/10998#comment:57
<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.0.beta4</em>
</li>
</ul>
Ticket