Description of graph6, sparse6 and digraph6 encodings ----------------------------------------------------- Brendan McKay, [email protected] Updated Jun 2015, Apr 2022. General principles: All numbers in this description are in decimal unless obviously in binary. Apart from the header, there is one object per line. Apart from the header, end-of-line characters, and the characters ":", ";" and "&" which might start a line, all bytes have a value in the range 63-126 (which are all printable ASCII characters). A file of objects is a text file, so whatever end-of-line convention is locally used is fine; however the C library input routines must show the standard single-LF end of line to programs). Bit vectors: A bit vector x of length k can be represented as follows. Example: 1000101100011100 (1) Pad on the right with 0 to make the length a multiple of 6. Example: 100010110001110000 (2) Split into groups of 6 bits each. Example: 100010 110001 110000 (3) Add 63 to each group, considering them as bigendian binary numbers. Example: 97 112 111 These values are then stored one per byte. So, the number of bytes is ceiling(k/6). Let R(x) denote this representation of x as a string of bytes. Small nonnegative integers: Let n be an integer in the range 0-68719476735 (2^36-1). If 0 >graph6>sparse6 v then v = x[i] else output {x[i],v} endif endfor In decoding, an incomplete (b,x) pair at the end is discarded. Example: :Fa@x^ ':' indicates sparse6 format. Subtract 63 from the other bytes and write them in binary, six bits each. 000111 100010 000001 111001 011111 The first byte is not 63, so it is n. n=7 n-1 needs 3 bits (k=3). Write the other bits in groups of 1 and k: 1 000 1 000 0 001 1 110 0 101 1 111 This is the b/x sequence 1,0 1,0 0,1 1,6 0,5 1,7. The 1,7 at the end is just padding. The remaining parts give the edges 0-1 0-2 1-2 5-6. Description of incremental sparse6 format. ----------------------------------------- This is an extension to sparse6 format that is very efficient if most graphs in a file are similar to the previous graph. Each graph occupies one text line. Except for the first character and end-of-line characters, each byte has the form 63+x, where 0 >digraph62, 0->4, 3->1 and 3->4. x = 00101 00000 00000 01001 00000 Then N(n) = 68 and R(x) = R(00101 00000 00000 01001 00000) = 73 63 65 79 63. So, the graph is 38 68 73 63 65 79 63.