networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph

class EdgeComponentAuxGraph

一种用于查找图中所有 k-边连通分量的简单算法。

构建辅助图（可能需要一些时间）后，可以在线性时间内找到任意 k 的 k-边连通分量。

说明

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

对于无向图，k=1 的情况就是连通分量。对于无向图，k=2 的情况就是桥连通分量。对于有向图，k=1 的情况就是强连通分量。

参考文献

[1]

Wang, Tianhao 等人 (2015) 一种查找所有 k-边连通分量的简单算法。http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

示例

>>> import itertools as it
>>> from networkx.utils import pairwise
>>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
>>> # Build an interesting graph with multiple levels of k-edge-ccs
>>> paths = [
...     (1, 2, 3, 4, 1, 3, 4, 2),  # a 3-edge-cc (a 4 clique)
...     (5, 6, 7, 5),  # a 2-edge-cc (a 3 clique)
...     (1, 5),  # combine first two ccs into a 1-edge-cc
...     (0,),  # add an additional disconnected 1-edge-cc
... ]
>>> G = nx.Graph()
>>> G.add_nodes_from(it.chain(*paths))
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
>>> # Constructing the AuxGraph takes about O(n ** 4)
>>> aux_graph = EdgeComponentAuxGraph.construct(G)
>>> # Once constructed, querying takes 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)

方法

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