Opened 3 years ago

Closed 3 years ago

#26994 closed defect (fixed)

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

Reported by: vdelecroix Owned by:
Priority: blocker Milestone: sage-8.6
Component: documentation Keywords: graph, database
Cc: fbissey, dcoudert Merged in:
Authors: David Coudert Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: a1a96fa (Commits, GitHub, GitLab) Commit: a1a96fa2e0627ddaa91d9a576190801c135ee58e
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

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]

Change History (12)

comment:1 Changed 3 years ago by vdelecroix

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.

comment:2 Changed 3 years ago by vdelecroix

  • Cc dcoudert added
  • Description modified (diff)
  • Summary changed from doctest failures in databases/sql_db.py to graph canonical labels and doctest failures in databases/sql_db.py

comment:3 Changed 3 years ago by vdelecroix

  • Description modified (diff)

comment:4 follow-up: Changed 3 years ago by chapoton

see #26800

comment:5 Changed 3 years ago by slabbe

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.

comment:6 Changed 3 years ago by slabbe

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

comment:7 in reply to: ↑ 4 Changed 3 years ago by vdelecroix

Replying to chapoton:

see #26800

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

comment:8 Changed 3 years ago by vdelecroix

  • Description modified (diff)

comment:9 Changed 3 years ago by embray

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.

comment:10 Changed 3 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/26994_sql_db
  • Commit set to a1a96fa2e0627ddaa91d9a576190801c135ee58e
  • Keywords graph database added
  • Status changed from new to needs_review

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

comment:11 Changed 3 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

comment:12 Changed 3 years ago by vbraun

  • Branch changed from public/26994_sql_db to a1a96fa2e0627ddaa91d9a576190801c135ee58e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.