Opened 8 years ago
Closed 7 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 )
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)
Change History (28)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:4 Changed 8 years ago by
comment:5 Changed 8 years ago by
- Status changed from needs_review to needs_work
- Work issues set to needs rebase
comment:6 Changed 8 years ago by
- Dependencies set to #12159 #11634
comment:8 Changed 8 years ago by
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 7 years ago by
Changed 7 years ago by
comment:9 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
- Status changed from needs_review to needs_info
comment:12 Changed 7 years ago by
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: ↓ 14 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
It's lines 302-303 of the file after the review patch is applied. Sorry if I wasn't clear!
Hugh
comment:16 Changed 7 years ago by
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 7 years ago by
Changed 7 years ago by
Changed 7 years ago by
comment:17 Changed 7 years ago by
- 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 7 years ago by
comment:18 Changed 7 years ago by
- 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 7 years ago by
- 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 7 years ago by
Wow ! Thank you very much :-)
Nathann
comment:21 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:22 Changed 7 years ago by
- Merged in set to sage-5.12.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
With more doctests and exceptions returned
:-)