networkx.algorithms.chains.chain_decomposition¶

chain_decomposition
(G, root=None)[source]¶ Returns the chain decomposition of a graph.
The chain decomposition of a graph with respect a depthfirst search tree is a set of cycles or paths derived from the set of fundamental cycles of the tree in the following manner. Consider each fundamental cycle with respect to the given tree, represented as a list of edges beginning with the nontree edge oriented away from the root of the tree. For each fundamental cycle, if it overlaps with any previous fundamental cycle, just take the initial nonoverlapping segment, which is a path instead of a cycle. Each cycle or path is called a chain. For more information, see [1].
Parameters:  G (undirected graph)
 root (node (optional)) – A node in the graph
G
. If specified, only the chain decomposition for the connected component containing this node will be returned. This node indicates the root of the depthfirst search tree.
Yields: chain (list) – A list of edges representing a chain. There is no guarantee on the orientation of the edges in each chain (for example, if a chain includes the edge joining nodes 1 and 2, the chain may include either (1, 2) or (2, 1)).
Raises: NodeNotFound
– Ifroot
is not in the graphG
.Notes
The worstcase running time of this implementation is linear in the number of nodes and number of edges [1].
References
[1] (1, 2) Jens M. Schmidt (2013). “A simple test on 2vertex and 2edgeconnectivity.” Information Processing Letters, 113, 241–244. Elsevier. <https://doi.org/10.1016/j.ipl.2013.01.016>