chain_decomposition(G, root=None)
The chain decomposition of a graph with respect a depth-first 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 non-overlapping segment, which is a path instead of a cycle. Each cycle or path is called a chain. For more information, see .
The worst-case running time of this implementation is linear in the number of nodes and number of edges .
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 depth-first search tree.
If :None:None:`root` is not in the graph G.
Returns the chain decomposition of a graph.
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)).
>>> G = nx.Graph([(0, 1), (1, 4), (3, 4), (3, 5), (4, 5)])See :
... list(nx.chain_decomposition(G)) [[(4, 5), (5, 3), (3, 4)]]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.chains.chain_decomposition
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them