Bug in computing the rank function a poset

[saliola]

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

Apply: trac_12993-graded_poset-folded-as.patch

[saliola]

Darij posted a proposed function here:  http://mit.edu/~darij/www/rf.txt

[saliola]

Hello Darij,

I took a quick look at your code and have a few comments.

1. 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.

2. 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) ]

3. I see you are using these lists to construct lists of upper and lower covers. I think you should just use the upper_covers and lower_covers methods for posets, or the neighbors_out neighbours_in methods for Hasse diagrams.

4. 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.

5. 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?

[stumpc5]

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

[saliola]

Christian, you forgot to attach your patch.

[stumpc5]

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...

[saliola]

1. I think Darij is not yet completely configured with the sage-combinat queue.

2. 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.

[stumpc5]

Replying to saliola:

1. I think Darij is not yet completely configured with the sage-combinat queue.

2. 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.

[saliola]

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.

[stumpc5]

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,

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?

[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.

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
**********************************************************************

[aschilling]

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

[stumpc5]

Replying to aschilling:

Franco, conversely, can I ask you to push your review patch to the sage-combinat queue?

I pushed it

[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.

[saliola]

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.

[saliola]

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.

[aschilling]

The review patch looks good to me.

Anne

[saliola]

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". :-)

[aschilling]

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

[saliola]

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

[aschilling]

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

[saliola]

For the patchbot:

Apply trac_12993-graded_poset-folded-as.patch

(According to the  buildbot wiki page, under "Hints and tricks", the patch list directive does not work in ticket descriptions.)

[aschilling]

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

[stumpc5]

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?

[saliola]

Replying to stumpc5:

Franco, do you want to have a look at the plotting issue, or should we let it go as is?

That shouldn't hold back this patch. It should be another ticket (Edit: #13079).

Apply trac_12993-graded_poset-folded-as.patch

[aschilling]

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