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

Question

我希望找出G的给定子图是否为完全图。我原本期望能够找到内置函数，例如is_complete_graph(G)，但我没有发现类似的东西。

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

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

我想这可能很快，但我感觉自己实现这种东西是错误的，而且我觉得在NetworkX中一定有一种“正确”的方法来做这件事。

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

- bubsy_revelations

---

不要使用 / 进行整数除法，而是使用 //。如果使用 /，Python 3 会将整数转换为浮点数，而 // 在 Python 2 和 3 中都可以使用，对于整数操作数产生整数结果。 - Tom Karzes

@Joel 不，实际上我不需要子图做其他事情。所以像 G.has_clique(t) 这样的东西就很好。 - bubsy_revelations

它是什么类型的图表？（简单、有向、多重等） - Joel

@TomKarzes 我理解你的观点，但我不同意（这似乎违背了传统智慧）。在Python中，我喜欢将数字视为数字，而不考虑底层类型。我也不想隐藏错误。假设我的代码出现问题，除法的结果不是整数。那么 // 将会向下取整并可能掩盖问题。 - bubsy_revelations

@bubsy_revelations 请记住，当有经验的程序员看到您将两个整数类型相除以产生浮点结果时，他们会自然地假设结果不总是期望为整数，否则您就不会使用浮点表示结果。也就是说，这与您想要传达的意思完全相反。他们还可能会修复它或完全重写它。请注意，即使使用/运算符，Python 2也不会给您提供浮点结果，除非您显式地先将其中一个操作数转换为浮点数。 - Tom Karzes

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

- Joel

---

嗨，Joel。感谢您回答我的问题！我已经比较了这个函数和我的原始函数。在这里查看我的代码。我发现对于大约200个节点的图形，由于组合的爆炸性增长，这个实现要慢得多。 - bubsy_revelations

即使对于大约10个节点的图形，这种实现方式也比一般慢上一个数量级左右。我认为创建新图的成本被以这种方式迭代边缘的成本所抵消。也许在处理内存受限的非常小的图形时，这种方法会更好？但对于我的用例来说，问题中的实现仍然是最好的。 - bubsy_revelations

这让我感到惊讶。我猜你在使用networkx中的subgraph命令？我原以为它是通过类似我做的循环来生成子图，但现在看源代码它正在做另一件事，我猜这样会更快。根据你的说法，我认为你的实现可能是最好的。 - Joel

好的，感谢您的帮助。我本来希望能在networkx中找到一个解决方案，但如果这不可行，那么我就不太可能得到一个合适的答案来回答这个问题了。 - bubsy_revelations

Answer 2

你实际上需要检查的不仅是边的数量，因为完全图不允许自环。此外，它们可能会改变期望的边数。

这里有一个非常快的函数 - 特别是如果它不是一个完全图。请注意，它甚至避免计算边的数量。它只是确保每个节点都有正确的邻居。

def is_complete_graph(G):
    N = len(G) - 1
    return not any(n in nbrdict or len(nbrdict)!=N for n, nbrdict in G.adj.items())

- dschult