Opened 4 years ago
Closed 4 years ago
#24923 closed defect (fixed)
sparse6 encoding and decoding of graphs with a single vertex
Reported by:  jaanos  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  graph theory  Keywords:  sparse6 graphs loops 
Cc:  dimpase  Merged in:  
Authors:  Janoš Vidali  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  f7d7e57 (Commits, GitHub, GitLab)  Commit:  f7d7e579262a96094ca15cd729ae62c6bee06105 
Dependencies:  Stopgaps: 
Description (last modified by )
Currently, the behaviour of sparse6 encoding and decoding for looped graphs with 1 vertex is inconsistent:
sage: G = Graph([(0, 0)], loops=True) sage: G.sparse6_string() ':@N' sage: Graph(_)  ValueError Traceback (most recent call last) <ipythoninput38f3a0616d27a> in <module>() > 1 Graph(_) /home/janos/sage/local/lib/python2.7/sitepackages/sage/graphs/graph.pyc in __init__(self, data, pos, loops, format, weighted, implementation, data_structure, vertex_labels, name, multiedges, convert_empty_dict_labels_to_None, sparse, immutable) 1150 self.allow_multiple_edges(False if multiedges is False else True, check=False) 1151 from .graph_input import from_sparse6 > 1152 from_sparse6(self, data) 1153 1154 elif format == 'adjacency_matrix': /home/janos/sage/local/lib/python2.7/sitepackages/sage/graphs/graph_input.pyc in from_sparse6(G, g6_string) 103 for i in range(len(bits)//(k+1)): 104 b.append(int(bits[(k+1)*i:(k+1)*i+1],2)) > 105 x.append(int(bits[(k+1)*i+1:(k+1)*i+k+1],2)) 106 v = 0 107 edges = [] ValueError: invalid literal for int() with base 2: ''
According to http://users.cecs.anu.edu.au/~bdm/data/formats.txt, each edge is represented by k+1
bits, where k
is the number of bits needed to represent n1
. For n = 1
, we should then have k = 0
(Integer(0).nbits()
agrees). Effectively, for a graph with a single vertex, the edge list should contain as many zero bits as there are loops on the vertex, followed by a padding consisting of one bits.
However, what currently happens is that when encoding, a zero is represented by a 0
bit, thus exceeding the k = 0
bits for the vertex representation. This results in two zero bits per loop (note that in the above example, we have ord('N')63 = 15 = 001111
).
A separate issue affects the decoding process. There, k = 0
is correctly identified, however this results in trying to parse an empty string, which throws the exception above.
This patch makes a special case when n = 1
, resulting in both correct encoding and decoding:
sage: G = Graph([(0, 0)], loops=True) sage: G.sparse6_string() ':@^' sage: Graph(_) Looped multigraph on 1 vertex
Change History (13)
comment:1 Changed 4 years ago by
 Branch set to u/jaanos/sparse6_encoding_and_decoding_of_graphs_with_a_single_vertex
comment:2 Changed 4 years ago by
 Commit set to 5261d5d88b1c0840a4860fd954f0b0c72b46ba0f
 Component changed from PLEASE CHANGE to graph theory
 Description modified (diff)
 Keywords sparse6 graphs loops added
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to defect
comment:3 Changed 4 years ago by
comment:4 Changed 4 years ago by
 Cc dimpase added
comment:5 Changed 4 years ago by
The patch is working well, and I tried also with multiple edges
sage: G = Graph([(0, 0), (0,0)], loops=True, multiedges=True) sage: G.sparse6_string() ':@N' sage: H = Graph(_) sage: H Looped multigraph on 1 vertex sage: H.size() 2
Can you add a doctest in the sparse6 encode / decoding methods, like:
Graphs with 1 vertex are correctly handled (:trac:`24923`):: sage: Graph([(0, 0)], loops=True).sparse6_string() ':@^' sage: G = Graph(_) sage: G.order(), G.size() (1, 1) sage: Graph([(0, 0), (0, 0)], loops=True, multiedges=True).sparse6_string() ':@^' sage: H = Graph(_) sage: H.order(), H.size() (1, 2)
comment:6 Changed 4 years ago by
 Commit changed from 5261d5d88b1c0840a4860fd954f0b0c72b46ba0f to ff6e7501768959c47888d3fbe58ced60fc1ca50e
comment:7 Changed 4 years ago by
OK, I've added the doctest (I've fixed an error in the output). I have also changed the loops for encoding/decoding the bytes: instead of multiplying the counter at each step, an appropriate increment is used.
comment:8 Changed 4 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
Thanks.
comment:10 Changed 4 years ago by
 Commit changed from ff6e7501768959c47888d3fbe58ced60fc1ca50e to f7d7e579262a96094ca15cd729ae62c6bee06105
Branch pushed to git repo; I updated commit sha1. New commits:
f7d7e57  Merge branch 'develop' into u/jaanos/sparse6_encoding_and_decoding_of_graphs_with_a_single_vertex

comment:11 Changed 4 years ago by
 Status changed from needs_work to needs_review
OK, should be fine now.
comment:12 Changed 4 years ago by
 Status changed from needs_review to positive_review
OK with beta8.
comment:13 Changed 4 years ago by
 Branch changed from u/jaanos/sparse6_encoding_and_decoding_of_graphs_with_a_single_vertex to f7d7e579262a96094ca15cd729ae62c6bee06105
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Fix sparse6 encoding and decoding for graphs with a single vertex