This documents the development version of NetworkX. Documentation for the current release can be found here.


one_exchange(G, initial_cut=None, seed=None, weight=None)[source]

Compute a partitioning of the graphs nodes and the corresponding cut value.

Use a greedy one exchange strategy to find a locally maximal cut and its value, it works by finding the best node (one that gives the highest gain to the cut value) to add to the current cut and repeats this process until no improvement can be made.

Gnetworkx Graph

Graph to find a maximum cut for.


Cut to use as a starting point. If not supplied the algorithm starts with an empty cut.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.


Edge attribute key to use as weight. If not specified, edges have weight one.


Value of the maximum cut.

partitionpair of node sets

A partitioning of the nodes that defines a maximum cut.