-
-
Save michaelsoltys/b7c0a054cddcea2c384e032420808f58 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Dec 15 01:52:35 2016 | |
@author: arewh | |
""" | |
from itertools import combinations, permutations | |
import matplotlib.pyplot as plt | |
import time | |
#directly from Joel's code | |
#converts encoding to adjacency matrix given vertex count | |
def convert_encoding_to_matrix(vertices, enc): | |
matrix = [[0 for x in range(vertices)] for y in range(vertices)] | |
upp_diag = [(i,j) for i in range(vertices-1) for j in range(i+1, vertices)] | |
for n in range(len(enc)): | |
i, j = upp_diag[n] | |
matrix[i][j] = matrix[j][i] = int(enc[n]) | |
return matrix | |
#checks if a given set of cliques (set of frozensets) covers graph with v vertices | |
#and adjacency matrix adj | |
def covers(cover,v,adj): | |
if not all(any(i in clique for clique in cover) for i in range(v)): | |
return False | |
for i in range(v-1): | |
for j in range(i+1,v): | |
if adj[i][j] and not any(set([i,j]).issubset(clique) for clique in cover): | |
return False | |
return True | |
#given vertex count (v) and adjacency matrix (adj) outputs set of maximal cliques | |
#in form: set of frozensets | |
def maximalCliques(v,adj): | |
cliques = [] | |
cliques.append(set(frozenset([i]) for i in range(v))) | |
toggle = True | |
notMaximal = set() | |
while toggle: | |
newCliques=set() | |
for clique in cliques[-1]: | |
for i in range(v): | |
if all(adj[i][j]==1 for j in clique): | |
new = set(clique) | |
new.add(i) | |
newCliques.add(frozenset(new)) | |
notMaximal.add(clique) | |
if newCliques: | |
cliques.append(newCliques) | |
else: | |
toggle = False | |
maxCliques = set() | |
for cliqueGroup in cliques: | |
maxCliques.update(cliqueGroup) | |
maxCliques.difference_update(notMaximal) | |
return maxCliques | |
#given vertex count(v), encoding, returns set of isomorphic encodings | |
def getIsomorphisms(v,encoding): | |
upp_diag = [(i,j) for i in range(v-1) for j in range(i+1, v)] | |
perms = set(permutations(range(v))) | |
perms.remove(tuple(range(v))) | |
isomorphicEncodings = set() | |
for perm in perms: | |
newIso = '' | |
perm_upp_diag = [(perm[i],perm[j]) for i in range(v-1) for j in range(i+1,v)] | |
for n in range(len(encoding)): | |
i,j = perm_upp_diag[n] | |
if i > j: | |
i,j = (j,i) | |
newIso += encoding[upp_diag.index((i,j))] | |
isomorphicEncodings.add(newIso) | |
return isomorphicEncodings | |
#given vertex count(v) and set of encodings, returns set of unique unlabelled encodings | |
def filterIsomorphisms(v,encoding_set): | |
uniques = set() | |
while encoding_set: | |
new = encoding_set.pop() | |
uniques.add(new) | |
isos = getIsomorphisms(v,new) | |
encoding_set.difference_update(isos) | |
return uniques | |
#given vertex count (v) and adjacency matrix (adj), ouputs size of smallest cover | |
def minCliqueSize(v,adj): | |
maxCliques = maximalCliques(v,adj) | |
mandatory = set() | |
optional = set() | |
for clique in maxCliques: | |
if len(clique) < 3: | |
mandatory.add(clique) | |
else: | |
optional.add(clique) | |
solution = 0 | |
i = 1 | |
if not optional: | |
return len(mandatory) | |
while True: | |
possibleCovers = combinations(optional,i) | |
for opcover in possibleCovers: | |
cover = mandatory.union(opcover) | |
if covers(cover,v,adj): | |
solution = i + len(mandatory) | |
break | |
i += 1 | |
if solution: | |
break | |
return solution | |
#outputs list of ordered pairs (e,c) where e is the number of edges | |
#and c is the size of the largest minimal clique cover for said edge count | |
#on the number of vertices input. | |
def worst_clique_cover_vs_edges(num_vertices): | |
num_edges = sum(range(num_vertices)) | |
#display progress, only when it's relevant... | |
display = bool(num_vertices>6) | |
#generate encodings representing top diagonal of adjacecy matrices for all | |
#graphs on specified number of vertices. | |
#TO DO: filter isomorphisms, we're testing each case countless times | |
if display: | |
print('Generating graphs...') | |
graph_encodings = set([bin(x)[2:].zfill(num_edges) for x in range(2**num_edges)]) | |
#attempt to filter isomorphisms... | |
if display: | |
print('Filtering isomorphisms...') | |
graph_encodings = filterIsomorphisms(num_vertices,graph_encodings) | |
#sort by number of edges | |
if display: | |
print('Sorting graphs...') | |
sorted_graph_encodings = dict() | |
for i in range(num_edges+1): | |
sorted_graph_encodings[i]=[] | |
for encoding in graph_encodings: | |
count = sum(int(i) for i in encoding) | |
sorted_graph_encodings[count].append(encoding) | |
#get ordered pairs | |
if display: | |
print('Checking up to',num_edges,'edges...') | |
pairs = list() | |
for i in range(num_edges+1): | |
maximum = 0 | |
for encoding in sorted_graph_encodings[i]: | |
adj = convert_encoding_to_matrix(num_vertices,encoding) | |
new = minCliqueSize(num_vertices,adj) | |
if new > maximum: | |
maximum = new | |
pairs.append((i,maximum)) | |
if display: | |
print(i,'/',num_edges,'edges complete.') | |
return pairs | |
if __name__ == '__main__': | |
while True: | |
try: | |
vertex_count = int(input('How many vertices? ')) | |
if vertex_count > 1: | |
break | |
else: | |
vertex_count = int('make a value error :)') | |
except ValueError: | |
print('Invalid input. Valid inputs are integers greater than 1.') | |
start_time = time.time() | |
pairs = worst_clique_cover_vs_edges(vertex_count) | |
x = [] | |
y = [] | |
print('Printing coordinates:') | |
for pair in pairs: | |
print(pair[0],' ',pair[1]) | |
'''x.append(pair[0]) | |
y.append(pair[1]) | |
plt.plot(x,y) | |
plt.scatter(x,y) | |
plt.grid(True) | |
plt.axis([0,max(x)+1,0,max(y)+1]) | |
plt.ylabel('size of largest minimal clique cover') | |
plt.xlabel('edges on ' + str(vertex_count) + ' vertices') | |
fig = plt.gcf() | |
fig.savefig(str(vertex_count) + '_vertices') | |
plt.show()''' | |
end_time = time.time() | |
elapsed = round(end_time-start_time,2) | |
print('elapsed time:','--- %s seconds ---' % elapsed) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment