Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (15.9 KB)

1
# -*- coding: utf-8 -*-
2
import random
3
import networkx as nx
4
import itertools as it
5
from networkx.utils import pairwise
6
from nose.tools import (assert_equal, assert_false, assert_true,
7
                        assert_greater_equal, assert_less, assert_less_equal,
8
                        assert_raises)
9
from networkx.algorithms.connectivity import (
10
    k_edge_augmentation,
11
)
12
from networkx.algorithms.connectivity.edge_augmentation import (
13
    collapse,
14
    complement_edges,
15
    is_locally_k_edge_connected,
16
    is_k_edge_connected,
17
    _unpack_available_edges,
18
)
19

    
20
# This should be set to the largest k for which an efficient algorithm is
21
# explicitly defined.
22
MAX_EFFICIENT_K = 2
23

    
24

    
25
def tarjan_bridge_graph():
26
    # graph from tarjan paper
27
    # RE Tarjan - "A note on finding the bridges of a graph"
28
    # Information Processing Letters, 1974 - Elsevier
29
    # doi:10.1016/0020-0190(74)90003-9.
30
    # define 2-connected components and bridges
31
    ccs = [(1, 2, 4, 3, 1, 4), (5, 6, 7, 5), (8, 9, 10, 8),
32
           (17, 18, 16, 15, 17), (11, 12, 14, 13, 11, 14)]
33
    bridges = [(4, 8), (3, 5), (3, 17)]
34
    G = nx.Graph(it.chain(*(pairwise(path) for path in ccs + bridges)))
35
    return G
36

    
37

    
38
def test_weight_key():
39
    G = nx.Graph()
40
    G.add_nodes_from([
41
        1, 2, 3, 4, 5, 6, 7, 8, 9])
42
    G.add_edges_from([(3, 8), (1, 2), (2, 3)])
43
    impossible = {(3, 6), (3, 9)}
44
    rng = random.Random(0)
45
    avail_uv = list(set(complement_edges(G)) - impossible)
46
    avail = [(u, v, {'cost': rng.random()}) for u, v in avail_uv]
47

    
48
    _augment_and_check(G, k=1)
49
    _augment_and_check(G, k=1, avail=avail_uv)
50
    _augment_and_check(G, k=1, avail=avail, weight='cost')
51

    
52
    _check_augmentations(G, avail, weight='cost')
53

    
54

    
55
def test_is_locally_k_edge_connected_exceptions():
56
    assert_raises(nx.NetworkXNotImplemented,
57
                  is_k_edge_connected,
58
                  nx.DiGraph(), k=0)
59
    assert_raises(nx.NetworkXNotImplemented,
60
                  is_k_edge_connected,
61
                  nx.MultiGraph(), k=0)
62
    assert_raises(ValueError, is_k_edge_connected,
63
                  nx.Graph(), k=0)
64

    
65

    
66
def test_is_k_edge_connected():
67
    G = nx.barbell_graph(10, 0)
68
    assert_true(is_k_edge_connected(G, k=1))
69
    assert_false(is_k_edge_connected(G, k=2))
70

    
71
    G = nx.Graph()
72
    G.add_nodes_from([5, 15])
73
    assert_false(is_k_edge_connected(G, k=1))
74
    assert_false(is_k_edge_connected(G, k=2))
75

    
76
    G = nx.complete_graph(5)
77
    assert_true(is_k_edge_connected(G, k=1))
78
    assert_true(is_k_edge_connected(G, k=2))
79
    assert_true(is_k_edge_connected(G, k=3))
80
    assert_true(is_k_edge_connected(G, k=4))
81

    
82

    
83
def test_is_k_edge_connected_exceptions():
84
    assert_raises(nx.NetworkXNotImplemented,
85
                  is_locally_k_edge_connected,
86
                  nx.DiGraph(), 1, 2, k=0)
87
    assert_raises(nx.NetworkXNotImplemented,
88
                  is_locally_k_edge_connected,
89
                  nx.MultiGraph(), 1, 2, k=0)
90
    assert_raises(ValueError,
91
                  is_locally_k_edge_connected,
92
                  nx.Graph(), 1, 2, k=0)
93

    
94

    
95
def test_is_locally_k_edge_connected():
96
    G = nx.barbell_graph(10, 0)
97
    assert_true(is_locally_k_edge_connected(G, 5, 15, k=1))
98
    assert_false(is_locally_k_edge_connected(G, 5, 15, k=2))
99

    
100
    G = nx.Graph()
101
    G.add_nodes_from([5, 15])
102
    assert_false(is_locally_k_edge_connected(G, 5, 15, k=2))
103

    
104

    
105
def test_null_graph():
106
    G = nx.Graph()
107
    _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2)
108

    
109

    
110
def test_cliques():
111
    for n in range(1, 10):
112
        G = nx.complete_graph(n)
113
        _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2)
114

    
115

    
116
def test_clique_and_node():
117
    for n in range(1, 10):
118
        G = nx.complete_graph(n)
119
        G.add_node(n + 1)
120
        _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2)
121

    
122

    
123
def test_point_graph():
124
    G = nx.Graph()
125
    G.add_node(1)
126
    _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2)
127

    
128

    
129
def test_edgeless_graph():
130
    G = nx.Graph()
131
    G.add_nodes_from([1, 2, 3, 4])
132
    _check_augmentations(G)
133

    
134

    
135
def test_invalid_k():
136
    G = nx.Graph()
137
    assert_raises(ValueError, list, k_edge_augmentation(G, k=-1))
138
    assert_raises(ValueError, list, k_edge_augmentation(G, k=0))
139

    
140

    
141
def test_unfeasible():
142
    G = tarjan_bridge_graph()
143
    assert_raises(nx.NetworkXUnfeasible, list,
144
                  k_edge_augmentation(G, k=1, avail=[]))
145

    
146
    assert_raises(nx.NetworkXUnfeasible, list,
147
                  k_edge_augmentation(G, k=2, avail=[]))
148

    
149
    assert_raises(nx.NetworkXUnfeasible, list,
150
                  k_edge_augmentation(G, k=2, avail=[(7, 9)]))
151

    
152
    # partial solutions should not error if real solutions are infeasible
153
    aug_edges = list(k_edge_augmentation(G, k=2, avail=[(7, 9)], partial=True))
154
    assert_equal(aug_edges, [(7, 9)])
155

    
156
    _check_augmentations(G, avail=[], max_k=MAX_EFFICIENT_K + 2)
157

    
158
    _check_augmentations(G, avail=[(7, 9)], max_k=MAX_EFFICIENT_K + 2)
159

    
160

    
161
def test_tarjan():
162
    G = tarjan_bridge_graph()
163

    
164
    aug_edges = set(_augment_and_check(G, k=2)[0])
165
    print('aug_edges = {!r}'.format(aug_edges))
166
    # can't assert edge exactly equality due to non-determinant edge order
167
    # but we do know the size of the solution must be 3
168
    assert_equal(len(aug_edges), 3)
169

    
170
    avail = [(9, 7), (8, 5), (2, 10), (6, 13), (11, 18), (1, 17), (2, 3),
171
             (16, 17), (18, 14), (15, 14)]
172
    aug_edges = set(_augment_and_check(G, avail=avail, k=2)[0])
173

    
174
    # Can't assert exact length since approximation depends on the order of a
175
    # dict traversal.
176
    assert_less_equal(len(aug_edges), 3 * 2)
177

    
178
    _check_augmentations(G, avail)
179

    
180

    
181
def test_configuration():
182
    # seeds = [2718183590, 2470619828, 1694705158, 3001036531, 2401251497]
183
    seeds = [1001, 1002, 1003, 1004]
184
    for seed in seeds:
185
        deg_seq = nx.random_powerlaw_tree_sequence(20, seed=seed, tries=5000)
186
        G = nx.Graph(nx.configuration_model(deg_seq, seed=seed))
187
        G.remove_edges_from(nx.selfloop_edges(G))
188
        _check_augmentations(G)
189

    
190

    
191
def test_shell():
192
    # seeds = [2057382236, 3331169846, 1840105863, 476020778, 2247498425]
193
    seeds = [18]
194
    for seed in seeds:
195
        constructor = [(12, 70, 0.8), (15, 40, 0.6)]
196
        G = nx.random_shell_graph(constructor, seed=seed)
197
        _check_augmentations(G)
198

    
199

    
200
def test_karate():
201
    G = nx.karate_club_graph()
202
    _check_augmentations(G)
203

    
204

    
205
def test_star():
206
    G = nx.star_graph(3)
207
    _check_augmentations(G)
208

    
209
    G = nx.star_graph(5)
210
    _check_augmentations(G)
211

    
212
    G = nx.star_graph(10)
213
    _check_augmentations(G)
214

    
215

    
216
def test_barbell():
217
    G = nx.barbell_graph(5, 0)
218
    _check_augmentations(G)
219

    
220
    G = nx.barbell_graph(5, 2)
221
    _check_augmentations(G)
222

    
223
    G = nx.barbell_graph(5, 3)
224
    _check_augmentations(G)
225

    
226
    G = nx.barbell_graph(5, 4)
227
    _check_augmentations(G)
228

    
229

    
230
def test_bridge():
231
    G = nx.Graph([(2393, 2257), (2393, 2685), (2685, 2257), (1758, 2257)])
232
    _check_augmentations(G)
233

    
234

    
235
def test_gnp_augmentation():
236
    rng = random.Random(0)
237
    G = nx.gnp_random_graph(30, 0.005, seed=0)
238
    # Randomly make edges available
239
    avail = {(u, v): 1 + rng.random()
240
             for u, v in complement_edges(G)
241
             if rng.random() < .25}
242
    _check_augmentations(G, avail)
243

    
244

    
245
def _assert_solution_properties(G, aug_edges, avail_dict=None):
246
    """ Checks that aug_edges are consistently formatted """
247
    if avail_dict is not None:
248
        assert_true(all(e in avail_dict for e in aug_edges),
249
                    'when avail is specified aug-edges should be in avail')
250

    
251
    unique_aug = set(map(tuple, map(sorted, aug_edges)))
252
    unique_aug = list(map(tuple, map(sorted, aug_edges)))
253
    assert_true(len(aug_edges) == len(unique_aug),
254
                'edges should be unique')
255

    
256
    assert_false(any(u == v for u, v in unique_aug),
257
                 'should be no self-edges')
258

    
259
    assert_false(any(G.has_edge(u, v) for u, v in unique_aug),
260
                 'aug edges and G.edges should be disjoint')
261

    
262

    
263
def _augment_and_check(G, k, avail=None, weight=None, verbose=False,
264
                       orig_k=None, max_aug_k=None):
265
    """
266
    Does one specific augmentation and checks for properties of the result
267
    """
268
    if orig_k is None:
269
        try:
270
            orig_k = nx.edge_connectivity(G)
271
        except nx.NetworkXPointlessConcept:
272
            orig_k = 0
273
    info = {}
274
    try:
275
        if avail is not None:
276
            # ensure avail is in dict form
277
            avail_dict = dict(zip(*_unpack_available_edges(avail,
278
                                                           weight=weight)))
279
        else:
280
            avail_dict = None
281
        try:
282
            # Find the augmentation if possible
283
            generator = nx.k_edge_augmentation(G, k=k, weight=weight,
284
                                               avail=avail)
285
            assert_false(isinstance(generator, list),
286
                         'should always return an iter')
287
            aug_edges = []
288
            for edge in generator:
289
                aug_edges.append(edge)
290
        except nx.NetworkXUnfeasible:
291
            infeasible = True
292
            info['infeasible'] = True
293
            assert_equal(len(aug_edges), 0,
294
                         'should not generate anything if unfeasible')
295

    
296
            if avail is None:
297
                n_nodes = G.number_of_nodes()
298
                assert_less_equal(n_nodes, k, (
299
                    'unconstrained cases are only unfeasible if |V| <= k. '
300
                    'Got |V|={} and k={}'.format(n_nodes, k)
301
                ))
302
            else:
303
                if max_aug_k is None:
304
                    G_aug_all = G.copy()
305
                    G_aug_all.add_edges_from(avail_dict.keys())
306
                    try:
307
                        max_aug_k = nx.edge_connectivity(G_aug_all)
308
                    except nx.NetworkXPointlessConcept:
309
                        max_aug_k = 0
310

    
311
                assert_less(max_aug_k, k, (
312
                    'avail should only be unfeasible if using all edges '
313
                    'does not achieve k-edge-connectivity'))
314

    
315
            # Test for a partial solution
316
            partial_edges = list(nx.k_edge_augmentation(
317
                G, k=k, weight=weight, partial=True, avail=avail))
318

    
319
            info['n_partial_edges'] = len(partial_edges)
320

    
321
            if avail_dict is None:
322
                assert_equal(set(partial_edges), set(complement_edges(G)), (
323
                    'unweighted partial solutions should be the complement'))
324
            elif len(avail_dict) > 0:
325
                H = G.copy()
326

    
327
                # Find the partial / full augmented connectivity
328
                H.add_edges_from(partial_edges)
329
                partial_conn = nx.edge_connectivity(H)
330

    
331
                H.add_edges_from(set(avail_dict.keys()))
332
                full_conn = nx.edge_connectivity(H)
333

    
334
                # Full connectivity should be no better than our partial
335
                # solution.
336
                assert_equal(partial_conn, full_conn,
337
                             'adding more edges should not increase k-conn')
338

    
339
            # Find the new edge-connectivity after adding the augmenting edges
340
            aug_edges = partial_edges
341
        else:
342
            infeasible = False
343

    
344
        # Find the weight of the augmentation
345
        num_edges = len(aug_edges)
346
        if avail is not None:
347
            total_weight = sum([avail_dict[e] for e in aug_edges])
348
        else:
349
            total_weight = num_edges
350

    
351
        info['total_weight'] = total_weight
352
        info['num_edges'] = num_edges
353

    
354
        # Find the new edge-connectivity after adding the augmenting edges
355
        G_aug = G.copy()
356
        G_aug.add_edges_from(aug_edges)
357
        try:
358
            aug_k = nx.edge_connectivity(G_aug)
359
        except nx.NetworkXPointlessConcept:
360
            aug_k = 0
361
        info['aug_k'] = aug_k
362

    
363
        # Do checks
364
        if not infeasible and orig_k < k:
365
            assert_greater_equal(info['aug_k'], k, (
366
                'connectivity should increase to k={} or more'.format(k)))
367

    
368
        assert_greater_equal(info['aug_k'], orig_k, (
369
            'augmenting should never reduce connectivity'))
370

    
371
        _assert_solution_properties(G, aug_edges, avail_dict)
372

    
373
    except Exception:
374
        info['failed'] = True
375
        print('edges = {}'.format(list(G.edges())))
376
        print('nodes = {}'.format(list(G.nodes())))
377
        print('aug_edges = {}'.format(list(aug_edges)))
378
        print('info  = {}'.format(info))
379
        raise
380
    else:
381
        if verbose:
382
            print('info  = {}'.format(info))
383

    
384
    if infeasible:
385
        aug_edges = None
386
    return aug_edges, info
387

    
388

    
389
def _check_augmentations(G, avail=None, max_k=None, weight=None,
390
                         verbose=False):
391
    """ Helper to check weighted/unweighted cases with multiple values of k """
392
    # Using all available edges, find the maximum edge-connectivity
393
    try:
394
        orig_k = nx.edge_connectivity(G)
395
    except nx.NetworkXPointlessConcept:
396
        orig_k = 0
397

    
398
    if avail is not None:
399
        all_aug_edges = _unpack_available_edges(avail, weight=weight)[0]
400
        G_aug_all = G.copy()
401
        G_aug_all.add_edges_from(all_aug_edges)
402
        try:
403
            max_aug_k = nx.edge_connectivity(G_aug_all)
404
        except nx.NetworkXPointlessConcept:
405
            max_aug_k = 0
406
    else:
407
        max_aug_k = G.number_of_nodes() - 1
408

    
409
    if max_k is None:
410
        max_k = min(4, max_aug_k)
411

    
412
    avail_uniform = {e: 1 for e in complement_edges(G)}
413

    
414
    if verbose:
415
        print('\n=== CHECK_AUGMENTATION ===')
416
        print('G.number_of_nodes = {!r}'.format(G.number_of_nodes()))
417
        print('G.number_of_edges = {!r}'.format(G.number_of_edges()))
418
        print('max_k = {!r}'.format(max_k))
419
        print('max_aug_k = {!r}'.format(max_aug_k))
420
        print('orig_k = {!r}'.format(orig_k))
421

    
422
    # check augmentation for multiple values of k
423
    for k in range(1, max_k + 1):
424
        if verbose:
425
            print('---------------')
426
            print('Checking k = {}'.format(k))
427

    
428
        # Check the unweighted version
429
        if verbose:
430
            print('unweighted case')
431
        aug_edges1, info1 = _augment_and_check(
432
            G, k=k,  verbose=verbose, orig_k=orig_k)
433

    
434
        # Check that the weighted version with all available edges and uniform
435
        # weights gives a similar solution to the unweighted case.
436
        if verbose:
437
            print('weighted uniform case')
438
        aug_edges2, info2 = _augment_and_check(
439
            G, k=k, avail=avail_uniform, verbose=verbose,
440
            orig_k=orig_k,
441
            max_aug_k=G.number_of_nodes() - 1)
442

    
443
        # Check the weighted version
444
        if avail is not None:
445
            if verbose:
446
                print('weighted case')
447
            aug_edges3, info3 = _augment_and_check(
448
                G, k=k, avail=avail, weight=weight, verbose=verbose,
449
                max_aug_k=max_aug_k, orig_k=orig_k)
450

    
451
        if aug_edges1 is not None:
452
            # Check approximation ratios
453
            if k == 1:
454
                # when k=1, both solutions should be optimal
455
                assert_equal(info2['total_weight'], info1['total_weight'])
456
            if k == 2:
457
                # when k=2, the weighted version is an approximation
458
                if orig_k == 0:
459
                    # the approximation ratio is 3 if G is not connected
460
                    assert_less_equal(info2['total_weight'],
461
                                      info1['total_weight'] * 3)
462
                else:
463
                    # the approximation ratio is 2 if G is was connected
464
                    assert_less_equal(info2['total_weight'],
465
                                      info1['total_weight'] * 2)
466
                _check_unconstrained_bridge_property(G, info1)
467

    
468

    
469
def _check_unconstrained_bridge_property(G, info1):
470
    # Check Theorem 5 from Eswaran and Tarjan. (1975) Augmentation problems
471
    import math
472
    bridge_ccs = list(nx.connectivity.bridge_components(G))
473
    # condense G into an forest C
474
    C = collapse(G, bridge_ccs)
475

    
476
    p = len([n for n, d in C.degree() if d == 1])  # leafs
477
    q = len([n for n, d in C.degree() if d == 0])  # isolated
478
    if p + q > 1:
479
        size_target = int(math.ceil(p / 2.0)) + q
480
        size_aug = info1['num_edges']
481
        assert_equal(size_aug, size_target, (
482
            'augmentation size is different from what theory predicts'))