Opened 11 years ago
Closed 10 years ago
#10998 closed enhancement (fixed)
Categories for posets
Reported by: | nthiery | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | combinatorics | Keywords: | days30, sd31, Cernay2012 |
Cc: | sage-combinat, niles, novoselt, vbraun | Merged in: | sage-5.0.beta4 |
Authors: | Frédéric Chapoton, Christian Stump, Nicolas M. Thiéry | Reviewers: | Franco Saliola, Christian Stump, Nicolas M. Thiéry, Florent Hivert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #8288,#10651,#11289, #10938, #9065 | Stopgaps: |
Description (last modified by )
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.
Apply: trac_10998-categories-posets-nt.patch
Apply on sagenb repo: trac_10998-categories-posets-sagenb-nt.patch
Attachments (2)
Change History (59)
comment:1 Changed 11 years ago by
- Description modified (diff)
- Type changed from task to enhancement
comment:2 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 11 years ago by
- Description modified (diff)
comment:4 Changed 11 years ago by
- Description modified (diff)
comment:5 Changed 11 years ago by
- Cc niles added
comment:6 Changed 11 years ago by
comment:7 follow-up: ↓ 8 Changed 11 years ago by
Salut Nicolas,
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, ...
In my (not yet final) review patch, I place some questions on implementations, some suggestions for additional methods, and I fixed several typos.
Best, Christian
comment:8 in reply to: ↑ 7 Changed 11 years ago by
Replying to stumpc5:
I must say: there is a lot of code where I don't really understand what you do, and why you do it.
Hmm, more specific questions (like the one below) would be useful to get a constructive discussion :-)
E.g., which code is generic enough to put in categories and which is not,
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.
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.
how are examples organized, how do you properly test the code, ...
Are those questions about the category framework in general, or about this specific patch?
In my (not yet final) review patch, I place some questions on implementations, some suggestions for additional methods, and I fixed several typos.
Ok, thanks!
Cheers,
Nicolas
comment:9 Changed 11 years ago by
- Description modified (diff)
- Milestone changed from sage-5.0 to sage-4.7.1
- Reviewers set to Franco Saliola, Christian Stump, Nicolas M. Thiéry
comment:10 Changed 11 years ago by
Apply only trac_10998-categories-posets-nt.patch
comment:11 Changed 11 years ago by
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.
Cheers,
Florent
comment:12 Changed 11 years ago by
Folded; thanks!
comment:13 Changed 11 years ago by
Fixed failing test.
comment:14 follow-up: ↓ 15 Changed 11 years ago by
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 11 years ago by
- Reviewers changed from Franco Saliola, Christian Stump, Nicolas M. Thiéry to Franco Saliola, Christian Stump, Nicolas M. Thiéry, Florent Hivert
Replying to nthiery:
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
I also just spotted a few more wrong sphinx markup ! I'm fixing those.
comment:16 in reply to: ↑ 15 Changed 11 years ago by
Replying to hivert:
Replying to nthiery:
Hmm, there are a couple more trivial ones. I'll work on those on Monday unless someone beats me to it!
I also just spotted a few more wrong sphinx markup ! I'm fixing those.
Please see my new review patch on sage-combinat queue trac_10998-categories-posets-docfix-fh.patch
comment:17 Changed 11 years ago by
- Status changed from needs_review to needs_work
I started with a fresh install of sage-4.7.rc1 and applied the patches at #9065 and #10938, followed by the patch for this ticket on the sage-combinat queue. I get a the following doctest failures.
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
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.)
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?
comment:18 Changed 11 years ago by
- Cc novoselt added
Oh right, I had forgotten about those. I tried a bit to find the problem, but to not avail yet.
Andrey, would you have any clue?
comment:19 follow-up: ↓ 20 Changed 11 years ago by
Hi Nicolas, thanks for ccing me!
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 fan.py
.
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.
I'll try to trace it down further, but it may take me a few days due to traveling and conferencing...
comment:20 in reply to: ↑ 19 ; follow-up: ↓ 21 Changed 11 years ago by
Replying to novoselt:
Hi Nicolas, thanks for ccing me!
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
fan.py
.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.
I'll try to trace it down further, but it may take me a few days due to traveling and conferencing...
Thanks!
For the record: finite posets and their elements, now have UniqueRepresentation?. This could have an influence if the same poset is created several times when constructing several fans.
comment:21 in reply to: ↑ 20 ; follow-up: ↓ 33 Changed 11 years ago by
Replying to nthiery:
For the record: finite posets and their elements, now have UniqueRepresentation?. This could have an influence if the same poset is created several times when constructing several fans.
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?
I really don't want to make fans unique at this point as I am planning some adjustments to them and related objects.
Does uniqueness test rely on ==
test? Is there any way to change it? Currently ==
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 is
-equivalence. On the other hand, Volker votes for ==
being mathematical equivalence without taking order into account. Such equivalence definitely would not be acceptable deep inside implementation which relies on fixed order.
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 ==
. Can I somehow attach id(fan)
to the poset without altering its structure?..
comment:22 Changed 11 years ago by
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.
With the exception of the issue highlighted above, I give a positive review to the changes.
- someone needs to review my patch
- someone needs to post a patch addressing the broken doctests
comment:23 Changed 11 years ago by
- Description modified (diff)
comment:24 Changed 11 years ago by
My previous comment refers to the patches on the sage-combinat queue.
comment:25 Changed 11 years ago by
- Keywords days30 added
comment:26 Changed 11 years ago by
Trying to help the buildbot to do its job
Apply trac_10998-categories-posets-nt.patch Apply trac_10998-review-fs.patch
comment:27 Changed 11 years ago by
try again
Apply trac_10998-categories-posets-nt.patch trac_10998-review-fs.patch
comment:28 Changed 11 years ago by
- Dependencies set to #11289, #10938, #9065
comment:29 Changed 11 years ago by
trying to help the bot again
Apply trac_10998-categories-posets-nt.patch trac_10998-review-fs.patch
comment:30 follow-up: ↓ 31 Changed 11 years ago by
ok, the bot has found a HUNK problem in poset_examples.py
Could somebody solve that ?
comment:31 in reply to: ↑ 30 Changed 11 years ago by
Replying to chapoton:
ok, the bot has found a HUNK problem in poset_examples.py
Could somebody solve that ?
Done! There just remains the cone issue.
comment:32 Changed 11 years ago by
Btw: I reviewed and folded in Franco's reviewer's patch. Thanks Franco!
comment:33 in reply to: ↑ 21 Changed 11 years ago by
Hi Andrei,
Replying to novoselt:
2) To the point: How to fix it?
I really don't want to make fans unique at this point as I am planning some adjustments to them and related objects.
Does uniqueness test rely on
==
test? Is there any way to change it? Currently==
for fans checks that fans have the same rays and the same generating cones in the same order. Things relates to facets require even strongeris
-equivalence. On the other hand, Volker votes for==
being mathematical equivalence without taking order into account. Such equivalence definitely would not be acceptable deep inside implementation which relies on fixed order.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
==
. Can I somehow attachid(fan)
to the poset without altering its structure?..
I have (finally!) just looked at this again. I traced through the execution of f.cone_containing(0)
, 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)?
We are both at FPSAC with Franco; it would be great if we could finish this patch today or tomorrow.
Thanks!
comment:34 follow-up: ↓ 35 Changed 11 years ago by
- Cc vbraun added
- Keywords sd31 added
Hi Nicolas!
With the patch:
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
The last command is heavily assumed to return True in the toric-related code. The problem is that when the cone lattice of F2
is constructed, it is considered as the same poset as the cone lattice of F1
and so all cones of F2
become linked to F1
. Possible solutions are:
- 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.
- 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.
- 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.
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.
So, in short, I prefer to be able to create different posets of cones for fans which are "==".
Thank you, Andrey
comment:35 in reply to: ↑ 34 ; follow-up: ↓ 36 Changed 11 years ago by
Replying to novoselt:
Hi Nicolas!
With the patch:
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 FalseThe last command is heavily assumed to return True in the toric-related code. The problem is that when the cone lattice of
F2
is constructed, it is considered as the same poset as the cone lattice ofF1
and so all cones ofF2
become linked toF1
. Possible solutions are:
- 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.
- 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.
- 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.
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.
So, in short, I prefer to be able to create different posets of cones for fans which are "==".
Thanks a lot! I'll look at this tonight.
I am still confused a bit: do you know where technically in the cone code is there an ==
or
is
test done on some posets, which cause the change of behaviour above?
comment:36 in reply to: ↑ 35 ; follow-up: ↓ 37 Changed 11 years ago by
Replying to nthiery:
I am still confused a bit: do you know where technically in the cone code is there an
==
or
is
test done on some posets, which cause the change of behaviour above?
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 _compute_cone_lattice
.
Now, I have actually realized, that it will have the same issue for cones, it just does not break the existent doctests yet:
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
The code for cones is in face_lattice
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.
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^{5} elements, how long would it take to check their equality? Maybe elements of posets should be unique, but not posets themselves?
comment:37 in reply to: ↑ 36 Changed 11 years ago by
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^{5} elements, how long would it take to check their equality? Maybe elements of posets should be unique, but not posets themselves?
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...
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.
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 ==.
My two cents,
Florent
comment:38 follow-up: ↓ 40 Changed 11 years ago by
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.
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.
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.
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^{n}, then the dual space is also ZZ^{n}, 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.
comment:39 Changed 11 years ago by
- Status changed from needs_work to needs_review
The updated patch fixes the issue with cones and fans by adding a key
argument to FinitePoset?. Using it, equal but not identical Cone's and Fan's create distinct posets.
I also folded in Christian's order_complex fix.
To me the whole thing seems ready to go.
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.
comment:40 in reply to: ↑ 38 Changed 11 years ago by
Replying to novoselt:
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.
Correct.
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.
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.
Anyway, this does not need to be settled now, and we can discuss this more efficiently face to face at the next occasion.
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^{n}, then the dual space is also ZZ^{n}, 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.
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.IsomorphicObjects?() to transfer the part of the structure that was to be kept.
But we could think of generalizing the use of a key=...
in UniqueRepresentation? as I used here for posets.
Cheers,
Nicolas
comment:41 follow-up: ↓ 42 Changed 11 years ago by
Hi Nicolas, thanks for the reply!
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.
Generalizing your key
argument for all UniqueRepresentation
s sound like a good idea to me!
Andrey
comment:42 in reply to: ↑ 41 Changed 11 years ago by
Replying to novoselt:
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.
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.
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.
Ok.
Generalizing your
key
argument for allUniqueRepresentation
s sound like a good idea to me!
Ok. I'll keep this in mind, and wait until we get enough other use cases.
Thanks Andrey for your fast review.
comment:43 Changed 11 years ago by
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.
Thanks in advance,
Nicolas
comment:44 Changed 11 years ago by
- Dependencies changed from #11289, #10938, #9065 to #8288,#10651,#11289, #10938, #9065,#11183
- Description modified (diff)
comment:45 Changed 11 years ago by
- Dependencies changed from #8288,#10651,#11289, #10938, #9065,#11183 to #8288,#10651,#11289, #10938, #9065
comment:46 follow-up: ↓ 52 Changed 11 years ago by
The poset elements have two attributes, .element
and .vertex
. Is there a one-to-one correspondence between elements and vertices? I do think so, but maybe there is something I'm overlooking.
If it is true, can we get rid of the superfluous element comparison in PosetElement.__eq__
? This causes a serious slowdown in the toric code - its much cheaper to compare vertices than cones.
comment:47 follow-up: ↓ 51 Changed 11 years ago by
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?
As an example, I tried
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)
In both cases, I see the numbers as labels.
Best, Christian
comment:48 follow-up: ↓ 49 Changed 10 years ago by
Hello, I wonder - what are the current plans for this ticket? (I am interested in #11559 which depends on it.)
comment:49 in reply to: ↑ 48 Changed 10 years ago by
comment:50 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to rebase relative sage-5.0.beta0
comment:51 in reply to: ↑ 47 Changed 10 years ago by
Replying to stumpc5:
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?
As an example, I tried
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)In both cases, I see the numbers as labels.
Fixed and tested in the updated patch!
comment:52 in reply to: ↑ 46 Changed 10 years ago by
- Keywords Cernay2012 added
- Status changed from needs_work to needs_review
Replying to vbraun:
The poset elements have two attributes,
.element
and.vertex
. Is there a one-to-one correspondence between elements and vertices? I do think so, but maybe there is something I'm overlooking.If it is true, can we get rid of the superfluous element comparison in
PosetElement.__eq__
? This causes a serious slowdown in the toric code - its much cheaper to compare vertices than cones.
Thanks for the suggestion. I implemented this in the latest version of my patch!
comment:53 Changed 10 years ago by
The latest version of the patch is here and in the Sage-Combinat queue. Florent will make the final review tomorrow morning.
comment:54 Changed 10 years ago by
- Description modified (diff)
Changed 10 years ago by
comment:55 Changed 10 years ago by
- Status changed from needs_review to positive_review
Final patch uploaded, after polishing of the doc and a final failing doctest. Crossreviewed with Florent. All tests pass. Positive review!
Thanks everyone!
comment:56 Changed 10 years ago by
- Work issues rebase relative sage-5.0.beta0 deleted
Wow, you win the award for longest commit message.
comment:57 Changed 10 years ago by
- Merged in set to sage-5.0.beta4
- Resolution set to fixed
- Status changed from positive_review to closed
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.