|
|
"""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 |
|
|
|
