Opened 13 months ago

Closed 13 months ago

Last modified 13 months ago

#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 13 months ago by chapoton

  • Branch set to u/chapoton/26447
  • Commit set to c92e95e77dd9a169275790f152a2e92f6dc6c724
  • Status changed from new to needs_review

New commits:

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

comment:2 Changed 13 months ago by dcoudert

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 13 months ago by chapoton

  • Status changed from needs_review to needs_work

damned.. This would have been too simple..

Last edited 13 months ago by chapoton (previous) (diff)

comment:4 Changed 13 months ago by 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 13 months ago by chapoton (previous) (diff)

comment:5 Changed 13 months ago by dcoudert

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 13 months ago by git

  • Commit changed from c92e95e77dd9a169275790f152a2e92f6dc6c724 to 9402ff34536ff144251144f700b66508a955556b

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

9402ff3trac 26447 fixing some easy doctests

comment:7 Changed 13 months ago by chapoton

  • 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:

1a87d7danother tentative

comment:8 Changed 13 months ago by git

  • Commit changed from 1a87d7d237a77e384bb6371f8a33bb0831d0d3d4 to b82d8ed9c195b7a786053d2730c79028fc560656

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

b82d8edtrac 26447 sorting when possible

comment:9 Changed 13 months ago by 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 13 months ago by chapoton (previous) (diff)

comment:10 Changed 13 months ago by chapoton

  • Status changed from needs_work to needs_review

comment:11 Changed 13 months ago by dcoudert

  • 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 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 13 months ago by git

  • Commit changed from b82d8ed9c195b7a786053d2730c79028fc560656 to d3a9a8b52b42630014f4aca95444c2400c4d830f

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

d3a9a8btrac 26447 more doc and doctest

comment:13 Changed 13 months ago by 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 13 months ago by dcoudert

  • 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 13 months ago by git

  • Commit changed from d3a9a8b52b42630014f4aca95444c2400c4d830f to 6cb9d36a6bab2e1753307e345385a4c19b81a8fa

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

6cb9d36trac 26447 adding check for length of vertex_list

comment:16 Changed 13 months ago by dcoudert

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

comment:17 Changed 13 months ago by git

  • Commit changed from 6cb9d36a6bab2e1753307e345385a4c19b81a8fa to f5e740c7f090ae2152009d19f77edf9d234486a3

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

f5e740cdetail

comment:18 Changed 13 months ago by chapoton

ok, done

comment:19 Changed 13 months ago by chapoton

  • Status changed from needs_work to needs_review

comment:20 Changed 13 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM, passes all long tests on graphs.

comment:21 Changed 13 months ago by vbraun

  • Branch changed from public/ticket/26447-version2 to f5e740c7f090ae2152009d19f77edf9d234486a3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 13 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.