python中的集团 [英] Cliques in python

问题描述

我遇到了这个问题，需要帮助，这是我的代码:

I have this problem and I need help with it, this is my code:

      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的团是否正确(如果它是真值)，我想删除一个边，因此可以消除complete-graph(3). 我该怎么办?

first I searched in my graph to find cliques, after that I test if the clique of length 3, if its true I want to delete one edge So I can eliminate complete-graph(3). How can I do that?

谢谢

推荐答案

我认为这里最棘手的问题是处理共享边缘.您不想每次删除边都需要搜索团，但是您需要记住已删除的边.

I think the trickiest problem here is dealing with shared edges. You don't want to search for cliques each time you remove an edge, and yet you need to remember which edges you've already removed.

查看文档，我们发现find_cliques函数是一个生成器.

Looking at the documentation, we find that the find_cliques function is a generator.

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

This implementation is a generator of lists each of which contains the members of a maximal clique

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

Does this mean that you can generate a clique, remove an edge, and then generate the next clique, and our generator will know that we've removed an edge?

用另一个问题来回答这个问题:为什么不每次分解集团后就跳出发电机?

Answering this question with another question: why not just break out of the generator each time you break down a clique?

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完全的.

You have to keep in mind that ANYTHING you do with cliques has the potential to be very resource-consuming, since even simply detecting a clique in a graph is NP-complete.

这篇关于python中的集团的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！