Opened 4 years ago

Closed 4 years ago

# sparse6 encoding and decoding of graphs with a single vertex

Reported by: Owned by: jaanos major sage-8.2 graph theory sparse6 graphs loops dimpase Janoš Vidali David Coudert N/A f7d7e57 f7d7e579262a96094ca15cd729ae62c6bee06105

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)
<ipython-input-3-8f3a0616d27a> in <module>()
----> 1 Graph(_)

/home/janos/sage/local/lib/python2.7/site-packages/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

/home/janos/sage/local/lib/python2.7/site-packages/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 n-1. 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 multi-graph on 1 vertex

### comment:1 Changed 4 years ago by jaanos

• Branch set to u/jaanos/sparse6_encoding_and_decoding_of_graphs_with_a_single_vertex

### comment:2 Changed 4 years ago by jaanos

• 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

New commits:

 ​5261d5d Fix sparse6 encoding and decoding for graphs with a single vertex

### comment:3 Changed 4 years ago by jaanos

• Authors set to Janoš Vidali

### comment:5 Changed 4 years ago by dcoudert

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 multi-graph 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 git

• Commit changed from 5261d5d88b1c0840a4860fd954f0b0c72b46ba0f to ff6e7501768959c47888d3fbe58ced60fc1ca50e

Branch pushed to git repo; I updated commit sha1. New commits:

 ​f8247eb Add test for sparse6_string ​ff6e750 Use appropriate steps when encoding/decoding sparse6 bytes

### comment:7 Changed 4 years ago by jaanos

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 dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to positive_review

Thanks.

### comment:9 Changed 4 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:10 Changed 4 years ago by git

• 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 jaanos

• Status changed from needs_work to needs_review

OK, should be fine now.

### comment:12 Changed 4 years ago by dcoudert

• Status changed from needs_review to positive_review

OK with beta8.

### comment:13 Changed 4 years ago by vbraun

• 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
Note: See TracTickets for help on using tickets.