id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
27695 Produce consistent graph6 and dig6 strings in python3 etn40ff "Currently given a `Graph` (or a `DiGraph`) `G` its graph6 (or dig6)
representation is produced via the auxiliary method `sage.graphs.generic_graph.GenericGraph._bit_vector`. This method converts vertices to integers from `range(n)` and then produces a binary string recording (directed) edges. The conversion is done basically via `enumerate(self)`.
Suppose that `G` has already vertices labelled by `range(n)`. Then in Python 2 the
above conversion does nothing and the correspondence
position_in_the_resulting_string --- edges_of_`G` depends uniquely on `n`.
On the contrary, since in Python 3 dictionaries are read in insertion order, the
correspondence depends heavily on the way in which `G` is created.
This makes the resulting string unreliable
{{{
sage: dg = DiGraph([(0,1,1)])
sage: dg.relabel({0:1,1:0})
sage: DiGraph(dg.dig6_string()) == dg # Python 3
False
sage: DiGraph(dg.dig6_string()) == dg # Python 2
True
}}}
and creates several doctes failures in `sage.combinat.cluster_algebra_quiver`.
This ticket proposes two alternative solutions to this problem.
Solution 1: replace `enumerate(self)` by `enumerate(sorted(self))` in
`_bit_vector`. This keeps the current behaviour at the price of a (small?)
slowdown.
Solution 2: enforce the fact that graph6 and dig6 representations make sense
only for graphs with vertex set `range(n)` and raise an error otherwise. (The current code silently encodes an isomorphic graph.) Then use this directly to access vertices.
To put things in perspective, these representations are barely used outside of `cluster_algebra_quiver` so neither solution would have a big impact on other code. On the contrary in `cluster_algebra_quiver` they are used extensively as a way of comparing isomorphism classes of quivers. This is not the right way of doing so (one should use `sage.graphs.generic_graph.GenericGraph.canonical_label` instead) but, personally, I do not thing that reimplementing `cluster_algebra_quiver` is worth the effort.
" defect closed major sage-8.8 graph theory fixed python3 dcoudert chapoton David Coudert Salvatore Stella N/A 5147873b85bd94e1eb77da5c575aa0c1b430e394 5147873b85bd94e1eb77da5c575aa0c1b430e394