Deprecate sorting of Graph vertices and edges by default

[jdemeyer]

Why does Graph.vertices() need to sort the list of vertices? If the user wants a sorted list, they can always call sorted() anyway. The same for Graph.edges().

Sorting is broken badly now that #22029 is merged.

CC: @sagetrac-Stefan @jm58660 @jhpalmieri

Component: graph theory

Keywords: richcmp

Author: John Palmieri, David Coudert

Branch/Commit: fe93716

Reviewer: David Coudert, John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/22349

[jdemeyer]

Branch: u/jdemeyer/graph_vertices___should_not_be_sorted

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1c3a584

Deprecate default sorting of Graph vertices and edges

[sagetrac-git]

Commit: 1c3a584

[dcoudert]

comment:9

What you propose to do is not an easy task. I suspect that many algorithms assume that the vertices are sorted. For sure, many algorithms assume that the ordering is always the same when calling vertices() and vertex_iterator(), so I hope that what you propose preserves this strong assumption.

Is your long term plan to remove parameter sort from the methods or just to set its default value to false ?
I don't know the potential problems of sorting with Python 3, so I'm not sure of the motivation.

Many many tests are broken

sage -t src/sage/graphs/generic_graph.py  # 45 doctests failed
sage -t src/sage/graphs/generators/smallgraphs.py  # 4 doctests failed
sage -t src/sage/graphs/strongly_regular_db.pyx  # 1 doctest failed
sage -t src/sage/graphs/graph.py  # 11 doctests failed
sage -t src/sage/graphs/base/static_sparse_graph.pyx  # 1 doctest failed
sage -t src/sage/graphs/generators/families.py  # 3 doctests failed
sage -t src/sage/graphs/digraph.py  # 10 doctests failed
sage -t src/sage/graphs/digraph_generators.py  # 3 doctests failed
sage -t src/sage/graphs/base/graph_backends.pyx  # 2 doctests failed
sage -t src/sage/graphs/generic_graph_pyx.pyx  # 3 doctests failed
sage -t src/sage/graphs/comparability.pyx  # 1 doctest failed
sage -t src/sage/graphs/bipartite_graph.py  # 3 doctests failed
sage -t src/sage/graphs/base/c_graph.pyx  # 1 doctest failed
sage -t src/sage/graphs/graph_decompositions/vertex_separation.pyx  # 4 doctests failed
sage -t src/sage/graphs/schnyder.py  # 1 doctest failed
sage -t src/sage/graphs/line_graph.py  # 3 doctests failed
sage -t src/sage/graphs/isgci.py  # 1 doctest failed
sage -t src/sage/graphs/graph_decompositions/graph_products.pyx  # 1 doctest failed
sage -t src/sage/quivers/path_semigroup.py  # 3 doctests failed
sage -t src/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx  # 1 doctest failed

for instance (random copy/paste)

File "src/sage/graphs/line_graph.py", line 466, in sage.graphs.line_graph.root_graph
Failed example:
    root_graph(graphs.DiamondGraph())
Expected:
    (Graph on 4 vertices, {0: (0, 3), 1: (0, 1), 2: (0, 2), 3: (1, 2)})
Got:
    (Graph on 4 vertices, {0: (1, 2), 1: (0, 1), 2: (0, 2), 3: (0, 3)})
**********************************************************************
File "src/sage/graphs/base/graph_backends.pyx", line 802, in sage.graphs.base.graph_backends.NetworkXGraphDeprecated.mutate
Failed example:
    G.edges(sort=False)
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 861, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.base.graph_backends.NetworkXGraphDeprecated.mutate[5]>", line 1, in <module>
        G.edges(sort=False)
    TypeError: edges() got an unexpected keyword argument 'sort'
**********************************************************************
File "src/sage/graphs/digraph.py", line 3424, in sage.graphs.digraph.DiGraph.flow_polytope
Failed example:
    fl.vertices(sort=False)
Exception raised:
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 861, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.digraph.DiGraph.flow_polytope[19]>", line 1, in <module>
        fl.vertices(sort=False)
    TypeError: __call__() got an unexpected keyword argument 'sort'
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 20558, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    d.automorphism_group(algorithm='sage')
Expected:
    Permutation Group with generators [('01','02')('10','20')('11','22')('12','21')]
Got:
    Permutation Group with generators [()]
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 20197, in sage.graphs.generic_graph.GenericGraph.degree_to_cell
Failed example:
    G.degree_to_cell('111', cell)
Expected:
    0
Got:
    1

[jdemeyer]

comment:10

Replying to @dcoudert:

What you propose to do is not an easy task.

I never claimed that it was easy. But it has to be done in order to support Python 3.

For sure, many algorithms assume that the ordering is always the same when calling vertices() and vertex_iterator(), so I hope that what you propose preserves this strong assumption.

It should remain the same, yes.

Is your long term plan to remove parameter sort from the methods or just to set its default value to false ?

I don't care much. I guess once the default is False, there will be little reason left to keep the sort keyword.

I don't know the potential problems of sorting with Python 3, so I'm not sure of the motivation.

The problem is that you cannot sort arbitrary things in Python 3. For example:

>>> sorted([1, "hello"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: str() < int()

[dcoudert]

comment:11

Now I understand the need for this big change.

Is there a way to sort arbitrary things in Python 3 ? some trick ?

[jdemeyer]

comment:12

Replying to @dcoudert:

Is there a way to sort arbitrary things in Python 3 ?

Of course there is. The question is: what would you expect from such "arbitrary" sorting?

And if it's arbitrary anyway: why would you want to "sort" in the first place?

[mezzarobba]

comment:13

As far as I understand, there are at least two different issues here:

• some algorithms want a consistent and easy to test order on the vertices, typically (but probably not only) to loop over the unordered pairs of vertices normalized by putting the smalled vertex first;
• in interactive use, when there is a natural order on the vertices (in practice, mostly when they are integers, strings, or possibly nested tuples of such things), people want to see the vertices, edges, etc. listed in an order that makes the output easy to read, and it would be a significant regression to take that away from them.

Additionally, it may well be the case that some algorithms also rely on vertices of a certain type (say tuples of integers) automatically coming out sorted in a particular order, I'm not sure.

[jdemeyer]

Dependencies: #22383

[sagetrac-git]

Changed commit from 1c3a584 to aa0691f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

aa0691f

Deprecate default sorting of Graph vertices and edges

[nbruin]

comment:17

Replying to @dcoudert:

Now I understand the need for this big change.

Is there a way to sort arbitrary things in Python 3 ? some trick ?

one way is

sorted( ..., key=str )

You could of course use another key function that uses some sorting heuristic (something like the key function used by https://pypi.python.org/pypi/natsort)

Display functions in IPython have hooks for nice sorting (used for dicts and sets), so if graphs need to display their keys and edges in a nice way, that's probably the hook to go for.

Algorithms that need their edges sorted should either insist on sortable labels or sort by index tuples or something like that (something that is guaranteed to be sortable regardless of what the user decides to use as labels).

[jdemeyer]

comment:18

Replying to @mezzarobba:

• in interactive use, when there is a natural order on the vertices (in practice, mostly when they are integers, strings, or possibly nested tuples of such things), people want to see the vertices, edges, etc. listed in an order that makes the output easy to read, and it would be a significant regression to take that away from them.

In that case, the best solution is probably to use a custom class for this. It would behave exactly like a Python list (or tuple) in all possible ways, except that it would be sorted on display.

[jdemeyer]

comment:19

Replying to @nbruin:

Display functions in IPython have hooks for nice sorting (used for dicts and sets), so if graphs need to display their keys and edges in a nice way, that's probably the hook to go for.

Nils, I only just saw your comment now. But yes, this was exactly my point too.

[mezzarobba]

comment:20

Replying to @nbruin:

Algorithms that need their edges sorted should either insist on sortable labels or sort by index tuples or something like that (something that is guaranteed to be sortable regardless of what the user decides to use as labels).

They could simply sort by id(), provided that the same label is not represented by several physically distinct objects that compare equal. Unfortunately, this probably does happen (see #22374).

[jdemeyer]

comment:21

Replying to @mezzarobba:

They could simply sort by id()

If you want to sort by id(), what is the purpose of sorting at all? I mean, it's not sorting, it's putting in a deterministic (but otherwise arbitrary) order. Assuming that methods like vertices() return the vertices in a deterministic order, I don't see the point.

[mezzarobba]

comment:22

Replying to @jdemeyer:

Replying to @mezzarobba:

They could simply sort by id()

If you want to sort by id(), what is the purpose of sorting at all? I mean, it's not sorting, it's putting in a deterministic (but otherwise arbitrary) order. Assuming that methods like vertices() return the vertices in a deterministic order, I don't see the point.

All I'm saying is that some algorithms do want to access the vertices in some arbitrary deterministic order, typically in order to iterate over the unordered pairs {v,v'}, and, as far as I remember, currently rely on the output of vertices() etc. being sorted to do that. If all the methods these algorithms use to access the vertices return them in the same deterministic order, then indeed, there is no need to do anything, otherwise, sorting by id() may be a better option than requiring the labels to be ordered.

[jdemeyer]

Changed keywords from none to richcmp

[jhpalmieri]

comment:78

Replying to @vbraun:

see patchbot

Which part? I believe the "deprecation number" warning is from this change:

@@ -12229,7 +12255,8 @@ class GenericGraph(GenericGraph_pyx):
             [(0, 1, None), (0, 2, None), (1, 3, None), (2, 3, None), (2, 4, None), (3, 4, None)]
         """
         if sort is None:
-            deprecation(27408, "parameter 'sort' will be set to False by default in the future")
+            if key is None:
+                deprecation(27408, "parameter 'sort' will be set to False by default in the future")
             sort = True
 
         if vertices is not None and vertices in self:

and that seems appropriate: no reason to change the ticket number. (That's the only match for "27408" in the changes for this ticket.)

The pyflakes warnings are not related to this ticket: they are in files touched by this ticket but not where we've modified them. (In addition, I don't understand the warning about simplicial_complex.py)

[tscrim]

comment:79

It is more fundamental: there is a test failing for src/sage/graphs/edge_connectivity.pyx.

[sagetrac-git]

Changed commit from 4362cae to fe93716

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

fe93716

trac 22349: fix one more doctest

[jhpalmieri]

comment:82

Doctest fixed.

[vbraun]

Changed branch from public/graphs/22349_deprecate_sorting_vertices_and_edges to fe93716

[tornaria]

How long it should take until the deprecation warning is removed?

[kcrisman]

How long it should take until the deprecation warning is removed?

I hear you - see e.g. here. I think there is still a waiting period for removing them, though - a year, was it? Maybe a new ticket/issue should be opened for that.