#9741 closed enhancement (fixed)
Sorting vertices of a graph
Reported by: | rbeezer | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.6 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.6.alpha1 | |
Authors: | Rob Beezer | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by rbeezer)
This patch adds a "key" argument to allow custom sorting of the output of the graph method vertices(). It adds to the documentation to make it clear that vertices will not always have a default sort order.
See:
#9742
http://groups.google.com/group/sage-devel/browse_thread/thread/40ac90ee3f28d723/
http://groups.google.com/group/sage-devel/browse_thread/thread/5adbb850f787373c/
Attachments (2)
Change History (23)
Changed 6 years ago by rbeezer
comment:1 Changed 6 years ago by rbeezer
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 6 years ago by jason
comment:3 in reply to: ↑ 2 Changed 6 years ago by rbeezer
Replying to jason:
Great idea! So what about those functions that call vertices(), like adjacency matrix, for example? Will they have a default key?
The default value for key (in Python) is None. I've specified None as the default for the key argument in this new function, so the behavior should be unchanged in other places that call vertices(), though after this patch that could be changed easily. This patch is really just a convenience, but more about highlighting that you should think about how the sorting is going to work (or not work) if you have "exotic" objects for vertices.
comment:4 follow-up: ↓ 5 Changed 6 years ago by ncohen
Hello !!!
Would it be possible to make a
"Return the list of vertices"
out of your
"Return a list of the vertices, usually as a sorted list" (Why "usually as") ?
When key=None, it is sorted using the "default" order... And anyway your docstrings make it perfectly clear later :-)
Nathann
comment:5 in reply to: ↑ 4 Changed 6 years ago by rbeezer
Replying to ncohen:
Would it be possible to make a
"Return the list of vertices"
out of your
"Return a list of the vertices, usually as a sorted list" (Why "usually as") ?
Yes, new v2 patch has this change. My original goal was to make the default sorting behavior more obvious, but you are right that the doctests should do the job of explaining that.
Thanks,
Rob
comment:6 Changed 6 years ago by ncohen
- Status changed from needs_review to positive_review
Nothing to add ! Positive review :-)
Nathann
comment:7 Changed 6 years ago by mpatel
- Reviewers set to Nathann Cohen
comment:8 Changed 6 years ago by mpatel
- Merged in set to sage-4.6.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:9 Changed 6 years ago by mpatel
We'll need to add a patch at #4000 to update this test line:
sage: dsc = sage.rings.polynomial.polynomial_element_generic.Polynomial_rational_dense.discriminant
I think we can use Polynomial_rational_flint, instead. See comment 88.
comment:10 Changed 6 years ago by ncohen
Mitesh ? Did you really intend to comment this ticket ? O_o
Nathann
comment:11 Changed 6 years ago by mpatel
Yes, in case the suggested change somehow compromises the test. Or was the dsc = ... line introduced elsewhere?
comment:12 Changed 6 years ago by ncohen
I really have no idea what this line is about... O_o
Nathann
comment:13 follow-up: ↓ 14 Changed 6 years ago by rbeezer
I made a graph with polynomials as vertices. The discriminant is a function on polynomials that I used as the key in a sort, to demo the new sorting capability of this ticket in the doctests.
Did something change elsewhere? This was passing tests before.
I could change this to something different. I'm traveling with family right now, but could work on it tomorrow night. How urgent is a fix?
Rob
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 16 Changed 6 years ago by mpatel
Replying to rbeezer:
Did something change elsewhere? This was passing tests before.
Ticket #4000 implements fast polynomial arithmetic over the rationals via FLINT1. It removes the class Polynomial_rational_dense but "replaces" it with Polynomial_rational_flint.
Would dsc = lambda x: x.discriminant() work in the sorting test? If it does, it could shield the test against changes to a lower-level API.
I could change this to something different. I'm traveling with family right now, but could work on it tomorrow night. How urgent is a fix?
It's not very urgent, though we're hoping to merge #4000 in 4.6.alpha2, which I plan to release at least a week from now (alpha1 is not yet out). Currently, however, there's a more serious build error at #4000.
comment:15 Changed 6 years ago by ncohen
(oops...sorry for my interruption then ^^; )
Nathann
comment:16 in reply to: ↑ 14 Changed 6 years ago by rbeezer
- Merged in sage-4.6.alpha1 deleted
- Status changed from closed to needs_work
Replying to mpatel:
Mitesh,
Thanks for the explanation and suggestion. I'll try to get something up in the next 12-24 hours.
Rob
comment:17 Changed 6 years ago by mpatel
- Merged in set to sage-4.6.alpha1
- Status changed from needs_work to closed
Thanks, Rob. This ticket is actually already in the released 4.6.alpha1, so we probably just need to change the key function in a small patch at #4000. I apologize for not being clear about this.
comment:18 Changed 6 years ago by rbeezer
Mitesh,
Sorry - not thinking clearly. I got it now. I thought carefully about messing with the ticket status - shoulda known not to!
I'll attach a fix to #4000 then. Maybe later tonight.
Thanks,
Rob
comment:19 follow-up: ↓ 20 Changed 6 years ago by rbeezer
Mitesh,
It would appear the dsc = lambda ... change would certainly fix this. But looking at the doctests, I remember now why I did what I did. All the other tests have keys made from lambda functions. I wanted to show how you could write out the fully-qualified name of some function (I could have imported it, as well) and use that as the key function.
Would it be so bad to just adjust the modules to the new names? I could add some documentation to make it clear why this construct looks a bit odd. But I think it would be educational for people not 100% familiar with Python having functions as first-class objects.
Rob
comment:20 in reply to: ↑ 19 ; follow-up: ↓ 21 Changed 6 years ago by mpatel
No, that's sounds good to me. Thanks for your explanation.
Oops: I suppose I should have written dsc = discriminant or dsc = sage.misc.functional.discriminant above.
comment:21 in reply to: ↑ 20 Changed 6 years ago by rbeezer
Replying to mpatel:
No, that's sounds good to me. Thanks for your explanation.
Oops: I suppose I should have written dsc = discriminant or dsc = sage.misc.functional.discriminant above.
Patch to fix this, with a bit more explanation, up at #4000.
Thanks, Mitesh, for guiding me through this one. First time I've had a mid-release conflict to resolve.
Rob
Great idea! So what about those functions that call vertices(), like adjacency matrix, for example? Will they have a default key?