Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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 of S. weight (object) – Edge attribute key to use as weight. If not specified, edges have weight one. 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). 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.