networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph#

class EdgeComponentAuxGraph[源代码]#

在图中查找所有k边连接组件的简单算法。

构造辅助图(可能需要一些时间)允许在线性时间内为任意k找到k-edge-ccs。

笔记

此实现基于 [1]. 其思想是构造一个辅助图,从中可以在线性时间内提取k-边-CCS。辅助图构建在 \(O(|V|\cdot F)\) 运算,其中F是最大流的复杂性。查询组件需要额外的 \(O(|V|)\) 运营部。这个算法对于大图来说可能很慢,但它可以处理任意的k,并且对有向和无向输入都有效。

k=1的无向情况是完全连接的组件。k=2的无向情况正好是桥接元件。k=1的有向情况是完全强连接的组件。

工具书类

1

王天浩等。(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-边-CCS,但它也可以通过优化搜索空间来提高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边连接子图的辅助图。