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