py3: do not sort vertices in static graphs

[Frédéric Chapoton]

as this may help to fix the posets

[Frédéric Chapoton]

New commits:

​c92e95e

py3: trying to fix posets by not sorting vertices in static graphs

[David Coudert]

This makes many doctests errors

sage -t --long src/sage/graphs/generic_graph.py  # 7 doctests failed
sage -t --long src/sage/graphs/strongly_regular_db.pyx  # 2 doctests failed
sage -t --long src/sage/graphs/connectivity.pyx  # 1 doctest failed
sage -t --long src/sage/graphs/base/static_sparse_graph.pyx  # 1 doctest failed
sage -t --long src/sage/graphs/generic_graph_pyx.pyx  # 2 doctests failed
sage -t --long src/sage/graphs/comparability.pyx  # 1 doctest failed
sage -t --long src/sage/graphs/base/static_sparse_backend.pyx  # 1 doctest failed
sage -t --long src/sage/graphs/hyperbolicity.pyx  # 8 doctests failed

[Frédéric Chapoton]

damned.. This would have been too simple..

[Frédéric Chapoton]

even just the simple change in static_sparse_backend.pyx triggers doctests failures in src/sage/graphs/connectivity.pyx (related to SPQR trees, in fact)

EDIT: more precisely

sage -t --long src/sage/graphs/connectivity.pyx  # 6 doctests failed
sage -t --long src/sage/graphs/base/static_sparse_backend.pyx  # 4 doctests failed

[David Coudert]

This is not surprising. The entire graph module assumes that the order of the vertices is always the same. Touching this ordering is a nightmare..

[git]

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

​9402ff3

trac 26447 fixing some easy doctests

[Frédéric Chapoton]

here is another tentative, previous one stored in "u/chapoton/26447"

---

New commits:

​1a87d7d

another tentative

[git]

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

​b82d8ed

trac 26447 sorting when possible

[Frédéric Chapoton]

Ok, so this is a working proposal: sort if possible. Not breaking any doctest on python2.

EDIT: and improving a lot of things on the python3 side !

[David Coudert]

In general I agree with this change. However, I have the following concern:

• the description of parameter vertex_list must be extended. It should be explained that if it is given, the ordering induced by this vertex_list is used to map vertices to integers.
• What if vertex_list is not a list but a set, dict, etc. ?
• What if vertex_list has length less than G.order(). In particular, we must check that set(vertex_list) == set(G.vertices()).
• Specific doctests are required.

Question: in the declaration of method init_short_digraph in file static_sparse_graph.pxd, you use vertex_list = ?. Shouldn't it be vertex_list=? to comply with PEP8 ?

[git]

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

​d3a9a8b

trac 26447 more doc and doctest

[Frédéric Chapoton]

Here is some more doc. I would prefer not to add checks for the type, length and content of "vertex_list".

[David Coudert]

I did several tests and it's working well except when the list has more vertices than the graph. This particular case could be tested at low cost, no ?

In all other cases, when the given list is not good, an error is raised somewhere.

sage: from sage.graphs.base.static_sparse_backend import StaticSparseCGraph
sage: G = graphs.PetersenGraph()
sage: S = StaticSparseCGraph(G, vertex_list=range(10))
sage: S = StaticSparseCGraph(G, vertex_list=range(10)[::-1])
sage: S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: S = StaticSparseCGraph(G, vertex_list=range(20)) ### should we care ??
sage: S.verts()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage:
sage: S = StaticSparseCGraph(G, vertex_list=range(5))
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
...
IndexError: list index out of range
sage:
sage: S = StaticSparseCGraph(G, vertex_list=range(1,11))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
....
TypeError: 'int' object is not iterable
sage:
sage: S = StaticSparseCGraph(G, vertex_list=set(range(10)))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: Expected list, got set

[git]

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

​6cb9d36

trac 26447 adding check for length of vertex_list

[David Coudert]

len(G) could be G.order().

[git]

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

​f5e740c

detail

[Frédéric Chapoton]

ok, done

[David Coudert]

LGTM, passes all long tests on graphs.

[Erik Bray]

This should be re-targeted for 8.5.