networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph

class EdgeComponentAuxGraph

一个简单的算法，用于在图中找到所有k边连通分量。

构建辅助图（可能需要一些时间）允许在任意k的情况下以线性时间找到k边连通分量。

Notes

该实现基于[1]。其思想是从辅助图中提取k边连通分量，该辅助图可以在线性时间内构建。辅助图的构建需要:math:`O(|V|cdot F)`次操作，其中F是最大流的复杂度。查询分量需要额外的:math:`O(|V|)`次操作。该算法对于大型图可能较慢，但它可以处理任意k，并且适用于有向和无向输入。

无向图中k=1的情况正是连通分量。 无向图中k=2的情况正是桥连通分量。 有向图中k=1的情况正是强连通分量。

References

[1]

Wang, Tianhao, et al. (2015) 一个简单的算法，用于找到所有k边连通分量。 http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

Examples

>>> import itertools as it
>>> from networkx.utils import pairwise
>>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
>>> # 构建一个具有多层k边连通分量的有趣图
>>> paths = [
...     (1, 2, 3, 4, 1, 3, 4, 2),  # 一个3边连通分量（一个4团）
...     (5, 6, 7, 5),  # 一个2边连通分量（一个3团）
...     (1, 5),  # 将前两个连通分量合并为一个1边连通分量
...     (0,),  # 添加一个额外的1边连通分量
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # 构建辅助图大约需要O(n ** 4)
>>> aux_graph = EdgeComponentAuxGraph.construct(G)
>>> # 构建完成后，查询需要O(n)
>>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))
[[0], [1, 2, 3, 4, 5, 6, 7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))
[[0], [1, 2, 3, 4], [5, 6, 7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
[[0], [1, 2, 3, 4], [5], [6], [7]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))
[[0], [1], [2], [3], [4], [5], [6], [7]]

辅助图主要用于k边连通分量，但它也可以通过细化搜索空间来加速k边子图的查询。

>>> import itertools as it
>>> from networkx.utils import pairwise
>>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
>>> paths = [
...     (1, 2, 4, 3, 1, 4),
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> aux_graph = EdgeComponentAuxGraph.construct(G)
>>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))
[[1], [2], [3], [4]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
[[1, 4], [2], [3]]

__init__(*args, **kwargs)

Methods

construct(G)	构建一个辅助图，用于编码节点之间的边连通性。
k_edge_components(k)	查询辅助图以获取k边连通分量。
k_edge_subgraphs(k)	查询辅助图以获取k边连通子图。