chain_decomposition#

chain_decomposition(G, root=None)[source]#

返回图的链分解。

图的链分解是相对于深度优先搜索树的一组循环或路径，其导出方式如下：对于给定树的每个基本循环，表示为一个以非树边开始的边列表，且非树边方向远离树的根。对于每个基本循环，如果它与任何先前的基本循环重叠，则只取初始非重叠的部分，这部分是一个路径而不是循环。每个循环或路径称为一条链。更多信息，请参阅 [1]。

参数:
G无向图
root节点 (可选)

图 G 中的一个节点。如果指定，则仅返回包含此节点的连通分量的链分解。此节点表示深度优先搜索树的根。

返回 (生成器):
chain列表

表示一条链的边列表。不保证每条链中边的方向性（例如，如果一条链包含连接节点 1 和 2 的边，则该链可能包含 (1, 2) 或 (2, 1)）。

抛出:
NodeNotFound

如果 root 不在图 G 中。

注意

该实现的在最坏情况下的运行时间与节点数和边数呈线性关系 [1]。

参考文献

[1] (1,2)

Jens M. Schmidt (2013). “A simple test on 2-vertex- and 2-edge-connectivity.” Information Processing Letters, 113, 241–244. Elsevier. <https://doi.org/10.1016/j.ipl.2013.01.016>

示例

>>> G = nx.Graph([(0, 1), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> list(nx.chain_decomposition(G))
[[(4, 5), (5, 3), (3, 4)]]
在本页