Opened 6 years ago

Closed 2 weeks ago

#22349 closed enhancement (fixed)

Deprecate sorting of Graph vertices and edges by default

Reported by: jdemeyer Owned by:
Priority: critical Milestone: sage-9.7
Component: graph theory Keywords: python3, richcmp
Cc: Stefan, jmantysalo, jhpalmieri Merged in:
Authors: John Palmieri, David Coudert Reviewers: David Coudert, John Palmieri
Report Upstream: N/A Work issues:
Branch: fe93716 (Commits, GitHub, GitLab) Commit: fe93716223af144c0c07fad94eea920e10f139bb
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (83)

comment:1 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 6 years ago by jdemeyer

  • Summary changed from Graph.vertices() should not sort by default to Graph.vertices() should not be sorted

comment:4 Changed 6 years ago by jdemeyer

  • Summary changed from Graph.vertices() should not be sorted to Deprecate sorting of Graph.vertices()

comment:5 Changed 6 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Deprecate sorting of Graph.vertices() to Deprecate sorting of Graph vertices and edges

comment:6 Changed 6 years ago by jdemeyer

  • Summary changed from Deprecate sorting of Graph vertices and edges to Deprecate sorting of Graph vertices and edges by default

comment:7 Changed 6 years ago by jdemeyer

  • Branch set to u/jdemeyer/graph_vertices___should_not_be_sorted

comment:8 Changed 6 years ago by git

  • Commit set to 1c3a584d5f578ab4ff71969b79904ed1220ca4a1

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

1c3a584Deprecate default sorting of Graph vertices and edges

comment:9 follow-up: Changed 6 years ago by dcoudert

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

comment:10 in reply to: ↑ 9 Changed 6 years ago by jdemeyer

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

comment:11 follow-ups: Changed 6 years ago by dcoudert

Now I understand the need for this big change.

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

comment:12 in reply to: ↑ 11 Changed 6 years ago by jdemeyer

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?

Last edited 6 years ago by jdemeyer (previous) (diff)

comment:13 follow-up: Changed 6 years ago by mmezzarobba

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.

comment:14 Changed 6 years ago by jdemeyer

  • Dependencies set to #22383

comment:15 Changed 6 years ago by git

  • Commit changed from 1c3a584d5f578ab4ff71969b79904ed1220ca4a1 to aa0691f9fa7b03f9130b398923d92de3fb5fcf36

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

aa0691fDeprecate default sorting of Graph vertices and edges

comment:16 Changed 5 years ago by Stefan

  • Cc Stefan added

comment:17 in reply to: ↑ 11 ; follow-ups: Changed 5 years ago by nbruin

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

comment:18 in reply to: ↑ 13 Changed 5 years ago by jdemeyer

Replying to mmezzarobba:

  • 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.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:19 in reply to: ↑ 17 Changed 5 years ago by jdemeyer

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.

comment:20 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by mmezzarobba

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

comment:21 in reply to: ↑ 20 ; follow-up: Changed 5 years ago by jdemeyer

Replying to mmezzarobba:

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.

comment:22 in reply to: ↑ 21 Changed 5 years ago by mmezzarobba

Replying to jdemeyer:

Replying to mmezzarobba:

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.

comment:23 Changed 4 years ago by jdemeyer

  • Keywords richcmp added
  • Milestone changed from sage-7.6 to sage-8.2

comment:24 Changed 4 years ago by chapoton

  • Keywords python3 added

comment:25 Changed 4 years ago by saraedum

  • Work issues set to merge conflicts

comment:26 Changed 4 years ago by jdemeyer

  • Work issues merge conflicts deleted

comment:27 Changed 4 years ago by chapoton

  • Dependencies #22383 deleted

comment:28 Changed 4 years ago by dcoudert

  • Milestone changed from sage-8.2 to sage-8.4

comment:29 Changed 4 years ago by jmantysalo

  • Cc jmantysalo added

comment:30 Changed 4 years ago by jhpalmieri

  • Cc jhpalmieri added

comment:31 Changed 4 years ago by dcoudert

Apart from the need for ensuring that the internal order of vertices/edges during iterations is always the same (many algorithms assume that we have such a fixed order, whatever it is) and doing our best to preserve a nice display for interactive use, I think we have another issue:

  • For an edge (u, v, label) in an undirected graph, we usually have u <= v. So somehow we have a sorting here and many algorithms assume that vertices are ordered (not all). If I understand well, it is a problem with Python3 if vertex labels are of different types. We must find a solution for that.
  • In many algorithms, we have tests like if u < v. Again a big problem.

So what can we do ?

The only good news here is that vertices must be immutable.

comment:32 Changed 4 years ago by dcoudert

#26169 Trial for not sorting multiple edges

comment:33 Changed 4 years ago by jdemeyer

Do we already have a plan for this ticket? I know that there have many graph-related Python 3 tickets, but I'm a bit lost on the overall plan.

comment:34 Changed 4 years ago by jdemeyer

I am asking because there are now only a handful of doctest failures remaining in #22029 and they are almost all due to sorting in graphs.

comment:35 Changed 4 years ago by dcoudert

There are 3 different points here: 1) sorting the list of vertices, 2) sorting the list of edges, and 3) sorting the vertices of an edge.

For 1), we made huge progresses in reducing the dependency of methods to .vertices(). I'm not sure how many methods still rely on it. Most of them now use the ordering given by list(G) without making specific assumption on that order. We create a mapping when needed, and pass it to some methods. We can certainly completely avoid that dependency, but can we do that without deprecation ?

For 2), similarly, we have reduced the number of methods relying on .edges(), plus we can use sort=False parameter. We can try and see...

3) is more tricky and I don't know how to do that yet.

comment:36 Changed 4 years ago by jdemeyer

For 1) there is still an issue with relabel(): #27027

comment:37 Changed 4 years ago by jdemeyer

And one more with graph_isom_equivalent_non_edge_labeled_graph(): #27029

comment:38 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Milestone changed from sage-8.4 to sage-8.7

comment:39 Changed 3 years ago by dcoudert

We have now drastically reduced the dependency to .vertices() and .edges() in the graph module (except in doctests, but we can specify sort=True or just change the expected output). We must now identify the remaining tasks to do and schedule the work. I propose to do that in #26640 to get a full picture.

comment:40 Changed 3 years ago by jdemeyer

Here is a concrete proposal for this ticket:

  1. If no sort option is given (the default), give a deprecation and try to sort but fail gracefully if the input is not sortable.
  1. If a sort option is given, do as before.

comment:41 Changed 3 years ago by jdemeyer

I also like the idea that somebody posted on sage-devel (I don't remember who) that .vertices() and .edges() should return a "view" which could have various operations on it.

comment:42 Changed 3 years ago by dcoudert

It's Thierry (this message). I also like this idea. Should we do that here, before in another ticket, or later ?

Networkx now also use views networkx.Graph.edges.

comment:43 Changed 3 years ago by dcoudert

A proposal for an EdgeView in #27408.

comment:44 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:45 Changed 3 years ago by embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

comment:46 Changed 2 years ago by dcoudert

  • Milestone set to sage-9.2

Now that we have EdgesView? #27408 and Python3, we have few remaining methods methods effectively relying on the order of the vertices and/or edges. So we should restart working on this ticket for 9.2.

comment:47 Changed 2 years ago by dcoudert

With #30145, we propose to deprecate edge_iterator, thus generalizing the use of .edges method and so of EdgesView. After that, it should be easier to deprecate sorting edges by default.

comment:48 Changed 2 years ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:49 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:50 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:51 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:52 follow-up: Changed 5 months ago by dcoudert

Actually, #27408 has silently (not mentioned in the ticket) introduced a deprecation warning for sorting edges by default, but it is used in method .edges(...) only when sort is None and the default value of sort is True. So I think no-one is aware of it.

I'm not sure how to make this deprecation warning visible without breaking numerous doctests.

comment:53 Changed 5 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7

comment:54 in reply to: ↑ 52 Changed 7 weeks ago by alexjbest

Replying to dcoudert:

Actually, #27408 has silently (not mentioned in the ticket) introduced a deprecation warning for sorting edges by default, but it is used in method .edges(...) only when sort is None and the default value of sort is True. So I think no-one is aware of it.

I'm not sure how to make this deprecation warning visible without breaking numerous doctests.

I'd be interested in seeing this ticket resolved, perhaps you could ask about how to go about this deprecation on sage-devel? Or I am happy to follow this up if you'd prefer.

comment:55 Changed 7 weeks ago by dcoudert

The difficulty is that we still have some methods relying on .vertices(), and I don't know how to avoid that.

For instance in graph.py: effective_resistance_matrix, common_neighbors_matrix, orientations (but this one can be avoided easily), chromatic_quasisymmetric_function, twograph, write_to_eps. And there might be other modules using graphs and relying on the ordering of the vertices given by .vertices() (e.g., combinat, geometry, groups, matroids, schemes, topology, etc..

So the first step might be to identify methods/modules relying on .vertices() and try to modify them. Once done, we will be able to safely deprecate sorting by default.

comment:56 Changed 7 weeks ago by jhpalmieri

The .vertices() method is probably used lots of times, but one fix could be:

  • every time it's used, add the argument sort=False or sort=True as necessary,
  • and then change the default to sort=False.

Maybe it's easier with edges: add the explicit argument everywhere and then change the default to None.

Or is that too naïve? I tried this change:

  • src/sage/graphs/graph.py

    diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
    index 1579f23ad8..5dbb937b6b 100644
    a b class Graph(GenericGraph): 
    34803480            name = 'An orientation of ' + name
    34813481
    34823482        if not self.size():
    3483             D = DiGraph(data=[self.vertices(), []],
     3483            D = DiGraph(data=[self.vertices(sort=False), []],
    34843484                        format='vertices_and_edges',
    34853485                        name=name,
    34863486                        pos=self._pos,
    class Graph(GenericGraph): 
    34943494
    34953495        E = [[(u,v,label), (v,u,label)] if u != v else [(u,v,label)]
    34963496             for u,v,label in self.edge_iterator()]
    3497         verts = self.vertices()
     3497        verts = self.vertices(sort=False)
    34983498        for edges in itertools.product(*E):
    34993499            D = DiGraph(data=[verts, edges],
    35003500                        format='vertices_and_edges',
    class Graph(GenericGraph): 
    40094009            R = t.parent()
    40104010        M = QuasiSymmetricFunctions(R).M()
    40114011        ret = M.zero()
    4012         V = self.vertices()
     4012        V = self.vertices(sort=False)
    40134013
    40144014        def asc(sigma):
    40154015            stat = 0
    class Graph(GenericGraph): 
    61856185                T.append([x, y, z])
    61866186
    61876187        T = TwoGraph(T)
    6188         T.relabel({i: v for i,v in enumerate(self.vertices())})
     6188        T.relabel({i: v for i,v in enumerate(self.vertices(sort=False))})
    61896189
    61906190        return T
    61916191
    class Graph(GenericGraph): 
    62216221        if filename[-4:] != '.eps':
    62226222            filename += '.eps'
    62236223        f = open(filename, 'w')
    6224         f.write( print_graph_eps(self.vertices(), self.edge_iterator(), pos) )
     6224        f.write( print_graph_eps(self.vertices(sort=False), self.edge_iterator(), pos) )
    62256225        f.close()
    62266226
    62276227    @doc_index("Algorithmically hard stuff")
    class Graph(GenericGraph): 
    79407940            D = None
    79417941        elif self.order() == 1:
    79427942            D = create_prime_node()
    7943             D.children.append(create_normal_node(self.vertices()[0]))
     7943            D.children.append(create_normal_node(self.vertices(sort=False)[0]))
    79447944        else:
    79457945            D = habib_maurer_algorithm(self)
    79467946
    class Graph(GenericGraph): 
    92259225        if not n:
    92269226            raise ValueError('unable to compute effective resistance for an empty Graph object')
    92279227        if vertices is None:
    9228             vertices = self.vertices()
     9228            vertices = self.vertices(sort=False)
    92299229        self._scream_if_not_simple()
    92309230        if not self.is_connected():
    92319231            raise ValueError('the Graph is not a connected graph')
    class Graph(GenericGraph): 
    94589458        """
    94599459        self._scream_if_not_simple()
    94609460        if vertices is None:
    9461             vertices = self.vertices()
     9461            vertices = self.vertices(sort=False)
    94629462        set_immutable = kwds.pop('immutable', False)
    94639463        A = self.adjacency_matrix(vertices=vertices, base_ring=base_ring, immutable=True, **kwds)
    94649464        M = A**2

and all tests in the graphs directory still passed.

comment:57 follow-up: Changed 7 weeks ago by dcoudert

We cannot blindly use .vertices(sort=False). It will clearly break badly some methods, for instance methods building adjacency or laplacian matrices, etc. We already pave the way by reducing the number of situations in which we call .vertices(), but we still have work to do to reduce the dependency. We did the same for .edges().

The safe way is to use only .vertices(sort=True), and whenever possible, avoid calls to .vertices(). For instance, I see in generic_graph.py a call to self.vertices(sort=False)[0] while we have self.order() == 1. So we can avoid this call.

Then, we can set the default to None with a deprecation warning that the default will be changed to False.

comment:58 in reply to: ↑ 57 Changed 7 weeks ago by jhpalmieri

Replying to dcoudert:

We cannot blindly use .vertices(sort=False).

That's not what I suggested. Please reread the first bullet point.

comment:59 Changed 7 weeks ago by dcoudert

Right, I missed some parts. I agree with your proposal, but we need an appropriate deprecation warning to inform users of the change. It's a big change.

comment:60 Changed 5 weeks ago by jhpalmieri

The best I can think of right now is:

  • Make the default sort=None and raise a deprecation warning if this default gets used, thereby requiring an explicit argument everywhere in the Sage library.
  • So use sort=False or sort=True as appropriate in the library.

Then later we can change the default to sort=False.

comment:61 Changed 5 weeks ago by jhpalmieri

  • Branch changed from u/jdemeyer/graph_vertices___should_not_be_sorted to u/jhpalmieri/graph_vertices___should_not_be_sorted

comment:62 Changed 5 weeks ago by jhpalmieri

  • Commit changed from aa0691f9fa7b03f9130b398923d92de3fb5fcf36 to b6b6c34d8647620f41b1b392c5755e4bcbfe4779

Here is a start. This does what I proposed in comment:60, and all tests pass. I was not that careful in choosing sort=True or sort=False, and so I would not surprised if we could use sort=False in more places. Feel free to modify the branch.


New commits:

27a6483trac 22349: vertex sorting
b6b6c34trac 22349: edge sorting

comment:63 Changed 5 weeks ago by jhpalmieri

The key changes are in graphs/generic_graph.py:

@@ -10972,15 +10974,20 @@ class GenericGraph(GenericGraph_pyx):
         for u in self._backend.iterator_nbrs(vertex):
             yield u
 
-    def vertices(self, sort=True, key=None, degree=None, vertex_property=None):
+    def vertices(self, sort=None, key=None, degree=None, vertex_property=None):
         r"""
         Return a list of the vertices.
 
         INPUT:
 
-        - ``sort`` -- boolean (default: ``True``); if ``True``, vertices are
+        - ``sort`` -- boolean (default: ``None``); if ``True``, vertices are
           sorted according to the default ordering
 
+          As of :trac:`22349`, this argument must be explicitly
+          specified (unless a ``key`` is given); otherwise a warning
+          is printed and ``sort=True`` is used. The default will
+          eventually be changed to ``False``.
+
         - ``key`` -- a function (default: ``None``); a function that takes a
           vertex as its one argument and returns a value that can be used for
           comparisons in the sorting algorithm (we must have ``sort=True``)

and

@@ -11065,9 +11072,23 @@ class GenericGraph(GenericGraph_pyx):
             Traceback (most recent call last):
             ...
             ValueError: sort keyword is False, yet a key function is given
+
+        Deprecation warning for ``sort=None`` (:trac:`22349`)::
+
+            sage: G = graphs.HouseGraph()
+            sage: G.vertices()
+            doctest:...: DeprecationWarning: parameter 'sort' will be set to False by default in the future
+            See http://trac.sagemath.org/22349 for details.
+            [0, 1, 2, 3, 4]
         """
+        if sort is None:
+            if key is None:
+                deprecation(22349, "parameter 'sort' will be set to False by default in the future")
+            sort = True
+
         if (not sort) and key:
             raise ValueError('sort keyword is False, yet a key function is given')
+
         if sort:
             return sorted(self.vertex_iterator(degree=degree, vertex_property=vertex_property), key=key)
         return list(self.vertex_iterator(degree=degree, vertex_property=vertex_property))

and similar for edges (although edges already printed a warning if None was used, but None was not the default, so it had to be called explicitly as g.edges(sort=None) to trigger the warning before).

comment:64 Changed 5 weeks ago by dcoudert

I'm impressed !

I'm currently doing some tests and will push later some corrections.

comment:65 Changed 5 weeks ago by dcoudert

  • Branch changed from u/jhpalmieri/graph_vertices___should_not_be_sorted to public/graphs/22349_deprecate_sorting_vertices_and_edges
  • Commit changed from b6b6c34d8647620f41b1b392c5755e4bcbfe4779 to fee74b61393ff08220faccfb5bf29c62a07ecb64

I did a few changes in graphs and many tests. I have not detected any problem yet, but others may raise some issues.

This ticket highlights many places were the usage of graphs must be improved. I did some (minor) corrections in src/sage/schemes/curves/zariski_vankampen.py as example, but more can be done in this file. Typically, it is better to use for u in G: than for u in G.vertices(sort=False):. The ordering of the vertices is the same, but we avoid building the list of vertices. Tests like u in G.vertices(sort=False) should be replaced by u in G. etc. In future tickets, we should address (very bad) code like this in src/sage/geometry/hyperplane_arrangement/library.py

-        for e in G.edges():
-            i = G.vertices().index(e[0])
-            j = G.vertices().index(e[1])
+        for e in G.edges(sort=True):
+            i = G.vertices(sort=True).index(e[0])
+            j = G.vertices(sort=True).index(e[1])

Clearly, we need to define a mapping from vertices to index.


New commits:

fee74b6trac #22349: some corrections

comment:66 Changed 5 weeks ago by dcoudert

  • Status changed from new to needs_review

comment:67 Changed 5 weeks ago by jhpalmieri

  • Priority changed from major to critical

Great! I'm happy with your changes. We can try to get it merged soon, although with this many files affected, there might very well be merge conflicts.

comment:68 Changed 5 weeks ago by jhpalmieri

  • Authors set to John Palmieri, David Coudert
  • Reviewers set to David Coudert, John Palmieri

Positive review from me for your contributions.

comment:69 Changed 5 weeks ago by dcoudert

  • Status changed from needs_review to positive_review

We will certainly get merge conflicts (due to the many tickets improving the coding style for instance), but let's try.

Positive review from me too.

comment:70 Changed 4 weeks ago by vbraun

  • Status changed from positive_review to needs_work

Merge failure on top of:

83a3df1c99 Trac #34131: some doc polishing in symbolic

dee5229b00 Trac #34130: some doc polishing in groups

fd80fa111f Trac #34126: some doc polishing in categories

718d356f1c Trac #34125: some doc polishing in modular

49390d8bcf Trac #34124: some doc polishing in combinat

af94c25b54 Trac #34096: Fix typo: enviroment -> environment

d04c189c8e Trac #34050: add some space around == in paths and rational

1634bb6946 Trac #34047: Typo in _repr_Expression in symbolic/expression.pyx

dc8086fd57 Trac #34154: Fix repeated word typos

17b1c177aa Trac #34148: fix and activate pycodestyle E306

785bdbd0ec Trac #34136: modernize super() in rings (part one)

9882001355 Trac #34129: Dummy packages should write proper log files

dbc6b9e161 Trac #34109: pep8 for sagedoc.py

5e6a3318c8 Trac #34103: randomize infinite recursion

17ba76f00b Trac #34093: Wrong evaluation of elements of CBF[x] on polynomials from other rings

4657052737 Trac #34122: Bug in is_planar() method for directed graphs

c9cfb5395f Trac #34087: inverse reciprocal trig functions not (back)translated to/from Mathematica

1d6d055563 Trac #34076: pycodestyle cleanup in src/sage/graphs/genus.pyx

043d862b5d Trac #34071: pycodestyle cleanup in asteroidal_triples.pyx, chrompoly.pyx, cliquer.pyx, convexity_properties.pyx

b9b25dc735 Trac #34070: pycodestyle cleanup in src/sage/graphs/centrality.pyx

4ef2c6597d Trac #34069: pycodestyle cleanup in src/sage/graphs/comparability.pyx

5b1146766b Trac #34066: Tachyon help message

798adaa5a3 Trac #34065: pycodestyle cleanup in src/sage/graphs/bliss.pyx

ce62be23a2 Trac #34063: pycodestyle cleanup in src/sage/graphs/base/

a0eadb3e40 Trac #34059: Fix trivial case in conversion of list to number field element

fea0ac50a6 Trac #34057: changes about avoiding double dieses

9eefd5c27e Trac #34145: modernize super in geometry/

01e117dfd8 Trac #34137: modernize super in categories/

6c79334402 Trac #33819: build.yml: In workflow_dispatch, make container and base tag selectable; add doc

6a64ab8d00 Trac #33760: do not update _pos, _pos3d, _embedding on vertex/edge deletions

dbf091dbbb Trac #34139: fix the linter

625ac58151 Updated SageMath version to 9.7.beta5

merge was not clean: conflicts in src/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx

comment:71 Changed 4 weeks ago by git

  • Commit changed from fee74b61393ff08220faccfb5bf29c62a07ecb64 to 1e1ea2425398d1481f8fb4954600e934f92daa0c

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

39d156bsome doc polishing in groups
40b5e2amore fixes
68ea9dcMerge branch 'u/chapoton/34130' in 9.7.b5
1ec4bdftrac 22349: vertex sorting
a9ecbc5trac 22349: edge sorting
1e1ea24trac #22349: some corrections

comment:72 Changed 4 weeks ago by jhpalmieri

  • Status changed from needs_work to positive_review

Rebased over #34130.

comment:73 Changed 3 weeks ago by vbraun

  • Status changed from positive_review to needs_work

Merge failure on top of:

7f7149489c Updated SageMath version to 9.7.beta6

merge was not clean: conflicts in src/sage/combinat/yang_baxter_graph.py

comment:74 Changed 3 weeks ago by git

  • Commit changed from 1e1ea2425398d1481f8fb4954600e934f92daa0c to 4362cae77922139d9f1a7c97b7ae32469f60cedd

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

4362caeMerge branch 'develop' into t/22349/public/graphs/22349_deprecate_sorting_vertices_and_edges

comment:75 Changed 3 weeks ago by jhpalmieri

  • Status changed from needs_work to positive_review

Merged 9.7.beta6.

comment:76 Changed 3 weeks ago by dcoudert

Let's hope this one can be merged soon to avoid new conflicts.

comment:77 follow-up: Changed 3 weeks ago by vbraun

  • Status changed from positive_review to needs_work

see patchbot

comment:78 in reply to: ↑ 77 Changed 3 weeks ago by jhpalmieri

  • Status changed from needs_work to positive_review

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)

comment:79 Changed 3 weeks ago by tscrim

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

comment:80 Changed 3 weeks ago by tscrim

  • Status changed from positive_review to needs_work

comment:81 Changed 3 weeks ago by git

  • Commit changed from 4362cae77922139d9f1a7c97b7ae32469f60cedd to fe93716223af144c0c07fad94eea920e10f139bb

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

fe93716trac 22349: fix one more doctest

comment:82 Changed 3 weeks ago by jhpalmieri

  • Status changed from needs_work to positive_review

Doctest fixed.

comment:83 Changed 2 weeks ago by vbraun

  • Branch changed from public/graphs/22349_deprecate_sorting_vertices_and_edges to fe93716223af144c0c07fad94eea920e10f139bb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.