chain_decomposition#

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

返回图的链分解。

相对于深度优先搜索树的图的*链分解*是从树的基本循环集合中导出的一组循环或路径。考虑相对于给定树的每个基本循环，表示为从远离树根的非树边开始的边列表。对于每个基本循环，如果它与任何先前的基本循环重叠，只需取初始的非重叠段，这是一个路径而不是循环。每个循环或路径称为*链*。更多信息请参见[1]。

Parameters:
G无向图
root节点（可选）

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

Yields:
chain列表

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

Raises:
NodeNotFound

如果 root 不在图 G 中。

Notes

此实现的 worst-case 运行时间是节点数和边数的线性时间[1]。

References

[1]

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>

Examples

>>> G = nx.Graph([(0, 1), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> list(nx.chain_decomposition(G))
[[(4, 5), (5, 3), (3, 4)]]
On this page