## Mercurial > repos > shellac > sam_consensus_v3

### view env/lib/python3.9/site-packages/networkx/algorithms/community/kernighan_lin.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

"""Functions for computing the Kernighanâ€“Lin bipartition algorithm.""" import networkx as nx from itertools import count from networkx.utils import not_implemented_for, py_random_state, BinaryHeap from networkx.algorithms.community.community_utils import is_partition __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 = 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 yield totcost, i, (u, v) @py_random_state(4) @not_implemented_for("directed") 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, which moves node individually, alternating between sides to keep the bisection balanced. Parameters ---------- G : graph 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 improvemement 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 e: raise nx.NetworkXError("partition must be two sets") from e if not is_partition(G, (A, B)): raise nx.NetworkXError("partition invalid") side = [0] * n for a in A: side[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 + 1]: 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