Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_max_weight_clique.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 """Maximum weight clique test suite. | |
| 2 | |
| 3 """ | |
| 4 | |
| 5 import networkx as nx | |
| 6 import pytest | |
| 7 | |
| 8 | |
| 9 class TestMaximumWeightClique: | |
| 10 def test_basic_cases(self): | |
| 11 def check_basic_case(graph_func, expected_weight, weight_accessor): | |
| 12 graph = graph_func() | |
| 13 clique, weight = nx.algorithms.max_weight_clique(graph, weight_accessor) | |
| 14 assert verify_clique( | |
| 15 graph, clique, weight, expected_weight, weight_accessor | |
| 16 ) | |
| 17 | |
| 18 for graph_func, (expected_weight, expected_size) in TEST_CASES.items(): | |
| 19 check_basic_case(graph_func, expected_weight, "weight") | |
| 20 check_basic_case(graph_func, expected_size, None) | |
| 21 | |
| 22 def test_key_error(self): | |
| 23 graph = two_node_graph() | |
| 24 with pytest.raises(KeyError): | |
| 25 nx.algorithms.max_weight_clique(graph, "non-existent-key") | |
| 26 | |
| 27 def test_error_on_non_integer_weight(self): | |
| 28 graph = two_node_graph() | |
| 29 graph.nodes[2]["weight"] = 1.5 | |
| 30 with pytest.raises(ValueError): | |
| 31 nx.algorithms.max_weight_clique(graph) | |
| 32 | |
| 33 def test_unaffected_by_self_loops(self): | |
| 34 graph = two_node_graph() | |
| 35 graph.add_edge(1, 1) | |
| 36 graph.add_edge(2, 2) | |
| 37 clique, weight = nx.algorithms.max_weight_clique(graph, "weight") | |
| 38 assert verify_clique(graph, clique, weight, 30, "weight") | |
| 39 graph = three_node_independent_set() | |
| 40 graph.add_edge(1, 1) | |
| 41 clique, weight = nx.algorithms.max_weight_clique(graph, "weight") | |
| 42 assert verify_clique(graph, clique, weight, 20, "weight") | |
| 43 | |
| 44 def test_30_node_prob(self): | |
| 45 G = nx.Graph() | |
| 46 G.add_nodes_from(range(1, 31)) | |
| 47 for i in range(1, 31): | |
| 48 G.nodes[i]["weight"] = i + 1 | |
| 49 # fmt: off | |
| 50 G.add_edges_from( | |
| 51 [ | |
| 52 (1, 12), (1, 13), (1, 15), (1, 16), (1, 18), (1, 19), (1, 20), | |
| 53 (1, 23), (1, 26), (1, 28), (1, 29), (1, 30), (2, 3), (2, 4), | |
| 54 (2, 5), (2, 8), (2, 9), (2, 10), (2, 14), (2, 17), (2, 18), | |
| 55 (2, 21), (2, 22), (2, 23), (2, 27), (3, 9), (3, 15), (3, 21), | |
| 56 (3, 22), (3, 23), (3, 24), (3, 27), (3, 28), (3, 29), (4, 5), | |
| 57 (4, 6), (4, 8), (4, 21), (4, 22), (4, 23), (4, 26), (4, 28), | |
| 58 (4, 30), (5, 6), (5, 8), (5, 9), (5, 13), (5, 14), (5, 15), | |
| 59 (5, 16), (5, 20), (5, 21), (5, 22), (5, 25), (5, 28), (5, 29), | |
| 60 (6, 7), (6, 8), (6, 13), (6, 17), (6, 18), (6, 19), (6, 24), | |
| 61 (6, 26), (6, 27), (6, 28), (6, 29), (7, 12), (7, 14), (7, 15), | |
| 62 (7, 16), (7, 17), (7, 20), (7, 25), (7, 27), (7, 29), (7, 30), | |
| 63 (8, 10), (8, 15), (8, 16), (8, 18), (8, 20), (8, 22), (8, 24), | |
| 64 (8, 26), (8, 27), (8, 28), (8, 30), (9, 11), (9, 12), (9, 13), | |
| 65 (9, 14), (9, 15), (9, 16), (9, 19), (9, 20), (9, 21), (9, 24), | |
| 66 (9, 30), (10, 12), (10, 15), (10, 18), (10, 19), (10, 20), | |
| 67 (10, 22), (10, 23), (10, 24), (10, 26), (10, 27), (10, 29), | |
| 68 (10, 30), (11, 13), (11, 15), (11, 16), (11, 17), (11, 18), | |
| 69 (11, 19), (11, 20), (11, 22), (11, 29), (11, 30), (12, 14), | |
| 70 (12, 17), (12, 18), (12, 19), (12, 20), (12, 21), (12, 23), | |
| 71 (12, 25), (12, 26), (12, 30), (13, 20), (13, 22), (13, 23), | |
| 72 (13, 24), (13, 30), (14, 16), (14, 20), (14, 21), (14, 22), | |
| 73 (14, 23), (14, 25), (14, 26), (14, 27), (14, 29), (14, 30), | |
| 74 (15, 17), (15, 18), (15, 20), (15, 21), (15, 26), (15, 27), | |
| 75 (15, 28), (16, 17), (16, 18), (16, 19), (16, 20), (16, 21), | |
| 76 (16, 29), (16, 30), (17, 18), (17, 21), (17, 22), (17, 25), | |
| 77 (17, 27), (17, 28), (17, 30), (18, 19), (18, 20), (18, 21), | |
| 78 (18, 22), (18, 23), (18, 24), (19, 20), (19, 22), (19, 23), | |
| 79 (19, 24), (19, 25), (19, 27), (19, 30), (20, 21), (20, 23), | |
| 80 (20, 24), (20, 26), (20, 28), (20, 29), (21, 23), (21, 26), | |
| 81 (21, 27), (21, 29), (22, 24), (22, 25), (22, 26), (22, 29), | |
| 82 (23, 25), (23, 30), (24, 25), (24, 26), (25, 27), (25, 29), | |
| 83 (26, 27), (26, 28), (26, 30), (28, 29), (29, 30), | |
| 84 ] | |
| 85 ) | |
| 86 # fmt: on | |
| 87 clique, weight = nx.algorithms.max_weight_clique(G) | |
| 88 assert verify_clique(G, clique, weight, 111, "weight") | |
| 89 | |
| 90 | |
| 91 # ############################ Utility functions ############################ | |
| 92 def verify_clique( | |
| 93 graph, clique, reported_clique_weight, expected_clique_weight, weight_accessor | |
| 94 ): | |
| 95 for node1 in clique: | |
| 96 for node2 in clique: | |
| 97 if node1 == node2: | |
| 98 continue | |
| 99 if not graph.has_edge(node1, node2): | |
| 100 return False | |
| 101 | |
| 102 if weight_accessor is None: | |
| 103 clique_weight = len(clique) | |
| 104 else: | |
| 105 clique_weight = sum(graph.nodes[v]["weight"] for v in clique) | |
| 106 | |
| 107 if clique_weight != expected_clique_weight: | |
| 108 return False | |
| 109 if clique_weight != reported_clique_weight: | |
| 110 return False | |
| 111 | |
| 112 return True | |
| 113 | |
| 114 | |
| 115 # ############################ Graph Generation ############################ | |
| 116 | |
| 117 | |
| 118 def empty_graph(): | |
| 119 return nx.Graph() | |
| 120 | |
| 121 | |
| 122 def one_node_graph(): | |
| 123 graph = nx.Graph() | |
| 124 graph.add_nodes_from([1]) | |
| 125 graph.nodes[1]["weight"] = 10 | |
| 126 return graph | |
| 127 | |
| 128 | |
| 129 def two_node_graph(): | |
| 130 graph = nx.Graph() | |
| 131 graph.add_nodes_from([1, 2]) | |
| 132 graph.add_edges_from([(1, 2)]) | |
| 133 graph.nodes[1]["weight"] = 10 | |
| 134 graph.nodes[2]["weight"] = 20 | |
| 135 return graph | |
| 136 | |
| 137 | |
| 138 def three_node_clique(): | |
| 139 graph = nx.Graph() | |
| 140 graph.add_nodes_from([1, 2, 3]) | |
| 141 graph.add_edges_from([(1, 2), (1, 3), (2, 3)]) | |
| 142 graph.nodes[1]["weight"] = 10 | |
| 143 graph.nodes[2]["weight"] = 20 | |
| 144 graph.nodes[3]["weight"] = 5 | |
| 145 return graph | |
| 146 | |
| 147 | |
| 148 def three_node_independent_set(): | |
| 149 graph = nx.Graph() | |
| 150 graph.add_nodes_from([1, 2, 3]) | |
| 151 graph.nodes[1]["weight"] = 10 | |
| 152 graph.nodes[2]["weight"] = 20 | |
| 153 graph.nodes[3]["weight"] = 5 | |
| 154 return graph | |
| 155 | |
| 156 | |
| 157 def disconnected(): | |
| 158 graph = nx.Graph() | |
| 159 graph.add_edges_from([(1, 2), (2, 3), (4, 5), (5, 6)]) | |
| 160 graph.nodes[1]["weight"] = 10 | |
| 161 graph.nodes[2]["weight"] = 20 | |
| 162 graph.nodes[3]["weight"] = 5 | |
| 163 graph.nodes[4]["weight"] = 100 | |
| 164 graph.nodes[5]["weight"] = 200 | |
| 165 graph.nodes[6]["weight"] = 50 | |
| 166 return graph | |
| 167 | |
| 168 | |
| 169 # -------------------------------------------------------------------------- | |
| 170 # Basic tests for all strategies | |
| 171 # For each basic graph function, specify expected weight of max weight clique | |
| 172 # and expected size of maximum clique | |
| 173 TEST_CASES = { | |
| 174 empty_graph: (0, 0), | |
| 175 one_node_graph: (10, 1), | |
| 176 two_node_graph: (30, 2), | |
| 177 three_node_clique: (35, 3), | |
| 178 three_node_independent_set: (20, 1), | |
| 179 disconnected: (300, 2), | |
| 180 } |