Finding the largest clique in an UnDirected Graph

Question

Given an Undirected Graph, I need to find the largest clique. What I do is first find its size (ie how many vertices/nodes). While doing so, I remove any nodes that are not part of the largest clique (ie if max size is 3, I remove any nodes with only one adjacent node because they can't be part of this larger clique).

This is my code:

def find_largest_clique(graph):
    def clique_size(graph, k):
        all_nodes = graph.nodes[:]
        '''TO CHECK IF CURRENT NUMBER OF NODES IS LESS THAN K, RETURN FALSE'''
        if len(all_nodes) < k:
                return False
        current_nodes = all_nodes[:]
        for nodes in current_nodes:
            adj_nodes = graph.adjacent_nodes(nodes)
            if len(adj_nodes) < k - 1:
                all_nodes.remove(nodes)
                graph.remove_node(nodes)

        if len(all_nodes) < k:
            return False
        return True


    clique = []

    all_nodes = graph.nodes[:]

    print(all_nodes)
    if len(all_nodes) < 2:
        return None

    '''FIND LARGEST CLIQUE SIZE'''
    k = 2
    while clique_size(graph, k):
        k += 1
    k -= 1
    print(k)
    if graph is None:
        return None
    '''FIND CLIQUE'''
    remaining_nodes = graph.nodes[:]

    for nodes in remaining_nodes:
        if graph.adjacent_nodes(nodes) == []:
            graph.remove_node(nodes)

    if graph.nodes == []:
        return None

    clique = graph.nodes[:]
    print(clique)
    return clique    

I am submitting through an online checker for Udemy course and this is the result:

['A', 'B']
k = 2
['A', 'B'] **PASSED**
['A', 'B', 'C']
k = 3
['A', 'B', 'C'] **PASSED**
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
k = 26
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] **PASSED**
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'Y', 'Z', 'X']
k = 20
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T'] **PASSED**
['A', 'B', 'C', 'D', 'a', 'b', 'c', 'd', 'e', 'f']
k = 6
['a', 'b', 'c', 'd', 'e', 'f'] **PASSED**
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
3
[] **FAILED, NONETYPE OBJECT NOT ITERABLE**

Answer 1

After hours of working, this code does the job. I am sure someone can do it much better, but this pretty much sums up how I thought of the process.

def clique_size(graph, k):

        all_nodes = []
        for keys in graph:
            all_nodes.append(keys)

        if len(all_nodes) < k:
                return False
        current_nodes = all_nodes[:]
        for nodes in current_nodes:
            adj_nodes = graph[nodes]
            if len(adj_nodes) < k - 1:
                all_nodes.remove(nodes)
                graph.pop(nodes)

        if len(all_nodes) < k:
            return False
        return True

def find_largest_clique(graph):

    all_nodes = graph.nodes[:]

    '''IF SOME NODES HAVE NO ADJACENT NODES, REMOVE THEM IMMEDIATELY'''

    for nodes in all_nodes:
        if graph.adjacent_nodes(nodes) == []:
            graph.remove_node(nodes)
    if len(all_nodes) < 2:
        return 
    '''MAKE A CLONE OF THE GRAPH EDGES DICTIONARY TO NOT ALTER GRAPH'''
    clone = {}
    for keys, vals in graph.edges.items(): 
        clone[keys] = vals

    '''CHECK CLIQUE SIZE'''
    k = 2
    while clique_size(clone, k):
        k += 1
    k -= 1


    '''RECREATE CLONE IN ORDER TO BE ABLE TO ITERATE THROUGH GRAPH EDGES 
    AND REMOVE ELEMENTS (IF ITEMS REMOVED DIRECLY FROM GRAPH EDGES, LOOP WILL BREAK'''
    clone = {}
    for keys, vals in graph.edges.items(): 
        clone[keys] = vals   

    for nodes, adj in clone.items():
        if len(clone[nodes]) < k - 1:
            graph.remove_node(nodes)

    #    print(graph.edges)
    '''IF NO NODES ARE LEFT, RETURN NONE'''
    if graph.nodes == []:
        return 
    '''FIND ANY LARGEST CLIQUE'''  
    clique = []
    for keys, vals in graph.edges.items():
        clique.append(keys)
        for i in range(len(graph.edges[keys])):
            clique.append(graph.edges[keys][i])
        break

    print(clique)
    return clique