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