The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Sorting vertices of a graph
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 6 messages
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful

From:
To:
Cc:
Followup To:
 Add Cc | Add Followup-to | Edit Subject
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jul 24 2010, 3:20 am
From: Rob Beezer <goo...@beezer.cotse.net>
Date: Sat, 24 Jul 2010 00:20:15 -0700 (PDT)
Local: Sat, Jul 24 2010 3:20 am
Subject: Sorting vertices of a graph
The vertices() method for graphs says the resulting list is always
sorted.  But while you can use a variety of objects as the vertices of
a graph (very nice), they do not always compare cleanly (not so
nice).  So I got bit tonight on a doctest where one vertex was an
integer and one was a symbolic expression.  With a randomized order
for the tests, the results would vary.

Do we need to be more careful about the vertices() method, either in
action or in claims?  When the documentation says the list is sorted,
is "sorted" a verb or an adjective?

I presume it is expecting too much that any two objects can be
comparable somehow?

Rob

sage: var('x')
x
sage: G=Graph({0:[x]})
sage: vert = G.vertices()
sage: vert
[0, x]
sage: sorted(vert)
[0, x]
sage: vert.reverse()
sage: vert
[x, 0]
sage: sorted(vert)
[x, 0]
sage: G.vertices?
<snip>
Note that the output of the vertices() function is always sorted.
<snip>

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Jul 24 2010, 7:27 am
From: Robert Miller <r...@rlmiller.org>
Date: Sat, 24 Jul 2010 13:27:26 +0200
Local: Sat, Jul 24 2010 7:27 am
Subject: Re: [sage-devel] Sorting vertices of a graph
I would simply add a caveat to the documentation. Most users use
either integers for vertices, or a set of certain kinds of objects. It
should be noted that "<" should implement a total ordering for this to
be consistent, e.g. not just a poset. This is related to a debate
about whether "<" should give an ordering of poset elements for
computer science reasons (like binary search in a list) or for
mathematicians...

--
Robert L. Miller
http://www.rlmiller.org/

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Jul 24 2010, 2:54 pm
From: Rob Beezer <goo...@beezer.cotse.net>
Date: Sat, 24 Jul 2010 11:54:27 -0700 (PDT)
Local: Sat, Jul 24 2010 2:54 pm
Subject: Re: Sorting vertices of a graph
So it is a verb.  ;-)

Looks like similar comments apply to   edges().

I'm thinking that optionally passing in a comparison function would be
a nice thing to add - a minor convenience, but also it would drive
home the point that the sorting is somewhat the caller's
responsibility in non-trivial situations (ie for not most users).

I'll get a ticket started soon.

Rob

On Jul 24, 4:27 am, Robert Miller <r...@rlmiller.org> wrote:

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Jul 24 2010, 4:20 pm
From: Carl Witty <carl.wi...@gmail.com>
Date: Sat, 24 Jul 2010 13:20:25 -0700
Local: Sat, Jul 24 2010 4:20 pm
Subject: Re: [sage-devel] Re: Sorting vertices of a graph

On Sat, Jul 24, 2010 at 11:54 AM, Rob Beezer <goo...@beezer.cotse.net> wrote:
> So it is a verb.  ;-)

> Looks like similar comments apply to   edges().

> I'm thinking that optionally passing in a comparison function would be
> a nice thing to add - a minor convenience, but also it would drive
> home the point that the sorting is somewhat the caller's
> responsibility in non-trivial situations (ie for not most users).

> I'll get a ticket started soon.

Note that Python 3 has removed the comparison function argument for
List.sort() and similar functions, in favor of a "key" argument giving
a function that transforms a list element into a sortable element.
For example, if you want to sort by string representations, currently
you could do:

verts.sort(cmp=lambda a, b: cmp(str(a), str(b)))

but in Python 3 you would have to do:

verts.sort(key=str)

The idea is to discourage inefficient programming; the Python 3
version is better, because it calls str() on each element only once,
whereas the old version calls str() on each element O(log(N)) times.

Our current Python also has a key= argument for sort().

I suggest that we should follow Python 3 here for such APIs, and
optionally pass in a key= function rather than a cmp= comparison
function.

Carl

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Jul 25 2010, 1:28 am
From: Rob Beezer <goo...@beezer.cotse.net>
Date: Sat, 24 Jul 2010 22:28:49 -0700 (PDT)
Local: Sun, Jul 25 2010 1:28 am
Subject: Re: Sorting vertices of a graph
Hi Carl,

Thanks for the heads-up, its been so long since I read the Python 3
changes and that one hadn't stuck.  Will do.

Rob

On Jul 24, 1:20 pm, Carl Witty <carl.wi...@gmail.com> wrote:

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 13 2010, 1:39 pm
From: Rob Beezer <goo...@beezer.cotse.net>
Date: Fri, 13 Aug 2010 10:39:33 -0700 (PDT)
Local: Fri, Aug 13 2010 1:39 pm
Subject: Re: Sorting vertices of a graph
On Jul 24, 11:54 am, Rob Beezer <goo...@beezer.cotse.net> wrote:

> I'll get a ticket started soon.

Patches (resp. for vertices, edges) now at:

Rob

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 End of messages
 « Back to Discussions « Newer topic Older topic »

 Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy ©2013 Google