Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

graph canonical labels and doctest failures in databases/sql_db.py #26994

Closed
videlec opened this issue Jan 2, 2019 · 15 comments
Closed

graph canonical labels and doctest failures in databases/sql_db.py #26994

videlec opened this issue Jan 2, 2019 · 15 comments
Labels
c: databases c: documentation c: graph theory p: blocker / 1 t: bug
Milestone
sage-8.6

Comments

@videlec
Copy link
Contributor

videlec commented Jan 2, 2019

Starting from somewhere around 8.5.beta the canonical labels given by Sage and bliss are different on some instances

sage: G1 = Graph("Cr")
sage: G2 = Graph("C]")
sage: G1 == G2
False
sage: G1.is_isomorphic(G2) and G2.is_isomorphic(G1)
True
sage: G1.canonical_label(algorithm='bliss') == G1
True
sage: G1.canonical_label(algorithm='sage') == G2
True

That is Cr is canonical for bliss while C] is canonical for Sage... More examples:

  • 4 vertices: C` vs CK, CR vs CL and Cr vs C]
  • 5 vertices: DGC vs D@O, DAK vs D@S, DC[ vs D@s, DIK vs DBW, DD[ vs DBk, DDW vs DBg, D`{ vs DK{, DqK vs DLo, DMk vs Dbk, DR{ vs DL{, DR[ vs DJk, Dr{ vs D]{

As a consequence, when bliss is installed, we have the two following doctest failures in databases/sql_db.py.

sage -t --long src/sage/databases/sql_db.py
**********************************************************************
File "src/sage/databases/sql_db.py", line 956, in
sage.databases.sql_db.SQLDatabase.__init__
Failed example:
    D.show('simon')
Expected:
    graph6               vertices             edges
    ------------------------------------------------------------
    ?                    0                    0
    @                    1                    0
    A?                   2                    0
    A_                   2                    1
    B?                   3                    0
    BG                   3                    1
    BW                   3                    2
    Bw                   3                    3
    C?                   4                    0
    C@                   4                    1
    CB                   4                    2
    CF                   4                    3
    CJ                   4                    3
    CK                   4                    2
    CL                   4                    3
    CN                   4                    4
    C]                   4                    4
    C^                   4                    5
    C~                   4                    6
Got:
    graph6               vertices             edges
    ------------------------------------------------------------
    ?                    0                    0
    @                    1                    0
    A?                   2                    0
    A_                   2                    1
    B?                   3                    0
    BG                   3                    1
    BW                   3                    2
    Bw                   3                    3
    C?                   4                    0
    C@                   4                    1
    CB                   4                    2
    CF                   4                    3
    CJ                   4                    3
    C`                   4                    2
    CR                   4                    3
    CN                   4                    4
    Cr                   4                    4
    C^                   4                    5
    C~                   4                    6
**********************************************************************
File "src/sage/databases/sql_db.py", line 1004, in
sage.databases.sql_db.SQLDatabase.__init__
Failed example:
    E.show('simon')
Expected:
    graph6               vertices             edges
    ------------------------------------------------------------
    ?                    0                    0
    @                    1                    0
    A?                   2                    0
    A_                   2                    1
    B?                   3                    0
    BG                   3                    1
    BW                   3                    2
    Bw                   3                    3
    C?                   4                    0
    C@                   4                    1
    CB                   4                    2
    CF                   4                    3
    CJ                   4                    3
    CK                   4                    2
    CL                   4                    3
    CN                   4                    4
    C]                   4                    4
    C^                   4                    5
    C~                   4                    6
Got:
    graph6               vertices             edges
    ------------------------------------------------------------
    ?                    0                    0
    @                    1                    0
    A?                   2                    0
    A_                   2                    1
    B?                   3                    0
    BG                   3                    1
    BW                   3                    2
    Bw                   3                    3
    C?                   4                    0
    C@                   4                    1
    CB                   4                    2
    CF                   4                    3
    CJ                   4                    3
    C`                   4                    2
    CR                   4                    3
    CN                   4                    4
    Cr                   4                    4
    C^                   4                    5
    C~                   4                    6
**********************************************************************
1 item had failures:
   2 of  26 in sage.databases.sql_db.SQLDatabase.__init__
    [288 tests, 2 failures, 1.59 s]

CC: @kiwifb @dcoudert

Component: documentation

Author: David Coudert

Branch/Commit: a1a96fa

Reviewer: Volker Braun

Issue created by migration from https://trac.sagemath.org/ticket/26994
@videlec videlec added this to the sage-8.6 milestone Jan 2, 2019
@videlec
Copy link
Contributor Author

videlec commented Jan 2, 2019

comment:1

The graph6 strings Cr and C] indeed corresponds to graphs on 4 vertices (isomorphic but not equal)

sage: G1 = Graph("Cr")
sage: G2 = Graph("C]")
sage: G1 == G2
False
sage: G1.is_isomorphic(G2) and G2.is_isomorphic(G1)
True

Still on SageMath 8.6.beta0 the canonical labeling is Cr

sage: G1.canonical_label() == G1 and G2.canonical_label() == G1
True

Hence the code in the doctest should have been added Cr in the database and not C] as it is currently written.

@videlec

This comment has been minimized.

Sign in to view
@videlec videlec changed the title doctest failures in databases/sql_db.py graph canonical labels and doctest failures in databases/sql_db.py Jan 2, 2019
@videlec

This comment has been minimized.

Sign in to view
@fchapoton
Copy link
Contributor

comment:4

see #26800

@seblabbe
Copy link
Contributor

seblabbe commented Jan 2, 2019

comment:5

This ticket is a duplicate of #26920 which I open about 2 weeks ago. I suggest to close #26920 since the one here seems more alive.

@seblabbe
Copy link
Contributor

seblabbe commented Jan 2, 2019

comment:6

See #25399 for another recent ticket fixing doctests failures related to bliss.

@videlec
Copy link
Contributor Author

videlec commented Jan 2, 2019

comment:7

Replying to @fchapoton:

see #26800

The failure in this ticket is not Python 3 related. Both Sage and bliss provides canonical labelings but different ones.

@videlec

This comment has been minimized.

Sign in to view
@embray
Copy link
Contributor

embray commented Jan 2, 2019

comment:9

Being that bliss is an optional package, should this be a blocker? I'm not sure what the latest consensus is on that (being that there is an unfortunate lack--for some reason--of buildbots that test optional packages). It doesn't seem to be a particularly substantive failure either.

@dcoudert
Copy link
Contributor

dcoudert commented Jan 2, 2019

Author: David Coudert

@dcoudert
Copy link
Contributor

dcoudert commented Jan 2, 2019

Commit: a1a96fa

@dcoudert
Copy link
Contributor

dcoudert commented Jan 2, 2019

Branch: public/26994_sql_db

@dcoudert
Copy link
Contributor

dcoudert commented Jan 2, 2019

comment:10

The canonical label of a graph depends on the algorithm used to compute it. See the note in the documentation of canonical_label: Make sure you always compare canonical forms obtained by the same algorithm.

So a simple fix is to force algorithm='sage' in the doctest.

New commits:

a1a96fatrac #26994: fix doctest in sql_db

@vbraun
Copy link
Member

vbraun commented Jan 2, 2019

Reviewer: Volker Braun

@vbraun
Copy link
Member

vbraun commented Jan 3, 2019

Changed branch from public/26994_sql_db to a1a96fa

@vbraun vbraun closed this as completed in bc5178a Jan 3, 2019
@seblabbe seblabbe mentioned this issue Oct 21, 2022
Open
dkrenn added a commit to dkrenn/sage that referenced this issue Jul 4, 2023
@dkrenn
Merge tag '8.6' into u/dkrenn/joint-spectral-radius
121c8ba 
SageMath version 8.6, Release Date: 2019-01-15

* tag '8.6': (15673 commits)
  Updated SageMath version to 8.6
  Updated SageMath version to 8.6.rc1
  maxint -> maxsize, for py2/3 compatibility
  sagemath#26326 : 32-bit vs 64-bit doctests
  sagemath#26326 : reorder creation of random graphs to avoid creating an empty one by bad luck on 32-bit systems.
  Updated SageMath version to 8.6.rc0
  trac sagemath#26994: fix doctest in sql_db
  trivial cleanup
  force a UTF-8 locale on GAP in these tests
  allow setting additional environment variables when starting a Gap interface instance
  p_group_cohomology: Avoid conflict with a new global variable name in Gap
  Updated SageMath version to 8.6.beta1
  25501: adding missing optional tags
  Fix tox testsuite for sage_bootstrap
  trac 26980 fix script for python3
  trac 26978 remove module finite_class from doc
  a little firework of typos
  remove FiniteCombinatorialClass after sagemath#13552
  remove some deprecated thing in combinat/partition
  remove deprecated things in combinat/integer_vector
  ...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: databases c: documentation c: graph theory p: blocker / 1 t: bug
Projects
None yet
Milestone
sage-8.6
Development

No branches or pull requests
6 participants
@embray @vbraun @seblabbe @fchapoton @videlec @dcoudert