Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (15.6 KB)

1
import itertools
2
from nose.tools import assert_equal, assert_true, assert_raises
3

    
4
import networkx as nx
5
from networkx.algorithms import flow
6
from networkx.algorithms.connectivity import local_edge_connectivity
7
from networkx.algorithms.connectivity import local_node_connectivity
8

    
9
flow_funcs = [
10
    flow.boykov_kolmogorov,
11
    flow.dinitz,
12
    flow.edmonds_karp,
13
    flow.preflow_push,
14
    flow.shortest_augmenting_path,
15
]
16

    
17

    
18
msg = "Assertion failed in function: {0}"
19

    
20
# helper functions for tests
21

    
22

    
23
def _generate_no_biconnected(max_attempts=50):
24
    attempts = 0
25
    while True:
26
        G = nx.fast_gnp_random_graph(100, 0.0575, seed=42)
27
        if nx.is_connected(G) and not nx.is_biconnected(G):
28
            attempts = 0
29
            yield G
30
        else:
31
            if attempts >= max_attempts:
32
                msg = "Tried %d times: no suitable Graph."
33
                raise Exception(msg % max_attempts)
34
            else:
35
                attempts += 1
36

    
37

    
38
def test_average_connectivity():
39
    # figure 1 from:
40
    # Beineke, L., O. Oellermann, and R. Pippert (2002). The average
41
    # connectivity of a graph. Discrete mathematics 252(1-3), 31-45
42
    # http://www.sciencedirect.com/science/article/pii/S0012365X01001807
43
    G1 = nx.path_graph(3)
44
    G1.add_edges_from([(1, 3), (1, 4)])
45
    G2 = nx.path_graph(3)
46
    G2.add_edges_from([(1, 3), (1, 4), (0, 3), (0, 4), (3, 4)])
47
    G3 = nx.Graph()
48
    for flow_func in flow_funcs:
49
        kwargs = dict(flow_func=flow_func)
50
        assert_equal(nx.average_node_connectivity(G1, **kwargs), 1,
51
                     msg=msg.format(flow_func.__name__))
52
        assert_equal(nx.average_node_connectivity(G2, **kwargs), 2.2,
53
                     msg=msg.format(flow_func.__name__))
54
        assert_equal(nx.average_node_connectivity(G3, **kwargs), 0,
55
                     msg=msg.format(flow_func.__name__))
56

    
57

    
58
def test_average_connectivity_directed():
59
    G = nx.DiGraph([(1, 3), (1, 4), (1, 5)])
60
    for flow_func in flow_funcs:
61
        assert_equal(nx.average_node_connectivity(G), 0.25,
62
                     msg=msg.format(flow_func.__name__))
63

    
64

    
65
def test_articulation_points():
66
    Ggen = _generate_no_biconnected()
67
    for flow_func in flow_funcs:
68
        for i in range(3):
69
            G = next(Ggen)
70
            assert_equal(nx.node_connectivity(G, flow_func=flow_func), 1,
71
                         msg=msg.format(flow_func.__name__))
72

    
73

    
74
def test_brandes_erlebach():
75
    # Figure 1 chapter 7: Connectivity
76
    # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
77
    G = nx.Graph()
78
    G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4),
79
                      (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8),
80
                      (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)])
81
    for flow_func in flow_funcs:
82
        kwargs = dict(flow_func=flow_func)
83
        assert_equal(3, local_edge_connectivity(G, 1, 11, **kwargs),
84
                     msg=msg.format(flow_func.__name__))
85
        assert_equal(3, nx.edge_connectivity(G, 1, 11, **kwargs),
86
                     msg=msg.format(flow_func.__name__))
87
        assert_equal(2, local_node_connectivity(G, 1, 11, **kwargs),
88
                     msg=msg.format(flow_func.__name__))
89
        assert_equal(2, nx.node_connectivity(G, 1, 11, **kwargs),
90
                     msg=msg.format(flow_func.__name__))
91
        assert_equal(2, nx.edge_connectivity(G, **kwargs),  # node 5 has degree 2
92
                     msg=msg.format(flow_func.__name__))
93
        assert_equal(2, nx.node_connectivity(G, **kwargs),
94
                     msg=msg.format(flow_func.__name__))
95

    
96

    
97
def test_white_harary_1():
98
    # Figure 1b white and harary (2001)
99
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
100
    # A graph with high adhesion (edge connectivity) and low cohesion
101
    # (vertex connectivity)
102
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
103
    G.remove_node(7)
104
    for i in range(4, 7):
105
        G.add_edge(0, i)
106
    G = nx.disjoint_union(G, nx.complete_graph(4))
107
    G.remove_node(G.order() - 1)
108
    for i in range(7, 10):
109
        G.add_edge(0, i)
110
    for flow_func in flow_funcs:
111
        assert_equal(1, nx.node_connectivity(G, flow_func=flow_func),
112
                     msg=msg.format(flow_func.__name__))
113
        assert_equal(3, nx.edge_connectivity(G, flow_func=flow_func),
114
                     msg=msg.format(flow_func.__name__))
115

    
116

    
117
def test_white_harary_2():
118
    # Figure 8 white and harary (2001)
119
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
120
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
121
    G.add_edge(0, 4)
122
    # kappa <= lambda <= delta
123
    assert_equal(3, min(nx.core_number(G).values()))
124
    for flow_func in flow_funcs:
125
        assert_equal(1, nx.node_connectivity(G, flow_func=flow_func),
126
                     msg=msg.format(flow_func.__name__))
127
        assert_equal(1, nx.edge_connectivity(G, flow_func=flow_func),
128
                     msg=msg.format(flow_func.__name__))
129

    
130

    
131
def test_complete_graphs():
132
    for n in range(5, 20, 5):
133
        for flow_func in flow_funcs:
134
            G = nx.complete_graph(n)
135
            assert_equal(n - 1, nx.node_connectivity(G, flow_func=flow_func),
136
                         msg=msg.format(flow_func.__name__))
137
            assert_equal(n - 1, nx.node_connectivity(G.to_directed(),
138
                                                     flow_func=flow_func),
139
                         msg=msg.format(flow_func.__name__))
140
            assert_equal(n - 1, nx.edge_connectivity(G, flow_func=flow_func),
141
                         msg=msg.format(flow_func.__name__))
142
            assert_equal(n - 1, nx.edge_connectivity(G.to_directed(),
143
                                                     flow_func=flow_func),
144
                         msg=msg.format(flow_func.__name__))
145

    
146

    
147
def test_empty_graphs():
148
    for k in range(5, 25, 5):
149
        G = nx.empty_graph(k)
150
        for flow_func in flow_funcs:
151
            assert_equal(0, nx.node_connectivity(G, flow_func=flow_func),
152
                         msg=msg.format(flow_func.__name__))
153
            assert_equal(0, nx.edge_connectivity(G, flow_func=flow_func),
154
                         msg=msg.format(flow_func.__name__))
155

    
156

    
157
def test_petersen():
158
    G = nx.petersen_graph()
159
    for flow_func in flow_funcs:
160
        assert_equal(3, nx.node_connectivity(G, flow_func=flow_func),
161
                     msg=msg.format(flow_func.__name__))
162
        assert_equal(3, nx.edge_connectivity(G, flow_func=flow_func),
163
                     msg=msg.format(flow_func.__name__))
164

    
165

    
166
def test_tutte():
167
    G = nx.tutte_graph()
168
    for flow_func in flow_funcs:
169
        assert_equal(3, nx.node_connectivity(G, flow_func=flow_func),
170
                     msg=msg.format(flow_func.__name__))
171
        assert_equal(3, nx.edge_connectivity(G, flow_func=flow_func),
172
                     msg=msg.format(flow_func.__name__))
173

    
174

    
175
def test_dodecahedral():
176
    G = nx.dodecahedral_graph()
177
    for flow_func in flow_funcs:
178
        assert_equal(3, nx.node_connectivity(G, flow_func=flow_func),
179
                     msg=msg.format(flow_func.__name__))
180
        assert_equal(3, nx.edge_connectivity(G, flow_func=flow_func),
181
                     msg=msg.format(flow_func.__name__))
182

    
183

    
184
def test_octahedral():
185
    G = nx.octahedral_graph()
186
    for flow_func in flow_funcs:
187
        assert_equal(4, nx.node_connectivity(G, flow_func=flow_func),
188
                     msg=msg.format(flow_func.__name__))
189
        assert_equal(4, nx.edge_connectivity(G, flow_func=flow_func),
190
                     msg=msg.format(flow_func.__name__))
191

    
192

    
193
def test_icosahedral():
194
    G = nx.icosahedral_graph()
195
    for flow_func in flow_funcs:
196
        assert_equal(5, nx.node_connectivity(G, flow_func=flow_func),
197
                     msg=msg.format(flow_func.__name__))
198
        assert_equal(5, nx.edge_connectivity(G, flow_func=flow_func),
199
                     msg=msg.format(flow_func.__name__))
200

    
201

    
202
def test_missing_source():
203
    G = nx.path_graph(4)
204
    for flow_func in flow_funcs:
205
        assert_raises(nx.NetworkXError, nx.node_connectivity, G, 10, 1,
206
                      flow_func=flow_func)
207

    
208

    
209
def test_missing_target():
210
    G = nx.path_graph(4)
211
    for flow_func in flow_funcs:
212
        assert_raises(nx.NetworkXError, nx.node_connectivity, G, 1, 10,
213
                      flow_func=flow_func)
214

    
215

    
216
def test_edge_missing_source():
217
    G = nx.path_graph(4)
218
    for flow_func in flow_funcs:
219
        assert_raises(nx.NetworkXError, nx.edge_connectivity, G, 10, 1,
220
                      flow_func=flow_func)
221

    
222

    
223
def test_edge_missing_target():
224
    G = nx.path_graph(4)
225
    for flow_func in flow_funcs:
226
        assert_raises(nx.NetworkXError, nx.edge_connectivity, G, 1, 10,
227
                      flow_func=flow_func)
228

    
229

    
230
def test_not_weakly_connected():
231
    G = nx.DiGraph()
232
    nx.add_path(G, [1, 2, 3])
233
    nx.add_path(G, [4, 5])
234
    for flow_func in flow_funcs:
235
        assert_equal(nx.node_connectivity(G), 0,
236
                     msg=msg.format(flow_func.__name__))
237
        assert_equal(nx.edge_connectivity(G), 0,
238
                     msg=msg.format(flow_func.__name__))
239

    
240

    
241
def test_not_connected():
242
    G = nx.Graph()
243
    nx.add_path(G, [1, 2, 3])
244
    nx.add_path(G, [4, 5])
245
    for flow_func in flow_funcs:
246
        assert_equal(nx.node_connectivity(G), 0,
247
                     msg=msg.format(flow_func.__name__))
248
        assert_equal(nx.edge_connectivity(G), 0,
249
                     msg=msg.format(flow_func.__name__))
250

    
251

    
252
def test_directed_edge_connectivity():
253
    G = nx.cycle_graph(10, create_using=nx.DiGraph())  # only one direction
254
    D = nx.cycle_graph(10).to_directed()  # 2 reciprocal edges
255
    for flow_func in flow_funcs:
256
        assert_equal(1, nx.edge_connectivity(G, flow_func=flow_func),
257
                     msg=msg.format(flow_func.__name__))
258
        assert_equal(1, local_edge_connectivity(G, 1, 4, flow_func=flow_func),
259
                     msg=msg.format(flow_func.__name__))
260
        assert_equal(1, nx.edge_connectivity(G, 1, 4, flow_func=flow_func),
261
                     msg=msg.format(flow_func.__name__))
262
        assert_equal(2, nx.edge_connectivity(D, flow_func=flow_func),
263
                     msg=msg.format(flow_func.__name__))
264
        assert_equal(2, local_edge_connectivity(D, 1, 4, flow_func=flow_func),
265
                     msg=msg.format(flow_func.__name__))
266
        assert_equal(2, nx.edge_connectivity(D, 1, 4, flow_func=flow_func),
267
                     msg=msg.format(flow_func.__name__))
268

    
269

    
270
def test_cutoff():
271
    G = nx.complete_graph(5)
272
    for local_func in [local_edge_connectivity, local_node_connectivity]:
273
        for flow_func in flow_funcs:
274
            if flow_func is flow.preflow_push:
275
                # cutoff is not supported by preflow_push
276
                continue
277
            for cutoff in [3, 2, 1]:
278
                result = local_func(G, 0, 4, flow_func=flow_func, cutoff=cutoff)
279
                assert_equal(cutoff, result,
280
                             msg="cutoff error in {0}".format(flow_func.__name__))
281

    
282

    
283
def test_invalid_auxiliary():
284
    G = nx.complete_graph(5)
285
    assert_raises(nx.NetworkXError, local_node_connectivity, G, 0, 3,
286
                  auxiliary=G)
287

    
288

    
289
def test_interface_only_source():
290
    G = nx.complete_graph(5)
291
    for interface_func in [nx.node_connectivity, nx.edge_connectivity]:
292
        assert_raises(nx.NetworkXError, interface_func, G, s=0)
293

    
294

    
295
def test_interface_only_target():
296
    G = nx.complete_graph(5)
297
    for interface_func in [nx.node_connectivity, nx.edge_connectivity]:
298
        assert_raises(nx.NetworkXError, interface_func, G, t=3)
299

    
300

    
301
def test_edge_connectivity_flow_vs_stoer_wagner():
302
    graph_funcs = [
303
        nx.icosahedral_graph,
304
        nx.octahedral_graph,
305
        nx.dodecahedral_graph,
306
    ]
307
    for graph_func in graph_funcs:
308
        G = graph_func()
309
        assert_equal(nx.stoer_wagner(G)[0], nx.edge_connectivity(G))
310

    
311

    
312
class TestAllPairsNodeConnectivity:
313

    
314
    def setUp(self):
315
        self.path = nx.path_graph(7)
316
        self.directed_path = nx.path_graph(7, create_using=nx.DiGraph())
317
        self.cycle = nx.cycle_graph(7)
318
        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
319
        self.gnp = nx.gnp_random_graph(30, 0.1, seed=42)
320
        self.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True, seed=42)
321
        self.K20 = nx.complete_graph(20)
322
        self.K10 = nx.complete_graph(10)
323
        self.K5 = nx.complete_graph(5)
324
        self.G_list = [self.path, self.directed_path, self.cycle,
325
                       self.directed_cycle, self.gnp, self.directed_gnp,
326
                       self.K10, self.K5, self.K20]
327

    
328
    def test_cycles(self):
329
        K_undir = nx.all_pairs_node_connectivity(self.cycle)
330
        for source in K_undir:
331
            for target, k in K_undir[source].items():
332
                assert_true(k == 2)
333
        K_dir = nx.all_pairs_node_connectivity(self.directed_cycle)
334
        for source in K_dir:
335
            for target, k in K_dir[source].items():
336
                assert_true(k == 1)
337

    
338
    def test_complete(self):
339
        for G in [self.K10, self.K5, self.K20]:
340
            K = nx.all_pairs_node_connectivity(G)
341
            for source in K:
342
                for target, k in K[source].items():
343
                    assert_true(k == len(G) - 1)
344

    
345
    def test_paths(self):
346
        K_undir = nx.all_pairs_node_connectivity(self.path)
347
        for source in K_undir:
348
            for target, k in K_undir[source].items():
349
                assert_true(k == 1)
350
        K_dir = nx.all_pairs_node_connectivity(self.directed_path)
351
        for source in K_dir:
352
            for target, k in K_dir[source].items():
353
                if source < target:
354
                    assert_true(k == 1)
355
                else:
356
                    assert_true(k == 0)
357

    
358
    def test_all_pairs_connectivity_nbunch(self):
359
        G = nx.complete_graph(5)
360
        nbunch = [0, 2, 3]
361
        C = nx.all_pairs_node_connectivity(G, nbunch=nbunch)
362
        assert_equal(len(C), len(nbunch))
363

    
364
    def test_all_pairs_connectivity_icosahedral(self):
365
        G = nx.icosahedral_graph()
366
        C = nx.all_pairs_node_connectivity(G)
367
        assert_true(all(5 == C[u][v] for u, v in itertools.combinations(G, 2)))
368

    
369
    def test_all_pairs_connectivity(self):
370
        G = nx.Graph()
371
        nodes = [0, 1, 2, 3]
372
        nx.add_path(G, nodes)
373
        A = {n: {} for n in G}
374
        for u, v in itertools.combinations(nodes, 2):
375
            A[u][v] = A[v][u] = nx.node_connectivity(G, u, v)
376
        C = nx.all_pairs_node_connectivity(G)
377
        assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
378
                     sorted((k, sorted(v)) for k, v in C.items()))
379

    
380
    def test_all_pairs_connectivity_directed(self):
381
        G = nx.DiGraph()
382
        nodes = [0, 1, 2, 3]
383
        nx.add_path(G, nodes)
384
        A = {n: {} for n in G}
385
        for u, v in itertools.permutations(nodes, 2):
386
            A[u][v] = nx.node_connectivity(G, u, v)
387
        C = nx.all_pairs_node_connectivity(G)
388
        assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
389
                     sorted((k, sorted(v)) for k, v in C.items()))
390

    
391
    def test_all_pairs_connectivity_nbunch_combinations(self):
392
        G = nx.complete_graph(5)
393
        nbunch = [0, 2, 3]
394
        A = {n: {} for n in nbunch}
395
        for u, v in itertools.combinations(nbunch, 2):
396
            A[u][v] = A[v][u] = nx.node_connectivity(G, u, v)
397
        C = nx.all_pairs_node_connectivity(G, nbunch=nbunch)
398
        assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
399
                     sorted((k, sorted(v)) for k, v in C.items()))
400

    
401
    def test_all_pairs_connectivity_nbunch_iter(self):
402
        G = nx.complete_graph(5)
403
        nbunch = [0, 2, 3]
404
        A = {n: {} for n in nbunch}
405
        for u, v in itertools.combinations(nbunch, 2):
406
            A[u][v] = A[v][u] = nx.node_connectivity(G, u, v)
407
        C = nx.all_pairs_node_connectivity(G, nbunch=iter(nbunch))
408
        assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
409
                     sorted((k, sorted(v)) for k, v in C.items()))