Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#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)

trac_9741-graph-vertices-sort.patch (4.9 KB) - added by rbeezer 4 years ago.
trac_9741-graph-vertices-sort-v2.patch (4.9 KB) - added by rbeezer 4 years ago.
Standalone patch, apply only this

Download all attachments as: .zip

Change History (23)

Changed 4 years ago by rbeezer

comment:1 Changed 4 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 follow-up: Changed 4 years ago by jason

Great idea! So what about those functions that call vertices(), like adjacency matrix, for example? Will they have a default key?

comment:3 in reply to: ↑ 2 Changed 4 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: Changed 4 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

Changed 4 years ago by rbeezer

Standalone patch, apply only this

comment:5 in reply to: ↑ 4 Changed 4 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 4 years ago by ncohen

  • Status changed from needs_review to positive_review

Nothing to add ! Positive review :-)

Nathann

comment:7 Changed 4 years ago by mpatel

  • Reviewers set to Nathann Cohen

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

Mitesh ? Did you really intend to comment this ticket ? O_o

Nathann

comment:11 Changed 4 years ago by mpatel

Yes, in case the suggested change somehow compromises the test. Or was the dsc = ... line introduced elsewhere?

comment:12 Changed 4 years ago by ncohen

I really have no idea what this line is about... O_o

Nathann

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

(oops...sorry for my interruption then ^^; )

Nathann

comment:16 in reply to: ↑ 14 Changed 4 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 4 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 4 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: Changed 4 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: Changed 4 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 4 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

Note: See TracTickets for help on using tickets.