Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# k_components¶

k_components(G, flow_func=None)[source]

Returns the k-component structure of a graph G.

A $$k$$-component is a maximal subgraph of a graph G that has, at least, node connectivity $$k$$: we need to remove at least $$k$$ nodes to break it into more components. $$k$$-components have an inherent hierarchical structure because they are nested in terms of connectivity: a connected graph can contain several 2-components, each of which can contain one or more 3-components, and so forth.

Parameters: G (NetworkX graph) – flow_func (function) – Function to perform the underlying flow computations. Default value edmonds_karp(). This function performs better in sparse graphs with right tailed degree distributions. shortest_augmenting_path() will perform better in denser graphs. k_components – Dictionary with all connectivity levels $$k$$ in the input Graph as keys and a list of sets of nodes that form a k-component of level $$k$$ as values. dict NetworkXNotImplemented: – If the input graph is directed.

Examples

>>> # Petersen graph has 10 nodes and it is triconnected, thus all
>>> # nodes are in a single component on all three connectivity levels
>>> G = nx.petersen_graph()
>>> k_components = nx.k_components(G)


Notes

Moody and White [1] (appendix A) provide an algorithm for identifying k-components in a graph, which is based on Kanevsky’s algorithm [2] for finding all minimum-size node cut-sets of a graph (implemented in all_node_cuts() function):

1. Compute node connectivity, k, of the input graph G.
2. Identify all k-cutsets at the current level of connectivity using Kanevsky’s algorithm.
3. Generate new graph components based on the removal of these cutsets. Nodes in a cutset belong to both sides of the induced cut.
4. If the graph is neither complete nor trivial, return to 1; else end.

This implementation also uses some heuristics (see [3] for details) to speed up the computation.

node_connectivity(), all_node_cuts()