cover_vs_edges.py

# -*- 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)