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"
with open(input_file, "r") as infile:
lines = infile.readlines()
with open(output_file, "w") as outfile:
for line in lines:
if line.startswith("&"):
outfile.write(line[1:])
else:
outfile.write(line)