Arrangements of pseudolines

[ncohen]

This module implements a class sage.geometry.pseudolines.PseudolinesArrangement? which can be used to encode an arrangement of pseudolines, and to go from one encoding to another.

It can also be used to plot an arrangement of pseudolines as a Wiring Diagram.

Apply:

• trac_12090-rebase.patch​
• trac_12090-review.patch​
• trac_12090-lastpatch.patch​

[ncohen]

With more doctests and exceptions returned :-)

[davidloeffler]

This doesn't apply to 5.0.beta10 -- according to the patchbot there's a conflict in doc/en/reference/geometry.rst. It worked in 5.0.beta8 so the conflict is with something merged in 5.0.beta9 or beta10, perhaps #12159 or #11634.

[ncohen]

Done ! :-)

Nathann

[davidloeffler]

That looks better. Notice the amusing line in the output of the patchbot test against 5.0.beta3:

#11634 already applied (5.0.beta10 <= 5.0.beta3)

which explains why it's coming up with "Apply Failed". That's a patchbot bug, which I've reported on #12486.

[hthomas]

I (trivially) rebased the patch so it applies.

I also uploaded a review patch (separate for ease of review). I changed PseudolinesArrangement to PseudolineArrangement. I think this is more idiomatic. I made other minor changes to the English throughout.

I slightly moved the labels in the wiring diagram output, so they don't overlap the diagram.

I made a small change which simplifies slightly the logic of the reading of the Felsner encoding. Maybe there was a reason for the way it was, but I couldn't see it. Please check me!

I'm not too happy about this:

sage: from sage.geometry.pseudolines import PseudolineArrangement 
sage: t=PseudolineArrangement([(1,2),(0,2),(1,0)],encoding="permutations")
sage: s=PseudolineArrangement(([1,2],[0,2],[1,0]),encoding="permutations")
sage: r=PseudolineArrangement([[1,2],[0,2],[1,0]],encoding="permutations")
sage: s==r
False
sage: t==r
False

Do you think the fact that the documentation refers to lists is enough to warn the user not to use tuples? It was a pleasure (and instructive!) to read your very efficient code, so I didn't want to mess it up with a clumsy attempt to handle this myself.

apply trac_12090-rebase.patch, trac_12090-review.patch

[ncohen]

Hellooooooooooooo !!!

God, I had completely forgotten this patch ! I wrote it more than one year ago ! :-P

If we are to merge it eventually, it would be nice to reuse the plot method of Braid Groups : #14533. They are prettier, and already in Sage !

I will write a patch to change that, but first could you tell me what you changed in the Felsner encoding ? I don't see it in your review patch. This encoding is only useful to prove that the number of such arrangements is in 2^(n^2), but it is cool to have around :-)

You are right that in your example all three should be equal, and I will fix that too. But really this class isn't made to work with pseudolines yet.. There is just a couple of methods to go from one encoding to the other, so a meaningless equality is not really a problem.

Have fuuuuuuuun ! And thank you again ! I'll write the additional patch when I will get your answer :-)

Nathann

[hthomas]

Bonjouuuuuuur!

Yes, I was looking to see what old combinatorial patches were lying around bitrotting. This deserves a better fate!

I didn't change the actual Felsner encoding. All I did was the following, in the procedure for turning a Felsner encoding into an arrangement. After you've pulled off a zero and a one, you have to update i. If seq[i-1] is non-empty, you decrement i. Fine. Otherwise, you either left i as it was, or incremented it, based on whether seq[i] was non-empty. But I think that at this point you can always increment it: the next thing you're going to pull off is not going to be in position i, because that would have to be the same crossing as the one you just removed. Am I wrong?

I agree, the braid group strands are pretty; it would be good to reuse them.

I don't know if this is worth bothering about, but for someone who is learning about the Felsner encoding, it might be convenient to be able to see the braid displayed with the crossings in the sequence that they're read off the Felsner diagram.

Do you know what is bothering the patchbot? The doctest_continuation plugin is known to be broken (fixed, apparently, in the newest version of the patchbot), but it's also failing to build the documentation, though it hardly seems likely that this is our problem.

che(eeee)ers,

Hugh

[hthomas]

Re-bonjour!

Actually, I thought some more about my suggestion to let people see the braid displayed with the transpositions in a particular order, and I think that, while it's not a bad idea for something to include eventually, it makes sense as part of a larger project including sorting networks / type A subword complexes, as studied by, for example, Christian Stump and Vincent Pilaud. But the implementation of this in Sage has not gone very far yet (see #11010).

cheers,

Hugh

[ncohen]

Helloooooo again ! I don't see the changes you mention in the Felsner encoding in your patch... Is that where you included them ?

Nathann

[hthomas]

It's lines 302-303 of the file after the review patch is applied. Sorry if I wasn't clear!

Hugh

[ncohen]

Arggggg ! I'm stupid :-P

Okayokay, I will give it a look soon. Right now, I am trying to move the plot function of Braid Groups to the plot/ directory, so that it can be reused easily elsewhere.

Nathann

[ncohen]

Hello agaiiiiiiiiiiiiiin !!

Wellwellwell.. I spend quiiiiiiiite a lot of time trying to move the Braid's plot function to plot/braid_plot.py, and it failed in many many differents ways. For a start this plot never draws two crossings atop of each other, which means that a large number of crossing will produce a veeeeery wide drawing. Then the code was a bit ugly, so I rewrote it with a lambda function. Then I noticed that there were some "negative" strands in this plot method, and I have no idea how to implement cleanly a function that would deal with those negative strands and those we need in this module.

Soooooooooooo I give up ! :-P

Sorry about that, but I really spent a lot of time on this and I know that I modify a code that I do not understand... And I did this many many times already, and it gets less and less funny :-P

Sooooooo instead of the 1000 patches I uploaded, please only consider the "lastpatch". It converts everything to a list instead of doing a deepcopy, which solves your equality problem. And you were right about this line in the decoding of a Felsner matrix ! The shorter it is, the better.. Thank you :-)

Nathann

[hthomas]

Hiiiii!

Thanks, nice solution to the lists/tuples!

If the code from braid groups can't be easily applied to this use, then there's no harm in not using it.

The patchbot cannot see the apply instruction in the description, so here it is for the bot:

apply trac_12090-rebase.patch, trac_12090-review.patch, trac_12090-lastpatch.patch

I should also run a test or two myself, I guess, but I should be able to give it a positive review within the next week.

cheers,

Hugh

[hthomas]

Sorry, it was apparently a long week!

I am fine with everything now.

For the record, the patchbot is complaining about two things.

• One is the format of multi-line doctests. This minor format issue in the original patch is fixed in the review patch.

• The other is that the patchbot detects that the number of modules has increased. But since nothing from the new module is imported at startup, there doesn't seem to me to be a problem with this.

[ncohen]

Wow ! Thank you very much :-)

Nathann