Note

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

networkx.algorithms.approximation.maxcut.one_exchange

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.

Parameters
Gnetworkx Graph

Graph to find a maximum cut for.

initial_cutset

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.

weightobject

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

Returns
cut_valuescalar

Value of the maximum cut.

partitionpair of node sets

A partitioning of the nodes that defines a maximum cut.