all_node_cuts(G, k=None, flow_func=None)
This implementation is based on Kanevsky's algorithm for finding all minimum-size node cut-sets of an undirected graph G; ie the set (or sets) of nodes of cardinality equal to the node connectivity of G. Thus if removed, would break G into two or more connected components.
This implementation is based on the sequential algorithm for finding all minimum-size separating vertex sets in a graph . The main idea is to compute minimum cuts using local maximum flow computations among a set of nodes of highest degree and all other non-adjacent nodes in the Graph. Once we find a minimum cut, we add an edge between the high degree node and the target node of the local maximum flow computation to make sure that we will not find that minimum cut again.
Undirected graph
Node connectivity of the input graph. If k is None, then it is computed. Default value: None.
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.
Each node cutset has cardinality equal to the node connectivity of the input graph.
Returns all minimum k cutsets of an undirected graph G.
>>> # A two-dimensional grid graph has 4 cutsets of cardinality 2
... G = nx.grid_2d_graph(5, 5)
... cutsets = list(nx.all_node_cuts(G))
... len(cutsets) 4
>>> all(2 == len(cutset) for cutset in cutsets) True
>>> nx.node_connectivity(G) 2See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.connectivity.kcomponents.k_components
networkx.algorithms.connectivity.kcutsets.all_node_cuts
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