Поиск наибольшей клики в неориентированном графе

Учитывая неориентированный граф, мне нужно найти самую большую клику. Что я делаю, так это сначала нахожу его размер (т.е. сколько вершин/узлов). При этом я удаляю все узлы, которые не являются частью самой большой клики (т. е. если максимальный размер равен 3, я удаляю все узлы только с одним соседним узлом, потому что они не могут быть частью этой большей клики).

Это мой код:

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

Я отправляю через онлайн-проверку на курс Udemy, и вот результат:

['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**

python undirected-graph clique clique-problem
person EddieEC    schedule 08.12.2019    source источник
comment
В чем тут вопрос?   -  person nicoring    schedule 09.12.2019
comment
@nicoring Можете ли вы проверить мой код, потому что в последний раз он дает мне объект NoneType, который не является итерируемым, но я не могу определить, где он находится (пожалуйста, проверьте блок кода результатов).   -  person EddieEC    schedule 09.12.2019
comment
В вашем коде есть несколько мест, где вы возвращаете None, поэтому я предполагаю, что программа проверки Udemy ожидает список в этом случае, потому что вы получаете OBJECT NOT ITERABLE, поэтому вместо этого вы можете попытаться вернуть пустой список.   -  person nicoring    schedule 09.12.2019
comment
К сожалению, я пробовал, чтобы программа проверки Udemy требовала возврата None, если нет кликов (Clique should be None for graph = {'A': [ ]})   -  person EddieEC    schedule 09.12.2019

Ответы (1)


arrow_upward
0
arrow_downward

После нескольких часов работы этот код выполняет свою работу. Я уверен, что кто-то может сделать это намного лучше, но это в значительной степени подводит итог тому, как я думал об этом процессе.

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
person EddieEC    schedule 09.12.2019