找到最大团并移除节点？

Question

我试图为一组项目找到最大的集团。在

目前我使用的是python的networkx库，使用find_cliques（）函数来查找所有最大的团，如下所示：

import newtworkx as nx

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6]]

G.add_edges_from(E)
#G.edges()

lst = list(nx.find_cliques(G))
lst

Out [] : [[2, 1, 3, 4], [2, 5, 6]]

但我实际期望的是找到最大团，然后移除最大团图中的节点，然后再从之前移除的节点中找到最大团。在

对于上面的例子，我希望得到[2，1，3，4]，然后删除这些节点，因此只剩下5和6，这将是另一个集团[5，6]。在

更新

我们可以使用G.remove_node（），它会按预期删除节点以及所有相邻的边。在

^{pr2}$

但每次移除节点时，都会发现新的最大团并将其存储在新的列表中，依此类推。它如何在while循环中运行，直到图G中没有剩余的边，即节点数为0或1。在

Answer 1

您可以使用G.remove_node从图中删除节点（以及相关联的边）。在

如何删除第一个集团的所有节点：

lst = list(nx.find_cliques(G))
[G.remove_node(nd) for nd in lst[0]]

要重复删除第一个团的节点，直到没有剩下的团：

^{pr2}$

请注意，这与在每个步骤移除任何最大团中的所有节点不同，这将是：

lst = list(nx.find_cliques(G))
while len(lst) > 0:

    # This flattens the list of cliques into one list. `set` reduces to unique values.
    flattened = set([nd for cl in lst for nd in cl])

    [G.remove_node(nd) for nd in flattened]
    lst = list(nx.find_cliques(G))

最后，如果您想按一定的顺序删除集团（例如，首先是最大集团），您可以通过相应地排序lst来完成此操作：

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    lst.sort(key=len, reverse=True)       # Sort maximum clique to the front
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

编辑：为了完整起见，以下是在删除之前如何存储这些集团（根据您的评论，@Ankie）：

out = []
lst = list(nx.find_cliques(G))
while len(lst) > 0:
    out.append(lst[0])
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

另外需要指出的是，这些操作基本上是“破坏”图G。如果以后再次需要该图，并且需要花费很长的时间来构建，那么有必要对该图进行复制，以便保留原始图。可以这样制作副本：

G2 = G.copy()