Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/maxcut.py: 38%

1import networkx as nx 

2from networkx.utils.decorators import not_implemented_for, py_random_state 

3 

4__all__ = ["randomized_partitioning", "one_exchange"] 

5 

6 

7@not_implemented_for("directed", "multigraph") 

8@py_random_state(1) 

9@nx._dispatch(edge_attrs="weight") 

10def randomized_partitioning(G, seed=None, p=0.5, weight=None): 

11 """Compute a random partitioning of the graph nodes and its cut value. 

12 

13 A partitioning is calculated by observing each node 

14 and deciding to add it to the partition with probability `p`, 

15 returning a random cut and its corresponding value (the 

16 sum of weights of edges connecting different partitions). 

17 

18 Parameters 

19 ---------- 

20 G : NetworkX graph 

21 

22 seed : integer, random_state, or None (default) 

23 Indicator of random number generation state. 

24 See :ref:`Randomness<randomness>`. 

25 

26 p : scalar 

27 Probability for each node to be part of the first partition. 

28 Should be in [0,1] 

29 

30 weight : object 

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

32 have weight one. 

33 

34 Returns 

35 ------- 

36 cut_size : scalar 

37 Value of the minimum cut. 

38 

39 partition : pair of node sets 

40 A partitioning of the nodes that defines a minimum cut. 

41 """ 

42 cut = {node for node in G.nodes() if seed.random() < p} 

43 cut_size = nx.algorithms.cut_size(G, cut, weight=weight) 

44 partition = (cut, G.nodes - cut) 

45 return cut_size, partition 

46 

47 

48def _swap_node_partition(cut, node): 

49 return cut - {node} if node in cut else cut.union({node}) 

50 

51 

52@not_implemented_for("directed", "multigraph") 

53@py_random_state(2) 

54@nx._dispatch(edge_attrs="weight") 

55def one_exchange(G, initial_cut=None, seed=None, weight=None): 

56 """Compute a partitioning of the graphs nodes and the corresponding cut value. 

57 

58 Use a greedy one exchange strategy to find a locally maximal cut 

59 and its value, it works by finding the best node (one that gives 

60 the highest gain to the cut value) to add to the current cut 

61 and repeats this process until no improvement can be made. 

62 

63 Parameters 

64 ---------- 

65 G : networkx Graph 

66 Graph to find a maximum cut for. 

67 

68 initial_cut : set 

69 Cut to use as a starting point. If not supplied the algorithm 

70 starts with an empty cut. 

71 

72 seed : integer, random_state, or None (default) 

73 Indicator of random number generation state. 

74 See :ref:`Randomness<randomness>`. 

75 

76 weight : object 

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

78 have weight one. 

79 

80 Returns 

81 ------- 

82 cut_value : scalar 

83 Value of the maximum cut. 

84 

85 partition : pair of node sets 

86 A partitioning of the nodes that defines a maximum cut. 

87 """ 

88 if initial_cut is None: 

89 initial_cut = set() 

90 cut = set(initial_cut) 

91 current_cut_size = nx.algorithms.cut_size(G, cut, weight=weight) 

92 while True: 

93 nodes = list(G.nodes()) 

94 # Shuffling the nodes ensures random tie-breaks in the following call to max 

95 seed.shuffle(nodes) 

96 best_node_to_swap = max( 

97 nodes, 

98 key=lambda v: nx.algorithms.cut_size( 

99 G, _swap_node_partition(cut, v), weight=weight 

100 ), 

101 default=None, 

102 ) 

103 potential_cut = _swap_node_partition(cut, best_node_to_swap) 

104 potential_cut_size = nx.algorithms.cut_size(G, potential_cut, weight=weight) 

105 

106 if potential_cut_size > current_cut_size: 

107 cut = potential_cut 

108 current_cut_size = potential_cut_size 

109 else: 

110 break 

111 

112 partition = (cut, G.nodes - cut) 

113 return current_cut_size, partition