k_components(G, flow_func=None)
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.
Moody and White (appendix A) provide an algorithm for identifying k-components in a graph, which is based on Kanevsky's algorithm for finding all minimum-size node cut-sets of a graph (implemented in all_node_cuts
function):
Compute node connectivity, k, of the input graph G.
Identify all k-cutsets at the current level of connectivity using Kanevsky's algorithm.
Generate new graph components based on the removal of these cutsets. Nodes in a cutset belong to both sides of the induced cut.
If the graph is neither complete nor trivial, return to 1; else end.
This implementation also uses some heuristics (see for details) to speed up the computation.
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.
If the input graph is directed.
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.
Returns the k-component structure of a graph G.
biconnected_components
special case of this function when k=2
k_edge_components
similar to this function, but uses edge-connectivity instead of node-connectivity
>>> # Petersen graph has 10 nodes and it is triconnected, thus allSee :
... # nodes are in a single component on all three connectivity levels
... G = nx.petersen_graph()
... k_components = nx.k_components(G)
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.connectivity.kcomponents.k_components
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