Search code examples
graph

How does graph6 format work?

I've been looking all over the place on how the .g6 or graph6 format works and I have no idea how it even works I swear it's like magic. 

F?B~w

That is a graph represented in ASCII form. It can be interpreted by Wolfram Mathematica, Sage, and Maple to name a few and give us a visual. However, after hours of diving into the open source code of Sage, I cannot for the life of me figure out how they can read that as a graph.

I want to know if it is possible to search the above graph for Hamiltonian Cycles without having to convert them into Adjacency Matrices? Or if that is not possible how do we even convert it into an Adjacency Matrix?

Any help would be appreciated.

Solution

  • The reference to the format description was already provided by Oliver Charlesworth, but in short the basic idea is to encode the graph size and the upper triangle of the adjacency matrix in ASCII-printable characters.

    1. From your original undirected graph, compute the adjacency matrix. This is guaranteed to be symmetric so all we care about is the upper triangle of this matrix, excluding the diagonal which will be identically zero.

    2. Next, build a bit vector of size n*(n-1)/2 by traversing the upper triangle of the matrix row by row. For example, for a 4x4 matrix the traversal would be (1,2),(1,3),(1,4),(2,3),(2,4),(3,4).

    3. Prepend your bit vector with the graph size n (as a binary word) and break the resulting bit vector into chunks of 6 bits each.

    4. Transform each 6-bit chunk into an integer in the range 63 to 126, then transform each of these to the corresponding ASCII character and concatenate them.

    Note the graph6 format does not support directed or weighted graphs. I believe it was created by Brendan McKay (there's an implementation of it in the nauty source) and there are two related formats: sparse6 (for sparse graphs) and digraph6 (for directed graphs).

    The digraph6 format appears to be fairly new (added in nauty 2.6) and is similar to graph6 except that in order to handle directed graphs, the format encodes the entire adjacency matrix minus the diagonal, not just the upper triangle.