#26447 closed enhancement (fixed)
py3: do not sort vertices in static graphs
Reported by: | chapoton | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.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 2 years ago by
- Branch set to u/chapoton/26447
- Commit set to c92e95e77dd9a169275790f152a2e92f6dc6c724
- Status changed from new to needs_review
comment:2 Changed 2 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 2 years ago by
- Status changed from needs_review to needs_work
damned.. This would have been too simple..
comment:4 Changed 2 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 2 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 2 years 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 2 years ago by
- Branch changed from u/chapoton/26447 to public/ticket/26447-version2
- 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 2 years 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 2 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 2 years ago by
- Status changed from needs_work to needs_review
comment:11 Changed 2 years 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 2 years 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 2 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 2 years 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 2 years 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 2 years ago by
len(G)
could be G.order()
.
comment:17 Changed 2 years ago by
- Commit changed from 6cb9d36a6bab2e1753307e345385a4c19b81a8fa to f5e740c7f090ae2152009d19f77edf9d234486a3
Branch pushed to git repo; I updated commit sha1. New commits:
f5e740c | detail
|
comment:18 Changed 2 years ago by
ok, done
comment:19 Changed 2 years ago by
- Status changed from needs_work to needs_review
comment:20 Changed 2 years ago by
- Status changed from needs_review to positive_review
LGTM, passes all long tests on graphs
.
comment:21 Changed 2 years ago by
- Branch changed from public/ticket/26447-version2 to f5e740c7f090ae2152009d19f77edf9d234486a3
- Resolution set to fixed
- Status changed from positive_review to closed
comment:22 Changed 2 years ago by
- Milestone changed from sage-8.4 to sage-8.5
This should be re-targeted for 8.5.
New commits:
py3: trying to fix posets by not sorting vertices in static graphs