Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.7 KB)

1
from nose.tools import assert_equal, assert_true, assert_false, assert_raises
2

    
3
import networkx as nx
4
from networkx.algorithms import flow
5
from networkx.algorithms.connectivity import minimum_st_edge_cut
6
from networkx.algorithms.connectivity import minimum_st_node_cut
7
from networkx.utils import arbitrary_element
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
msg = "Assertion failed in function: {0}"
18

    
19
# Tests for node and edge cutsets
20

    
21

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

    
36

    
37
def test_articulation_points():
38
    Ggen = _generate_no_biconnected()
39
    for flow_func in flow_funcs:
40
        for i in range(1):  # change 1 to 3 or more for more realizations.
41
            G = next(Ggen)
42
            cut = nx.minimum_node_cut(G, flow_func=flow_func)
43
            assert_true(len(cut) == 1, msg=msg.format(flow_func.__name__))
44
            assert_true(cut.pop() in set(nx.articulation_points(G)),
45
                        msg=msg.format(flow_func.__name__))
46

    
47

    
48
def test_brandes_erlebach_book():
49
    # Figure 1 chapter 7: Connectivity
50
    # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
51
    G = nx.Graph()
52
    G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4),
53
                      (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8),
54
                      (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)])
55
    for flow_func in flow_funcs:
56
        kwargs = dict(flow_func=flow_func)
57
        # edge cutsets
58
        assert_equal(3, len(nx.minimum_edge_cut(G, 1, 11, **kwargs)),
59
                     msg=msg.format(flow_func.__name__))
60
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
61
        # Node 5 has only two edges
62
        assert_equal(2, len(edge_cut), msg=msg.format(flow_func.__name__))
63
        H = G.copy()
64
        H.remove_edges_from(edge_cut)
65
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
66
        # node cuts
67
        assert_equal(set([6, 7]), minimum_st_node_cut(G, 1, 11, **kwargs),
68
                     msg=msg.format(flow_func.__name__))
69
        assert_equal(set([6, 7]), nx.minimum_node_cut(G, 1, 11, **kwargs),
70
                     msg=msg.format(flow_func.__name__))
71
        node_cut = nx.minimum_node_cut(G, **kwargs)
72
        assert_equal(2, len(node_cut), msg=msg.format(flow_func.__name__))
73
        H = G.copy()
74
        H.remove_nodes_from(node_cut)
75
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
76

    
77

    
78
def test_white_harary_paper():
79
    # Figure 1b white and harary (2001)
80
    # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
81
    # A graph with high adhesion (edge connectivity) and low cohesion
82
    # (node connectivity)
83
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
84
    G.remove_node(7)
85
    for i in range(4, 7):
86
        G.add_edge(0, i)
87
    G = nx.disjoint_union(G, nx.complete_graph(4))
88
    G.remove_node(G.order() - 1)
89
    for i in range(7, 10):
90
        G.add_edge(0, i)
91
    for flow_func in flow_funcs:
92
        kwargs = dict(flow_func=flow_func)
93
        # edge cuts
94
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
95
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
96
        H = G.copy()
97
        H.remove_edges_from(edge_cut)
98
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
99
        # node cuts
100
        node_cut = nx.minimum_node_cut(G, **kwargs)
101
        assert_equal(set([0]), node_cut, msg=msg.format(flow_func.__name__))
102
        H = G.copy()
103
        H.remove_nodes_from(node_cut)
104
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
105

    
106

    
107
def test_petersen_cutset():
108
    G = nx.petersen_graph()
109
    for flow_func in flow_funcs:
110
        kwargs = dict(flow_func=flow_func)
111
        # edge cuts
112
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
113
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
114
        H = G.copy()
115
        H.remove_edges_from(edge_cut)
116
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
117
        # node cuts
118
        node_cut = nx.minimum_node_cut(G, **kwargs)
119
        assert_equal(3, len(node_cut), msg=msg.format(flow_func.__name__))
120
        H = G.copy()
121
        H.remove_nodes_from(node_cut)
122
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
123

    
124

    
125
def test_octahedral_cutset():
126
    G = nx.octahedral_graph()
127
    for flow_func in flow_funcs:
128
        kwargs = dict(flow_func=flow_func)
129
        # edge cuts
130
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
131
        assert_equal(4, len(edge_cut), msg=msg.format(flow_func.__name__))
132
        H = G.copy()
133
        H.remove_edges_from(edge_cut)
134
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
135
        # node cuts
136
        node_cut = nx.minimum_node_cut(G, **kwargs)
137
        assert_equal(4, len(node_cut), msg=msg.format(flow_func.__name__))
138
        H = G.copy()
139
        H.remove_nodes_from(node_cut)
140
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
141

    
142

    
143
def test_icosahedral_cutset():
144
    G = nx.icosahedral_graph()
145
    for flow_func in flow_funcs:
146
        kwargs = dict(flow_func=flow_func)
147
        # edge cuts
148
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
149
        assert_equal(5, len(edge_cut), msg=msg.format(flow_func.__name__))
150
        H = G.copy()
151
        H.remove_edges_from(edge_cut)
152
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
153
        # node cuts
154
        node_cut = nx.minimum_node_cut(G, **kwargs)
155
        assert_equal(5, len(node_cut), msg=msg.format(flow_func.__name__))
156
        H = G.copy()
157
        H.remove_nodes_from(node_cut)
158
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
159

    
160

    
161
def test_node_cutset_exception():
162
    G = nx.Graph()
163
    G.add_edges_from([(1, 2), (3, 4)])
164
    for flow_func in flow_funcs:
165
        assert_raises(nx.NetworkXError, nx.minimum_node_cut, G, flow_func=flow_func)
166

    
167

    
168
def test_node_cutset_random_graphs():
169
    for flow_func in flow_funcs:
170
        for i in range(3):
171
            G = nx.fast_gnp_random_graph(50, 0.25, seed=42)
172
            if not nx.is_connected(G):
173
                ccs = iter(nx.connected_components(G))
174
                start = arbitrary_element(next(ccs))
175
                G.add_edges_from((start, arbitrary_element(c)) for c in ccs)
176
            cutset = nx.minimum_node_cut(G, flow_func=flow_func)
177
            assert_equal(nx.node_connectivity(G), len(cutset),
178
                         msg=msg.format(flow_func.__name__))
179
            G.remove_nodes_from(cutset)
180
            assert_false(nx.is_connected(G), msg=msg.format(flow_func.__name__))
181

    
182

    
183
def test_edge_cutset_random_graphs():
184
    for flow_func in flow_funcs:
185
        for i in range(3):
186
            G = nx.fast_gnp_random_graph(50, 0.25, seed=42)
187
            if not nx.is_connected(G):
188
                ccs = iter(nx.connected_components(G))
189
                start = arbitrary_element(next(ccs))
190
                G.add_edges_from((start, arbitrary_element(c)) for c in ccs)
191
            cutset = nx.minimum_edge_cut(G, flow_func=flow_func)
192
            assert_equal(nx.edge_connectivity(G), len(cutset),
193
                         msg=msg.format(flow_func.__name__))
194
            G.remove_edges_from(cutset)
195
            assert_false(nx.is_connected(G), msg=msg.format(flow_func.__name__))
196

    
197

    
198
def test_empty_graphs():
199
    G = nx.Graph()
200
    D = nx.DiGraph()
201
    for interface_func in [nx.minimum_node_cut, nx.minimum_edge_cut]:
202
        for flow_func in flow_funcs:
203
            assert_raises(nx.NetworkXPointlessConcept, interface_func, G,
204
                          flow_func=flow_func)
205
            assert_raises(nx.NetworkXPointlessConcept, interface_func, D,
206
                          flow_func=flow_func)
207

    
208

    
209
def test_unbounded():
210
    G = nx.complete_graph(5)
211
    for flow_func in flow_funcs:
212
        assert_equal(4, len(minimum_st_edge_cut(G, 1, 4, flow_func=flow_func)))
213

    
214

    
215
def test_missing_source():
216
    G = nx.path_graph(4)
217
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
218
        for flow_func in flow_funcs:
219
            assert_raises(nx.NetworkXError, interface_func, G, 10, 1,
220
                          flow_func=flow_func)
221

    
222

    
223
def test_missing_target():
224
    G = nx.path_graph(4)
225
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
226
        for flow_func in flow_funcs:
227
            assert_raises(nx.NetworkXError, interface_func, G, 1, 10,
228
                          flow_func=flow_func)
229

    
230

    
231
def test_not_weakly_connected():
232
    G = nx.DiGraph()
233
    nx.add_path(G, [1, 2, 3])
234
    nx.add_path(G, [4, 5])
235
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
236
        for flow_func in flow_funcs:
237
            assert_raises(nx.NetworkXError, interface_func, G,
238
                          flow_func=flow_func)
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 interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
246
        for flow_func in flow_funcs:
247
            assert_raises(nx.NetworkXError, interface_func, G,
248
                          flow_func=flow_func)
249

    
250

    
251
def tests_min_cut_complete():
252
    G = nx.complete_graph(5)
253
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
254
        for flow_func in flow_funcs:
255
            assert_equal(4, len(interface_func(G, flow_func=flow_func)))
256

    
257

    
258
def tests_min_cut_complete_directed():
259
    G = nx.complete_graph(5)
260
    G = G.to_directed()
261
    for interface_func in [nx.minimum_edge_cut, nx.minimum_node_cut]:
262
        for flow_func in flow_funcs:
263
            assert_equal(4, len(interface_func(G, flow_func=flow_func)))
264

    
265

    
266
def tests_minimum_st_node_cut():
267
    G = nx.Graph()
268
    G.add_nodes_from([0, 1, 2, 3, 7, 8, 11, 12])
269
    G.add_edges_from([(7, 11), (1, 11), (1, 12), (12, 8), (0, 1)])
270
    nodelist = minimum_st_node_cut(G, 7, 11)
271
    assert(nodelist == [])
272

    
273

    
274
def test_invalid_auxiliary():
275
    G = nx.complete_graph(5)
276
    assert_raises(nx.NetworkXError, minimum_st_node_cut, G, 0, 3,
277
                  auxiliary=G)
278

    
279

    
280
def test_interface_only_source():
281
    G = nx.complete_graph(5)
282
    for interface_func in [nx.minimum_node_cut, nx.minimum_edge_cut]:
283
        assert_raises(nx.NetworkXError, interface_func, G, s=0)
284

    
285

    
286
def test_interface_only_target():
287
    G = nx.complete_graph(5)
288
    for interface_func in [nx.minimum_node_cut, nx.minimum_edge_cut]:
289
        assert_raises(nx.NetworkXError, interface_func, G, t=3)