graph6: Description of the graph6 format

In rgraph6: Interface to graph6 format for R

Description

Description of graph6 format for storing undirected graphs.

Details

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 and the end-of-line characters, 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).

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-262143 (262143 = 2^18-1).

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

Examples:

N(30) = 93

N(12345) = N(000011 000000 111001) = 126 69 63 120

Description of graph6 format

Data type: simple undirected graphs of order 0 to 262143.

Optional Header: >>graph6<< (without end of line!)

File name extension: .g6

One graph:

Suppose G has n vertices. Write the upper triangle of the adjacency matrix of G as a bit vector x of length n(n-1)/2, using the ordering (0,1),(0,2),(1,2),(0,3),(1,3),(2,3),...,(n-1,n).

Then the graph is represented as N(n) R(x).

Example:

Suppose n=5 and G has edges 0-2, 0-4, 1-3 and 3-4.

x = 0 10 010 1001

Then N(n) = 68 and R(x) = R(010010 100100) = 81 99. So, the graph is 68 81 99.

Author(s)

Michal Bojanowski [e-mail] based on the above webpage

References

http://cs.anu.edu.au/people/bdm/data/formats.txt

See Also

asAMatrix and asGraph6 for conversion functions.

rgraph6 documentation built on May 2, 2019, 4:50 p.m.