node_connectivity#
- node_connectivity(G, s=None, t=None, flow_func=None)[源代码]#
返回图或有向图G的节点连接。
节点连接性等于断开G连接或使G变得微不足道时必须删除的最小节点数。如果提供了源节点和目标节点,则此函数返回本地节点连接:在g中,必须删除的节点的最小数目,才能中断从源到目标的所有路径。
- 参数
- G网络X图表
无向图
- s结点
源节点。可选的。默认值:无。
- t结点
目标节点。可选的。默认值:无。
- flow_func功能
一种函数,用于计算一对节点之间的最大流。该函数必须接受至少三个参数:有向图、源节点和目标节点。并返回遵循NetworkX约定的剩余网络(请参见
maximum_flow()
有关详细信息,请参见)。如果FLOW_FUNC为NONE,则默认的最大流量函数 (edmonds_karp()
)被使用。详情见下文。默认功能的选择可能因版本不同而有所不同,不应依赖。默认值:无。
- 返回
- K整数
G的节点连接,如果提供了源和目标,则为本地节点连接。
参见
local_node_connectivity()
edge_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()
笔记
这是节点连接性的基于流的实现。该算法通过求解 \(O((n-\delta-1+\delta(\delta-1)/2))\) 辅助有向图上的最大流问题。哪里 \(\delta\) 是G的最小次数。有关辅助有向图和局部节点连通性计算的详细信息,请参阅
local_node_connectivity()
。此实现基于 [1].工具书类
- 1
Abdol Hossein Esfahanian。连接算法。http://www.cse.msu.edu/~cse835/papers/graph_connectivity_revised.pdf
实例
>>> # Platonic icosahedral graph is 5-node-connected >>> G = nx.icosahedral_graph() >>> nx.node_connectivity(G) 5
您可以使用可选的流算法进行底层最大流计算。在稠密网络中,算法
shortest_augmenting_path()
通常会比默认性能更好edmonds_karp()
对于高度倾斜度分布的稀疏网络来说,这一点更快。必须从流包显式导入可选流函数。>>> from networkx.algorithms.flow import shortest_augmenting_path >>> nx.node_connectivity(G, flow_func=shortest_augmenting_path) 5
如果指定一对节点(源和目标)作为参数,则此函数返回本地节点连接的值。
>>> nx.node_connectivity(G, 3, 7) 5
如果需要在同一个图上的不同节点对之间执行多个本地计算,建议重用最大流计算中使用的数据结构。见
local_node_connectivity()
有关详细信息。