Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#26447 closed enhancement (fixed)

py3: do not sort vertices in static graphs

Reported by: Frédéric Chapoton Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description

as this may help to fix the posets

Change History (22)

comment:1 Changed 4 years ago by Frédéric Chapoton

Branch: u/chapoton/26447
Commit: c92e95e77dd9a169275790f152a2e92f6dc6c724
Status: newneeds_review

New commits:

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

comment:2 Changed 4 years ago by 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

comment:3 Changed 4 years ago by Frédéric Chapoton

Status: needs_reviewneeds_work

damned.. This would have been too simple..

Last edited 4 years ago by Frédéric Chapoton (previous) (diff)

comment:4 Changed 4 years ago by 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
Last edited 4 years ago by Frédéric Chapoton (previous) (diff)

comment:5 Changed 4 years ago by 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..

comment:6 Changed 4 years ago by git

Commit: c92e95e77dd9a169275790f152a2e92f6dc6c7249402ff34536ff144251144f700b66508a955556b

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

9402ff3trac 26447 fixing some easy doctests

comment:7 Changed 4 years ago by Frédéric Chapoton

Branch: u/chapoton/26447public/ticket/26447-version2
Commit: 9402ff34536ff144251144f700b66508a955556b1a87d7d237a77e384bb6371f8a33bb0831d0d3d4

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


New commits:

1a87d7danother tentative

comment:8 Changed 4 years ago by git

Commit: 1a87d7d237a77e384bb6371f8a33bb0831d0d3d4b82d8ed9c195b7a786053d2730c79028fc560656

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

b82d8edtrac 26447 sorting when possible

comment:9 Changed 4 years ago by 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 !

Last edited 4 years ago by Frédéric Chapoton (previous) (diff)

comment:10 Changed 4 years ago by Frédéric Chapoton

Status: needs_workneeds_review

comment:11 Changed 4 years ago by David Coudert

Status: needs_reviewneeds_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 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 ?

comment:12 Changed 4 years ago by git

Commit: b82d8ed9c195b7a786053d2730c79028fc560656d3a9a8b52b42630014f4aca95444c2400c4d830f

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

d3a9a8btrac 26447 more doc and doctest

comment:13 Changed 4 years ago by 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".

comment:14 Changed 4 years ago by David Coudert

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 git

Commit: d3a9a8b52b42630014f4aca95444c2400c4d830f6cb9d36a6bab2e1753307e345385a4c19b81a8fa

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

6cb9d36trac 26447 adding check for length of vertex_list

comment:16 Changed 4 years ago by David Coudert

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

comment:17 Changed 4 years ago by git

Commit: 6cb9d36a6bab2e1753307e345385a4c19b81a8faf5e740c7f090ae2152009d19f77edf9d234486a3

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

f5e740cdetail

comment:18 Changed 4 years ago by Frédéric Chapoton

ok, done

comment:19 Changed 4 years ago by Frédéric Chapoton

Status: needs_workneeds_review

comment:20 Changed 4 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM, passes all long tests on graphs.

comment:21 Changed 4 years ago by Volker Braun

Branch: public/ticket/26447-version2f5e740c7f090ae2152009d19f77edf9d234486a3
Resolution: fixed
Status: positive_reviewclosed

comment:22 Changed 4 years ago by Erik Bray

Milestone: sage-8.4sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.