#26447 closed enhancement (fixed)
py3: do not sort vertices in static graphs
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  python3  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  f5e740c (Commits)  Commit:  f5e740c7f090ae2152009d19f77edf9d234486a3 
Dependencies:  Stopgaps: 
Description
as this may help to fix the posets
Change History (22)
comment:1 Changed 8 months ago by
 Branch set to u/chapoton/26447
 Commit set to c92e95e77dd9a169275790f152a2e92f6dc6c724
 Status changed from new to needs_review
comment:2 Changed 8 months ago by
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
comment:3 Changed 8 months ago by
 Status changed from needs_review to needs_work
damned.. This would have been too simple..
comment:4 Changed 8 months ago by
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
comment:5 Changed 8 months ago by
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..
comment:6 Changed 8 months ago by
 Commit changed from c92e95e77dd9a169275790f152a2e92f6dc6c724 to 9402ff34536ff144251144f700b66508a955556b
Branch pushed to git repo; I updated commit sha1. New commits:
9402ff3  trac 26447 fixing some easy doctests

comment:7 Changed 8 months ago by
 Branch changed from u/chapoton/26447 to public/ticket/26447version2
 Commit changed from 9402ff34536ff144251144f700b66508a955556b to 1a87d7d237a77e384bb6371f8a33bb0831d0d3d4
here is another tentative, previous one stored in "u/chapoton/26447"
New commits:
1a87d7d  another tentative

comment:8 Changed 8 months ago by
 Commit changed from 1a87d7d237a77e384bb6371f8a33bb0831d0d3d4 to b82d8ed9c195b7a786053d2730c79028fc560656
Branch pushed to git repo; I updated commit sha1. New commits:
b82d8ed  trac 26447 sorting when possible

comment:9 Changed 8 months ago by
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 !
comment:10 Changed 8 months ago by
 Status changed from needs_work to needs_review
comment:11 Changed 8 months ago by
 Status changed from needs_review to needs_work
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 thatset(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 ?
comment:12 Changed 8 months ago by
 Commit changed from b82d8ed9c195b7a786053d2730c79028fc560656 to d3a9a8b52b42630014f4aca95444c2400c4d830f
Branch pushed to git repo; I updated commit sha1. New commits:
d3a9a8b  trac 26447 more doc and doctest

comment:13 Changed 8 months ago by
Here is some more doc. I would prefer not to add checks for the type, length and content of "vertex_list".
comment:14 Changed 8 months ago by
 Reviewers set to 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
comment:15 Changed 8 months ago by
 Commit changed from d3a9a8b52b42630014f4aca95444c2400c4d830f to 6cb9d36a6bab2e1753307e345385a4c19b81a8fa
Branch pushed to git repo; I updated commit sha1. New commits:
6cb9d36  trac 26447 adding check for length of vertex_list

comment:16 Changed 8 months ago by
len(G)
could be G.order()
.
comment:17 Changed 8 months ago by
 Commit changed from 6cb9d36a6bab2e1753307e345385a4c19b81a8fa to f5e740c7f090ae2152009d19f77edf9d234486a3
Branch pushed to git repo; I updated commit sha1. New commits:
f5e740c  detail

comment:18 Changed 8 months ago by
ok, done
comment:19 Changed 8 months ago by
 Status changed from needs_work to needs_review
comment:20 Changed 8 months ago by
 Status changed from needs_review to positive_review
LGTM, passes all long tests on graphs
.
comment:21 Changed 7 months ago by
 Branch changed from public/ticket/26447version2 to f5e740c7f090ae2152009d19f77edf9d234486a3
 Resolution set to fixed
 Status changed from positive_review to closed
comment:22 Changed 7 months ago by
 Milestone changed from sage8.4 to sage8.5
This should be retargeted for 8.5.
New commits:
py3: trying to fix posets by not sorting vertices in static graphs