检查子图是否是 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它来生成我们检查的对。注意，如果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