Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/coloring/tests/test_coloring.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Greedy coloring test suite. | |
2 | |
3 """ | |
4 | |
5 import networkx as nx | |
6 import pytest | |
7 | |
8 | |
9 is_coloring = nx.algorithms.coloring.equitable_coloring.is_coloring | |
10 is_equitable = nx.algorithms.coloring.equitable_coloring.is_equitable | |
11 | |
12 | |
13 ALL_STRATEGIES = [ | |
14 "largest_first", | |
15 "random_sequential", | |
16 "smallest_last", | |
17 "independent_set", | |
18 "connected_sequential_bfs", | |
19 "connected_sequential_dfs", | |
20 "connected_sequential", | |
21 "saturation_largest_first", | |
22 "DSATUR", | |
23 ] | |
24 | |
25 # List of strategies where interchange=True results in an error | |
26 INTERCHANGE_INVALID = ["independent_set", "saturation_largest_first", "DSATUR"] | |
27 | |
28 | |
29 class TestColoring: | |
30 def test_basic_cases(self): | |
31 def check_basic_case(graph_func, n_nodes, strategy, interchange): | |
32 graph = graph_func() | |
33 coloring = nx.coloring.greedy_color( | |
34 graph, strategy=strategy, interchange=interchange | |
35 ) | |
36 assert verify_length(coloring, n_nodes) | |
37 assert verify_coloring(graph, coloring) | |
38 | |
39 for graph_func, n_nodes in BASIC_TEST_CASES.items(): | |
40 for interchange in [True, False]: | |
41 for strategy in ALL_STRATEGIES: | |
42 check_basic_case(graph_func, n_nodes, strategy, False) | |
43 if strategy not in INTERCHANGE_INVALID: | |
44 check_basic_case(graph_func, n_nodes, strategy, True) | |
45 | |
46 def test_special_cases(self): | |
47 def check_special_case(strategy, graph_func, interchange, colors): | |
48 graph = graph_func() | |
49 coloring = nx.coloring.greedy_color( | |
50 graph, strategy=strategy, interchange=interchange | |
51 ) | |
52 if not hasattr(colors, "__len__"): | |
53 colors = [colors] | |
54 assert any(verify_length(coloring, n_colors) for n_colors in colors) | |
55 assert verify_coloring(graph, coloring) | |
56 | |
57 for strategy, arglist in SPECIAL_TEST_CASES.items(): | |
58 for args in arglist: | |
59 check_special_case(strategy, args[0], args[1], args[2]) | |
60 | |
61 def test_interchange_invalid(self): | |
62 graph = one_node_graph() | |
63 for strategy in INTERCHANGE_INVALID: | |
64 pytest.raises( | |
65 nx.NetworkXPointlessConcept, | |
66 nx.coloring.greedy_color, | |
67 graph, | |
68 strategy=strategy, | |
69 interchange=True, | |
70 ) | |
71 | |
72 def test_bad_inputs(self): | |
73 graph = one_node_graph() | |
74 pytest.raises( | |
75 nx.NetworkXError, | |
76 nx.coloring.greedy_color, | |
77 graph, | |
78 strategy="invalid strategy", | |
79 ) | |
80 | |
81 def test_strategy_as_function(self): | |
82 graph = lf_shc() | |
83 colors_1 = nx.coloring.greedy_color(graph, "largest_first") | |
84 colors_2 = nx.coloring.greedy_color(graph, nx.coloring.strategy_largest_first) | |
85 assert colors_1 == colors_2 | |
86 | |
87 def test_seed_argument(self): | |
88 graph = lf_shc() | |
89 rs = nx.coloring.strategy_random_sequential | |
90 c1 = nx.coloring.greedy_color(graph, lambda g, c: rs(g, c, seed=1)) | |
91 for u, v in graph.edges: | |
92 assert c1[u] != c1[v] | |
93 | |
94 def test_is_coloring(self): | |
95 G = nx.Graph() | |
96 G.add_edges_from([(0, 1), (1, 2)]) | |
97 coloring = {0: 0, 1: 1, 2: 0} | |
98 assert is_coloring(G, coloring) | |
99 | |
100 coloring[0] = 1 | |
101 assert not is_coloring(G, coloring) | |
102 assert not is_equitable(G, coloring) | |
103 | |
104 def test_is_equitable(self): | |
105 G = nx.Graph() | |
106 G.add_edges_from([(0, 1), (1, 2)]) | |
107 coloring = {0: 0, 1: 1, 2: 0} | |
108 assert is_equitable(G, coloring) | |
109 | |
110 G.add_edges_from([(2, 3), (2, 4), (2, 5)]) | |
111 coloring[3] = 1 | |
112 coloring[4] = 1 | |
113 coloring[5] = 1 | |
114 assert is_coloring(G, coloring) | |
115 assert not is_equitable(G, coloring) | |
116 | |
117 def test_num_colors(self): | |
118 G = nx.Graph() | |
119 G.add_edges_from([(0, 1), (0, 2), (0, 3)]) | |
120 pytest.raises(nx.NetworkXAlgorithmError, nx.coloring.equitable_color, G, 2) | |
121 | |
122 def test_equitable_color(self): | |
123 G = nx.fast_gnp_random_graph(n=10, p=0.2, seed=42) | |
124 coloring = nx.coloring.equitable_color(G, max_degree(G) + 1) | |
125 assert is_equitable(G, coloring) | |
126 | |
127 def test_equitable_color_empty(self): | |
128 G = nx.empty_graph() | |
129 coloring = nx.coloring.equitable_color(G, max_degree(G) + 1) | |
130 assert is_equitable(G, coloring) | |
131 | |
132 def test_equitable_color_large(self): | |
133 G = nx.fast_gnp_random_graph(100, 0.1, seed=42) | |
134 coloring = nx.coloring.equitable_color(G, max_degree(G) + 1) | |
135 assert is_equitable(G, coloring, num_colors=max_degree(G) + 1) | |
136 | |
137 def test_case_V_plus_not_in_A_cal(self): | |
138 # Hand crafted case to avoid the easy case. | |
139 L = { | |
140 0: [2, 5], | |
141 1: [3, 4], | |
142 2: [0, 8], | |
143 3: [1, 7], | |
144 4: [1, 6], | |
145 5: [0, 6], | |
146 6: [4, 5], | |
147 7: [3], | |
148 8: [2], | |
149 } | |
150 | |
151 F = { | |
152 # Color 0 | |
153 0: 0, | |
154 1: 0, | |
155 # Color 1 | |
156 2: 1, | |
157 3: 1, | |
158 4: 1, | |
159 5: 1, | |
160 # Color 2 | |
161 6: 2, | |
162 7: 2, | |
163 8: 2, | |
164 } | |
165 | |
166 C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F) | |
167 N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C) | |
168 H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N) | |
169 | |
170 nx.algorithms.coloring.equitable_coloring.procedure_P( | |
171 V_minus=0, V_plus=1, N=N, H=H, F=F, C=C, L=L | |
172 ) | |
173 check_state(L=L, N=N, H=H, F=F, C=C) | |
174 | |
175 def test_cast_no_solo(self): | |
176 L = { | |
177 0: [8, 9], | |
178 1: [10, 11], | |
179 2: [8], | |
180 3: [9], | |
181 4: [10, 11], | |
182 5: [8], | |
183 6: [9], | |
184 7: [10, 11], | |
185 8: [0, 2, 5], | |
186 9: [0, 3, 6], | |
187 10: [1, 4, 7], | |
188 11: [1, 4, 7], | |
189 } | |
190 | |
191 F = {0: 0, 1: 0, 2: 2, 3: 2, 4: 2, 5: 3, 6: 3, 7: 3, 8: 1, 9: 1, 10: 1, 11: 1} | |
192 | |
193 C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F) | |
194 N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C) | |
195 H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N) | |
196 | |
197 nx.algorithms.coloring.equitable_coloring.procedure_P( | |
198 V_minus=0, V_plus=1, N=N, H=H, F=F, C=C, L=L | |
199 ) | |
200 check_state(L=L, N=N, H=H, F=F, C=C) | |
201 | |
202 def test_hard_prob(self): | |
203 # Tests for two levels of recursion. | |
204 num_colors, s = 5, 5 | |
205 | |
206 G = nx.Graph() | |
207 G.add_edges_from( | |
208 [ | |
209 (0, 10), | |
210 (0, 11), | |
211 (0, 12), | |
212 (0, 23), | |
213 (10, 4), | |
214 (10, 9), | |
215 (10, 20), | |
216 (11, 4), | |
217 (11, 8), | |
218 (11, 16), | |
219 (12, 9), | |
220 (12, 22), | |
221 (12, 23), | |
222 (23, 7), | |
223 (1, 17), | |
224 (1, 18), | |
225 (1, 19), | |
226 (1, 24), | |
227 (17, 5), | |
228 (17, 13), | |
229 (17, 22), | |
230 (18, 5), | |
231 (19, 5), | |
232 (19, 6), | |
233 (19, 8), | |
234 (24, 7), | |
235 (24, 16), | |
236 (2, 4), | |
237 (2, 13), | |
238 (2, 14), | |
239 (2, 15), | |
240 (4, 6), | |
241 (13, 5), | |
242 (13, 21), | |
243 (14, 6), | |
244 (14, 15), | |
245 (15, 6), | |
246 (15, 21), | |
247 (3, 16), | |
248 (3, 20), | |
249 (3, 21), | |
250 (3, 22), | |
251 (16, 8), | |
252 (20, 8), | |
253 (21, 9), | |
254 (22, 7), | |
255 ] | |
256 ) | |
257 F = {node: node // s for node in range(num_colors * s)} | |
258 F[s - 1] = num_colors - 1 | |
259 | |
260 params = make_params_from_graph(G=G, F=F) | |
261 | |
262 nx.algorithms.coloring.equitable_coloring.procedure_P( | |
263 V_minus=0, V_plus=num_colors - 1, **params | |
264 ) | |
265 check_state(**params) | |
266 | |
267 def test_hardest_prob(self): | |
268 # Tests for two levels of recursion. | |
269 num_colors, s = 10, 4 | |
270 | |
271 G = nx.Graph() | |
272 G.add_edges_from( | |
273 [ | |
274 (0, 19), | |
275 (0, 24), | |
276 (0, 29), | |
277 (0, 30), | |
278 (0, 35), | |
279 (19, 3), | |
280 (19, 7), | |
281 (19, 9), | |
282 (19, 15), | |
283 (19, 21), | |
284 (19, 24), | |
285 (19, 30), | |
286 (19, 38), | |
287 (24, 5), | |
288 (24, 11), | |
289 (24, 13), | |
290 (24, 20), | |
291 (24, 30), | |
292 (24, 37), | |
293 (24, 38), | |
294 (29, 6), | |
295 (29, 10), | |
296 (29, 13), | |
297 (29, 15), | |
298 (29, 16), | |
299 (29, 17), | |
300 (29, 20), | |
301 (29, 26), | |
302 (30, 6), | |
303 (30, 10), | |
304 (30, 15), | |
305 (30, 22), | |
306 (30, 23), | |
307 (30, 39), | |
308 (35, 6), | |
309 (35, 9), | |
310 (35, 14), | |
311 (35, 18), | |
312 (35, 22), | |
313 (35, 23), | |
314 (35, 25), | |
315 (35, 27), | |
316 (1, 20), | |
317 (1, 26), | |
318 (1, 31), | |
319 (1, 34), | |
320 (1, 38), | |
321 (20, 4), | |
322 (20, 8), | |
323 (20, 14), | |
324 (20, 18), | |
325 (20, 28), | |
326 (20, 33), | |
327 (26, 7), | |
328 (26, 10), | |
329 (26, 14), | |
330 (26, 18), | |
331 (26, 21), | |
332 (26, 32), | |
333 (26, 39), | |
334 (31, 5), | |
335 (31, 8), | |
336 (31, 13), | |
337 (31, 16), | |
338 (31, 17), | |
339 (31, 21), | |
340 (31, 25), | |
341 (31, 27), | |
342 (34, 7), | |
343 (34, 8), | |
344 (34, 13), | |
345 (34, 18), | |
346 (34, 22), | |
347 (34, 23), | |
348 (34, 25), | |
349 (34, 27), | |
350 (38, 4), | |
351 (38, 9), | |
352 (38, 12), | |
353 (38, 14), | |
354 (38, 21), | |
355 (38, 27), | |
356 (2, 3), | |
357 (2, 18), | |
358 (2, 21), | |
359 (2, 28), | |
360 (2, 32), | |
361 (2, 33), | |
362 (2, 36), | |
363 (2, 37), | |
364 (2, 39), | |
365 (3, 5), | |
366 (3, 9), | |
367 (3, 13), | |
368 (3, 22), | |
369 (3, 23), | |
370 (3, 25), | |
371 (3, 27), | |
372 (18, 6), | |
373 (18, 11), | |
374 (18, 15), | |
375 (18, 39), | |
376 (21, 4), | |
377 (21, 10), | |
378 (21, 14), | |
379 (21, 36), | |
380 (28, 6), | |
381 (28, 10), | |
382 (28, 14), | |
383 (28, 16), | |
384 (28, 17), | |
385 (28, 25), | |
386 (28, 27), | |
387 (32, 5), | |
388 (32, 10), | |
389 (32, 12), | |
390 (32, 16), | |
391 (32, 17), | |
392 (32, 22), | |
393 (32, 23), | |
394 (33, 7), | |
395 (33, 10), | |
396 (33, 12), | |
397 (33, 16), | |
398 (33, 17), | |
399 (33, 25), | |
400 (33, 27), | |
401 (36, 5), | |
402 (36, 8), | |
403 (36, 15), | |
404 (36, 16), | |
405 (36, 17), | |
406 (36, 25), | |
407 (36, 27), | |
408 (37, 5), | |
409 (37, 11), | |
410 (37, 15), | |
411 (37, 16), | |
412 (37, 17), | |
413 (37, 22), | |
414 (37, 23), | |
415 (39, 7), | |
416 (39, 8), | |
417 (39, 15), | |
418 (39, 22), | |
419 (39, 23), | |
420 ] | |
421 ) | |
422 F = {node: node // s for node in range(num_colors * s)} | |
423 F[s - 1] = num_colors - 1 # V- = 0, V+ = num_colors - 1 | |
424 | |
425 params = make_params_from_graph(G=G, F=F) | |
426 | |
427 nx.algorithms.coloring.equitable_coloring.procedure_P( | |
428 V_minus=0, V_plus=num_colors - 1, **params | |
429 ) | |
430 check_state(**params) | |
431 | |
432 | |
433 # ############################ Utility functions ############################ | |
434 def verify_coloring(graph, coloring): | |
435 for node in graph.nodes(): | |
436 if node not in coloring: | |
437 return False | |
438 | |
439 color = coloring[node] | |
440 for neighbor in graph.neighbors(node): | |
441 if coloring[neighbor] == color: | |
442 return False | |
443 | |
444 return True | |
445 | |
446 | |
447 def verify_length(coloring, expected): | |
448 coloring = dict_to_sets(coloring) | |
449 return len(coloring) == expected | |
450 | |
451 | |
452 def dict_to_sets(colors): | |
453 if len(colors) == 0: | |
454 return [] | |
455 | |
456 k = max(colors.values()) + 1 | |
457 sets = [set() for _ in range(k)] | |
458 | |
459 for (node, color) in colors.items(): | |
460 sets[color].add(node) | |
461 | |
462 return sets | |
463 | |
464 | |
465 # ############################ Graph Generation ############################ | |
466 | |
467 | |
468 def empty_graph(): | |
469 return nx.Graph() | |
470 | |
471 | |
472 def one_node_graph(): | |
473 graph = nx.Graph() | |
474 graph.add_nodes_from([1]) | |
475 return graph | |
476 | |
477 | |
478 def two_node_graph(): | |
479 graph = nx.Graph() | |
480 graph.add_nodes_from([1, 2]) | |
481 graph.add_edges_from([(1, 2)]) | |
482 return graph | |
483 | |
484 | |
485 def three_node_clique(): | |
486 graph = nx.Graph() | |
487 graph.add_nodes_from([1, 2, 3]) | |
488 graph.add_edges_from([(1, 2), (1, 3), (2, 3)]) | |
489 return graph | |
490 | |
491 | |
492 def disconnected(): | |
493 graph = nx.Graph() | |
494 graph.add_edges_from([(1, 2), (2, 3), (4, 5), (5, 6)]) | |
495 return graph | |
496 | |
497 | |
498 def rs_shc(): | |
499 graph = nx.Graph() | |
500 graph.add_nodes_from([1, 2, 3, 4]) | |
501 graph.add_edges_from([(1, 2), (2, 3), (3, 4)]) | |
502 return graph | |
503 | |
504 | |
505 def slf_shc(): | |
506 graph = nx.Graph() | |
507 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7]) | |
508 graph.add_edges_from( | |
509 [(1, 2), (1, 5), (1, 6), (2, 3), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6)] | |
510 ) | |
511 return graph | |
512 | |
513 | |
514 def slf_hc(): | |
515 graph = nx.Graph() | |
516 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8]) | |
517 graph.add_edges_from( | |
518 [ | |
519 (1, 2), | |
520 (1, 3), | |
521 (1, 4), | |
522 (1, 5), | |
523 (2, 3), | |
524 (2, 4), | |
525 (2, 6), | |
526 (5, 7), | |
527 (5, 8), | |
528 (6, 7), | |
529 (6, 8), | |
530 (7, 8), | |
531 ] | |
532 ) | |
533 return graph | |
534 | |
535 | |
536 def lf_shc(): | |
537 graph = nx.Graph() | |
538 graph.add_nodes_from([1, 2, 3, 4, 5, 6]) | |
539 graph.add_edges_from([(6, 1), (1, 4), (4, 3), (3, 2), (2, 5)]) | |
540 return graph | |
541 | |
542 | |
543 def lf_hc(): | |
544 graph = nx.Graph() | |
545 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7]) | |
546 graph.add_edges_from( | |
547 [ | |
548 (1, 7), | |
549 (1, 6), | |
550 (1, 3), | |
551 (1, 4), | |
552 (7, 2), | |
553 (2, 6), | |
554 (2, 3), | |
555 (2, 5), | |
556 (5, 3), | |
557 (5, 4), | |
558 (4, 3), | |
559 ] | |
560 ) | |
561 return graph | |
562 | |
563 | |
564 def sl_shc(): | |
565 graph = nx.Graph() | |
566 graph.add_nodes_from([1, 2, 3, 4, 5, 6]) | |
567 graph.add_edges_from( | |
568 [(1, 2), (1, 3), (2, 3), (1, 4), (2, 5), (3, 6), (4, 5), (4, 6), (5, 6)] | |
569 ) | |
570 return graph | |
571 | |
572 | |
573 def sl_hc(): | |
574 graph = nx.Graph() | |
575 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8]) | |
576 graph.add_edges_from( | |
577 [ | |
578 (1, 2), | |
579 (1, 3), | |
580 (1, 5), | |
581 (1, 7), | |
582 (2, 3), | |
583 (2, 4), | |
584 (2, 8), | |
585 (8, 4), | |
586 (8, 6), | |
587 (8, 7), | |
588 (7, 5), | |
589 (7, 6), | |
590 (3, 4), | |
591 (4, 6), | |
592 (6, 5), | |
593 (5, 3), | |
594 ] | |
595 ) | |
596 return graph | |
597 | |
598 | |
599 def gis_shc(): | |
600 graph = nx.Graph() | |
601 graph.add_nodes_from([1, 2, 3, 4]) | |
602 graph.add_edges_from([(1, 2), (2, 3), (3, 4)]) | |
603 return graph | |
604 | |
605 | |
606 def gis_hc(): | |
607 graph = nx.Graph() | |
608 graph.add_nodes_from([1, 2, 3, 4, 5, 6]) | |
609 graph.add_edges_from([(1, 5), (2, 5), (3, 6), (4, 6), (5, 6)]) | |
610 return graph | |
611 | |
612 | |
613 def cs_shc(): | |
614 graph = nx.Graph() | |
615 graph.add_nodes_from([1, 2, 3, 4, 5]) | |
616 graph.add_edges_from([(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)]) | |
617 return graph | |
618 | |
619 | |
620 def rsi_shc(): | |
621 graph = nx.Graph() | |
622 graph.add_nodes_from([1, 2, 3, 4, 5, 6]) | |
623 graph.add_edges_from( | |
624 [(1, 2), (1, 5), (1, 6), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)] | |
625 ) | |
626 return graph | |
627 | |
628 | |
629 def lfi_shc(): | |
630 graph = nx.Graph() | |
631 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7]) | |
632 graph.add_edges_from( | |
633 [(1, 2), (1, 5), (1, 6), (2, 3), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6)] | |
634 ) | |
635 return graph | |
636 | |
637 | |
638 def lfi_hc(): | |
639 graph = nx.Graph() | |
640 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
641 graph.add_edges_from( | |
642 [ | |
643 (1, 2), | |
644 (1, 5), | |
645 (1, 6), | |
646 (1, 7), | |
647 (2, 3), | |
648 (2, 8), | |
649 (2, 9), | |
650 (3, 4), | |
651 (3, 8), | |
652 (3, 9), | |
653 (4, 5), | |
654 (4, 6), | |
655 (4, 7), | |
656 (5, 6), | |
657 ] | |
658 ) | |
659 return graph | |
660 | |
661 | |
662 def sli_shc(): | |
663 graph = nx.Graph() | |
664 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7]) | |
665 graph.add_edges_from( | |
666 [ | |
667 (1, 2), | |
668 (1, 3), | |
669 (1, 5), | |
670 (1, 7), | |
671 (2, 3), | |
672 (2, 6), | |
673 (3, 4), | |
674 (4, 5), | |
675 (4, 6), | |
676 (5, 7), | |
677 (6, 7), | |
678 ] | |
679 ) | |
680 return graph | |
681 | |
682 | |
683 def sli_hc(): | |
684 graph = nx.Graph() | |
685 graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
686 graph.add_edges_from( | |
687 [ | |
688 (1, 2), | |
689 (1, 3), | |
690 (1, 4), | |
691 (1, 5), | |
692 (2, 3), | |
693 (2, 7), | |
694 (2, 8), | |
695 (2, 9), | |
696 (3, 6), | |
697 (3, 7), | |
698 (3, 9), | |
699 (4, 5), | |
700 (4, 6), | |
701 (4, 8), | |
702 (4, 9), | |
703 (5, 6), | |
704 (5, 7), | |
705 (5, 8), | |
706 (6, 7), | |
707 (6, 9), | |
708 (7, 8), | |
709 (8, 9), | |
710 ] | |
711 ) | |
712 return graph | |
713 | |
714 | |
715 # -------------------------------------------------------------------------- | |
716 # Basic tests for all strategies | |
717 # For each basic graph function, specify the number of expected colors. | |
718 BASIC_TEST_CASES = { | |
719 empty_graph: 0, | |
720 one_node_graph: 1, | |
721 two_node_graph: 2, | |
722 disconnected: 2, | |
723 three_node_clique: 3, | |
724 } | |
725 | |
726 | |
727 # -------------------------------------------------------------------------- | |
728 # Special test cases. Each strategy has a list of tuples of the form | |
729 # (graph function, interchange, valid # of colors) | |
730 SPECIAL_TEST_CASES = { | |
731 "random_sequential": [ | |
732 (rs_shc, False, (2, 3)), | |
733 (rs_shc, True, 2), | |
734 (rsi_shc, True, (3, 4)), | |
735 ], | |
736 "saturation_largest_first": [(slf_shc, False, (3, 4)), (slf_hc, False, 4)], | |
737 "largest_first": [ | |
738 (lf_shc, False, (2, 3)), | |
739 (lf_hc, False, 4), | |
740 (lf_shc, True, 2), | |
741 (lf_hc, True, 3), | |
742 (lfi_shc, True, (3, 4)), | |
743 (lfi_hc, True, 4), | |
744 ], | |
745 "smallest_last": [ | |
746 (sl_shc, False, (3, 4)), | |
747 (sl_hc, False, 5), | |
748 (sl_shc, True, 3), | |
749 (sl_hc, True, 4), | |
750 (sli_shc, True, (3, 4)), | |
751 (sli_hc, True, 5), | |
752 ], | |
753 "independent_set": [(gis_shc, False, (2, 3)), (gis_hc, False, 3)], | |
754 "connected_sequential": [(cs_shc, False, (3, 4)), (cs_shc, True, 3)], | |
755 "connected_sequential_dfs": [(cs_shc, False, (3, 4))], | |
756 } | |
757 | |
758 | |
759 # -------------------------------------------------------------------------- | |
760 # Helper functions to test | |
761 # (graph function, interchange, valid # of colors) | |
762 | |
763 | |
764 def check_state(L, N, H, F, C): | |
765 s = len(C[0]) | |
766 num_colors = len(C.keys()) | |
767 | |
768 assert all(u in L[v] for u in L.keys() for v in L[u]) | |
769 assert all(F[u] != F[v] for u in L.keys() for v in L[u]) | |
770 assert all(len(L[u]) < num_colors for u in L.keys()) | |
771 assert all(len(C[x]) == s for x in C) | |
772 assert all(H[(c1, c2)] >= 0 for c1 in C.keys() for c2 in C.keys()) | |
773 assert all(N[(u, F[u])] == 0 for u in F.keys()) | |
774 | |
775 | |
776 def max_degree(G): | |
777 """Get the maximum degree of any node in G.""" | |
778 return max([G.degree(node) for node in G.nodes]) if len(G.nodes) > 0 else 0 | |
779 | |
780 | |
781 def make_params_from_graph(G, F): | |
782 """Returns {N, L, H, C} from the given graph.""" | |
783 num_nodes = len(G) | |
784 L = {u: [] for u in range(num_nodes)} | |
785 for (u, v) in G.edges: | |
786 L[u].append(v) | |
787 L[v].append(u) | |
788 | |
789 C = nx.algorithms.coloring.equitable_coloring.make_C_from_F(F) | |
790 N = nx.algorithms.coloring.equitable_coloring.make_N_from_L_C(L, C) | |
791 H = nx.algorithms.coloring.equitable_coloring.make_H_from_C_N(C, N) | |
792 | |
793 return {"N": N, "F": F, "C": C, "H": H, "L": L} |