Sorting vertices of a graph

20 views
Skip to first unread message

Rob Beezer

unread,
Jul 24, 2010, 3:20:15 AM7/24/10
to sage-devel
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>

Robert Miller

unread,
Jul 24, 2010, 7:27:26 AM7/24/10
to sage-...@googlegroups.com
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...

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

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

Rob Beezer

unread,
Jul 24, 2010, 2:54:27 PM7/24/10
to sage-devel
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
> > For more options, visit this group athttp://groups.google.com/group/sage-devel

Carl Witty

unread,
Jul 24, 2010, 4:20:25 PM7/24/10
to sage-...@googlegroups.com
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

Rob Beezer

unread,
Jul 25, 2010, 1:28:49 AM7/25/10
to sage-devel
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

Rob Beezer

unread,
Aug 13, 2010, 1:39:33 PM8/13/10
to sage-devel
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:

http://trac.sagemath.org/sage_trac/ticket/9741
http://trac.sagemath.org/sage_trac/ticket/9742

Rob
Reply all
Reply to author
Forward
0 new messages