时间戳

首页 > 解决方案 > 在有向（或无向）图中查找所有 st 节点切割

python - 在有向（或无向）图中查找所有 st 节点切割

问题描述

我需要在 st 图中找到所有可能的节点切割。这是一个有向图，但找到无向图的切割就足够了（我可以在之后过滤它们）。

Networkx 提供以下功能：

但它不是针对有向图实现的（没问题），并且它不考虑 st graphs，因此该解决方案在我的情况下没有用（至少对于函数包含源 S 的割集）。

我尝试实现组合方法（检查所有可能的节点组合），它可以工作，但效率极低，从超过 10 个节点的图形开始，执行时间过长。

我试图检查是否可以修改诸如minimum_st_node_cut之类的网络功能，但没有成功，我不知道是否可以列出所有可能的削减。

如果它为此提供了一些有用的工具（甚至是编程语言，如果需要），我也可以使用任何其他库。

标签： pythongraphnetworkx

解决方案

IGraph提供了一种算法，但我无法评估它的计算效率。对于我的 93 个节点的实例，它直到我在几个小时后停止它才能找到切割。不过，它适用于较小的实例：

import numpy as np
from igraph import Graph

# Create adjacancy matrix
adjacency = np.array([  [0,0,0],
                        [0,0,1],
                        [1,0,0],])

iG = Graph.Adjacency((adjacency > 0).tolist())
cuts = iG.all_st_cuts(1,2)

推荐阅读