python - 检查子图是否是 NetworkX 中的集团的最快方法

Question

我想知道 G 的给定子图是否是完全图。我期待找到一个内置函数，例如 is_complete_graph(G)，但我看不到类似的东西。

我目前的解决方案是创建一个新的辅助函数:

def is_complete(G):
    n = G.order()
    return n*(n-1)/2 == G.size()

我想这可能很快，但我觉得自己实现这种事情是错误的，我觉得在 NetworkX 中必须有一种“正确”的方法来做到这一点。

我只需要一个简单无向图的解决方案。

Answer 1

编辑

底部的答案比较干净。但是，似乎以下速度更快:

def is_subclique(G,nodelist):
    H = G.subgraph(nodelist)
    n = len(nodelist)
    return H.size() == n*(n-1)/2

我不得不承认，我并不完全理解。但显然创建子图比检查每条边是否存在要快。

---

我希望速度较慢的替代方案:

我们将检查是否所有边都存在。我们将使用组合 来生成我们检查的对。请注意，如果 combinations 返回 (1,2)，则它不会返回 (2,1)。

from itertools import combinations
import networkx as nx

def is_subclique(G, nodelist):
    r'''For each pair of nodes in nodelist whether there is an edge
        if any edge is missing, we know that it's not a subclique.
        if all edges are there, it is a subclique
    '''
    for (u,v) in combinations(nodelist,2):  #check each possible pair
        if not G.has_edge(u,v):
            return False #if any edge is missing we're done
    return True  #if we get to here, then every edge was there.  It's True.

G = nx.Graph()
G.add_edges_from([(1,2), (2,3), (3,1), (4,1)])

is_subclique(G, [1,2,3])
> True
is_subclique(G, [1,4])
> True
is_subclique(G, [2,3,4])
> False