Opened 9 months ago

Last modified 4 months ago

#26800 closed defect

py3: bug with canonical_label — at Version 1

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: py3, graph
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by dcoudert)

The following doctest of petersen_family in families.py fails with with Python3:

        sage: F1 = graphs.petersen_family(generate=False)
        sage: F2 = graphs.petersen_family(generate=True)
        sage: F1 = [g.canonical_label().graph6_string() for g in F1]
        sage: F2 = [g.canonical_label().graph6_string() for g in F2]
        sage: set(F1) == set(F2)
        True

Some investigation suggests that the issue comes from canonical_label. Consider the following example (part of the code of petersen_family).

sage: def YDeltaTrans(G, v):
....:     """
....:     Apply a Y-Delta transformation to a given vertex v of G.
....:     """
....:     G = G.copy()
....:     a, b, c = G.neighbors(v)
....:     G.delete_vertex(v)
....:     G.add_cycle([a, b, c])
....:     return G.canonical_label(algorithm='sage')
....: 
sage: P = graphs.PetersenGraph()
sage: Q = YDeltaTrans(P, 0)
sage: for v in P:
....:     g = YDeltaTrans(P, v)
....:     print(g.graph6_string(), g.is_isomorphic(Q))

With Python 2, we get:

('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)
('HKN?Yeb', True)

With Python 3, we get:

HleAPWU True
HlbAPWU True
Hl`BPWU True
Hl`@PwU True
Hl`@OyU True
HhdDCkM True
Hhe@IhJ True
Hhea?km True
HheQhGJ True
HheAP[U True

so the canonical_label method seems broken with Python 3.

Change History (1)

comment:1 Changed 9 months ago by dcoudert

  • Description modified (diff)
  • Keywords py3 graph added
Note: See TracTickets for help on using tickets.