one_exchange

one_exchange(G, initial_cut=None, seed=None, weight=None)

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.

Raises:

NetworkXNotImplemented

If the graph is directed or is a multigraph.

Examples

>>> G = nx.complete_graph(5)
>>> curr_cut_size, partition = nx.approximation.one_exchange(G, seed=1)
>>> curr_cut_size
6
>>> partition
({0, 2}, {1, 3, 4})