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

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/community/kernighan_lin.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,134 @@
+"""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