Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/community/kernighan_lin.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for computing the Kernighan–Lin bipartition algorithm.""" | |
2 | |
3 import networkx as nx | |
4 from itertools import count | |
5 from networkx.utils import not_implemented_for, py_random_state, BinaryHeap | |
6 from networkx.algorithms.community.community_utils import is_partition | |
7 | |
8 __all__ = ["kernighan_lin_bisection"] | |
9 | |
10 | |
11 def _kernighan_lin_sweep(edges, side): | |
12 """ | |
13 This is a modified form of Kernighan-Lin, which moves single nodes at a | |
14 time, alternating between sides to keep the bisection balanced. We keep | |
15 two min-heaps of swap costs to make optimal-next-move selection fast. | |
16 """ | |
17 costs0, costs1 = costs = BinaryHeap(), BinaryHeap() | |
18 for u, side_u, edges_u in zip(count(), side, edges): | |
19 cost_u = sum(w if side[v] else -w for v, w in edges_u) | |
20 costs[side_u].insert(u, cost_u if side_u else -cost_u) | |
21 | |
22 def _update_costs(costs_x, x): | |
23 for y, w in edges[x]: | |
24 costs_y = costs[side[y]] | |
25 cost_y = costs_y.get(y) | |
26 if cost_y is not None: | |
27 cost_y += 2 * (-w if costs_x is costs_y else w) | |
28 costs_y.insert(y, cost_y, True) | |
29 | |
30 i = totcost = 0 | |
31 while costs0 and costs1: | |
32 u, cost_u = costs0.pop() | |
33 _update_costs(costs0, u) | |
34 v, cost_v = costs1.pop() | |
35 _update_costs(costs1, v) | |
36 totcost += cost_u + cost_v | |
37 yield totcost, i, (u, v) | |
38 | |
39 | |
40 @py_random_state(4) | |
41 @not_implemented_for("directed") | |
42 def kernighan_lin_bisection(G, partition=None, max_iter=10, weight="weight", seed=None): | |
43 """Partition a graph into two blocks using the Kernighan–Lin | |
44 algorithm. | |
45 | |
46 This algorithm partitions a network into two sets by iteratively | |
47 swapping pairs of nodes to reduce the edge cut between the two sets. The | |
48 pairs are chosen according to a modified form of Kernighan-Lin, which | |
49 moves node individually, alternating between sides to keep the bisection | |
50 balanced. | |
51 | |
52 Parameters | |
53 ---------- | |
54 G : graph | |
55 | |
56 partition : tuple | |
57 Pair of iterables containing an initial partition. If not | |
58 specified, a random balanced partition is used. | |
59 | |
60 max_iter : int | |
61 Maximum number of times to attempt swaps to find an | |
62 improvemement before giving up. | |
63 | |
64 weight : key | |
65 Edge data key to use as weight. If None, the weights are all | |
66 set to one. | |
67 | |
68 seed : integer, random_state, or None (default) | |
69 Indicator of random number generation state. | |
70 See :ref:`Randomness<randomness>`. | |
71 Only used if partition is None | |
72 | |
73 Returns | |
74 ------- | |
75 partition : tuple | |
76 A pair of sets of nodes representing the bipartition. | |
77 | |
78 Raises | |
79 ------- | |
80 NetworkXError | |
81 If partition is not a valid partition of the nodes of the graph. | |
82 | |
83 References | |
84 ---------- | |
85 .. [1] Kernighan, B. W.; Lin, Shen (1970). | |
86 "An efficient heuristic procedure for partitioning graphs." | |
87 *Bell Systems Technical Journal* 49: 291--307. | |
88 Oxford University Press 2011. | |
89 | |
90 """ | |
91 n = len(G) | |
92 labels = list(G) | |
93 seed.shuffle(labels) | |
94 index = {v: i for i, v in enumerate(labels)} | |
95 | |
96 if partition is None: | |
97 side = [0] * (n // 2) + [1] * ((n + 1) // 2) | |
98 else: | |
99 try: | |
100 A, B = partition | |
101 except (TypeError, ValueError) as e: | |
102 raise nx.NetworkXError("partition must be two sets") from e | |
103 if not is_partition(G, (A, B)): | |
104 raise nx.NetworkXError("partition invalid") | |
105 side = [0] * n | |
106 for a in A: | |
107 side[a] = 1 | |
108 | |
109 if G.is_multigraph(): | |
110 edges = [ | |
111 [ | |
112 (index[u], sum(e.get(weight, 1) for e in d.values())) | |
113 for u, d in G[v].items() | |
114 ] | |
115 for v in labels | |
116 ] | |
117 else: | |
118 edges = [ | |
119 [(index[u], e.get(weight, 1)) for u, e in G[v].items()] for v in labels | |
120 ] | |
121 | |
122 for i in range(max_iter): | |
123 costs = list(_kernighan_lin_sweep(edges, side)) | |
124 min_cost, min_i, _ = min(costs) | |
125 if min_cost >= 0: | |
126 break | |
127 | |
128 for _, _, (u, v) in costs[: min_i + 1]: | |
129 side[u] = 1 | |
130 side[v] = 0 | |
131 | |
132 A = {u for u, s in zip(labels, side) if s == 0} | |
133 B = {u for u, s in zip(labels, side) if s == 1} | |
134 return A, B |