cut_size

cut_size(G, S, T=None, weight=None)

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 of S.

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 set T (and, in the case of directed graphs, all edges from nodes in T to nodes in S).

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.