0

给定一个无向图，我需要找到最大的集团。我要做的是首先找到它的大小（即有多少顶点/节点）。这样做时，我删除了不属于最大集团的所有节点（即，如果最大大小为 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**
4

1 回答 1

0

经过数小时的工作，这段代码完成了这项工作。我相信有人可以做得更好，但这几乎总结了我对这个过程的看法。

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
于 2019-12-09T04:15:52.243 回答