python - 使用 networkx 在图中查找基数为 k 的所有 node_cut

Question

networkx 函数 minimum_node_cut(G) 返回一组断开 G 的最小基数节点。但它只返回一个集合，即使可能存在其他解决方案。我想知道如何获得给定图 G 的所有这些 minimum_node_cuts。

在扩展中，如何获得基数为 k 的所有节点切割？

我想不出可以有效计算的算法。是否存在比尝试 k 个节点的每个组合并检查 G 是否断开连接的朴素方法更好的方法？

编辑:我真的很喜欢 David Eisenstat 的回答，但我无法实现它。我试过了，但我收到一个错误，这可能是由于递归性错误导致的，并且无法弄清楚它是什么。这是代码:

def all_small_cuts(G, k, S=set()): 
    try:
        kappa = nx.node_connectivity(G)
    except nx.NetworkXPointlessConcept:
        return

    if kappa > k - len(S):
        return
    if kappa == 0:  # disconnected
        yield S
    if len(S) < k:
        for node in G.nodes():
            G.remove_node(node)
            S.update(set(str(node)))
            for el in all_small_cuts(G, k, S):
                yield el

因为我使用的是 python 2.7，所以我刚刚替换了 yield from。

Answer 1

我不确定您的性能要求是什么，但可以在不编写太多新代码的情况下做得比指数更好。假设我们有一个闭包 node_connectivity 这样，当 U 是一组节点时，node_connectivity(U) 是导出子图的连通性在 U 上。对于最多 k 的基数削减，有一个递归枚举策略。 (警告:未经测试。)

def all_small_cuts(U, k, S={}):  # U is the set of vertices
                                 # whose inclusion in S
                                 # is not yet decided
    kappa = node_connectivity(U)
    if kappa > k - len(S):
        return
    if kappa == 0:  # disconnected already
        yield S
    if len(S) < k:
        for v in U:
            yield from all_small_cuts(U - {v}, k, S | {v})

这通过修剪不会产生任何结果的递归树的分支来枚举具有多项式延迟的相关切割。

这里有很大的改进空间，因为连接测试背后的流问题具有丰富的组合结构。