Skip to main content
`Ctrl`+`K`

# 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:
    G networkx Graph

      Graph to find a maximum cut for.

    initial_cut set

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

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

    weight object

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

  Returns:
    cut_value scalar

      Value of the maximum cut.

    partition pair 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})