Labelled graph formats

Katja Berčič, Janoš Vidali; May 2018

lsparse6

lsparse6 is a format for storing undirected labelled multigraphs in a compact manner, using only printable ASCII characters. It is most suitable for sparse multigraphs.

Brendan McKay has descriptions for the graph6, sparse6 and digraph6 encodings.

Description

All numbers are stored as big endian unsigned integers unless otherwise noted.

The format consists of:

1. the sparse6 encoding of the unlabelled graph,
2. the character #,
3. ord(x)-63 encoding of the number of labels and list of labels.

List of labels

lsparse6 uses McKay's N to determine the number of bytes needed to write the number of labels.

  If 0 <= n <= 62, define N(n) to be the single byte n+63.
  If 63 <= n <= 258047, define N(n) to be the four bytes
      126 R(x), where x is the bigendian 18-bit binary form of n.
  If 258048 <= n <= 68719476735, define N(n) to be the eight bytes
      126 126 R(x), where x is the bigendian 36-bit binary form of n.

Let k be the number of bits needed to represent l-1 in binary. The edge labels are listed in the same order as in the graph encoding, each label represented by k bits. This sequence is packed in a bigendian order and padded with 1-bits to a multiple of 6.

disparse6

This is a modified sparse6 format that allows for directed edges. The edge list format is changed so that each entry is like this:

• if the first bit is 0, an out-neighbour of the current vertex follows,
• if the first bit is 1, then
  • if the next bit is 0, then the index of the current vertex is increased by one, and its out-neighbour follows,
  • if the next bit is 1, then the current vertex is set to the given index.

In other words, the edge list is a sequence b[0] x[0] b[1] x[1] b[2] x[2] ... b[m] x[m], where each b[i] is either 0, 10 or 11, and each x[i] occupies k bits. Decoding the edges would go like this:

v = 0
for i from 0 to m:
    if b[i] = 11:
        v = x[i]
        continue
    else if b[i] = 10:
        v += 1
    add edge (v, x[i])

Special rules for padding are then not needed, as an extra string of 1 bits could only be interpreted as changing v, and no edge would be added.

This format can be extended with edge labels in the same way as sparse6, obtaining ldisparse6.