Sage: Ticket #22349: Deprecate sorting of Graph vertices and edges by default
https://trac.sagemath.org/ticket/22349
<p>
Why does <code>Graph.vertices()</code> need to <em>sort</em> the list of vertices? If the user wants a sorted list, they can always call <code>sorted()</code> anyway. The same for <code>Graph.edges()</code>.
</p>
<p>
Sorting is broken badly now that <a class="closed ticket" href="https://trac.sagemath.org/ticket/22029" title="enhancement: Element richcmp: never use id() (closed: fixed)">#22029</a> is merged.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/22349
Trac 1.1.6jdemeyerFri, 10 Feb 2017 16:07:54 GMTdescription changed
https://trac.sagemath.org/ticket/22349#comment:1
https://trac.sagemath.org/ticket/22349#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/22349?action=diff&version=1">diff</a>)
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:08:51 GMTdescription changed
https://trac.sagemath.org/ticket/22349#comment:2
https://trac.sagemath.org/ticket/22349#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/22349?action=diff&version=2">diff</a>)
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:09:08 GMTsummary changed
https://trac.sagemath.org/ticket/22349#comment:3
https://trac.sagemath.org/ticket/22349#comment:3
<ul>
<li><strong>summary</strong>
changed from <em>Graph.vertices() should not sort by default</em> to <em>Graph.vertices() should not be sorted</em>
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:23:47 GMTsummary changed
https://trac.sagemath.org/ticket/22349#comment:4
https://trac.sagemath.org/ticket/22349#comment:4
<ul>
<li><strong>summary</strong>
changed from <em>Graph.vertices() should not be sorted</em> to <em>Deprecate sorting of Graph.vertices()</em>
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:37:39 GMTdescription, summary changed
https://trac.sagemath.org/ticket/22349#comment:5
https://trac.sagemath.org/ticket/22349#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/22349?action=diff&version=5">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Deprecate sorting of Graph.vertices()</em> to <em>Deprecate sorting of Graph vertices and edges</em>
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:40:39 GMTsummary changed
https://trac.sagemath.org/ticket/22349#comment:6
https://trac.sagemath.org/ticket/22349#comment:6
<ul>
<li><strong>summary</strong>
changed from <em>Deprecate sorting of Graph vertices and edges</em> to <em>Deprecate sorting of Graph vertices and edges by default</em>
</li>
</ul>
TicketjdemeyerFri, 10 Feb 2017 16:45:40 GMTbranch set
https://trac.sagemath.org/ticket/22349#comment:7
https://trac.sagemath.org/ticket/22349#comment:7
<ul>
<li><strong>branch</strong>
set to <em>u/jdemeyer/graph_vertices___should_not_be_sorted</em>
</li>
</ul>
TicketgitFri, 10 Feb 2017 17:28:04 GMTcommit set
https://trac.sagemath.org/ticket/22349#comment:8
https://trac.sagemath.org/ticket/22349#comment:8
<ul>
<li><strong>commit</strong>
set to <em>1c3a584d5f578ab4ff71969b79904ed1220ca4a1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1c3a584d5f578ab4ff71969b79904ed1220ca4a1"><span class="icon"></span>1c3a584</a></td><td><code>Deprecate default sorting of Graph vertices and edges</code>
</td></tr></table>
TicketdcoudertSat, 11 Feb 2017 10:36:38 GMT
https://trac.sagemath.org/ticket/22349#comment:9
https://trac.sagemath.org/ticket/22349#comment:9
<p>
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 <code>vertices()</code> and <code>vertex_iterator()</code>, so I hope that what you propose preserves this strong assumption.
</p>
<p>
Is your long term plan to remove parameter <code>sort</code> 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.
</p>
<p>
Many many tests are broken
</p>
<pre class="wiki">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
</pre><p>
for instance (random copy/paste)
</p>
<pre class="wiki">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
</pre>
TicketjdemeyerSat, 11 Feb 2017 13:22:50 GMT
https://trac.sagemath.org/ticket/22349#comment:10
https://trac.sagemath.org/ticket/22349#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:9" title="Comment 9">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
What you propose to do is not an easy task.
</p>
</blockquote>
<p>
I never claimed that it was easy. But it has to be done in order to support Python 3.
</p>
<blockquote class="citation">
<p>
For sure, many algorithms assume that the ordering is always the same when calling <code>vertices()</code> and <code>vertex_iterator()</code>, so I hope that what you propose preserves this strong assumption.
</p>
</blockquote>
<p>
It should remain the same, yes.
</p>
<blockquote class="citation">
<p>
Is your long term plan to remove parameter <code>sort</code> from the methods or just to set its default value to false ?
</p>
</blockquote>
<p>
I don't care much. I guess once the default is <code>False</code>, there will be little reason left to keep the <code>sort</code> keyword.
</p>
<blockquote class="citation">
<p>
I don't know the potential problems of sorting with Python 3, so I'm not sure of the motivation.
</p>
</blockquote>
<p>
The problem is that you cannot sort arbitrary things in Python 3. For example:
</p>
<pre class="wiki">>>> sorted([1, "hello"])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: str() < int()
</pre>
TicketdcoudertSat, 11 Feb 2017 15:10:56 GMT
https://trac.sagemath.org/ticket/22349#comment:11
https://trac.sagemath.org/ticket/22349#comment:11
<p>
Now I understand the need for this big change.
</p>
<p>
Is there a way to sort arbitrary things in Python 3 ? some trick ?
</p>
TicketjdemeyerSat, 11 Feb 2017 15:35:33 GMT
https://trac.sagemath.org/ticket/22349#comment:12
https://trac.sagemath.org/ticket/22349#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:11" title="Comment 11">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
Is there a way to sort arbitrary things in Python 3 ?
</p>
</blockquote>
<p>
Of course there is. The question is: what would you expect from such "arbitrary" sorting?
</p>
<p>
And if it's arbitrary anyway: why would you want to "sort" in the first place?
</p>
TicketmmezzarobbaTue, 14 Feb 2017 18:53:15 GMT
https://trac.sagemath.org/ticket/22349#comment:13
https://trac.sagemath.org/ticket/22349#comment:13
<p>
As far as I understand, there are at least two different issues here:
</p>
<ul><li>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;
</li><li>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), <em>people</em> 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.
</li></ul><p>
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.
</p>
TicketjdemeyerWed, 15 Feb 2017 08:36:36 GMTdependencies set
https://trac.sagemath.org/ticket/22349#comment:14
https://trac.sagemath.org/ticket/22349#comment:14
<ul>
<li><strong>dependencies</strong>
set to <em>#22383</em>
</li>
</ul>
TicketgitWed, 15 Feb 2017 08:36:50 GMTcommit changed
https://trac.sagemath.org/ticket/22349#comment:15
https://trac.sagemath.org/ticket/22349#comment:15
<ul>
<li><strong>commit</strong>
changed from <em>1c3a584d5f578ab4ff71969b79904ed1220ca4a1</em> to <em>aa0691f9fa7b03f9130b398923d92de3fb5fcf36</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=aa0691f9fa7b03f9130b398923d92de3fb5fcf36"><span class="icon"></span>aa0691f</a></td><td><code>Deprecate default sorting of Graph vertices and edges</code>
</td></tr></table>
TicketStefanWed, 09 Aug 2017 20:54:45 GMTcc set
https://trac.sagemath.org/ticket/22349#comment:16
https://trac.sagemath.org/ticket/22349#comment:16
<ul>
<li><strong>cc</strong>
<em>Stefan</em> added
</li>
</ul>
TicketnbruinMon, 06 Nov 2017 11:06:01 GMT
https://trac.sagemath.org/ticket/22349#comment:17
https://trac.sagemath.org/ticket/22349#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:11" title="Comment 11">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
Now I understand the need for this big change.
</p>
<p>
Is there a way to sort arbitrary things in Python 3 ? some trick ?
</p>
</blockquote>
<p>
one way is
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
sorted( ..., key=str )
</p>
</blockquote>
</blockquote>
</blockquote>
<p>
You could of course use another key function that uses some sorting heuristic (something like the key function used by <a class="ext-link" href="https://pypi.python.org/pypi/natsort"><span class="icon"></span>https://pypi.python.org/pypi/natsort</a>)
</p>
<p>
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.
</p>
<p>
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).
</p>
TicketjdemeyerMon, 06 Nov 2017 12:02:41 GMT
https://trac.sagemath.org/ticket/22349#comment:18
https://trac.sagemath.org/ticket/22349#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:13" title="Comment 13">mmezzarobba</a>:
</p>
<blockquote class="citation">
<ul><li>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), <em>people</em> 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.
</li></ul></blockquote>
<p>
In that case, the best solution is probably to use a custom class for this. It would behave exactly like a Python <code>list</code> (or <code>tuple</code>) in all possible ways, except that it would be sorted on display.
</p>
TicketjdemeyerMon, 06 Nov 2017 12:28:40 GMT
https://trac.sagemath.org/ticket/22349#comment:19
https://trac.sagemath.org/ticket/22349#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:17" title="Comment 17">nbruin</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Nils, I only just saw your comment now. But yes, this was exactly my point too.
</p>
TicketmmezzarobbaMon, 06 Nov 2017 12:37:52 GMT
https://trac.sagemath.org/ticket/22349#comment:20
https://trac.sagemath.org/ticket/22349#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:17" title="Comment 17">nbruin</a>:
</p>
<blockquote class="citation">
<p>
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).
</p>
</blockquote>
<p>
They could simply sort by <code>id()</code>, provided that the same label is not represented by several physically distinct objects that compare equal. Unfortunately, this probably does happen (see <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/22374" title="defect: {c,sparse}_graph: systematically turn integer-like vertices into ints (needs_work)">#22374</a>).
</p>
TicketjdemeyerMon, 06 Nov 2017 12:43:02 GMT
https://trac.sagemath.org/ticket/22349#comment:21
https://trac.sagemath.org/ticket/22349#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:20" title="Comment 20">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
They could simply sort by <code>id()</code>
</p>
</blockquote>
<p>
If you want to sort by <code>id()</code>, 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 <code>vertices()</code> return the vertices in a deterministic order, I don't see the point.
</p>
TicketmmezzarobbaMon, 06 Nov 2017 13:02:42 GMT
https://trac.sagemath.org/ticket/22349#comment:22
https://trac.sagemath.org/ticket/22349#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:21" title="Comment 21">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22349#comment:20" title="Comment 20">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
They could simply sort by <code>id()</code>
</p>
</blockquote>
<p>
If you want to sort by <code>id()</code>, 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 <code>vertices()</code> return the vertices in a deterministic order, I don't see the point.
</p>
</blockquote>
<p>
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 <code>vertices()</code> 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 <code>id()</code> may be a better option than requiring the labels to be ordered.
</p>
TicketjdemeyerThu, 29 Mar 2018 12:51:14 GMTmilestone changed; keywords set
https://trac.sagemath.org/ticket/22349#comment:23
https://trac.sagemath.org/ticket/22349#comment:23
<ul>
<li><strong>keywords</strong>
<em>richcmp</em> added
</li>
<li><strong>milestone</strong>
changed from <em>sage-7.6</em> to <em>sage-8.2</em>
</li>
</ul>
TicketchapotonWed, 11 Jul 2018 15:22:35 GMTkeywords changed
https://trac.sagemath.org/ticket/22349#comment:24
https://trac.sagemath.org/ticket/22349#comment:24
<ul>
<li><strong>keywords</strong>
<em>python3</em> added
</li>
</ul>
TicketsaraedumThu, 12 Jul 2018 12:37:43 GMTwork_issues set
https://trac.sagemath.org/ticket/22349#comment:25
https://trac.sagemath.org/ticket/22349#comment:25
<ul>
<li><strong>work_issues</strong>
set to <em>merge conflicts</em>
</li>
</ul>
TicketjdemeyerThu, 12 Jul 2018 14:23:50 GMTwork_issues deleted
https://trac.sagemath.org/ticket/22349#comment:26
https://trac.sagemath.org/ticket/22349#comment:26
<ul>
<li><strong>work_issues</strong>
<em>merge conflicts</em> deleted
</li>
</ul>
TicketchapotonThu, 30 Aug 2018 14:57:46 GMTdependencies deleted
https://trac.sagemath.org/ticket/22349#comment:27
https://trac.sagemath.org/ticket/22349#comment:27
<ul>
<li><strong>dependencies</strong>
<em>#22383</em> deleted
</li>
</ul>
TicketdcoudertThu, 30 Aug 2018 15:51:19 GMTmilestone changed
https://trac.sagemath.org/ticket/22349#comment:28
https://trac.sagemath.org/ticket/22349#comment:28
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.2</em> to <em>sage-8.4</em>
</li>
</ul>
TicketjmantysaloThu, 30 Aug 2018 17:18:48 GMTcc changed
https://trac.sagemath.org/ticket/22349#comment:29
https://trac.sagemath.org/ticket/22349#comment:29
<ul>
<li><strong>cc</strong>
<em>jmantysalo</em> added
</li>
</ul>
TicketjhpalmieriThu, 30 Aug 2018 21:49:38 GMTcc changed
https://trac.sagemath.org/ticket/22349#comment:30
https://trac.sagemath.org/ticket/22349#comment:30
<ul>
<li><strong>cc</strong>
<em>jhpalmieri</em> added
</li>
</ul>
TicketdcoudertFri, 31 Aug 2018 16:35:03 GMT
https://trac.sagemath.org/ticket/22349#comment:31
https://trac.sagemath.org/ticket/22349#comment:31
<p>
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:
</p>
<ul><li>For an edge <code>(u, v, label)</code> in an undirected graph, we usually have <code>u <= v</code>. 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.
</li><li>In many algorithms, we have tests like <code>if u < v</code>. Again a big problem.
</li></ul><p>
So what can we do ?
</p>
<p>
The only good news here is that vertices must be immutable.
</p>
TicketdcoudertSat, 01 Sep 2018 09:30:10 GMT
https://trac.sagemath.org/ticket/22349#comment:32
https://trac.sagemath.org/ticket/22349#comment:32
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/26169" title="enhancement: py3: trying not to sort the edges of graphs (step 1) (closed: fixed)">#26169</a> Trial for not sorting multiple edges
</p>
TicketjdemeyerMon, 07 Jan 2019 08:46:49 GMT
https://trac.sagemath.org/ticket/22349#comment:33
https://trac.sagemath.org/ticket/22349#comment:33
<p>
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.
</p>
TicketjdemeyerMon, 07 Jan 2019 08:48:02 GMT
https://trac.sagemath.org/ticket/22349#comment:34
https://trac.sagemath.org/ticket/22349#comment:34
<p>
I am asking because there are now only a handful of doctest failures remaining in <a class="closed ticket" href="https://trac.sagemath.org/ticket/22029" title="enhancement: Element richcmp: never use id() (closed: fixed)">#22029</a> and they are almost all due to sorting in graphs.
</p>
TicketdcoudertMon, 07 Jan 2019 08:59:21 GMT
https://trac.sagemath.org/ticket/22349#comment:35
https://trac.sagemath.org/ticket/22349#comment:35
<p>
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.
</p>
<p>
For 1), we made huge progresses in reducing the dependency of methods to <code>.vertices()</code>. I'm not sure how many methods still rely on it. Most of them now use the ordering given by <code>list(G)</code> 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 ?
</p>
<p>
For 2), similarly, we have reduced the number of methods relying on <code>.edges()</code>, plus we can use <code>sort=False</code> parameter. We can try and see...
</p>
<p>
3) is more tricky and I don't know how to do that yet.
</p>
TicketjdemeyerMon, 07 Jan 2019 09:23:06 GMT
https://trac.sagemath.org/ticket/22349#comment:36
https://trac.sagemath.org/ticket/22349#comment:36
<p>
For 1) there is still an issue with <code>relabel()</code>: <a class="closed ticket" href="https://trac.sagemath.org/ticket/27027" title="defect: graph relabel() assumes sortable vertices (closed: fixed)">#27027</a>
</p>
TicketjdemeyerMon, 07 Jan 2019 15:55:27 GMT
https://trac.sagemath.org/ticket/22349#comment:37
https://trac.sagemath.org/ticket/22349#comment:37
<p>
And one more with <code>graph_isom_equivalent_non_edge_labeled_graph()</code>: <a class="closed ticket" href="https://trac.sagemath.org/ticket/27029" title="enhancement: Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph() (closed: fixed)">#27029</a>
</p>
TicketjdemeyerFri, 22 Feb 2019 21:09:56 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/22349#comment:38
https://trac.sagemath.org/ticket/22349#comment:38
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/22349?action=diff&version=38">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-8.4</em> to <em>sage-8.7</em>
</li>
</ul>
TicketdcoudertSat, 23 Feb 2019 10:34:18 GMT
https://trac.sagemath.org/ticket/22349#comment:39
https://trac.sagemath.org/ticket/22349#comment:39
<p>
We have now drastically reduced the dependency to <code>.vertices()</code> and <code>.edges()</code> in the graph module (except in doctests, but we can specify <code>sort=True</code> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/26640" title="task: Meta-ticket: make graphs compatible with Python 3 (closed: worksforme)">#26640</a> to get a full picture.
</p>
TicketjdemeyerSun, 24 Feb 2019 13:16:26 GMT
https://trac.sagemath.org/ticket/22349#comment:40
https://trac.sagemath.org/ticket/22349#comment:40
<p>
Here is a concrete proposal for this ticket:
</p>
<ol><li>If no <code>sort</code> option is given (the default), give a deprecation and try to sort but fail gracefully if the input is not sortable.
</li></ol><ol start="2"><li>If a <code>sort</code> option is given, do as before.
</li></ol>
TicketjdemeyerSun, 24 Feb 2019 13:17:21 GMT
https://trac.sagemath.org/ticket/22349#comment:41
https://trac.sagemath.org/ticket/22349#comment:41
<p>
I also like the idea that somebody posted on sage-devel (I don't remember who) that <code>.vertices()</code> and <code>.edges()</code> should return a "view" which could have various operations on it.
</p>
TicketdcoudertSun, 24 Feb 2019 13:54:13 GMT
https://trac.sagemath.org/ticket/22349#comment:42
https://trac.sagemath.org/ticket/22349#comment:42
<p>
It's Thierry (<a class="ext-link" href="https://groups.google.com/d/msg/sage-devel/uEHBKekJ_Cw/peoyx4PaBQAJ"><span class="icon"></span>this message</a>). I also like this idea. Should we do that here, before in another ticket, or later ?
</p>
<p>
Networkx now also use views <a class="ext-link" href="https://networkx.github.io/documentation/latest/reference/classes/generated/networkx.Graph.edges.html#networkx.Graph.edges"><span class="icon"></span>networkx.Graph.edges</a>.
</p>
TicketdcoudertSun, 03 Mar 2019 21:21:11 GMT
https://trac.sagemath.org/ticket/22349#comment:43
https://trac.sagemath.org/ticket/22349#comment:43
<p>
A proposal for an <code>EdgeView</code> in <a class="closed ticket" href="https://trac.sagemath.org/ticket/27408" title="enhancement: Edge view for graphs (closed: fixed)">#27408</a>.
</p>
TicketembrayMon, 25 Mar 2019 10:56:15 GMTmilestone changed
https://trac.sagemath.org/ticket/22349#comment:44
https://trac.sagemath.org/ticket/22349#comment:44
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.7</em> to <em>sage-8.8</em>
</li>
</ul>
<p>
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
</p>
TicketembrayFri, 14 Jun 2019 14:54:19 GMTmilestone deleted
https://trac.sagemath.org/ticket/22349#comment:45
https://trac.sagemath.org/ticket/22349#comment:45
<ul>
<li><strong>milestone</strong>
<em>sage-8.8</em> deleted
</li>
</ul>
<p>
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).
</p>
TicketdcoudertSat, 18 Apr 2020 10:16:26 GMTmilestone set
https://trac.sagemath.org/ticket/22349#comment:46
https://trac.sagemath.org/ticket/22349#comment:46
<ul>
<li><strong>milestone</strong>
set to <em>sage-9.2</em>
</li>
</ul>
<p>
Now that we have <a class="missing wiki">EdgesView?</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/27408" title="enhancement: Edge view for graphs (closed: fixed)">#27408</a> 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.
</p>
Ticket