wgddlZddlmZmZddgZedededej d dd Zd Zededed ej d dd Z y)N)not_implemented_forpy_random_staterandomized_partitioning one_exchangedirected multigraphweight) edge_attrsc|jDchc]}|j|ks|}}tjj |||}||j|z f}||fScc}w)aCompute a random partitioning of the graph nodes and its cut value. A partitioning is calculated by observing each node and deciding to add it to the partition with probability `p`, returning a random cut and its corresponding value (the sum of weights of edges connecting different partitions). Parameters ---------- G : NetworkX graph seed : integer, random_state, or None (default) Indicator of random number generation state. See :ref:`Randomness`. p : scalar Probability for each node to be part of the first partition. Should be in [0,1] weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- cut_size : scalar Value of the minimum cut. partition : pair of node sets A partitioning of the nodes that defines a minimum cut. Examples -------- >>> G = nx.complete_graph(5) >>> cut_size, partition = nx.approximation.randomized_partitioning(G, seed=1) >>> cut_size 6 >>> partition ({0, 3, 4}, {1, 2}) Raises ------ NetworkXNotImplemented If the graph is directed or is a multigraph. r )nodesrandomnx algorithmscut_size)Gseedpr nodecutr partitions m/home/mcse/projects/flask/flask-venv/lib/python3.12/site-packages/networkx/algorithms/approximation/maxcut.pyrrshdGGI ;D):4 ;C ;}}%%aV%`. 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. 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}) Raises ------ NetworkXNotImplemented If the graph is directed or is a multigraph. Nr c\tjjt|S)Nr )rrrr)vrrr s rzone_exchange..s*"--00'Q/1r)keydefault) setrrrlistrshufflemaxr) r initial_cutrr current_cut_sizerbest_node_to_swap potential_cutpotential_cut_sizerrs ` ` @rrrCsfe k C}}--aV-D QWWY U   -S2CD ]]33A}V3T  0 0C1  % (aggm$I Y &&r)Ng?N)NNN) networkxrnetworkx.utils.decoratorsrr__all__ _dispatchablerrrrrr3sJ $n 5Z \"X&1'#!1h>Z \"X&H''#!H'r