#26447 closed enhancement (fixed)
py3: do not sort vertices in static graphs
Reported by:  Frédéric Chapoton  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  python3  Keywords:  
Cc:  David Coudert  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  f5e740c (Commits, GitHub, GitLab)  Commit:  f5e740c7f090ae2152009d19f77edf9d234486a3 
Dependencies:  Stopgaps: 
Description
as this may help to fix the posets
Change History (22)
comment:1 Changed 4 years ago by
Branch:  → u/chapoton/26447 

Commit:  → c92e95e77dd9a169275790f152a2e92f6dc6c724 
Status:  new → needs_review 
comment:2 Changed 4 years 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 4 years ago by
Status:  needs_review → needs_work 

damned.. This would have been too simple..
comment:4 Changed 4 years 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 4 years 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 4 years ago by
Commit:  c92e95e77dd9a169275790f152a2e92f6dc6c724 → 9402ff34536ff144251144f700b66508a955556b 

Branch pushed to git repo; I updated commit sha1. New commits:
9402ff3  trac 26447 fixing some easy doctests

comment:7 Changed 4 years ago by
Branch:  u/chapoton/26447 → public/ticket/26447version2 

Commit:  9402ff34536ff144251144f700b66508a955556b → 1a87d7d237a77e384bb6371f8a33bb0831d0d3d4 
here is another tentative, previous one stored in "u/chapoton/26447"
New commits:
1a87d7d  another tentative

comment:8 Changed 4 years ago by
Commit:  1a87d7d237a77e384bb6371f8a33bb0831d0d3d4 → b82d8ed9c195b7a786053d2730c79028fc560656 

Branch pushed to git repo; I updated commit sha1. New commits:
b82d8ed  trac 26447 sorting when possible

comment:9 Changed 4 years 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 4 years ago by
Status:  needs_work → needs_review 

comment:11 Changed 4 years ago by
Status:  needs_review → 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 4 years ago by
Commit:  b82d8ed9c195b7a786053d2730c79028fc560656 → d3a9a8b52b42630014f4aca95444c2400c4d830f 

Branch pushed to git repo; I updated commit sha1. New commits:
d3a9a8b  trac 26447 more doc and doctest

comment:13 Changed 4 years 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 4 years ago by
Reviewers:  → 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 4 years ago by
Commit:  d3a9a8b52b42630014f4aca95444c2400c4d830f → 6cb9d36a6bab2e1753307e345385a4c19b81a8fa 

Branch pushed to git repo; I updated commit sha1. New commits:
6cb9d36  trac 26447 adding check for length of vertex_list

comment:17 Changed 4 years ago by
Commit:  6cb9d36a6bab2e1753307e345385a4c19b81a8fa → f5e740c7f090ae2152009d19f77edf9d234486a3 

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

comment:19 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:20 Changed 4 years ago by
Status:  needs_review → positive_review 

LGTM, passes all long tests on graphs
.
comment:21 Changed 4 years ago by
Branch:  public/ticket/26447version2 → f5e740c7f090ae2152009d19f77edf9d234486a3 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:22 Changed 4 years ago by
Milestone:  sage8.4 → sage8.5 

This should be retargeted for 8.5.
New commits:
py3: trying to fix posets by not sorting vertices in static graphs