Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / tests / test_kcutsets.py @ 5cef0f13

History | View | Annotate | Download (8.63 KB)

1
# Jordi Torrents
2
# Test for k-cutsets
3
import itertools
4
from nose.tools import assert_equal, assert_false, assert_true, assert_raises
5

    
6
import networkx as nx
7
from networkx.algorithms import flow
8
from networkx.algorithms.connectivity.kcutsets import _is_separating_set
9

    
10
MAX_CUTSETS_TO_TEST = 4  # originally 100. cut to decrease testing time
11

    
12
flow_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
##
24
def graph_example_1():
25
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
26
                                           label_attribute='labels')
27
    rlabels = nx.get_node_attributes(G, 'labels')
28
    labels = {v: k for k, v in rlabels.items()}
29

    
30
    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
31
                  (labels[(0, 4)], labels[(1, 4)]),
32
                  (labels[(3, 0)], labels[(4, 0)]),
33
                  (labels[(3, 4)], labels[(4, 4)])]:
34
        new_node = G.order() + 1
35
        # Petersen graph is triconnected
36
        P = nx.petersen_graph()
37
        G = nx.disjoint_union(G, P)
38
        # Add two edges between the grid and P
39
        G.add_edge(new_node + 1, nodes[0])
40
        G.add_edge(new_node, nodes[1])
41
        # K5 is 4-connected
42
        K = nx.complete_graph(5)
43
        G = nx.disjoint_union(G, K)
44
        # Add three edges between P and K5
45
        G.add_edge(new_node + 2, new_node + 11)
46
        G.add_edge(new_node + 3, new_node + 12)
47
        G.add_edge(new_node + 4, new_node + 13)
48
        # Add another K5 sharing a node
49
        G = nx.disjoint_union(G, K)
50
        nbrs = G[new_node + 10]
51
        G.remove_node(new_node + 10)
52
        for nbr in nbrs:
53
            G.add_edge(new_node + 17, nbr)
54
        G.add_edge(new_node + 16, new_node + 5)
55
    return G
56

    
57

    
58
def torrents_and_ferraro_graph():
59
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
60
                                           label_attribute='labels')
61
    rlabels = nx.get_node_attributes(G, 'labels')
62
    labels = {v: k for k, v in rlabels.items()}
63

    
64
    for nodes in [(labels[(0, 4)], labels[(1, 4)]),
65
                  (labels[(3, 4)], labels[(4, 4)])]:
66
        new_node = G.order() + 1
67
        # Petersen graph is triconnected
68
        P = nx.petersen_graph()
69
        G = nx.disjoint_union(G, P)
70
        # Add two edges between the grid and P
71
        G.add_edge(new_node + 1, nodes[0])
72
        G.add_edge(new_node, nodes[1])
73
        # K5 is 4-connected
74
        K = nx.complete_graph(5)
75
        G = nx.disjoint_union(G, K)
76
        # Add three edges between P and K5
77
        G.add_edge(new_node + 2, new_node + 11)
78
        G.add_edge(new_node + 3, new_node + 12)
79
        G.add_edge(new_node + 4, new_node + 13)
80
        # Add another K5 sharing a node
81
        G = nx.disjoint_union(G, K)
82
        nbrs = G[new_node + 10]
83
        G.remove_node(new_node + 10)
84
        for nbr in nbrs:
85
            G.add_edge(new_node + 17, nbr)
86
        # Commenting this makes the graph not biconnected !!
87
        # This stupid mistake make one reviewer very angry :P
88
        G.add_edge(new_node + 16, new_node + 8)
89

    
90
    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
91
                  (labels[(3, 0)], labels[(4, 0)])]:
92
        new_node = G.order() + 1
93
        # Petersen graph is triconnected
94
        P = nx.petersen_graph()
95
        G = nx.disjoint_union(G, P)
96
        # Add two edges between the grid and P
97
        G.add_edge(new_node + 1, nodes[0])
98
        G.add_edge(new_node, nodes[1])
99
        # K5 is 4-connected
100
        K = nx.complete_graph(5)
101
        G = nx.disjoint_union(G, K)
102
        # Add three edges between P and K5
103
        G.add_edge(new_node + 2, new_node + 11)
104
        G.add_edge(new_node + 3, new_node + 12)
105
        G.add_edge(new_node + 4, new_node + 13)
106
        # Add another K5 sharing two nodes
107
        G = nx.disjoint_union(G, K)
108
        nbrs = G[new_node + 10]
109
        G.remove_node(new_node + 10)
110
        for nbr in nbrs:
111
            G.add_edge(new_node + 17, nbr)
112
        nbrs2 = G[new_node + 9]
113
        G.remove_node(new_node + 9)
114
        for nbr in nbrs2:
115
            G.add_edge(new_node + 18, nbr)
116
    return G
117

    
118

    
119
# Helper function
120
def _check_separating_sets(G):
121
    for cc in nx.connected_components(G):
122
        if len(cc) < 3:
123
            continue
124
        Gc = G.subgraph(cc)
125
        node_conn = nx.node_connectivity(Gc)
126
        all_cuts = nx.all_node_cuts(Gc)
127
        # Only test a limited number of cut sets to reduce test time.
128
        for cut in itertools.islice(all_cuts, MAX_CUTSETS_TO_TEST):
129
            assert_equal(node_conn, len(cut))
130
            assert_false(nx.is_connected(nx.restricted_view(G, cut, [])))
131

    
132

    
133
def test_torrents_and_ferraro_graph():
134
    G = torrents_and_ferraro_graph()
135
    _check_separating_sets(G)
136

    
137

    
138
def test_example_1():
139
    G = graph_example_1()
140
    _check_separating_sets(G)
141

    
142

    
143
def test_random_gnp():
144
    G = nx.gnp_random_graph(100, 0.1, seed=42)
145
    _check_separating_sets(G)
146

    
147

    
148
def test_shell():
149
    constructor = [(20, 80, 0.8), (80, 180, 0.6)]
150
    G = nx.random_shell_graph(constructor, seed=42)
151
    _check_separating_sets(G)
152

    
153

    
154
def test_configuration():
155
    deg_seq = nx.random_powerlaw_tree_sequence(100, tries=5, seed=72)
156
    G = nx.Graph(nx.configuration_model(deg_seq))
157
    G.remove_edges_from(nx.selfloop_edges(G))
158
    _check_separating_sets(G)
159

    
160

    
161
def test_karate():
162
    G = nx.karate_club_graph()
163
    _check_separating_sets(G)
164

    
165

    
166
def _generate_no_biconnected(max_attempts=50):
167
    attempts = 0
168
    while True:
169
        G = nx.fast_gnp_random_graph(100, 0.0575, seed=42)
170
        if nx.is_connected(G) and not nx.is_biconnected(G):
171
            attempts = 0
172
            yield G
173
        else:
174
            if attempts >= max_attempts:
175
                msg = "Tried %d times: no suitable Graph." % attempts
176
                raise Exception(msg % max_attempts)
177
            else:
178
                attempts += 1
179

    
180

    
181
def test_articulation_points():
182
    Ggen = _generate_no_biconnected()
183
    for i in range(1):  # change 1 to 3 or more for more realizations.
184
        G = next(Ggen)
185
        articulation_points = list({a} for a in nx.articulation_points(G))
186
        for cut in nx.all_node_cuts(G):
187
            assert_true(cut in articulation_points)
188

    
189

    
190
def test_grid_2d_graph():
191
    # All minimum node cuts of a 2d grid
192
    # are the four pairs of nodes that are
193
    # neighbors of the four corner nodes.
194
    G = nx.grid_2d_graph(5, 5)
195
    solution = [
196
        set([(0, 1), (1, 0)]),
197
        set([(3, 0), (4, 1)]),
198
        set([(3, 4), (4, 3)]),
199
        set([(0, 3), (1, 4)]),
200
    ]
201
    for cut in nx.all_node_cuts(G):
202
        assert_true(cut in solution)
203

    
204

    
205
def test_disconnected_graph():
206
    G = nx.fast_gnp_random_graph(100, 0.01, seed=42)
207
    cuts = nx.all_node_cuts(G)
208
    assert_raises(nx.NetworkXError, next, cuts)
209

    
210

    
211
def test_alternative_flow_functions():
212
    graphs = [nx.grid_2d_graph(4, 4),
213
              nx.cycle_graph(5)]
214
    for G in graphs:
215
        node_conn = nx.node_connectivity(G)
216
        for flow_func in flow_funcs:
217
            all_cuts = nx.all_node_cuts(G, flow_func=flow_func)
218
            # Only test a limited number of cut sets to reduce test time.
219
            for cut in itertools.islice(all_cuts, MAX_CUTSETS_TO_TEST):
220
                assert_equal(node_conn, len(cut))
221
                assert_false(nx.is_connected(nx.restricted_view(G, cut, [])))
222

    
223

    
224
def test_is_separating_set_complete_graph():
225
    G = nx.complete_graph(5)
226
    assert_true(_is_separating_set(G, {0, 1, 2, 3}))
227

    
228

    
229
def test_is_separating_set():
230
    for i in [5, 10, 15]:
231
        G = nx.star_graph(i)
232
        max_degree_node = max(G, key=G.degree)
233
        assert_true(_is_separating_set(G, {max_degree_node}))
234

    
235

    
236
def test_non_repeated_cuts():
237
    # The algorithm was repeating the cut {0, 1} for the giant biconnected
238
    # component of the Karate club graph.
239
    K = nx.karate_club_graph()
240
    G = max(list(nx.biconnected_component_subgraphs(K)), key=len)
241
    solution = [{32, 33}, {2, 33}, {0, 3}, {0, 1}, {29, 33}]
242
    cuts = list(nx.all_node_cuts(G))
243
    if len(solution) != len(cuts):
244
        print(nx.info(G))
245
        print("Solution: {}".format(solution))
246
        print("Result: {}".format(cuts))
247
    assert_true(len(solution) == len(cuts))
248
    for cut in cuts:
249
        assert_true(cut in solution)
250

    
251

    
252
def test_cycle_graph():
253
    G = nx.cycle_graph(5)
254
    solution = [{0, 2}, {0, 3}, {1, 3}, {1, 4}, {2, 4}]
255
    cuts = list(nx.all_node_cuts(G))
256
    assert_true(len(solution) == len(cuts))
257
    for cut in cuts:
258
        assert_true(cut in solution)
259

    
260

    
261
def test_complete_graph():
262
    G = nx.complete_graph(5)
263
    solution = [
264
        {0, 1, 2, 3},
265
        {0, 1, 2, 4},
266
        {0, 1, 3, 4},
267
        {0, 2, 3, 4},
268
        {1, 2, 3, 4},
269
    ]
270
    cuts = list(nx.all_node_cuts(G))
271
    assert_true(len(solution) == len(cuts))
272
    for cut in cuts:
273
        assert_true(cut in solution)