k_edge_subgraphs

k_edge_subgraphs(G, k)

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

Parameters:

GNetworkX 图

k整数

所需的边连通性

Returns:

k_edge_subgraphsk-边连通子图的生成器

每个 k-边连通子图是由一组节点定义的 G 的子图，该子图是 k-边连通的。

Raises:

NetworkXNotImplemented

如果输入图是多重图。

ValueError:

如果 k 小于 1

See also

edge_connectivity()

k_edge_components()

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

Notes

尝试根据 k 使用最有效的实现。如果 k=1 或 k=2 且图是无向的，则直接调用 k_edge_components 。否则使用参考文献 [1] 中的算法。

References

[1]

Zhou, Liu, et al. (2012) 从大图中寻找最大 k-边连通子图。ACM 国际扩展数据库技术会议 2012 480-–491. https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

Examples

>>> 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]))
>>> # 注意这与 k_edge_components 不同，不会返回 {1, 4}
>>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3)))
[[1], [2], [3], [4], [5, 6, 7, 8]]