如何使用networkx + python枚举图中的所有*最大*集团? [英] How do I enumerate all *maximal* cliques in a graph using networkx + python?

问题描述

如果您查看 https://en.wikipedia.org/wiki/Clique_problem ，您会注意到集团与最大集团之间有所区别.最大派别仅包含在其他派别中.所以我想要那些团体，但是networkx似乎只提供:

If you look at https://en.wikipedia.org/wiki/Clique_problem, you'll notice there is a distinction between cliques and maximal cliques. A maximal clique is contained in no other clique but itself. So I want those clique, but networkx seems to only provide:

networkx.algorithms.clique.enumerate_all_cliques(G)

所以我尝试了一种简单的for循环过滤机制(见下文).

So I tried a simple for loop filtering mechanism (see below).

def filter_cliques(self, cliques):
    # TODO: why do we need this?  Post in forum...
    res = []
    for C in cliques:
        C = set(C)
        for D in res:
            if C.issuperset(D) and len(C) != len(D):
                res.remove(D)
                res.append(C)
                break
            elif D.issuperset(C):
                break
        else:
            res.append(C)
    res1 = []
    for C in res:
        for D in res1:
            if C.issuperset(D) and len(C) != len(D):
                res1.remove(D)
                res1.append(C)
            elif D.issuperset(C):
                break
        else:
            res1.append(C)     
    return res1

我想过滤掉所有合适的子斜面.但是您可以看到它很烂，因为我不得不对其进行两次过滤.这不是很优雅.因此，问题在于，给出了对象列表(整数，字符串)的列表，这些对象列表是图中的节点标签； enumerate_all_cliques(G)完全返回此标签列表列表.现在，根据此列表列表，筛选出所有适当的子clicli.例如:

I want to filter out all the proper subcliques. But as you can see it sucks because I had to filter it twice. It's not very elegant. So, the problem is, given a list of lists of objects (integers, strings), which were the node labels in the graph; enumerate_all_cliques(G) returns exactly this list of lists of labels. Now, given this list of lists, filter out all proper subcliques. So for instance:

[[[a，b，c]，[a，b]，[b，c，d]] => [[a，b，c]，[b，c，d]]

[[a, b, c], [a, b], [b, c, d]] => [[a, b, c], [b, c, d]]

最快的pythonic方法是什么?

What's the quickest pythonic way of doing that?

推荐答案

为此提供了一个功能:

There's a function for that: networkx.algorithms.clique.find_cliques, and yes, it does return only maximal cliques, despite the absence of "maximal" from the name. It should run a lot faster than any filtering approach.

如果您发现名称令人困惑(我愿意)，则可以将其重命名:

If you find the name confusing (I do), you can rename it:

from networkx.algorithms.clique import find_cliques as maximal_cliques

这篇关于如何使用networkx + python枚举图中的所有*最大*集团?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！