k_edge_subgraphs

k_edge_subgraphs(G, k)

在图 G 中生成每个极大 k-边连通子图中的节点。

参数:

GNetworkX 图

k整数

期望的边连通性

返回:

k_edge_subgraphsk-边子图的生成器

每个 k-边子图是一个节点的最大集合，该集合定义了 G 的一个 k-边连通子图。

引发:

NetworkXNotImplemented

如果输入图是多重图。

ValueError

如果 k 小于 1

另请参见

edge_connectivity()

k_edge_components()

与此函数类似，但节点只需要在图 G 中具有 k-边连通性，并且子图可能不是 k-边连通的。

注意

尝试使用基于 k 的最高效的可用实现。如果 k=1，或者 k=2 且图是无向的，则此函数仅调用 k_edge_components。否则使用文献 [1] 中的算法。

参考文献

[1]

Zhou, Liu, et al. (2012) 从大型图中寻找最大的 k-边连通子图。ACM International Conference on Extending Database Technology 2012 480-–491。https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

示例

>>> 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 does not return {1, 4} unlike k_edge_components
>>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3)))
[[1], [2], [3], [4], [5, 6, 7, 8]]