#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 )
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 (24)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
comment:3 in reply to: ↑ 2 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
- Status changed from needs_review to positive_review
Nothing to add ! Positive review :-)
Nathann
comment:7 Changed 8 years ago by
- Reviewers set to Nathann Cohen
comment:8 Changed 8 years ago by
- Merged in set to sage-4.6.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:9 Changed 8 years ago by
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 8 years ago by
Mitesh ? Did you really intend to comment this ticket ? O_o
Nathann
comment:11 Changed 8 years ago by
Yes, in case the suggested change somehow compromises the test. Or was the dsc = ...
line introduced elsewhere?
comment:12 Changed 8 years ago by
I really have no idea what this line is about... O_o
Nathann
comment:13 follow-up: ↓ 14 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
(oops...sorry for my interruption then ^^;
)
Nathann
comment:16 in reply to: ↑ 14 Changed 8 years ago by
- 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 8 years ago by
- 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 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
Replying to mpatel:
No, that's sounds good to me. Thanks for your explanation.
Oops: I suppose I should have written
dsc = discriminant
ordsc = 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
comment:22 Changed 18 months ago by
Why should vertices be sorted in the first place? This is going to break badly in Python 3: #22349
Great idea! So what about those functions that call vertices(), like adjacency matrix, for example? Will they have a default key?