python中的集团

Question

我有这个问题，我需要帮助，这是我的代码：

      cliques=[clique for clique in nx.find_cliques(GC) if len(clique)>2]    

      for clique in cliques:
        if len (clique)==3:
        GC.remove_edge()
        print "Clique to appear: ",clique
      #draw the graph        
      nx.draw(GC)
      plt.show()

首先我在我的图中寻找团，然后我测试长度为3的团，如果是真的，我想删除一条边，这样我就可以消除完整图(3)。我该怎么做呢？

谢谢

Answer 1

我认为这里最棘手的问题是如何处理共享边缘。您不希望在每次删除边时都搜索集团，但您需要记住您已经删除了哪些边。

查看the documentation，我们发现find_cliques函数是一个生成器。

此实现是列表的生成器，每个列表包含最大团的成员

这是否意味着您可以生成一个集团，删除一个边，然后生成下一个集团，我们的生成器将知道我们已经删除了一个边？

用另一个问题来回答这个问题:为什么不在每次你打破一个派系的时候就打破生成器呢？

edge_removed = True
while edge_removed:
    edge_removed = False
    for clique in nx.find_cliques(GC):
        if len (clique)>=3:
            GC.remove_edge(clique[0], clique[1])
            edge_removed = True
            break # Gotta restart the generator now...

您必须记住，您对集团所做的任何操作都有可能非常消耗资源，因为即使是简单地在图中检测集团也是NP-完全的。

Answer 2

if len(clique)==3:
    GC.remove_edge(*clique[0:2])

或(等效)

if len(clique)==3:
    GC.remove_edge(clique[0], clique[1])

但我可能遗漏了一些重要的东西，因为这似乎很明显，而且我不是专家-我只是阅读了networkx文档(上面说一个集团是一个节点列表，而remove_edge需要两个节点)。