Opened 8 years ago

Closed 6 years ago

#12090 closed enhancement (fixed)

Arrangements of pseudolines

Reported by: ncohen Owned by: mhampton
Priority: major Milestone: sage-5.12
Component: geometry Keywords:
Cc: Merged in: sage-5.12.beta1
Authors: Nathann Cohen Reviewers: Hugh Thomas
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12159 #11634 Stopgaps:

Description (last modified by 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:

Attachments (6)

trac_12090-rebase.patch (20.1 KB) - added by hthomas 6 years ago.
trac_12090-review.patch (17.8 KB) - added by hthomas 6 years ago.
trac_12090-braid-plot.patch (5.5 KB) - added by ncohen 6 years ago.
trac_12090-pseudolines-braid.patch (3.0 KB) - added by ncohen 6 years ago.
trac_12090-inprogress.patch (24.6 KB) - added by ncohen 6 years ago.
trac_12090-lastpatch.patch (753 bytes) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:3 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:4 Changed 8 years ago by ncohen

With more doctests and exceptions returned :-)

comment:5 Changed 7 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to needs rebase

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.

comment:6 Changed 7 years ago by davidloeffler

  • Dependencies set to #12159 #11634

comment:7 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

Done ! :-)

Nathann

comment:8 Changed 7 years ago by 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.

Changed 6 years ago by hthomas

Changed 6 years ago by hthomas

comment:9 Changed 6 years ago by 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

comment:10 Changed 6 years ago by 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

comment:11 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:12 Changed 6 years ago by 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

comment:13 follow-up: Changed 6 years ago by 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

comment:14 in reply to: ↑ 13 Changed 6 years ago by 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

comment:15 Changed 6 years ago by hthomas

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

Hugh

comment:16 Changed 6 years ago by 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

Changed 6 years ago by ncohen

Changed 6 years ago by ncohen

Changed 6 years ago by ncohen

comment:17 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_info to needs_review

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

Changed 6 years ago by ncohen

comment:18 Changed 6 years ago by hthomas

  • Reviewers set to Hugh Thomas
  • Work issues needs rebase deleted

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

comment:19 Changed 6 years ago by hthomas

  • Status changed from needs_review to positive_review

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.

comment:20 Changed 6 years ago by ncohen

Wow ! Thank you very much :-)

Nathann

comment:21 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:22 Changed 6 years ago by jdemeyer

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