Opened 10 years ago
Closed 10 years ago
#12993 closed defect (fixed)
Bug in computing the rank function a poset
Reported by: | Franco Saliola | Owned by: | Sage Combinat CC user |
---|---|---|---|
Priority: | major | Milestone: | sage-5.1 |
Component: | combinatorics | Keywords: | poset, combinat |
Cc: | Sage Combinat CC user, darijgrinberg@… | Merged in: | sage-5.1.beta5 |
Authors: | Darij Grinberg, Anne Schilling | Reviewers: | Christian Stump, Franco Saliola |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This should return True:
sage: P = Poset(([1,2,3,4],[[1,4],[2,3],[3,4]]), facade = True) sage: P.is_ranked() False
Anne's suggestion from this thread on sage-combinat-devel:
For a finite poset perhaps the easiest would be to
- start with a random element in the poset, assign rank 0
- look at all covers and cocovers and assign the rank according to the recurrence rank(x) = rank(y) + 1 if x covers y.
- repeat with the new elements
- if at any point an element is reached again and is assigned a different value from before, the poset is not graded; otherwise continue with new elements
Attachments (1)
Change History (31)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
Hello Darij,
I took a quick look at your code and have a few comments.
- You should add the poset that Anne provided illustrating the bug as a doctest in the examples section. This way, it is guaranteed to work in all future versions of Sage.
- I see that you are trying to create a list of empty lists. An easier and more efficient way to do this is:
[ [] for x in range(n) ]
- I see you are using these lists to construct lists of upper and lower covers. I think you should just use the
upper_covers
andlower_covers
methods for posets, or theneighbors_out
neighbours_in
methods for Hasse diagrams.
- I would probably use a dictionary for
rank_fcn
instead of a list. This way you don't have to create a list of the required length beforehand.
- Your code first creates a function and then tests it to see if it is a rank function. Is it possible to do the tests as you are creating the function so that in case the poset is not graded, then we get an error as soon as one is detected? I haven't given it much thought. Maybe it isn't as efficient?
comment:3 Changed 10 years ago by
Authors: | → Darij Grinberg, Anne Schilling |
---|---|
Status: | new → needs_review |
comment:4 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Summary: | Bug in determining whether a poset is graded → Bug in computing the rank function a poset |
comment:5 Changed 10 years ago by
Hello --
I pushed a new version of the algorithm that speeds quite a bit, and also modified the show method to get the grading properly. If you are fine with it, I would then finalizing the review (though it might be better if someone else looks at my algo and tries to break it).
Best, Christian
comment:7 Changed 10 years ago by
Replying to saliola:
Christian, you forgot to attach your patch.
I uploaded the file -- actually I thought it is enough to push it to the queue so you guys can look at it...
comment:8 follow-up: 9 Changed 10 years ago by
- I think Darij is not yet completely configured with the sage-combinat queue.
- If you push it to the queue only, you are effectively restricting the number of people that will look at the patch. There are people that can review patches that don't use sage-combinat and some that have no intention of using sage-combinat.
comment:9 Changed 10 years ago by
Replying to saliola:
- I think Darij is not yet completely configured with the sage-combinat queue.
- If you push it to the queue only, you are effectively restricting the number of people that will look at the patch. There are people that can review patches that don't use sage-combinat and some that have no intention of using sage-combinat.
right, right, it's here now.
comment:10 follow-up: 11 Changed 10 years ago by
Christian,
Nice idea to use the rank_function
for the plot method!
I don't like this loop:
579 for i,j in edges: # to find new elements, we run through all edges of the Hasse diagram 580 if i in rank_fcn: ... 589 else: 590 if j in rank_fcn: # as above
This means that you will be looking at edges multiple times until one of them has been assigned a rank. You are also looking at edges in other connected components. If there are several connected components, then this will take too long. For example,
sage: P = lambda n : Poset([range(n), [(i,i+1) for i in range(0,n,2)]]) sage: time p = P(10000); p Time: CPU 2.32 s, Wall: 2.32 s Finite poset containing 10000 elements sage: time p.is_ranked() True Time: CPU 13.35 s, Wall: 13.36 s
With Darij and Anne's patch, this only takes 0.99s.
I'm preparing a patch right now to address this.
comment:11 Changed 10 years ago by
I don't like this loop:
579 for i,j in edges: # to find new elements, we run through all edges of the Hasse diagram 580 if i in rank_fcn: ... 589 else: 590 if j in rank_fcn: # as aboveThis means that you will be looking at edges multiple times until one of them has been assigned a rank. You are also looking at edges in other connected components. If there are several connected components, then this will take too long. For example,
That is right -- I first had taken the connected components into account as Darij and Anne did it, but in the examples I had it was always faster to not first compute th connected components. A second thing I had was to delete an edge after it was found to have both vertices ranked and the rank comparison tested (since we will not get any new info back from doing this test again). But also that seemed to take for small posets more time than running through all edges again and again.
I guess that for larger posets, it is worth first computing the connected components (but only because that is done in the backbone of graphs and thus really fast), and also deleting edges that are not needed anymore.
Do you first want me to put these things in my algo, or do you wanna do it?
comment:12 follow-ups: 13 16 Changed 10 years ago by
Here is a review patch. Apply on top of Christian's review patch (which goes on top of Anne's).
It looks at each edge exactly twice.
I also updated the documentation for Poset.rank_function.
Christian: I see you didn't run the doctests. I had to fix your attempt at using rank_function for plotting.
Also, there is a pickling error that got introduced by your patch in posets.py, but I can't replicated it from within Sage. I don't have time to debug this now, so go ahead and try to sort it out.
Edit: Here is the doctest failure message:
sage -t "devel/sage-reviews/sage/combinat/posets/posets.py" ********************************************************************** File "/Users/saliola/Applications/sage-5.0/devel/sage-reviews/sage/combinat/posets/posets.py", line 545: sage: TestSuite(P).run() Expected nothing Got: Failure in _test_pickling: Traceback (most recent call last): File "/Users/saliola/Applications/sage-5.0/local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "sage_object.pyx", line 396, in sage.structure.sage_object.SageObject._test_pickling (sage/structure/sage_object.c:3197) File "sage_object.pyx", line 889, in sage.structure.sage_object.dumps (sage/structure/sage_object.c:9006) TypeError: expected string or Unicode object, NoneType found ------------------------------------------------------------ The following tests failed: _test_pickling **********************************************************************
comment:13 follow-up: 15 Changed 10 years ago by
Hi Christian and Franco,
Thank you for your review patches and investigating this! Franco, conversely, can I ask you to push your review patch to the sage-combinat queue? That would be easier for me and we can fold all patches once everyone is happy!
I'll be traveling back to Davis soon (from Oberwolfach), so might not have internet in the meantime.
Anne
comment:14 Changed 10 years ago by
Cc: | darijgrinberg@… added |
---|---|
Reviewers: | → Christian Stump, Franco Saliola |
comment:15 Changed 10 years ago by
Replying to aschilling:
Franco, conversely, can I ask you to push your review patch to the sage-combinat queue?
I pushed it
comment:16 follow-up: 17 Changed 10 years ago by
Replying to saliola:
Here is a review patch. Apply on top of Christian's review patch (which goes on top of Anne's).
It looks at each edge exactly twice.
your code is certainly cleaner than mine was!
I don't see why, but my method seems to be twice as fast for boolean lattices (tested with up to sets of size 8). I would still vote for keeping yours since you have examples where it is much faster, and the code is nicer as well.
comment:17 Changed 10 years ago by
Replying to stumpc5:
Replying to saliola:
Here is a review patch. Apply on top of Christian's review patch (which goes on top of Anne's).
It looks at each edge exactly twice.
your code is certainly cleaner than mine was!
I don't see why, but my method seems to be twice as fast for boolean lattices (tested with up to sets of size 8). I would still vote for keeping yours since you have examples where it is much faster, and the code is nicer as well.
Thanks for pushing my patch.
The algorithm starts with some vertex, and propagates the value of the rank function along incoming and outgoing edges. If there is a unique minimal vertex in each connected component, then we could just use outgoing edges starting from that minimal vertex. Otherwise, we have to go backwards along some edges.
comment:18 follow-up: 19 Changed 10 years ago by
I just uploaded a new review patch with a small change. I changed one line:
m = min(rank_fcn.values())
to
m = min(rank_fcn[j] for j in component)
in order to renormalize each connected component.
I also pushed my change to the sage-combinat queue.
comment:20 follow-up: 21 Changed 10 years ago by
Hello Anne,
Is the documentation satisfactory?
We still haven't decided about "graded" vs "ranked" (whether they mean the same thing or not), but that's for another ticket. Or it can be our next "Sage Days Discussion". :-)
comment:21 follow-up: 22 Changed 10 years ago by
Hello Franco,
I had added something to the documentation of rank function (about what happens when there are several components and how the normalization works). So this is fine with me.
Yes, there is the issue about is_ranked versus is_graded. Perhaps we should indeed discuss this at the next Sage Days in Minneapolis. At least now Sage does what the documentation says it does! I could add a link from is_graded and is_ranked to rank_function, so that it is easier for the user to find that definition. What do you think?
I could fold all three patches, add this link, post it here and on sage-combinat and you or Christian could have a final look.
Best,
Anne
comment:22 follow-up: 24 Changed 10 years ago by
Hello Anne,
Replying to aschilling:
I could add a link from is_graded and is_ranked to rank_function, so that it is easier for the user to find that definition. What do you think?
I could fold all three patches, add this link, post it here and on sage-combinat and you or Christian could have a final look.
Great idea. What about "see also" sections for is_graded and is_ranked that point to each other? Perhaps this is what you meant by "add a link"?
Franco
comment:23 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:24 Changed 10 years ago by
Hello Franco and Christian,
I folded the patches and added the links to the rank_function method from is_graded and is_ranked. However, perhaps this was premature since like Franco I get the pickling failure in the doctests which I also cannot reproduce inside sage.
Any idea on how to fix this? I gues this introduced through Christian's review patch by adding the height???
Best,
Anne
comment:25 follow-up: 26 Changed 10 years ago by
For the patchbot:
(According to the buildbot wiki page, under "Hints and tricks", the patch list directive does not work in ticket descriptions.)
comment:26 follow-up: 27 Changed 10 years ago by
Hi!
The following seems the line causing the pickling failure
+ rank_function = self.rank_function()
So I will remove the height function stuff that Christian added, since I have no idea how to fix this pickling failure otherwise.
Could you please review the new patch?
Thanks,
Anne
Changed 10 years ago by
Attachment: | trac_12993-graded_poset-folded-as.patch added |
---|
comment:27 follow-up: 28 Changed 10 years ago by
Replying to aschilling:
Could you please review the new patch?
I also don't know how to fix the pickling thing...
Beside that, I give it a positive review assuming the patchbot doesn't make any trouble. Franco, do you want to have a look at the plotting issue, or should we let it go as is?
comment:28 follow-up: 29 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
comment:29 Changed 10 years ago by
Thank you! I saw that you opened #13079 to work on the height function for plotting. Christian, in the sage-combinat queue, you can probably rename you trac_???? patch to this ticket number.
Anne
comment:30 Changed 10 years ago by
Merged in: | → sage-5.1.beta5 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Darij posted a proposed function here: http://mit.edu/~darij/www/rf.txt