networkx.algorithms.cuts.cut_size¶

cut_size
(G, S, T=None, weight=None)[source]¶ Returns the size of the cut between two sets of nodes.
A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges “between” the two sets of nodes.
 Parameters
G (NetworkX graph)
S (sequence) – A sequence of nodes in
G
.T (sequence) – A sequence of nodes in
G
. If not specified, this is taken to be the set complement ofS
.weight (object) – Edge attribute key to use as weight. If not specified, edges have weight one.
 Returns
Total weight of all edges from nodes in set
S
to nodes in setT
(and, in the case of directed graphs, all edges from nodes inT
to nodes inS
). Return type
number
Examples
In the graph with two cliques joined by a single edges, the natural bipartition of the graph into two blocks, one for each clique, yields a cut of weight one:
>>> G = nx.barbell_graph(3, 0) >>> S = {0, 1, 2} >>> T = {3, 4, 5} >>> nx.cut_size(G, S, T) 1
Each parallel edge in a multigraph is counted when determining the cut size:
>>> G = nx.MultiGraph(['ab', 'ab']) >>> S = {'a'} >>> T = {'b'} >>> nx.cut_size(G, S, T) 2
Notes
In a multigraph, the cut size is the total weight of edges including multiplicity.