Skip to content

Instantly share code, notes, and snippets.

@michaelsoltys

michaelsoltys/cover_vs_edges.py Secret

Created Sep 18, 2018
Embed
What would you like to do?
# -*- 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
You can’t perform that action at this time.