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:  sage8.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: 
Description (last modified by )
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`
vsCK
,CR
vsCL
andCr
vsC]
 5 vertices:
DGC
vsD@O
,DAK
vsD@S
,DC[
vsD@s
,DIK
vsDBW
,DD[
vsDBk
,DDW
vsDBg
,D`{
vsDK{
,DqK
vsDLo
,DMk
vsDbk
,DR{
vsDL{
,DR[
vsDJk
,Dr{
vsD]{
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
comment:2 Changed 3 years ago by
 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
 Description modified (diff)
comment:4 followup: ↓ 7 Changed 3 years ago by
see #26800
comment:5 Changed 3 years ago by
comment:6 Changed 3 years ago by
See #25399 for another recent ticket fixing doctests failures related to bliss.
comment:7 in reply to: ↑ 4 Changed 3 years ago by
comment:8 Changed 3 years ago by
 Description modified (diff)
comment:9 Changed 3 years ago by
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 lackfor some reasonof buildbots that test optional packages). It doesn't seem to be a particularly substantive failure either.
comment:10 Changed 3 years ago by
 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:
a1a96fa  trac #26994: fix doctest in sql_db

comment:11 Changed 3 years ago by
 Reviewers set to Volker Braun
 Status changed from needs_review to positive_review
comment:12 Changed 3 years ago by
 Branch changed from public/26994_sql_db to a1a96fa2e0627ddaa91d9a576190801c135ee58e
 Resolution set to fixed
 Status changed from positive_review to closed
The graph6 strings
Cr
andC]
indeed corresponds to graphs on 4 vertices (isomorphic but not equal)Still on SageMath 8.6.beta0 the canonical labeling is
Cr
Hence the code in the doctest should have been added
Cr
in the database and notC]
as it is currently written.