1# Jordi Torrents 2# Test for k-cutsets 3import itertools 4import pytest 5 6import networkx as nx 7from networkx.algorithms import flow 8from networkx.algorithms.connectivity.kcutsets import _is_separating_set 9 10MAX_CUTSETS_TO_TEST = 4 # originally 100. cut to decrease testing time 11 12flow_funcs = [ 13 flow.boykov_kolmogorov, 14 flow.dinitz, 15 flow.edmonds_karp, 16 flow.preflow_push, 17 flow.shortest_augmenting_path, 18] 19 20 21## 22# Some nice synthetic graphs 23## 24def graph_example_1(): 25 G = nx.convert_node_labels_to_integers( 26 nx.grid_graph([5, 5]), label_attribute="labels" 27 ) 28 rlabels = nx.get_node_attributes(G, "labels") 29 labels = {v: k for k, v in rlabels.items()} 30 31 for nodes in [ 32 (labels[(0, 0)], labels[(1, 0)]), 33 (labels[(0, 4)], labels[(1, 4)]), 34 (labels[(3, 0)], labels[(4, 0)]), 35 (labels[(3, 4)], labels[(4, 4)]), 36 ]: 37 new_node = G.order() + 1 38 # Petersen graph is triconnected 39 P = nx.petersen_graph() 40 G = nx.disjoint_union(G, P) 41 # Add two edges between the grid and P 42 G.add_edge(new_node + 1, nodes[0]) 43 G.add_edge(new_node, nodes[1]) 44 # K5 is 4-connected 45 K = nx.complete_graph(5) 46 G = nx.disjoint_union(G, K) 47 # Add three edges between P and K5 48 G.add_edge(new_node + 2, new_node + 11) 49 G.add_edge(new_node + 3, new_node + 12) 50 G.add_edge(new_node + 4, new_node + 13) 51 # Add another K5 sharing a node 52 G = nx.disjoint_union(G, K) 53 nbrs = G[new_node + 10] 54 G.remove_node(new_node + 10) 55 for nbr in nbrs: 56 G.add_edge(new_node + 17, nbr) 57 G.add_edge(new_node + 16, new_node + 5) 58 return G 59 60 61def torrents_and_ferraro_graph(): 62 G = nx.convert_node_labels_to_integers( 63 nx.grid_graph([5, 5]), label_attribute="labels" 64 ) 65 rlabels = nx.get_node_attributes(G, "labels") 66 labels = {v: k for k, v in rlabels.items()} 67 68 for nodes in [(labels[(0, 4)], labels[(1, 4)]), (labels[(3, 4)], labels[(4, 4)])]: 69 new_node = G.order() + 1 70 # Petersen graph is triconnected 71 P = nx.petersen_graph() 72 G = nx.disjoint_union(G, P) 73 # Add two edges between the grid and P 74 G.add_edge(new_node + 1, nodes[0]) 75 G.add_edge(new_node, nodes[1]) 76 # K5 is 4-connected 77 K = nx.complete_graph(5) 78 G = nx.disjoint_union(G, K) 79 # Add three edges between P and K5 80 G.add_edge(new_node + 2, new_node + 11) 81 G.add_edge(new_node + 3, new_node + 12) 82 G.add_edge(new_node + 4, new_node + 13) 83 # Add another K5 sharing a node 84 G = nx.disjoint_union(G, K) 85 nbrs = G[new_node + 10] 86 G.remove_node(new_node + 10) 87 for nbr in nbrs: 88 G.add_edge(new_node + 17, nbr) 89 # Commenting this makes the graph not biconnected !! 90 # This stupid mistake make one reviewer very angry :P 91 G.add_edge(new_node + 16, new_node + 8) 92 93 for nodes in [(labels[(0, 0)], labels[(1, 0)]), (labels[(3, 0)], labels[(4, 0)])]: 94 new_node = G.order() + 1 95 # Petersen graph is triconnected 96 P = nx.petersen_graph() 97 G = nx.disjoint_union(G, P) 98 # Add two edges between the grid and P 99 G.add_edge(new_node + 1, nodes[0]) 100 G.add_edge(new_node, nodes[1]) 101 # K5 is 4-connected 102 K = nx.complete_graph(5) 103 G = nx.disjoint_union(G, K) 104 # Add three edges between P and K5 105 G.add_edge(new_node + 2, new_node + 11) 106 G.add_edge(new_node + 3, new_node + 12) 107 G.add_edge(new_node + 4, new_node + 13) 108 # Add another K5 sharing two nodes 109 G = nx.disjoint_union(G, K) 110 nbrs = G[new_node + 10] 111 G.remove_node(new_node + 10) 112 for nbr in nbrs: 113 G.add_edge(new_node + 17, nbr) 114 nbrs2 = G[new_node + 9] 115 G.remove_node(new_node + 9) 116 for nbr in nbrs2: 117 G.add_edge(new_node + 18, nbr) 118 return G 119 120 121# Helper function 122def _check_separating_sets(G): 123 for cc in nx.connected_components(G): 124 if len(cc) < 3: 125 continue 126 Gc = G.subgraph(cc) 127 node_conn = nx.node_connectivity(Gc) 128 all_cuts = nx.all_node_cuts(Gc) 129 # Only test a limited number of cut sets to reduce test time. 130 for cut in itertools.islice(all_cuts, MAX_CUTSETS_TO_TEST): 131 assert node_conn == len(cut) 132 assert not nx.is_connected(nx.restricted_view(G, cut, [])) 133 134 135@pytest.mark.slow 136def test_torrents_and_ferraro_graph(): 137 G = torrents_and_ferraro_graph() 138 _check_separating_sets(G) 139 140 141def test_example_1(): 142 G = graph_example_1() 143 _check_separating_sets(G) 144 145 146def test_random_gnp(): 147 G = nx.gnp_random_graph(100, 0.1, seed=42) 148 _check_separating_sets(G) 149 150 151def test_shell(): 152 constructor = [(20, 80, 0.8), (80, 180, 0.6)] 153 G = nx.random_shell_graph(constructor, seed=42) 154 _check_separating_sets(G) 155 156 157def test_configuration(): 158 deg_seq = nx.random_powerlaw_tree_sequence(100, tries=5, seed=72) 159 G = nx.Graph(nx.configuration_model(deg_seq)) 160 G.remove_edges_from(nx.selfloop_edges(G)) 161 _check_separating_sets(G) 162 163 164def test_karate(): 165 G = nx.karate_club_graph() 166 _check_separating_sets(G) 167 168 169def _generate_no_biconnected(max_attempts=50): 170 attempts = 0 171 while True: 172 G = nx.fast_gnp_random_graph(100, 0.0575, seed=42) 173 if nx.is_connected(G) and not nx.is_biconnected(G): 174 attempts = 0 175 yield G 176 else: 177 if attempts >= max_attempts: 178 msg = f"Tried {attempts} times: no suitable Graph." 179 raise Exception(msg) 180 else: 181 attempts += 1 182 183 184def test_articulation_points(): 185 Ggen = _generate_no_biconnected() 186 for i in range(1): # change 1 to 3 or more for more realizations. 187 G = next(Ggen) 188 articulation_points = list({a} for a in nx.articulation_points(G)) 189 for cut in nx.all_node_cuts(G): 190 assert cut in articulation_points 191 192 193def test_grid_2d_graph(): 194 # All minimum node cuts of a 2d grid 195 # are the four pairs of nodes that are 196 # neighbors of the four corner nodes. 197 G = nx.grid_2d_graph(5, 5) 198 solution = [{(0, 1), (1, 0)}, {(3, 0), (4, 1)}, {(3, 4), (4, 3)}, {(0, 3), (1, 4)}] 199 for cut in nx.all_node_cuts(G): 200 assert cut in solution 201 202 203def test_disconnected_graph(): 204 G = nx.fast_gnp_random_graph(100, 0.01, seed=42) 205 cuts = nx.all_node_cuts(G) 206 pytest.raises(nx.NetworkXError, next, cuts) 207 208 209@pytest.mark.slow 210def test_alternative_flow_functions(): 211 graphs = [nx.grid_2d_graph(4, 4), nx.cycle_graph(5)] 212 for G in graphs: 213 node_conn = nx.node_connectivity(G) 214 for flow_func in flow_funcs: 215 all_cuts = nx.all_node_cuts(G, flow_func=flow_func) 216 # Only test a limited number of cut sets to reduce test time. 217 for cut in itertools.islice(all_cuts, MAX_CUTSETS_TO_TEST): 218 assert node_conn == len(cut) 219 assert not nx.is_connected(nx.restricted_view(G, cut, [])) 220 221 222def test_is_separating_set_complete_graph(): 223 G = nx.complete_graph(5) 224 assert _is_separating_set(G, {0, 1, 2, 3}) 225 226 227def test_is_separating_set(): 228 for i in [5, 10, 15]: 229 G = nx.star_graph(i) 230 max_degree_node = max(G, key=G.degree) 231 assert _is_separating_set(G, {max_degree_node}) 232 233 234def test_non_repeated_cuts(): 235 # The algorithm was repeating the cut {0, 1} for the giant biconnected 236 # component of the Karate club graph. 237 K = nx.karate_club_graph() 238 bcc = max(list(nx.biconnected_components(K)), key=len) 239 G = K.subgraph(bcc) 240 solution = [{32, 33}, {2, 33}, {0, 3}, {0, 1}, {29, 33}] 241 cuts = list(nx.all_node_cuts(G)) 242 if len(solution) != len(cuts): 243 print(nx.info(G)) 244 print(f"Solution: {solution}") 245 print(f"Result: {cuts}") 246 assert len(solution) == len(cuts) 247 for cut in cuts: 248 assert cut in solution 249 250 251def test_cycle_graph(): 252 G = nx.cycle_graph(5) 253 solution = [{0, 2}, {0, 3}, {1, 3}, {1, 4}, {2, 4}] 254 cuts = list(nx.all_node_cuts(G)) 255 assert len(solution) == len(cuts) 256 for cut in cuts: 257 assert cut in solution 258 259 260def test_complete_graph(): 261 G = nx.complete_graph(5) 262 solution = [{0, 1, 2, 3}, {0, 1, 2, 4}, {0, 1, 3, 4}, {0, 2, 3, 4}, {1, 2, 3, 4}] 263 cuts = list(nx.all_node_cuts(G)) 264 assert len(solution) == len(cuts) 265 for cut in cuts: 266 assert cut in solution 267