时间戳

首页 > 解决方案 > 在 NetworkX 中检查子图是否为集团的最快方法

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

问题描述

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

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

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

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

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

标签： pythonnetworkxgraph-theory

解决方案

编辑

底部的答案比较干净。但是，似乎以下方法更快：

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

推荐阅读