1import networkx as nx 2from networkx.utils.decorators import py_random_state, not_implemented_for 3 4__all__ = ["randomized_partitioning", "one_exchange"] 5 6 7@not_implemented_for("directed", "multigraph") 8@py_random_state(1) 9def randomized_partitioning(G, seed=None, p=0.5, weight=None): 10 """Compute a random partitioning of the graph nodes and its cut value. 11 12 A partitioning is calculated by observing each node 13 and deciding to add it to the partition with probability `p`, 14 returning a random cut and its corresponding value (the 15 sum of weights of edges connecting different partitions). 16 17 Parameters 18 ---------- 19 G : NetworkX graph 20 21 seed : integer, random_state, or None (default) 22 Indicator of random number generation state. 23 See :ref:`Randomness<randomness>`. 24 25 p : scalar 26 Probability for each node to be part of the first partition. 27 Should be in [0,1] 28 29 weight : object 30 Edge attribute key to use as weight. If not specified, edges 31 have weight one. 32 33 Returns 34 ------- 35 cut_size : scalar 36 Value of the minimum cut. 37 38 partition : pair of node sets 39 A partitioning of the nodes that defines a minimum cut. 40 """ 41 cut = {node for node in G.nodes() if seed.random() < p} 42 cut_size = nx.algorithms.cut_size(G, cut, weight=weight) 43 partition = (cut, G.nodes - cut) 44 return cut_size, partition 45 46 47def _swap_node_partition(cut, node): 48 return cut - {node} if node in cut else cut.union({node}) 49 50 51@not_implemented_for("directed", "multigraph") 52@py_random_state(2) 53def one_exchange(G, initial_cut=None, seed=None, weight=None): 54 """Compute a partitioning of the graphs nodes and the corresponding cut value. 55 56 Use a greedy one exchange strategy to find a locally maximal cut 57 and its value, it works by finding the best node (one that gives 58 the highest gain to the cut value) to add to the current cut 59 and repeats this process until no improvement can be made. 60 61 Parameters 62 ---------- 63 G : networkx Graph 64 Graph to find a maximum cut for. 65 66 initial_cut : set 67 Cut to use as a starting point. If not supplied the algorithm 68 starts with an empty cut. 69 70 seed : integer, random_state, or None (default) 71 Indicator of random number generation state. 72 See :ref:`Randomness<randomness>`. 73 74 weight : object 75 Edge attribute key to use as weight. If not specified, edges 76 have weight one. 77 78 Returns 79 ------- 80 cut_value : scalar 81 Value of the maximum cut. 82 83 partition : pair of node sets 84 A partitioning of the nodes that defines a maximum cut. 85 """ 86 if initial_cut is None: 87 initial_cut = set() 88 cut = set(initial_cut) 89 current_cut_size = nx.algorithms.cut_size(G, cut, weight=weight) 90 while True: 91 nodes = list(G.nodes()) 92 # Shuffling the nodes ensures random tie-breaks in the following call to max 93 seed.shuffle(nodes) 94 best_node_to_swap = max( 95 nodes, 96 key=lambda v: nx.algorithms.cut_size( 97 G, _swap_node_partition(cut, v), weight=weight 98 ), 99 default=None, 100 ) 101 potential_cut = _swap_node_partition(cut, best_node_to_swap) 102 potential_cut_size = nx.algorithms.cut_size(G, potential_cut, weight=weight) 103 104 if potential_cut_size > current_cut_size: 105 cut = potential_cut 106 current_cut_size = potential_cut_size 107 else: 108 break 109 110 partition = (cut, G.nodes - cut) 111 return current_cut_size, partition 112