edge_connectivity#

edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None)[源代码]#

返回图形或有向图G的边缘连接。

边缘连接等于断开G连接或使G变得微不足道时必须删除的最小边缘数。如果提供了源节点和目标节点,则此函数返回本地边缘连接:在g中,必须删除的最小边缘数,以中断从源到目标的所有路径。

参数
G网络X图表

无向图或有向图

s结点

源节点。可选的。默认值:无。

t结点

目标节点。可选的。默认值:无。

flow_func功能

一种函数,用于计算一对节点之间的最大流。该函数必须接受至少三个参数:有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见 maximum_flow() 有关详细信息,请参见)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (edmonds_karp() )被使用。详情见下文。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。

cutoff整数、浮点数

如果指定,当流量值达到或超过分界值时,最大流量算法将终止。这仅适用于支持截止参数的算法:例如, edmonds_karp()shortest_augmenting_path() 。其他算法将忽略此参数。默认值:无。

返回
K整数

G的边连通性,如果提供了源和目标,则为局部边连通性

参见

local_edge_connectivity()
local_node_connectivity()
node_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()
k_edge_components()
k_edge_subgraphs()

笔记

这是基于流的全局边缘连接实施。对于无向图,该算法的工作原理是找到G的一组占支配地位的节点(参见 [1] )和计算局部最大流量(请参见 local_edge_connectivity() )在支配集合中的任意节点和其中的其余节点之间。这是中算法6的一个实现 [1] 。对于有向图,该算法对最大流函数进行n次调用。这是中算法8的一个实现 [1]

工具书类

1(1,2,3)

Abdol Hossein Esfahanian。连接算法。http://www.cse.msu.edu/~cse835/papers/graph_connectivity_revised.pdf

实例

>>> # Platonic icosahedral graph is 5-edge-connected
>>> G = nx.icosahedral_graph()
>>> nx.edge_connectivity(G)
5

您可以使用可选的流算法进行底层最大流计算。在稠密网络中,算法 shortest_augmenting_path() 通常会比默认性能更好 edmonds_karp() 对于高度倾斜度分布的稀疏网络来说,这一点更快。必须从流包显式导入可选流函数。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
5

如果指定一对节点(源和目标)作为参数,则此函数返回本地边缘连接的值。

>>> nx.edge_connectivity(G, 3, 7)
5

如果需要在同一个图上的不同节点对之间执行多个本地计算,建议重用最大流计算中使用的数据结构。见 local_edge_connectivity() 有关详细信息。