Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/community/kernighan_lin.py: 17%

1"""Functions for computing the Kernighan–Lin bipartition algorithm.""" 

2 

3from itertools import count 

4 

5import networkx as nx 

6from networkx.algorithms.community.community_utils import is_partition 

7from networkx.utils import BinaryHeap, not_implemented_for, py_random_state 

8 

9__all__ = ["kernighan_lin_bisection"] 

10 

11 

12def _kernighan_lin_sweep(edges, side): 

13 """ 

14 This is a modified form of Kernighan-Lin, which moves single nodes at a 

15 time, alternating between sides to keep the bisection balanced. We keep 

16 two min-heaps of swap costs to make optimal-next-move selection fast. 

17 """ 

18 costs0, costs1 = costs = BinaryHeap(), BinaryHeap() 

19 for u, side_u, edges_u in zip(count(), side, edges): 

20 cost_u = sum(w if side[v] else -w for v, w in edges_u) 

21 costs[side_u].insert(u, cost_u if side_u else -cost_u) 

22 

23 def _update_costs(costs_x, x): 

24 for y, w in edges[x]: 

25 costs_y = costs[side[y]] 

26 cost_y = costs_y.get(y) 

27 if cost_y is not None: 

28 cost_y += 2 * (-w if costs_x is costs_y else w) 

29 costs_y.insert(y, cost_y, True) 

30 

31 i = 0 

32 totcost = 0 

33 while costs0 and costs1: 

34 u, cost_u = costs0.pop() 

35 _update_costs(costs0, u) 

36 v, cost_v = costs1.pop() 

37 _update_costs(costs1, v) 

38 totcost += cost_u + cost_v 

39 i += 1 

40 yield totcost, i, (u, v) 

41 

42 

43@not_implemented_for("directed") 

44@py_random_state(4) 

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

46def kernighan_lin_bisection(G, partition=None, max_iter=10, weight="weight", seed=None): 

47 """Partition a graph into two blocks using the Kernighan–Lin 

48 algorithm. 

49 

50 This algorithm partitions a network into two sets by iteratively 

51 swapping pairs of nodes to reduce the edge cut between the two sets. The 

52 pairs are chosen according to a modified form of Kernighan-Lin [1]_, which 

53 moves node individually, alternating between sides to keep the bisection 

54 balanced. 

55 

56 Parameters 

57 ---------- 

58 G : NetworkX graph 

59 Graph must be undirected. 

60 

61 partition : tuple 

62 Pair of iterables containing an initial partition. If not 

63 specified, a random balanced partition is used. 

64 

65 max_iter : int 

66 Maximum number of times to attempt swaps to find an 

67 improvement before giving up. 

68 

69 weight : key 

70 Edge data key to use as weight. If None, the weights are all 

71 set to one. 

72 

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

74 Indicator of random number generation state. 

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

76 Only used if partition is None 

77 

78 Returns 

79 ------- 

80 partition : tuple 

81 A pair of sets of nodes representing the bipartition. 

82 

83 Raises 

84 ------ 

85 NetworkXError 

86 If partition is not a valid partition of the nodes of the graph. 

87 

88 References 

89 ---------- 

90 .. [1] Kernighan, B. W.; Lin, Shen (1970). 

91 "An efficient heuristic procedure for partitioning graphs." 

92 *Bell Systems Technical Journal* 49: 291--307. 

93 Oxford University Press 2011. 

94 

95 """ 

96 n = len(G) 

97 labels = list(G) 

98 seed.shuffle(labels) 

99 index = {v: i for i, v in enumerate(labels)} 

100 

101 if partition is None: 

102 side = [0] * (n // 2) + [1] * ((n + 1) // 2) 

103 else: 

104 try: 

105 A, B = partition 

106 except (TypeError, ValueError) as err: 

107 raise nx.NetworkXError("partition must be two sets") from err 

108 if not is_partition(G, (A, B)): 

109 raise nx.NetworkXError("partition invalid") 

110 side = [0] * n 

111 for a in A: 

112 side[index[a]] = 1 

113 

114 if G.is_multigraph(): 

115 edges = [ 

116 [ 

117 (index[u], sum(e.get(weight, 1) for e in d.values())) 

118 for u, d in G[v].items() 

119 ] 

120 for v in labels 

121 ] 

122 else: 

123 edges = [ 

124 [(index[u], e.get(weight, 1)) for u, e in G[v].items()] for v in labels 

125 ] 

126 

127 for i in range(max_iter): 

128 costs = list(_kernighan_lin_sweep(edges, side)) 

129 min_cost, min_i, _ = min(costs) 

130 if min_cost >= 0: 

131 break 

132 

133 for _, _, (u, v) in costs[:min_i]: 

134 side[u] = 1 

135 side[v] = 0 

136 

137 A = {u for u, s in zip(labels, side) if s == 0} 

138 B = {u for u, s in zip(labels, side) if s == 1} 

139 return A, B