minimum_st_node_cut#
- minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None)[源代码]#
返回一组最小基数的节点,这些节点将源与g中的目标断开连接。
此函数返回一组最小基数的节点,如果删除这些节点,将销毁g中源和目标之间的所有路径。
- 参数
- G网络X图表
- s结点
源节点。
- t结点
目标节点。
- flow_func功能
一种函数,用于计算一对节点之间的最大流。该函数必须接受至少三个参数:有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见
maximum_flow()
有关详细信息,请参见)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (edmonds_karp()
)被使用。详情见下文。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。- auxiliary网络X有向图
计算基于流的节点连通性的辅助有向图。它必须有一个名为map的图属性,并有一个字典映射G和辅助有向图中的节点名称。如果提供,它将被重复使用,而不是重新创建。默认值:无。
- residual网络X有向图
计算最大流量的残差网络。如果提供,它将被重复使用,而不是重新创建。默认值:无。
- 返回
- cutset设置
一组节点,如果删除,将销毁G中源和目标之间的所有路径。
参见
minimum_node_cut()
minimum_edge_cut()
stoer_wagner()
node_connectivity()
edge_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()
笔记
这是基于流的最小结点割的实现。该算法基于求解大量的最大流计算,以确定与G的最小结点割相对应的辅助有向网络上的最小割的容量。它同时处理有向图和无向图。此实现基于 [1].
工具书类
- 1
Abdol Hossein Esfahanian。连接算法。http://www.cse.msu.edu/~cse835/papers/graph_connectivity_revised.pdf
实例
此函数未导入到基本NetworkX命名空间中,因此必须从连接包中显式导入:
>>> from networkx.algorithms.connectivity import minimum_st_node_cut
我们在这个例子中使用了柏拉图二十面体图,它具有节点连通性5。
>>> G = nx.icosahedral_graph() >>> len(minimum_st_node_cut(G, 0, 6)) 5
如果需要在同一个图中计算多对节点之间的局部ST切割,建议重用NetworkX在计算中使用的数据结构:用于节点连接和节点切割的辅助有向图,以及用于底层最大流量计算的剩余网络。
如何使用数据结构计算本地ST节点切割的示例:
>>> # You also have to explicitly import the function for >>> # building the auxiliary digraph from the connectivity package >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity >>> H = build_auxiliary_node_connectivity(G) >>> # And the function for building the residual network from the >>> # flow package >>> from networkx.algorithms.flow import build_residual_network >>> # Note that the auxiliary digraph has an edge attribute named capacity >>> R = build_residual_network(H, "capacity") >>> # Reuse the auxiliary digraph and the residual network by passing them >>> # as parameters >>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R)) 5
您还可以使用可选的流算法来计算最小ST节点切割。例如,在稠密网络中,算法
shortest_augmenting_path()
通常会比默认性能更好edmonds_karp()
对于高度倾斜度分布的稀疏网络,这一点更快。必须从流包显式导入可选流函数。>>> from networkx.algorithms.flow import shortest_augmenting_path >>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path)) 5