Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (18.5 KB)

1
# -*- coding: utf-8 -*-
2
"""Greedy coloring test suite.
3

4
Run with nose: nosetests -v test_coloring.py
5
"""
6

    
7
__author__ = "\n".join(["Christian Olsson <chro@itu.dk>",
8
                        "Jan Aagaard Meier <jmei@itu.dk>",
9
                        "Henrik Haugbølle <hhau@itu.dk>",
10
                        "Jake VanderPlas <jakevdp@uw.edu>"])
11

    
12
import networkx as nx
13
from nose.tools import *
14

    
15

    
16
is_coloring = nx.algorithms.coloring.equitable_coloring.is_coloring
17
is_equitable = nx.algorithms.coloring.equitable_coloring.is_equitable
18

    
19

    
20
ALL_STRATEGIES = [
21
    'largest_first',
22
    'random_sequential',
23
    'smallest_last',
24
    'independent_set',
25
    'connected_sequential_bfs',
26
    'connected_sequential_dfs',
27
    'connected_sequential',
28
    'saturation_largest_first',
29
    'DSATUR',
30
]
31

    
32
# List of strategies where interchange=True results in an error
33
INTERCHANGE_INVALID = [
34
    'independent_set',
35
    'saturation_largest_first',
36
    'DSATUR'
37
]
38

    
39

    
40
class TestColoring:
41
    def test_basic_cases(self):
42
        def check_basic_case(graph_func, n_nodes, strategy, interchange):
43
            graph = graph_func()
44
            coloring = nx.coloring.greedy_color(graph,
45
                                                strategy=strategy,
46
                                                interchange=interchange)
47
            assert_true(verify_length(coloring, n_nodes))
48
            assert_true(verify_coloring(graph, coloring))
49

    
50
        for graph_func, n_nodes in BASIC_TEST_CASES.items():
51
            for interchange in [True, False]:
52
                for strategy in ALL_STRATEGIES:
53
                    if interchange and (strategy in INTERCHANGE_INVALID):
54
                        continue
55
                    yield (check_basic_case, graph_func,
56
                           n_nodes, strategy, interchange)
57

    
58
    def test_special_cases(self):
59
        def check_special_case(strategy, graph_func, interchange, colors):
60
            graph = graph_func()
61
            coloring = nx.coloring.greedy_color(graph,
62
                                                strategy=strategy,
63
                                                interchange=interchange)
64
            if not hasattr(colors, '__len__'):
65
                colors = [colors]
66
            assert_true(any(verify_length(coloring, n_colors)
67
                            for n_colors in colors))
68
            assert_true(verify_coloring(graph, coloring))
69

    
70
        for strategy, arglist in SPECIAL_TEST_CASES.items():
71
            for args in arglist:
72
                yield (check_special_case, strategy, args[0], args[1], args[2])
73

    
74
    def test_interchange_invalid(self):
75
        graph = one_node_graph()
76

    
77
        def check_raises(strategy):
78
            assert_raises(nx.NetworkXPointlessConcept,
79
                          nx.coloring.greedy_color,
80
                          graph, strategy=strategy, interchange=True)
81

    
82
        for strategy in INTERCHANGE_INVALID:
83
            yield check_raises, strategy
84

    
85
    def test_bad_inputs(self):
86
        graph = one_node_graph()
87
        assert_raises(nx.NetworkXError, nx.coloring.greedy_color,
88
                      graph, strategy='invalid strategy')
89

    
90
    def test_strategy_as_function(self):
91
        graph = lf_shc()
92
        colors_1 = nx.coloring.greedy_color(graph,
93
                                            'largest_first')
94
        colors_2 = nx.coloring.greedy_color(graph,
95
                                            nx.coloring.strategy_largest_first)
96
        assert_equal(colors_1, colors_2)
97

    
98
    def test_seed_argument(self):
99
        graph = lf_shc()
100
        rs = nx.coloring.strategy_random_sequential
101
        c1 = nx.coloring.greedy_color(graph,lambda g, c: rs(g, c, seed=1))
102
        for u, v in graph.edges:
103
            assert_not_equal(c1[u], c1[v])
104

    
105
    def test_is_coloring(self):
106
        G = nx.Graph()
107
        G.add_edges_from([(0, 1), (1, 2)])
108
        coloring = {0: 0, 1: 1, 2: 0}
109
        assert is_coloring(G, coloring)
110

    
111
        coloring[0] = 1
112
        assert not is_coloring(G, coloring)
113
        assert not is_equitable(G, coloring)
114

    
115
    def test_is_equitable(self):
116
        G = nx.Graph()
117
        G.add_edges_from([(0, 1), (1, 2)])
118
        coloring = {0: 0, 1: 1, 2: 0}
119
        assert is_equitable(G, coloring)
120

    
121
        G.add_edges_from([(2, 3), (2, 4), (2, 5)])
122
        coloring[3] = 1
123
        coloring[4] = 1
124
        coloring[5] = 1
125
        assert is_coloring(G, coloring)
126
        assert not is_equitable(G, coloring)
127

    
128
    def test_num_colors(self):
129
        G = nx.Graph()
130
        G.add_edges_from([(0, 1), (0, 2), (0, 3)])
131
        assert_raises(nx.NetworkXAlgorithmError,
132
                      nx.coloring.equitable_color, G, 2)
133

    
134
    def test_equitable_color(self):
135
        G = nx.fast_gnp_random_graph(n=10, p=0.2, seed=42)
136
        coloring = nx.coloring.equitable_color(G, max_degree(G) + 1)
137
        assert is_equitable(G, coloring)
138

    
139
    def test_equitable_color_empty(self):
140
        G = nx.empty_graph()
141
        coloring = nx.coloring.equitable_color(G, max_degree(G) + 1)
142
        assert is_equitable(G, coloring)
143

    
144
    def test_equitable_color_large(self):
145
        G = nx.fast_gnp_random_graph(100, 0.1, seed=42)
146
        coloring = nx.coloring.equitable_color(G, max_degree(G) + 1)
147
        assert is_equitable(G, coloring, num_colors=max_degree(G) + 1)
148

    
149
    def test_case_V_plus_not_in_A_cal(self):
150
        # Hand crafted case to avoid the easy case.
151
        L = {
152
            0: [2, 5],
153
            1: [3, 4],
154
            2: [0, 8],
155
            3: [1, 7],
156
            4: [1, 6],
157
            5: [0, 6],
158
            6: [4, 5],
159
            7: [3],
160
            8: [2],
161
        }
162

    
163
        F = {
164
            # Color 0
165
            0: 0,
166
            1: 0,
167

    
168
            # Color 1
169
            2: 1,
170
            3: 1,
171
            4: 1,
172
            5: 1,
173

    
174
            # Color 2
175
            6: 2,
176
            7: 2,
177
            8: 2,
178
        }
179

    
180
        C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F)
181
        N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C)
182
        H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N)
183

    
184
        nx.algorithms.coloring.equitable_coloring.procedure_P(
185
            V_minus=0, V_plus=1, N=N, H=H, F=F, C=C, L=L
186
        )
187
        check_state(L=L, N=N, H=H, F=F, C=C)
188

    
189
    def test_cast_no_solo(self):
190
        L = {
191
            0: [8, 9],
192
            1: [10, 11],
193

    
194
            2: [8],
195
            3: [9],
196
            4: [10, 11],
197

    
198
            5: [8],
199
            6: [9],
200
            7: [10, 11],
201

    
202
            8: [0, 2, 5],
203
            9: [0, 3, 6],
204
            10: [1, 4, 7],
205
            11: [1, 4, 7],
206
        }
207

    
208
        F = {
209
            0: 0,
210
            1: 0,
211

    
212
            2: 2,
213
            3: 2,
214
            4: 2,
215

    
216
            5: 3,
217
            6: 3,
218
            7: 3,
219

    
220
            8: 1,
221
            9: 1,
222
            10: 1,
223
            11: 1,
224
        }
225

    
226
        C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F)
227
        N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C)
228
        H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N)
229

    
230
        nx.algorithms.coloring.equitable_coloring.procedure_P(
231
            V_minus=0, V_plus=1, N=N, H=H, F=F, C=C, L=L
232
        )
233
        check_state(L=L, N=N, H=H, F=F, C=C)
234

    
235
    def test_hard_prob(self):
236
        # Tests for two levels of recursion.
237
        num_colors, s = 5, 5
238

    
239
        G = nx.Graph()
240
        G.add_edges_from(
241
            [(0, 10), (0, 11), (0, 12), (0, 23), (10, 4), (10, 9),
242
             (10, 20), (11, 4), (11, 8), (11, 16), (12, 9), (12, 22),
243
             (12, 23), (23, 7), (1, 17), (1, 18), (1, 19), (1, 24),
244
             (17, 5), (17, 13), (17, 22), (18, 5), (19, 5), (19, 6),
245
             (19, 8), (24, 7), (24, 16), (2, 4), (2, 13), (2, 14),
246
             (2, 15), (4, 6), (13, 5), (13, 21), (14, 6), (14, 15),
247
             (15, 6), (15, 21), (3, 16), (3, 20), (3, 21), (3, 22),
248
             (16, 8), (20, 8), (21, 9), (22, 7)]
249
        )
250
        F = {node: node // s for node in range(num_colors * s)}
251
        F[s - 1] = num_colors - 1
252

    
253
        params = make_params_from_graph(G=G, F=F)
254

    
255
        nx.algorithms.coloring.equitable_coloring.procedure_P(
256
            V_minus=0, V_plus=num_colors - 1, **params
257
        )
258
        check_state(**params)
259

    
260
    def test_hardest_prob(self):
261
        # Tests for two levels of recursion.
262
        num_colors, s = 10, 4
263

    
264
        G = nx.Graph()
265
        G.add_edges_from(
266
            [(0, 19), (0, 24), (0, 29), (0, 30), (0, 35), (19, 3), (19, 7),
267
             (19, 9), (19, 15), (19, 21), (19, 24), (19, 30), (19, 38),
268
             (24, 5), (24, 11), (24, 13), (24, 20), (24, 30), (24, 37),
269
             (24, 38), (29, 6), (29, 10), (29, 13), (29, 15), (29, 16),
270
             (29, 17), (29, 20), (29, 26), (30, 6), (30, 10), (30, 15),
271
             (30, 22), (30, 23), (30, 39), (35, 6), (35, 9), (35, 14),
272
             (35, 18), (35, 22), (35, 23), (35, 25), (35, 27), (1, 20),
273
             (1, 26), (1, 31), (1, 34), (1, 38), (20, 4), (20, 8), (20, 14),
274
             (20, 18), (20, 28), (20, 33), (26, 7), (26, 10), (26, 14),
275
             (26, 18), (26, 21), (26, 32), (26, 39), (31, 5), (31, 8),
276
             (31, 13), (31, 16), (31, 17), (31, 21), (31, 25), (31, 27),
277
             (34, 7), (34, 8), (34, 13), (34, 18), (34, 22), (34, 23),
278
             (34, 25), (34, 27), (38, 4), (38, 9), (38, 12), (38, 14),
279
             (38, 21), (38, 27), (2, 3), (2, 18), (2, 21), (2, 28), (2, 32),
280
             (2, 33), (2, 36), (2, 37), (2, 39), (3, 5), (3, 9), (3, 13),
281
             (3, 22), (3, 23), (3, 25), (3, 27), (18, 6), (18, 11), (18, 15),
282
             (18, 39), (21, 4), (21, 10), (21, 14), (21, 36), (28, 6),
283
             (28, 10), (28, 14), (28, 16), (28, 17), (28, 25), (28, 27),
284
             (32, 5), (32, 10), (32, 12), (32, 16), (32, 17), (32, 22),
285
             (32, 23), (33, 7), (33, 10), (33, 12), (33, 16), (33, 17),
286
             (33, 25), (33, 27), (36, 5), (36, 8), (36, 15), (36, 16),
287
             (36, 17), (36, 25), (36, 27), (37, 5), (37, 11), (37, 15),
288
             (37, 16), (37, 17), (37, 22), (37, 23), (39, 7), (39, 8),
289
             (39, 15), (39, 22), (39, 23)]
290
        )
291
        F = {node: node // s for node in range(num_colors * s)}
292
        F[s - 1] = num_colors - 1  # V- = 0, V+ = num_colors - 1
293

    
294
        params = make_params_from_graph(G=G, F=F)
295

    
296
        nx.algorithms.coloring.equitable_coloring.procedure_P(
297
            V_minus=0, V_plus=num_colors - 1, **params
298
        )
299
        check_state(**params)
300

    
301

    
302
############################## Utility functions ##############################
303
def verify_coloring(graph, coloring):
304
    for node in graph.nodes():
305
        if node not in coloring:
306
            return False
307

    
308
        color = coloring[node]
309
        for neighbor in graph.neighbors(node):
310
            if coloring[neighbor] == color:
311
                return False
312

    
313
    return True
314

    
315

    
316
def verify_length(coloring, expected):
317
    coloring = dict_to_sets(coloring)
318
    return len(coloring) == expected
319

    
320

    
321
def dict_to_sets(colors):
322
    if len(colors) == 0:
323
        return []
324

    
325
    k = max(colors.values()) + 1
326
    sets = [set() for _ in range(k)]
327

    
328
    for (node, color) in colors.items():
329
        sets[color].add(node)
330

    
331
    return sets
332

    
333
############################## Graph Generation ##############################
334

    
335

    
336
def empty_graph():
337
    return nx.Graph()
338

    
339

    
340
def one_node_graph():
341
    graph = nx.Graph()
342
    graph.add_nodes_from([1])
343
    return graph
344

    
345

    
346
def two_node_graph():
347
    graph = nx.Graph()
348
    graph.add_nodes_from([1, 2])
349
    graph.add_edges_from([(1, 2)])
350
    return graph
351

    
352

    
353
def three_node_clique():
354
    graph = nx.Graph()
355
    graph.add_nodes_from([1, 2, 3])
356
    graph.add_edges_from([(1, 2), (1, 3), (2, 3)])
357
    return graph
358

    
359

    
360
def disconnected():
361
    graph = nx.Graph()
362
    graph.add_edges_from([
363
        (1, 2),
364
        (2, 3),
365
        (4, 5),
366
        (5, 6)
367
    ])
368
    return graph
369

    
370

    
371
def rs_shc():
372
    graph = nx.Graph()
373
    graph.add_nodes_from([1, 2, 3, 4])
374
    graph.add_edges_from([
375
        (1, 2),
376
        (2, 3),
377
        (3, 4)
378
    ])
379
    return graph
380

    
381

    
382
def slf_shc():
383
    graph = nx.Graph()
384
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7])
385
    graph.add_edges_from([
386
        (1, 2),
387
        (1, 5),
388
        (1, 6),
389
        (2, 3),
390
        (2, 7),
391
        (3, 4),
392
        (3, 7),
393
        (4, 5),
394
        (4, 6),
395
        (5, 6)
396
    ])
397
    return graph
398

    
399

    
400
def slf_hc():
401
    graph = nx.Graph()
402
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8])
403
    graph.add_edges_from([
404
        (1, 2),
405
        (1, 3),
406
        (1, 4),
407
        (1, 5),
408
        (2, 3),
409
        (2, 4),
410
        (2, 6),
411
        (5, 7),
412
        (5, 8),
413
        (6, 7),
414
        (6, 8),
415
        (7, 8)
416
    ])
417
    return graph
418

    
419

    
420
def lf_shc():
421
    graph = nx.Graph()
422
    graph.add_nodes_from([1, 2, 3, 4, 5, 6])
423
    graph.add_edges_from([
424
        (6, 1),
425
        (1, 4),
426
        (4, 3),
427
        (3, 2),
428
        (2, 5)
429
    ])
430
    return graph
431

    
432

    
433
def lf_hc():
434
    graph = nx.Graph()
435
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7])
436
    graph.add_edges_from([
437
        (1, 7),
438
        (1, 6),
439
        (1, 3),
440
        (1, 4),
441
        (7, 2),
442
        (2, 6),
443
        (2, 3),
444
        (2, 5),
445
        (5, 3),
446
        (5, 4),
447
        (4, 3)
448
    ])
449
    return graph
450

    
451

    
452
def sl_shc():
453
    graph = nx.Graph()
454
    graph.add_nodes_from([1, 2, 3, 4, 5, 6])
455
    graph.add_edges_from([
456
        (1, 2),
457
        (1, 3),
458
        (2, 3),
459
        (1, 4),
460
        (2, 5),
461
        (3, 6),
462
        (4, 5),
463
        (4, 6),
464
        (5, 6)
465
    ])
466
    return graph
467

    
468

    
469
def sl_hc():
470
    graph = nx.Graph()
471
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8])
472
    graph.add_edges_from([
473
        (1, 2),
474
        (1, 3),
475
        (1, 5),
476
        (1, 7),
477
        (2, 3),
478
        (2, 4),
479
        (2, 8),
480
        (8, 4),
481
        (8, 6),
482
        (8, 7),
483
        (7, 5),
484
        (7, 6),
485
        (3, 4),
486
        (4, 6),
487
        (6, 5),
488
        (5, 3)
489
    ])
490
    return graph
491

    
492

    
493
def gis_shc():
494
    graph = nx.Graph()
495
    graph.add_nodes_from([1, 2, 3, 4])
496
    graph.add_edges_from([
497
        (1, 2),
498
        (2, 3),
499
        (3, 4)
500
    ])
501
    return graph
502

    
503

    
504
def gis_hc():
505
    graph = nx.Graph()
506
    graph.add_nodes_from([1, 2, 3, 4, 5, 6])
507
    graph.add_edges_from([
508
        (1, 5),
509
        (2, 5),
510
        (3, 6),
511
        (4, 6),
512
        (5, 6)
513
    ])
514
    return graph
515

    
516

    
517
def cs_shc():
518
    graph = nx.Graph()
519
    graph.add_nodes_from([1, 2, 3, 4, 5])
520
    graph.add_edges_from([
521
        (1, 2),
522
        (1, 5),
523
        (2, 3),
524
        (2, 4),
525
        (2, 5),
526
        (3, 4),
527
        (4, 5)
528
    ])
529
    return graph
530

    
531

    
532
def rsi_shc():
533
    graph = nx.Graph()
534
    graph.add_nodes_from([1, 2, 3, 4, 5, 6])
535
    graph.add_edges_from([
536
        (1, 2),
537
        (1, 5),
538
        (1, 6),
539
        (2, 3),
540
        (3, 4),
541
        (4, 5),
542
        (4, 6),
543
        (5, 6)
544
    ])
545
    return graph
546

    
547

    
548
def lfi_shc():
549
    graph = nx.Graph()
550
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7])
551
    graph.add_edges_from([
552
        (1, 2),
553
        (1, 5),
554
        (1, 6),
555
        (2, 3),
556
        (2, 7),
557
        (3, 4),
558
        (3, 7),
559
        (4, 5),
560
        (4, 6),
561
        (5, 6)
562
    ])
563
    return graph
564

    
565

    
566
def lfi_hc():
567
    graph = nx.Graph()
568
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9])
569
    graph.add_edges_from([
570
        (1, 2),
571
        (1, 5),
572
        (1, 6),
573
        (1, 7),
574
        (2, 3),
575
        (2, 8),
576
        (2, 9),
577
        (3, 4),
578
        (3, 8),
579
        (3, 9),
580
        (4, 5),
581
        (4, 6),
582
        (4, 7),
583
        (5, 6)
584
    ])
585
    return graph
586

    
587

    
588
def sli_shc():
589
    graph = nx.Graph()
590
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7])
591
    graph.add_edges_from([
592
        (1, 2),
593
        (1, 3),
594
        (1, 5),
595
        (1, 7),
596
        (2, 3),
597
        (2, 6),
598
        (3, 4),
599
        (4, 5),
600
        (4, 6),
601
        (5, 7),
602
        (6, 7)
603
    ])
604
    return graph
605

    
606

    
607
def sli_hc():
608
    graph = nx.Graph()
609
    graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9])
610
    graph.add_edges_from([
611
        (1, 2),
612
        (1, 3),
613
        (1, 4),
614
        (1, 5),
615
        (2, 3),
616
        (2, 7),
617
        (2, 8),
618
        (2, 9),
619
        (3, 6),
620
        (3, 7),
621
        (3, 9),
622
        (4, 5),
623
        (4, 6),
624
        (4, 8),
625
        (4, 9),
626
        (5, 6),
627
        (5, 7),
628
        (5, 8),
629
        (6, 7),
630
        (6, 9),
631
        (7, 8),
632
        (8, 9)
633
    ])
634
    return graph
635

    
636

    
637
#---------------------------------------------------------------------------
638
# Basic tests for all strategies
639
# For each basic graph function, specify the number of expected colors.
640
BASIC_TEST_CASES = {empty_graph: 0,
641
                    one_node_graph: 1,
642
                    two_node_graph: 2,
643
                    disconnected: 2,
644
                    three_node_clique: 3}
645

    
646

    
647
#---------------------------------------------------------------------------
648
# Special test cases. Each strategy has a list of tuples of the form
649
# (graph function, interchange, valid # of colors)
650
SPECIAL_TEST_CASES = {
651
    'random_sequential': [
652
        (rs_shc, False, (2, 3)),
653
        (rs_shc, True, 2),
654
        (rsi_shc, True, (3, 4))],
655
    'saturation_largest_first': [
656
        (slf_shc, False, (3, 4)),
657
        (slf_hc, False, 4)],
658
    'largest_first': [
659
        (lf_shc, False, (2, 3)),
660
        (lf_hc, False, 4),
661
        (lf_shc, True, 2),
662
        (lf_hc, True, 3),
663
        (lfi_shc, True, (3, 4)),
664
        (lfi_hc, True, 4)],
665
    'smallest_last': [
666
        (sl_shc, False, (3, 4)),
667
        (sl_hc, False, 5),
668
        (sl_shc, True, 3),
669
        (sl_hc, True, 4),
670
        (sli_shc, True, (3, 4)),
671
        (sli_hc, True, 5)],
672
    'independent_set': [
673
        (gis_shc, False, (2, 3)),
674
        (gis_hc, False, 3)],
675
    'connected_sequential': [
676
        (cs_shc, False, (3, 4)),
677
        (cs_shc, True, 3)],
678
    'connected_sequential_dfs': [
679
        (cs_shc, False, (3, 4))],
680
}
681

    
682

    
683
#---------------------------------------------------------------------------
684
# Helper functions to test
685
# (graph function, interchange, valid # of colors)
686

    
687

    
688
def check_state(L, N, H, F, C):
689
    s = len(C[0])
690
    num_colors = len(C.keys())
691

    
692
    assert all(u in L[v] for u in L.keys() for v in L[u])
693
    assert all(F[u] != F[v] for u in L.keys() for v in L[u])
694
    assert all(len(L[u]) < num_colors for u in L.keys())
695
    assert all(len(C[x]) == s for x in C)
696
    assert all(H[(c1, c2)] >= 0 for c1 in C.keys() for c2 in C.keys())
697
    assert all(N[(u, F[u])] == 0 for u in F.keys())
698

    
699

    
700
def max_degree(G):
701
    """Get the maximum degree of any node in G."""
702
    return max([G.degree(node) for node in G.nodes]) if len(G.nodes) > 0 else 0
703

    
704

    
705
def make_params_from_graph(G, F):
706
    """Returns {N, L, H, C} from the given graph."""
707
    num_nodes = len(G)
708
    L = {u: [] for u in range(num_nodes)}
709
    for (u, v) in G.edges:
710
        L[u].append(v)
711
        L[v].append(u)
712

    
713
    C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F)
714
    N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C)
715
    H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N)
716

    
717
    return {
718
        'N': N,
719
        'F': F,
720
        'C': C,
721
        'H': H,
722
        'L': L,
723
    }
724