Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / community / kernighan_lin.py @ 5cef0f13

History | View | Annotate | Download (5.44 KB)

1
# -*- coding: utf-8 -*-
2
#
3
# kernighan_lin.py - Kernighan–Lin bipartition algorithm
4
#
5
# Copyright 2011 Ben Edwards <bedwards@cs.unm.edu>.
6
# Copyright 2011 Aric Hagberg <hagberg@lanl.gov>.
7
# Copyright 2015 NetworkX developers.
8
#
9
# This file is part of NetworkX.
10
#
11
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
12
# information.
13
"""Functions for computing the Kernighan–Lin bipartition algorithm."""
14
from __future__ import division
15

    
16
from collections import defaultdict
17
from itertools import islice
18
from operator import itemgetter
19

    
20
import networkx as nx
21
from networkx.utils import not_implemented_for, py_random_state
22
from networkx.algorithms.community.community_utils import is_partition
23

    
24
__all__ = ['kernighan_lin_bisection']
25

    
26

    
27
def _compute_delta(G, A, B, weight):
28
    # helper to compute initial swap deltas for a pass
29
    delta = defaultdict(float)
30
    for u, v, d in G.edges(data=True):
31
        w = d.get(weight, 1)
32
        if u in A:
33
            if v in A:
34
                delta[u] -= w
35
                delta[v] -= w
36
            elif v in B:
37
                delta[u] += w
38
                delta[v] += w
39
        elif u in B:
40
            if v in A:
41
                delta[u] += w
42
                delta[v] += w
43
            elif v in B:
44
                delta[u] -= w
45
                delta[v] -= w
46
    return delta
47

    
48

    
49
def _update_delta(delta, G, A, B, u, v, weight):
50
    # helper to update swap deltas during single pass
51
    for _, nbr, d in G.edges(u, data=True):
52
        w = d.get(weight, 1)
53
        if nbr in A:
54
            delta[nbr] += 2 * w
55
        if nbr in B:
56
            delta[nbr] -= 2 * w
57
    for _, nbr, d in G.edges(v, data=True):
58
        w = d.get(weight, 1)
59
        if nbr in A:
60
            delta[nbr] -= 2 * w
61
        if nbr in B:
62
            delta[nbr] += 2 * w
63
    return delta
64

    
65

    
66
def _kernighan_lin_pass(G, A, B, weight):
67
    # do a single iteration of Kernighan–Lin algorithm
68
    # returns list of  (g_i,u_i,v_i) for i node pairs u_i,v_i
69
    multigraph = G.is_multigraph()
70
    delta = _compute_delta(G, A, B, weight)
71
    swapped = set()
72
    gains = []
73
    while len(swapped) < len(G):
74
        gain = []
75
        for u in A - swapped:
76
            for v in B - swapped:
77
                try:
78
                    if multigraph:
79
                        w = sum(d.get(weight, 1) for d in G[u][v].values())
80
                    else:
81
                        w = G[u][v].get(weight, 1)
82
                except KeyError:
83
                    w = 0
84
                gain.append((delta[u] + delta[v] - 2 * w, u, v))
85
        if len(gain) == 0:
86
            break
87
        maxg, u, v = max(gain, key=itemgetter(0))
88
        swapped |= {u, v}
89
        gains.append((maxg, u, v))
90
        delta = _update_delta(delta, G, A - swapped, B - swapped, u, v, weight)
91
    return gains
92

    
93

    
94
@py_random_state(4)
95
@not_implemented_for('directed')
96
def kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight',
97
                            seed=None):
98
    """Partition a graph into two blocks using the Kernighan–Lin
99
    algorithm.
100

101
    This algorithm paritions a network into two sets by iteratively
102
    swapping pairs of nodes to reduce the edge cut between the two sets.
103

104
    Parameters
105
    ----------
106
    G : graph
107

108
    partition : tuple
109
        Pair of iterables containing an initial partition. If not
110
        specified, a random balanced partition is used.
111

112
    max_iter : int
113
        Maximum number of times to attempt swaps to find an
114
        improvemement before giving up.
115

116
    weight : key
117
        Edge data key to use as weight. If None, the weights are all
118
        set to one.
119

120
    seed : integer, random_state, or None (default)
121
        Indicator of random number generation state.
122
        See :ref:`Randomness<randomness>`.
123
        Only used if partition is None
124

125
    Returns
126
    -------
127
    partition : tuple
128
        A pair of sets of nodes representing the bipartition.
129

130
    Raises
131
    -------
132
    NetworkXError
133
        If partition is not a valid partition of the nodes of the graph.
134

135
    References
136
    ----------
137
    .. [1] Kernighan, B. W.; Lin, Shen (1970).
138
       "An efficient heuristic procedure for partitioning graphs."
139
       *Bell Systems Technical Journal* 49: 291--307.
140
       Oxford University Press 2011.
141

142
    """
143
    # If no partition is provided, split the nodes randomly into a
144
    # balanced partition.
145
    if partition is None:
146
        nodes = list(G)
147
        seed.shuffle(nodes)
148
        h = len(nodes) // 2
149
        partition = (nodes[:h], nodes[h:])
150
    # Make a copy of the partition as a pair of sets.
151
    try:
152
        A, B = set(partition[0]), set(partition[1])
153
    except:
154
        raise ValueError('partition must be two sets')
155
    if not is_partition(G, (A, B)):
156
        raise nx.NetworkXError('partition invalid')
157
    for i in range(max_iter):
158
        # `gains` is a list of triples of the form (g, u, v) for each
159
        # node pair (u, v), where `g` is the gain of that node pair.
160
        gains = _kernighan_lin_pass(G, A, B, weight)
161
        csum = list(nx.utils.accumulate(g for g, u, v in gains))
162
        max_cgain = max(csum)
163
        if max_cgain <= 0:
164
            break
165
        # Get the node pairs up to the index of the maximum cumulative
166
        # gain, and collect each `u` into `anodes` and each `v` into
167
        # `bnodes`, for each pair `(u, v)`.
168
        index = csum.index(max_cgain)
169
        nodesets = islice(zip(*gains[:index + 1]), 1, 3)
170
        anodes, bnodes = (set(s) for s in nodesets)
171
        A |= bnodes
172
        A -= anodes
173
        B |= anodes
174
        B -= bnodes
175
    return A, B