Labelled graph formats

[jaanos]

@katjabercic, I see that you have added a wiki page for the lsparse64 format. I have some comments:

• Rather than base64, I'd prefer McKay's encoding - it is simpler and we want to be "compatible" (then I'd just name the format lsparse6)
• To represent the number of vertices and the size of the label, we could use McKay's representation with 1, 4 or 8 bytes - this way, we save space with small graphs while still keeping the possibility of storing larger graphs. The number of bits needed to represent a vertex can be deduced from the number of vertices.
• Do we really need the minimal and maximal degrees?

Now that I think of it, sparse6 already supports multiple edges - all we're adding is labels. I think it might be wiser to simply extend sparse6 to add labels to the edges in the order they're specified (this way, we can store the labels separately - in the database, we could refer to the basic graph, and additionally store the labels). So we may have something like this:

: num-of-vertices list-of-edges # size-of-label list-of-labels

An lsparse6 parser can then behave similarly as a sparse6 parser, except that it can find the # character in advance and assign labels as it reads the edges.

By the way, I was also thinking about a format for sparse directed graphs (so we could store Ferrán's automata). It would have the same basic structure as sparse6, so I'd call it disparse6. However, the edge list format should be changed to allow for directed edges. I suggest that each entry is like this (compare to sparse6):

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

We could also extend this format to add edge labels in the same way as above, thus obtaining ldisparse6.

What do you think?

[katjabercic]

Let me just address two things you brought up here and get to the others later.

• The main reason for using base64 is that encoders and decoders already exist in libraries for all major languages and it is a standard way to do this.
• A format for sparse digraphs makes sense.

[jaanos]

What you say about base64 is of course true, but in the end, we also want to support McKay's formats, and decoding a byte there is simply ord(x)-63.

[jaanos]

One thing I've noticed: ~ may appear as a valid byte in the *6 formats (ASCII 126, thus representing 126 - 63 = 63 = 111111), and as such, is not a good format marker or delimiter. A better choice would be, say # - I have already updated my post above. Note that sparse6, incremental sparse6 and digraph6 already use :, ; and &, respectively, while I have proposed using ! for the auto6 format.

[katjabercic]

@jaanos, I'm still not convinced about using ord(x)-63 over base64. For the other part, I think my main reason to not base the serialisation on *6 was ease of encoding/decoding and optimising it for regular graphs (i.e. maniplexes, which is what I need in the end). I think I realised at some point that that didn't make sense.

• We agree about using 1, 4 or 8 bytes for the number of vertices.
• I like the format : num-of-vertices list-of-edges # size-of-label list-of-labels.

I'll go fix the format description.

[jaanos]

The only reason I'm advocating the *6 style is backwards compatibility - for example, one could simply ignore everything after # and still read the graph with a sparse6 decoder.

That said, the *6 format does have its drawbacks - particularly the use of backslashes, which will often be escaped, thus lengthening the representation of the graph.