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: sage-8.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:

Status badges

Description (last modified by jaanos)

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 
   1154         elif format == 'adjacency_matrix':

/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

Change History (13)

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:

5261d5dFix sparse6 encoding and decoding for graphs with a single vertex

comment:3 Changed 4 years ago by jaanos

  • Authors set to Janoš Vidali

comment:4 Changed 4 years ago by tscrim

  • Cc dimpase added

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:

f8247ebAdd test for sparse6_string
ff6e750Use 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:

f7d7e57Merge 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.