# Ticket #12993(closed defect: fixed)

Opened 12 months ago

## Bug in computing the rank function a poset

Reported by: Owned by: saliola sage-combinat major sage-5.1 combinatorics poset, combinat sage-combinat, darijgrinberg@… N/A Christian Stump, Franco Saliola Darij Grinberg, Anne Schilling sage-5.1.beta5

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

## Change History

### comment:1 Changed 12 months ago by saliola

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

### comment:2 Changed 12 months ago by 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.
1. 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) ]

1. 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.
1. 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.
1. 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 12 months ago by aschilling

• Status changed from new to needs_review
• Authors set to Darij Grinberg, Anne Schilling

### comment:4 Changed 12 months ago by saliola

• Description modified (diff)
• Summary changed from Bug in determining whether a poset is graded to Bug in computing the rank function a poset

### comment:5 Changed 12 months ago by 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

### comment:6 follow-up: ↓ 7 Changed 12 months ago by saliola

Christian, you forgot to attach your patch.

### comment:7 in reply to: ↑ 6 Changed 12 months ago by stumpc5

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 12 months ago by saliola

1. I think Darij is not yet completely configured with the sage-combinat queue.
1. 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 in reply to: ↑ 8 Changed 12 months ago by stumpc5

1. I think Darij is not yet completely configured with the sage-combinat queue.
1. 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 12 months ago by 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.

### comment:11 in reply to: ↑ 10 Changed 12 months ago by 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?

### comment:12 follow-ups: ↓ 13 ↓ 16 Changed 12 months ago by 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
**********************************************************************
```
Last edited 12 months ago by saliola (previous) (diff)

### comment:13 in reply to: ↑ 12 ; follow-up: ↓ 15 Changed 12 months ago by 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

### comment:14 Changed 12 months ago by aschilling

• Reviewers set to Christian Stump, Franco Saliola

### comment:15 in reply to: ↑ 13 Changed 12 months ago by stumpc5

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

I pushed it

### comment:16 in reply to: ↑ 12 ; follow-up: ↓ 17 Changed 12 months ago by stumpc5

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 in reply to: ↑ 16 Changed 12 months ago by 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 12 months ago by 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.

### comment:19 in reply to: ↑ 18 ; follow-up: ↓ 20 Changed 12 months ago by aschilling

The review patch looks good to me.

Anne

### comment:20 in reply to: ↑ 19 ; follow-up: ↓ 21 Changed 12 months ago by 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". :-)

### comment:21 in reply to: ↑ 20 ; follow-up: ↓ 22 Changed 12 months ago by 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

### comment:22 in reply to: ↑ 21 ; follow-up: ↓ 24 Changed 12 months ago by saliola

Hello Anne,

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.

Franco

### comment:23 Changed 12 months ago by aschilling

• Description modified (diff)

### comment:24 in reply to: ↑ 22 Changed 12 months ago by 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

### comment:25 follow-up: ↓ 26 Changed 12 months ago by saliola

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 in reply to: ↑ 25 ; follow-up: ↓ 27 Changed 12 months ago by 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

### comment:27 in reply to: ↑ 26 ; follow-up: ↓ 28 Changed 12 months ago by stumpc5

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 in reply to: ↑ 27 ; follow-up: ↓ 29 Changed 12 months ago by saliola

• Status changed from needs_review to positive_review

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

Last edited 12 months ago by saliola (previous) (diff)

### comment:29 in reply to: ↑ 28 Changed 12 months ago by 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

### comment:30 Changed 11 months ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-5.1.beta5
Note: See TracTickets for help on using tickets.