Three formats: graph6, sparse6 and digraph6

These formats are designed to store (di)graphs such that each byte is a printable ASCII character. graph6 compresses the adjacency matrix into a last 6 bits of each character. However sparse6 compresses the adjacency list into the last 6 bits for each character and such graphs begin with a : character to distinguish the two formats.

A detailed description of the two formats may be found here. Some nauty programs produce sparse6 output by default:

Generating 3 random graphs of order 5:

$ ./genrang 5 3

:DgWCgCb

:DgXcn

:DaWE@ I

Here is a python script to convert an adjacency matrix as a list of lists to digraph6 format.

def adjToDigraph6(adjMatrix):

n = len(adjMatrix)

# Convert adjacency matrix to binary string

bin_list = ""

for i in range(n):

for j in range(n):

bin_list += str(adjMatrix[i][j])

# Pad binary string with zeros to make its length a multiple of 6

bin_list += "0" * (6 - len(bin_list) % 6) if len(bin_list) % 6 != 0 else ""

# Convert binary string to digraph6 format

digraph6 = "&" + chr(n + 63) + ""

for i in range(0, len(bin_list), 6):

x = int(bin_list[i:i+6], 2)

digraph6 += chr(x + 63)

return digraph6

Next we convert a digraph6 format to a list of lists(adjacency matrix).

def digraph6ToAdj(digraph6):

# vertices + 63 = second char

vertices = ord(digraph6[1]) - 63

bin_list = ""

# Turn into 6 bit pieces

for i in digraph6[2:]:

bin_list += ("{0:06b}".format(ord(i) - 63))

adjMatrix = []

for i in range(vertices):

sub_adjMatrix = [0 for i in range(vertices)]

for j in range(vertices):

sub_adjMatrix[j] = int(bin_list[0])

bin_list = bin_list[1:]

adjMatrix.append(sub_adjMatrix)

return vertices, adjMatrix

In the Graph6 format, the encoding starts with a single character that is not a tilde (~) or an ampersand (&). In the Digraph6 format, the encoding starts with an ampersand (&) followed by the rest of the encoded graph string.

In the Digraph6 format in Sage, the first character should be an ampersand (&). If the ampersand is missing, you can add it using the following Python code:

input_file = "digraph6_input.txt"

output_file = "digraph6_output.txt"

with open(input_file, "r") as infile:

lines = infile.readlines()

with open(output_file, "w") as outfile:

for line in lines:

if not line.startswith("&"):

outfile.write("&" + line)

else:

outfile.write(line)

here's a Python script that removes the ampersand (&) from the beginning of each line in a text file:

input_file = "input_with_ampersands.txt"

output_file = "output_without_ampersands.txt"