# Program to generate Hadamard Graphs for a 32x32 matrix by Steve Butler
# Written in Sage
def find_hadamard_graphs(S):
# S = a hexadecimal string of length 256 used to store the matrix
# First step is to convert the hexadecimal string to a hadamard matrix
translate = {'0':[-1,-1,-1,-1], '1':[-1,-1,-1, 1], '2':[-1,-1, 1,-1], '3':[-1,-1, 1, 1], '4':[-1, 1,-1,-1], '5':[-1, 1,-1, 1], '6':[-1, 1, 1,-1], '7':[-1, 1, 1, 1], '8':[ 1,-1,-1,-1], '9':[ 1,-1,-1, 1], 'A':[ 1,-1, 1,-1], 'B':[ 1,-1, 1, 1], 'C':[ 1, 1,-1,-1], 'D':[ 1, 1,-1, 1], 'E':[ 1, 1, 1,-1], 'F':[ 1, 1, 1, 1]}
H = []
for s in S:
H.extend(translate[s])
H = matrix([H[i*32:(i+1)*32] for i in range(32)])
'''
print H.str()
'''
#return
# We now find all possible form of entries of M = H^* \Lambda H
# these are the form of +/-1 vectors corresponding to diagonal
# elements of \Lambda. We will also keep track of the
# locations for which the various forms occur.
# These are both lists.
all_entries = []
locations = []
for i in range(0,32):
for j in range(i+1,32):
entry = [-1*H[k,j]*H[k,i] for k in range(1,32)] # M_{i,j}
if entry in all_entries:
# Have we seen this entry before? If we have, add
# to the list of locations for entry
locations[all_entries.index(entry)].append([i,j])
else:
# Have we not seen this entry before? If not, add
# a new entry type and note where the location was
all_entries.append(entry)
locations.append([[i,j]])
'''
print all_entries[100]
print len(all_entries)
return
'''
# Important note: the entries in locations are going to be the
# edges of the graph. So ideally should be stored in some format
# which is friendly to making graphs.
# Big idea == if we specify the entries in the first row, this
# determines \Lambda and so determines all remaining entries.
# So we now want to express all entries in terms of the entries
# in the first row. This is what following will be used for!
MM = [[1-H[j][i] for j in range(1,32)] for i in range(1,32)]
'''
for x in MM:
print x
return
'''
# The i-th row of the following matrix indicates how to write
# an entry in H^* \Lambda H in terms of an entry on the first
# row (up to a scaling factor).
NN = [[sum([MM[i][j]*all_entries[k][j] for j in range(31)]) for i in range(31)] for k in range(len(all_entries))]
#NN = [[sum([MM[i][j] for j in range(31)]) for i in range(31)] for k in range(len(all_entries))]
#NN = [[sum([all_entries[k][j] for j in range(31)]) for i in range(31)] for k in range(len(all_entries))]
'''
print len(NN)
print NN[0]
print NN[1]
print NN[-3]
print NN[-2]
print NN[-1]
print
for x in NN: print x
return
'''
# Theoretical side note: At this point what we are looking for
# is an assignment of values to the first row so that all of the
# entries of the matrix will be of a proper form. So we think
# of the assignment of the first row as a {0,1}-vector and this
# corresponds to selecting some columns of NN so that the row
# sums of those columns will be a {0,32}-vector (32 coming from
# scaling factor hidden inside computation of MM above).
# To shrink the search space we will look at ways to explore
# it as a tree where we can prune at some point if we know that
# any terminal nodes below will not result in a vector of the
# corret form. First we look for a way to order the columns
# to cause problems earlier (= smaller part of tree to search)
columns = presort([[NN[j][i] for j in range(len(NN))] for i in range(31)])
'''
for x in columns: print x
print len(columns)
return
'''
# We now store information about what partial sums are possible
# in each entry; this can be used if we see a partial sum which
# cannot extend then we stop computation (prune the tree).
# The first 31 entries can *never* create problems, so we skip.
stop_check = [0]*31
for r in range(31,len(all_entries)):
stop = [set([0,32])]
for i in range(31):
stop.append(set([x for x in stop[-1]]+[x-columns[30-i][r] for x in stop[-1]]))
stop.reverse()
stop_check.append(stop)
'''
for x in stop_check: print x
print
print stop_check[-1];
print len(stop_check)
print len(stop_check[-1])
return
'''
# Initialize some parameters in preparation for running through
# our decision tree.
generated_graphs = set([])
#generated_graphs = []
column_sum = [0]*len(all_entries)
# Recursively run our decision tree
recurse_find_hadamard_graphs(column_sum, columns, stop_check, 0, locations, generated_graphs)
print "found: ", len(generated_graphs)
'''
print len(columns)
print columns[0]
print len(columns[0])
print len(stop_check[-1])
print stop_check[-1][0]
print stop_check[-1][1]
'''
return generated_graphs
def recurse_find_hadamard_graphs(partial_sum, columns, stop_check, current_column, edges, generated_graphs):
#print edges
#return
# The heart of the computation, a recursive routine which searchs
# through all combinations of columns, and for those that that
# produce a valid graph adds to the list of generated graphs.
if current_column==31:
# We have reached a leaf in our decision tree; time to decide
# if this node is a graph.
if set(partial_sum).issubset(set([0,32])):
# We have produced a graph; now to find which one.
# generated_graphs.append(1)
# return
graph_edges = []
for i in range(len(partial_sum)):
if partial_sum[i] == 32:
# The entries corresponding to this term are of the
# correct form to be an edge, add in all edges
# this will create
graph_edges.extend(edges[i])
# Now make the graph
G = Graph(32) # create empty graph on 32 vertices
G.add_edges(graph_edges) # add in the edges
# Following gives unique(!) string for the graph
# which we then add into the set of generated graphs
generated_graphs.add(G.canonical_label().graph6_string())
else:
# First, we check what happens if we do not add the current column
for i in range(31,len(partial_sum)):
if partial_sum[i] not in stop_check[i][current_column]:
# If we don't add the current column, then it is
# impossible to get a graph regardless of choices
# made further down the tree, do not progress
break
else:
# Entrywise it is still possible to end with a graph
# so keep recursing further down
recurse_find_hadamard_graphs(partial_sum, columns, stop_check, current_column+1, edges, generated_graphs)
# Second, we check what happens if we do add the current column
new_partial_sum = [partial_sum[i]+columns[current_column][i] for i in range(len(partial_sum))]
for i in range(31,len(partial_sum)):
if new_partial_sum[i] not in stop_check[i][current_column]:
# If we do add the current column, then it is
# impossible to get a graph regardless of choices
# made further down the tree, do not progress
break
else:
# Entrywise it is still possible to end with a graph
# so keep recursing further down
recurse_find_hadamard_graphs(new_partial_sum, columns, stop_check, current_column+1, edges, generated_graphs)
def presort(columns):
#return columns
# We presort the columns by trying to put lots of problems early
# Note the first 31 rows are uninteresting, so we look past them
h = len(columns[0]) # the height of the columns
sort_order = [] # the final sorting order
while len(sort_order)<31: # still need to make a decision on sorting
print "New iteration"
# Basic idea == look for fewest number of columns that would
# create a problem AND among those find ones which effect the
# most entries
sort_options = {}
sort_options[tuple([i for i in range(31) if i not in sort_order])] = 1
print sort_options
for i in range(31,h):
# test stores which unsorted columns are still involved
test = tuple([j for j in range(31) if (columns[j][i] and j not in sort_order)])
if len(test): # make sure something to be sorted!
if test in sort_options:
sort_options[test] += 1
else:
sort_options[test] = 1
print sort_options
print sort_order
# sort_options gives us possible ways to sort; want to find
# one which is used most often (= more likely to cause conflict)
# we now run through sort_options and find a best candidate
few_columns = 32
most_rows = 0
best = []
for S in sort_options:
if len(S) == few_columns:
if sort_options[S] > most_rows:
most_rows = sort_options[S]
best = S
elif len(S) < few_columns:
few_columns = len(S)
most_rows = sort_options[S]
best = S
# Now extend the sort by ordering found
sort_order.extend(list(best))
#Return the columns resorted according to new order
return [columns[i] for i in sort_order]
###########
# EXAMPLE #
###########
# The following is a list of hadamard matrices. In final implementation this data will
# be in a text file with each line corresponding to exactly one matrix.
hadamard_matrices = [
'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33C3C3CC333C3CC3C3C33CC3C33CC3C33CCC33C33C33CCAAAAAAAAAAA59955AA5A6559A9599666A65569A6A5A96695A596959AA5665A699A9656A599956A5A996A59969965A5A996A9556A9666A65696599A99959AA965',
#'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3C3AAC3C33C55C33CC355C33C3CAAAAAAAAC3AAAA553CAA55AA3CAA5555C3A5A599A5A5A5665AA55A995AA55A66A59996A59999965A66996996969969696996999669969969969666A56696665A99',
#'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3C3AAC3C33C55C33CC355C33C3CAAAAAAAAC3AAAA553CAA55A599AA555A66A59699A5A596665AA5699696A56969699999AA3C999955C39966A56699665A9996A5966996A56996965A995A965A66A5',
#'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3C3AAC3C33C55C33CC355C33C3CAAAAAAAAC3AAAA553CAA55A599AA555A66A59699A5A596665AA5699669A56969969999AA3C999955C39966A56699665A9996A5995A96A566A5965A9696965A6969',
#'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3C3AAC3C33C55C33CC355C33C3CAAAAAAAAC3AAAA553CAA55A599AA555A66A59699A5A596665AA5699669A56969969999AA3C999955C39966A56699665A9996A5969696A56969965A995A965A66A5',
#'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3AAAAC3C35555C33CAA55C33C55AAAAAAC3A5AAAA3C5AAA559996AA556669A596A5C3A5965A3CA5699699A56969669999C35A99993CA5996699699966669696A5966696A56999965AA53C965A5AC3', 'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3AAAAC3C35555C33CAA55C33C55AAAAAAC3A5AAAA3C5AAA559996AA556669A596A5C3A5965A3CA5699666A56969999999C35A99993CA5996699699966669696A5A53C96A55AC3965A9699965A6966', 'FFFFFFFFFFFF0000FF00FF00FF0000FFF0F0F0F0F0F00F0FF00FF00FF00F0FF0CCCCCCCCCCCC3333CC33CC33CC3333CCC3C3AAAAC3C35555C33CAA55C33C55AAAAAAC3A5AAAA3C5AAA559996AA556669A596A5C3A5965A3CA5699666A56969999999C35A99993CA5996699699966669696A5969996A56966965AA53C965A5AC3',
]
generated_graphs = set([])
for S in hadamard_matrices:
generated_graphs = generated_graphs.union(find_hadamard_graphs(S))
for g in generated_graphs:
print g