Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / coloring / equitable_coloring.py @ 5cef0f13

History | View | Annotate | Download (15.3 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2018 by
3
#    Utkarsh Upadhyay <musically.ut@gmail.com>
4
#    All rights reserved.
5
#    BSD license.
6
"""
7
Equitable coloring of graphs with bounded degree.
8
"""
9

    
10
import networkx as nx
11
from collections import defaultdict
12

    
13
__all__ = ['equitable_color']
14

    
15

    
16
def is_coloring(G, coloring):
17
    """Determine if the coloring is a valid coloring for the graph G."""
18
    # Verify that the coloring is valid.
19
    for (s, d) in G.edges:
20
        if coloring[s] == coloring[d]:
21
            return False
22
    return True
23

    
24

    
25
def is_equitable(G, coloring, num_colors=None):
26
    """Determines if the coloring is valid and equitable for the graph G."""
27

    
28
    if not is_coloring(G, coloring):
29
        return False
30

    
31
    # Verify whether it is equitable.
32
    color_set_size = defaultdict(int)
33
    for color in coloring.values():
34
        color_set_size[color] += 1
35

    
36
    if num_colors is not None:
37
        for color in range(num_colors):
38
            if color not in color_set_size:
39
                # These colors do not have any vertices attached to them.
40
                color_set_size[color] = 0
41

    
42
    # If there are more than 2 distinct values, the coloring cannot be equitable
43
    all_set_sizes = set(color_set_size.values())
44
    if len(all_set_sizes) == 0 and num_colors is None:  # Was an empty graph
45
        return True
46
    elif len(all_set_sizes) == 1:
47
        return True
48
    elif len(all_set_sizes) == 2:
49
        a, b = list(all_set_sizes)
50
        return abs(a - b) <= 1
51
    else:   # len(all_set_sizes) > 2:
52
        return False
53

    
54

    
55
def make_C_from_F(F):
56
    C = defaultdict(lambda: [])
57
    for node, color in F.items():
58
        C[color].append(node)
59

    
60
    return C
61

    
62

    
63
def make_N_from_L_C(L, C):
64
    nodes = L.keys()
65
    colors = C.keys()
66
    return {(node, color): sum(1 for v in L[node] if v in C[color])
67
            for node in nodes for color in colors}
68

    
69

    
70
def make_H_from_C_N(C, N):
71
    return {(c1, c2): sum(1 for node in C[c1] if N[(node, c2)] == 0)
72
            for c1 in C.keys() for c2 in C.keys()}
73

    
74

    
75
def change_color(u, X, Y, N, H, F, C, L):
76
    """Change the color of 'u' from X to Y and update N, H, F, C."""
77
    assert F[u] == X and X != Y
78

    
79
    # Change the class of 'u' from X to Y
80
    F[u] = Y
81

    
82
    for k in C.keys():
83
        # 'u' witnesses an edge from k -> Y instead of from k -> X now.
84
        if N[u, k] == 0:
85
            H[(X, k)] -= 1
86
            H[(Y, k)] += 1
87

    
88
    for v in L[u]:
89
        # 'v' has lost a neighbor in X and gained one in Y
90
        N[(v, X)] -= 1
91
        N[(v, Y)] += 1
92

    
93
        if N[(v, X)] == 0:
94
            # 'v' witnesses F[v] -> X
95
            H[(F[v], X)] += 1
96

    
97
        if N[(v, Y)] == 1:
98
            # 'v' no longer witnesses F[v] -> Y
99
            H[(F[v], Y)] -= 1
100

    
101
    C[X].remove(u)
102
    C[Y].append(u)
103

    
104

    
105
def move_witnesses(src_color, dst_color, N, H, F, C, T_cal, L):
106
    """Move witness along a path from src_color to dst_color."""
107
    X = src_color
108
    while X != dst_color:
109
        Y = T_cal[X]
110
        # Move _any_ witness from X to Y = T_cal[X]
111
        w = [x for x in C[X] if N[(x, Y)] == 0][0]
112
        change_color(w, X, Y, N=N, H=H, F=F, C=C, L=L)
113
        X = Y
114

    
115

    
116
def pad_graph(G, num_colors):
117
    """Add a disconnected complete clique K_p such that the number of nodes in
118
    the graph becomes a multiple of `num_colors`.
119

120
    Assumes that the graph's nodes are labelled using integers.
121

122
    Returns the number of nodes with each color.
123
    """
124

    
125
    n_ = len(G)
126
    r = num_colors - 1
127

    
128
    # Ensure that the number of nodes in G is a multiple of (r + 1)
129
    s = n_ // (r + 1)
130
    if n_ != s * (r + 1):
131
        p = (r + 1) - n_ % (r + 1)
132
        s += 1
133

    
134
        # Complete graph K_p between (imaginary) nodes [n_, ... , n_ + p]
135
        K = nx.relabel_nodes(nx.complete_graph(p),
136
                             {idx: idx + n_ for idx in range(p)})
137
        G.add_edges_from(K.edges)
138

    
139
    return s
140

    
141

    
142
def procedure_P(V_minus, V_plus, N, H, F, C, L, excluded_colors=None):
143
    """Procedure P as described in the paper."""
144

    
145
    if excluded_colors is None:
146
        excluded_colors = set()
147

    
148
    A_cal = set()
149
    T_cal = {}
150
    R_cal = []
151

    
152
    # BFS to determine A_cal, i.e. colors reachable from V-
153
    reachable = [V_minus]
154
    marked = set(reachable)
155
    idx = 0
156

    
157
    while idx < len(reachable):
158
        pop = reachable[idx]
159
        idx += 1
160

    
161
        A_cal.add(pop)
162
        R_cal.append(pop)
163

    
164
        # TODO: Checking whether a color has been visited can be made faster by
165
        # using a look-up table instead of testing for membership in a set by a
166
        # logarithmic factor.
167
        next_layer = []
168
        for k in C.keys():
169
            if H[(k, pop)] > 0 and \
170
                    k not in A_cal and \
171
                    k not in excluded_colors and \
172
                    k not in marked:
173
                next_layer.append(k)
174

    
175
        for dst in next_layer:
176
            # Record that `dst` can reach `pop`
177
            T_cal[dst] = pop
178

    
179
        marked.update(next_layer)
180
        reachable.extend(next_layer)
181

    
182
    # Variables for the algorithm
183
    b = (len(C) - len(A_cal))
184

    
185
    if V_plus in A_cal:
186
        # Easy case: V+ is in A_cal
187
        # Move one node from V+ to V- using T_cal to find the parents.
188
        move_witnesses(V_plus, V_minus, N=N, H=H, F=F, C=C, T_cal=T_cal, L=L)
189
    else:
190
        # If there is a solo edge, we can resolve the situation by
191
        # moving witnesses from B to A, making G[A] equitable and then
192
        # recursively balancing G[B - w] with a different V_minus and
193
        # but the same V_plus.
194

    
195
        A_0 = set()
196
        A_cal_0 = set()
197
        num_terminal_sets_found = 0
198
        made_equitable = False
199

    
200
        for W_1 in R_cal[::-1]:
201

    
202
            for v in C[W_1]:
203
                X = None
204

    
205
                for U in C.keys():
206
                    if N[(v, U)] == 0 and U in A_cal and U != W_1:
207
                        X = U
208

    
209
                # v does not witness an edge in H[A_cal]
210
                if X is None:
211
                    continue
212

    
213
                for U in C.keys():
214
                    # Note: Departing from the paper here.
215
                    if N[(v, U)] >= 1 and U not in A_cal:
216
                        X_prime = U
217
                        w = v
218

    
219
                        # Finding the solo neighbor of w in X_prime
220
                        y_candidates = [node for node in L[w]
221
                                        if F[node] == X_prime and N[(node, W_1)] == 1]
222

    
223
                        if len(y_candidates) > 0:
224
                            y = y_candidates[0]
225
                            W = W_1
226

    
227
                            # Move w from W to X, now X has one extra node.
228
                            change_color(w, W, X, N=N, H=H, F=F, C=C, L=L)
229

    
230
                            # Move witness from X to V_minus, making the coloring
231
                            # equitable.
232
                            move_witnesses(src_color=X, dst_color=V_minus,
233
                                           N=N, H=H, F=F, C=C, T_cal=T_cal, L=L)
234

    
235
                            # Move y from X_prime to W, making W the correct size.
236
                            change_color(y, X_prime, W, N=N, H=H, F=F, C=C, L=L)
237

    
238
                            # Then call the procedure on G[B - y]
239
                            procedure_P(V_minus=X_prime, V_plus=V_plus,
240
                                        N=N, H=H, C=C, F=F, L=L,
241
                                        excluded_colors=excluded_colors.union(A_cal))
242
                            made_equitable = True
243
                            break
244

    
245
                if made_equitable:
246
                    break
247
            else:
248
                # No node in W_1 was found such that
249
                # it had a solo-neighbor.
250
                A_cal_0.add(W_1)
251
                A_0.update(C[W_1])
252
                num_terminal_sets_found += 1
253

    
254
            if num_terminal_sets_found == b:
255
                # Otherwise, construct the maximal independent set and find
256
                # a pair of z_1, z_2 as in Case II.
257

    
258
                # BFS to determine B_cal': the set of colors reachable from V+
259
                B_cal_prime = set()
260
                T_cal_prime = {}
261

    
262
                reachable = [V_plus]
263
                marked = set(reachable)
264
                idx = 0
265
                while idx < len(reachable):
266
                    pop = reachable[idx]
267
                    idx += 1
268

    
269
                    B_cal_prime.add(pop)
270

    
271
                    # No need to check for excluded_colors here because
272
                    # they only exclude colors from A_cal
273
                    next_layer = [k for k in C.keys()
274
                                  if H[(pop, k)] > 0 and
275
                                  k not in B_cal_prime and
276
                                  k not in marked]
277

    
278
                    for dst in next_layer:
279
                        T_cal_prime[pop] = dst
280

    
281
                    marked.update(next_layer)
282
                    reachable.extend(next_layer)
283

    
284
                # Construct the independent set of G[B']
285
                I_set = set()
286
                I_covered = set()
287
                W_covering = {}
288

    
289
                B_prime = [node for k in B_cal_prime for node in C[k]]
290

    
291
                # Add the nodes in V_plus to I first.
292
                for z in C[V_plus] + B_prime:
293
                    if z in I_covered or F[z] not in B_cal_prime:
294
                        continue
295

    
296
                    I_set.add(z)
297
                    I_covered.add(z)
298
                    I_covered.update([nbr for nbr in L[z]])
299

    
300
                    for w in L[z]:
301
                        if F[w] in A_cal_0 and N[(z, F[w])] == 1:
302
                            if w not in W_covering:
303
                                W_covering[w] = z
304
                            else:
305
                                # Found z1, z2 which have the same solo
306
                                # neighbor in some W
307
                                z_1 = W_covering[w]
308
                                # z_2 = z
309

    
310
                                Z = F[z_1]
311
                                W = F[w]
312

    
313
                                # shift nodes along W, V-
314
                                move_witnesses(W, V_minus,
315
                                               N=N, H=H, F=F, C=C,
316
                                               T_cal=T_cal, L=L)
317

    
318
                                # shift nodes along V+ to Z
319
                                move_witnesses(V_plus, Z,
320
                                               N=N, H=H, F=F, C=C,
321
                                               T_cal=T_cal_prime, L=L)
322

    
323
                                # change color of z_1 to W
324
                                change_color(z_1, Z, W,
325
                                             N=N, H=H, F=F, C=C, L=L)
326

    
327
                                # change color of w to some color in B_cal
328
                                W_plus = [k for k in C.keys()
329
                                          if N[(w, k)] == 0 and
330
                                          k not in A_cal][0]
331
                                change_color(w, W, W_plus,
332
                                             N=N, H=H, F=F, C=C, L=L)
333

    
334
                                # recurse with G[B \cup W*]
335
                                excluded_colors.update([
336
                                    k for k in C.keys()
337
                                    if k != W and k not in B_cal_prime
338
                                ])
339
                                procedure_P(V_minus=W, V_plus=W_plus,
340
                                            N=N, H=H, C=C, F=F, L=L,
341
                                            excluded_colors=excluded_colors)
342

    
343
                                made_equitable = True
344
                                break
345

    
346
                    if made_equitable:
347
                        break
348
                else:
349
                    assert False, "Must find a w which is the solo neighbor " \
350
                                  "of two vertices in B_cal_prime."
351

    
352
            if made_equitable:
353
                break
354

    
355

    
356
def equitable_color(G, num_colors):
357
    """Provides equitable (r + 1)-coloring for nodes of G in O(r * n^2) time
358
     if deg(G) <= r. The algorithm is described in [1]_.
359

360
     Attempts to color a graph using r colors, where no neighbors of a node
361
     can have same color as the node itself and the number of nodes with each
362
     color differ by at most 1.
363

364
     Parameters
365
     ----------
366
     G : networkX graph
367
        The nodes of this graph will be colored.
368

369
     num_colors : number of colors to use
370
        This number must be at least one more than the maximum degree of nodes
371
        in the graph.
372

373
     Returns
374
     -------
375
     A dictionary with keys representing nodes and values representing
376
     corresponding coloring.
377

378
     Examples
379
     --------
380
     >>> G = nx.cycle_graph(4)
381
     >>> d = nx.coloring.equitable_color(G, num_colors=3)
382
     >>> nx.algorithms.coloring.equitable_coloring.is_equitable(G, d)
383
     True
384

385
     Raises
386
     ------
387
     NetworkXAlgorithmError
388
         If the maximum degree of the graph ``G`` is greater than
389
         ``num_colors``.
390

391
     References
392
     ----------
393
     .. [1] Kierstead, H. A., Kostochka, A. V., Mydlarz, M., & Szemer├ędi, E.
394
         (2010). A fast algorithm for equitable coloring. Combinatorica, 30(2),
395
         217-224.
396
    """
397

    
398
    # Map nodes to integers for simplicity later.
399
    nodes_to_int = {}
400
    int_to_nodes = {}
401

    
402
    for idx, node in enumerate(G.nodes):
403
        nodes_to_int[node] = idx
404
        int_to_nodes[idx] = node
405

    
406
    G = nx.relabel_nodes(G, nodes_to_int, copy=True)
407

    
408
    # Basic graph statistics and sanity check.
409
    if len(G.nodes) > 0:
410
        r_ = max([G.degree(node) for node in G.nodes])
411
    else:
412
        r_ = 0
413

    
414
    if r_ >= num_colors:
415
        raise nx.NetworkXAlgorithmError(
416
            'Graph has maximum degree {}, needs {} (> {}) colors for guaranteed coloring.'
417
            .format(r_, r_ + 1, num_colors)
418
        )
419

    
420
    # Ensure that the number of nodes in G is a multiple of (r + 1)
421
    pad_graph(G, num_colors)
422

    
423
    # Starting the algorithm.
424
    # L = {node: list(G.neighbors(node)) for node in G.nodes}
425
    L_ = {node: [] for node in G.nodes}
426

    
427
    # Arbitrary equitable allocation of colors to nodes.
428
    F = {node: idx % num_colors for idx, node in enumerate(G.nodes)}
429

    
430
    C = make_C_from_F(F)
431

    
432
    # The neighborhood is empty initially.
433
    N = make_N_from_L_C(L_, C)
434

    
435
    # Currently all nodes witness all edges.
436
    H = make_H_from_C_N(C, N)
437

    
438
    # Start of algorithm.
439
    edges_seen = set()
440

    
441
    for u in sorted(G.nodes):
442
        for v in sorted(G.neighbors(u)):
443

    
444
            # Do not double count edges if (v, u) has already been seen.
445
            if (v, u) in edges_seen:
446
                continue
447

    
448
            edges_seen.add((u, v))
449

    
450
            L_[u].append(v)
451
            L_[v].append(u)
452

    
453
            N[(u, F[v])] += 1
454
            N[(v, F[u])] += 1
455

    
456
            if F[u] != F[v]:
457
                # Were 'u' and 'v' witnesses for F[u] -> F[v] or F[v] -> F[u]?
458
                if N[(u, F[v])] == 1:
459
                    H[F[u], F[v]] -= 1  # u cannot witness an edge between F[u], F[v]
460

    
461
                if N[(v, F[u])] == 1:
462
                    H[F[v], F[u]] -= 1  # v cannot witness an edge between F[v], F[u]
463

    
464
        if N[(u, F[u])] != 0:
465
            # Find the first color where 'u' does not have any neighbors.
466
            Y = [k for k in C.keys() if N[(u, k)] == 0][0]
467
            X = F[u]
468
            change_color(u, X, Y, N=N, H=H, F=F, C=C, L=L_)
469

    
470
            # Procedure P
471
            procedure_P(V_minus=X, V_plus=Y,
472
                        N=N, H=H, F=F, C=C, L=L_)
473

    
474
    return {int_to_nodes[x]: F[x] for x in int_to_nodes}