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:
- GNetworkX graph
- Scollection
A collection of nodes in
G
.- Tcollection
A collection of nodes in
G
. If not specified, this is taken to be the set complement ofS
.- weightobject
Edge attribute key to use as weight. If not specified, edges have weight one.
- Returns:
- number
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
).
Notes
In a multigraph, the cut size is the total weight of edges including multiplicity.
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
Additional backends implement this function
graphblas : OpenMP-enabled sparse linear algebra backend.