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.
- 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})