k_edge_components#

k_edge_components(G, k)[源代码]#

在G中的每个最大k边连接组件中生成节点。

参数

G网络X图表
k整数: 所需的边连接

返回

k_edge_componentsK-EDGE-CCS的生成器。返回的每组节点: 将在图G中具有k-边连通性。

加薪

NetworkXNotImplemented: 如果输入图是多重图。
ValueError：: 如果k小于1

参见

local_edge_connectivity()
k_edge_subgraphs(): 与此函数类似，但是由节点定义的子图也必须具有k边连通性。
k_components(): 类似于此函数，但使用节点连接而不是边缘连接

笔记

尝试使用基于k的最有效的实现。如果k=1，则这是有向图的简单连通分量和无向图的连通分量。如果k=2，则得到一个有效的桥连通域算法 [[1] 是基于链分解来运行的。否则，来自 [[2] 是使用的。

工具书类

1: https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29
2: 王天浩等。（2015）查找所有K边连接组件的简单算法。http://journals.plos.org/plosone/article？ID=10.1371/journal.pone.0136264

实例

>>> import itertools as it
>>> from networkx.utils import pairwise
>>> paths = [
...     (1, 2, 4, 3, 1, 4),
...     (5, 6, 7, 8, 5, 7, 8, 6),
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # note this returns {1, 4} unlike k_edge_subgraphs
>>> sorted(map(sorted, nx.k_edge_components(G, k=3)))
[[1, 4], [2], [3], [5, 6, 7, 8]]