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
。
最佳答案
我不确定您的性能要求是什么,但可以在不编写太多新代码的情况下做得比指数更好。假设我们有一个闭包 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})
这通过修剪不会产生任何结果的递归树的分支来枚举具有多项式延迟的相关切割。
这里有很大的改进空间,因为连接测试背后的流问题具有丰富的组合结构。
关于python - 使用 networkx 在图中查找基数为 k 的所有 node_cut,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32058971/